If d ∣ n ∏ f ( d ) = n for all positive integers n , find f ( 2 0 1 5 ) × f ( 2 0 1 6 ) × f ( 2 0 1 7 ) .
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
By Mobius Inversion,
f ( n ) = d ∣ n ∏ ( d n ) μ ( d )
We calculate f ( 2 0 1 5 ) f ( 2 0 1 6 ) f ( 2 0 1 7 ) = d ∣ 5 ⋅ 1 3 ⋅ 3 1 ∏ ( d 2 0 1 5 ) μ ( d ) = 6 5 ⋅ 1 5 5 ⋅ 4 0 3 2 0 1 5 ⋅ 5 ⋅ 1 3 ⋅ 3 1 = 1 = d ∣ 2 5 ⋅ 3 2 ⋅ 7 ∏ ( d 2 0 1 6 ) μ ( d ) = d ∣ 2 ⋅ 3 ⋅ 7 ∏ ( d 2 0 1 6 ) μ ( d ) = ( 2 0 1 6 ) ( 2 2 0 1 6 ) − 1 ( 3 2 0 1 6 ) − 1 ( 7 2 0 1 6 ) − 1 ( 2 ⋅ 3 2 0 1 6 ) ( 2 ⋅ 7 2 0 1 6 ) ( 3 ⋅ 7 2 0 1 6 ) ( 2 ⋅ 3 ⋅ 7 2 0 1 6 ) − 1 = 1 = d ∣ 2 0 1 7 ∏ ( d 2 0 1 7 ) μ ( d ) = 2 0 1 7 Thus, f ( 2 0 1 5 ) × f ( 2 0 1 6 ) × f ( 2 0 1 7 ) = 2 0 1 7 .
Nice! (+1) You could further simplify and clarify your work by observing that f ( n ) = ∏ d ∣ n d − μ ( d )
take log ln ( n ) = d ∣ n ∑ ln ( f ( d ) ) let g ( n ) = ln ( f ( n ) ) .and p ( n ) = ln ( n ) .then in dirichlet convolution form: p = g ∗ u . convolute both sides with μ to get: p ∗ μ = g ∗ I = g . in other words: ln ( f ( d ) ) = d ∣ n ∑ ln ( d ) μ ( d n ) it is well known ln ( n ) = d ∣ n ∑ Λ ( d ) where Λ ( n ) is the von mangoldt function . this is easy to prove, try it yourself.
in dirichlet convolution form this is: p = Λ ∗ u . convolute bothsides with μ to get: p ∗ μ = Λ ∗ I = Λ . in other words d ∣ n ∑ ln ( d ) μ ( d n ) = Λ ( n ) . we get that ln ( f ( n ) ) = Λ ( n ) or f ( n ) = e Λ ( n ) . the only power of prime among these are 2 0 1 7 = 2 0 1 7 1 . we get e 0 × e 0 × e ln ( 2 0 1 7 ) = 2 0 1 7 .
a 'bit' copied from my solution here .
Yes, exactly! You are the expert on this kind of questions (+1)... let's see how many others get it.
You can simplify your argument a bit by observing that for every arithmetic function f ( n ) there exists a unique g ( n ) such that f ( n ) = ∑ d ∣ n g ( d ) ; you can construct g ( n ) recursively.
Thus, if we know that ln ( n ) = ∑ d ∣ n Λ ( d ) , as you assume (small typo there in your formula), and we are given that ln ( n ) = ∑ d ∣ n ln ( f ( d ) ) , we can conclude that Λ ( n ) = ln ( f ( n ) ) for all n , so f ( n ) = e Λ ( n ) = p if n is a power of a prime p , and f ( n ) = 1 otherwise... the answer follows.
With this approach, you don't need all this convolution stuff.
Did you try part 46 of my series... I'm still waiting for an answer there.
Log in to reply
Sir,you forgot my query?
part 46, i did try that but wasn't able to solve it. i too am waiting to know how to solve it.
Log in to reply
I will give you a hint: Consider Ramanujan Sums
Problem Loading...
Note Loading...
Set Loading...
Aareyan and Alan have written fine solutions. Let me show a more basic approach for those members who are not familiar with Mobius and von Mangoldt.
By definition , we have the recursive formula
f ( n ) = ∏ d f ( d ) n where the product is taken over all proper divisors d of n .
We will show by induction on n that f ( n ) = p if n = p m is a prime power and f ( n ) = 1 otherwise. The base case f ( 1 ) = 1 is trivial.
If n = p m , then f ( p m ) = ∏ j = 1 m − 1 f ( p j ) p m = p m − 1 p m = p .
If n = ∏ i = 1 r p i m i = p 1 m 1 × . . × p i m i × . . × p r m r with r > 1 , then it suffices to consider the divisors d of n that are prime powers, by induction: f ( n ) = ∏ i = 1 r ∏ j = 1 m i f ( p i j ) n = ∏ i = 1 r ∏ j = 1 m i p i n = n n = 1
Since 2017 is prime while 2015 and 2016 have more than one prime factor each, we have f ( 2 0 1 5 ) × f ( 2 0 1 6 ) × f ( 2 0 1 7 ) = 1 × 1 × 2 0 1 7 = 2 0 1 7