More fun in 2015 (and beyond), Part 47

If d n f ( d ) = n \prod_{d|n}f(d)=n for all positive integers n n , find f ( 2015 ) × f ( 2016 ) × f ( 2017 ) f(2015)\times f(2016)\times f(2017) .


The answer is 2017.

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.

3 solutions

Otto Bretscher
Dec 30, 2015

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 ) = n d f ( d ) f(n)=\frac{n}{\prod_{d} f(d)} where the product is taken over all proper divisors d d of n n .

We will show by induction on n n that f ( n ) = p f(n)=p if n = p m n=p^m is a prime power and f ( n ) = 1 f(n)=1 otherwise. The base case f ( 1 ) = 1 f(1)=1 is trivial.

If n = p m n=p^m , then f ( p m ) = p m j = 1 m 1 f ( p j ) = p m p m 1 = p f(p^m)=\frac{p^m}{\prod_{j=1}^{m-1}f(p^j)}=\frac{p^m}{p^{m-1}}=p .

If n = i = 1 r p i m i = p 1 m 1 × . . × p i m i × . . × p r m r n=\prod_{i=1}^{r}p_i^{m_i}=p_1^{m_1}\times ..\times p_i^{m_i}\times..\times p_r^{m_r} with r > 1 r>1 , then it suffices to consider the divisors d d of n n that are prime powers, by induction: f ( n ) = n i = 1 r j = 1 m i f ( p i j ) = n i = 1 r j = 1 m i p i = n n = 1 f(n)=\frac{n}{\prod_{i=1}^{r}\prod_{j=1}^{m_i}f(p_i^j)}=\frac{n}{\prod_{i=1}^{r}\prod_{j=1}^{m_i}p_i}=\frac{n}{n}=1

Since 2017 is prime while 2015 and 2016 have more than one prime factor each, we have f ( 2015 ) × f ( 2016 ) × f ( 2017 ) = 1 × 1 × 2017 = 2017 f(2015)\times f(2016)\times f(2017)=1\times 1 \times 2017=\boxed{2017}

Alan Yan
Dec 30, 2015

By Mobius Inversion,

f ( n ) = d n ( n d ) μ ( d ) f(n) = \prod_{d | n}\left(\frac{n}{d}\right)^{\mu(d)}

We calculate f ( 2015 ) = d 5 13 31 ( 2015 d ) μ ( d ) = 2015 5 13 31 65 155 403 = 1 f ( 2016 ) = d 2 5 3 2 7 ( 2016 d ) μ ( d ) = d 2 3 7 ( 2016 d ) μ ( d ) = ( 2016 ) ( 2016 2 ) 1 ( 2016 3 ) 1 ( 2016 7 ) 1 ( 2016 2 3 ) ( 2016 2 7 ) ( 2016 3 7 ) ( 2016 2 3 7 ) 1 = 1 f ( 2017 ) = d 2017 ( 2017 d ) μ ( d ) = 2017 \begin{aligned} f(2015) & = \prod_{d | 5 \cdot 13 \cdot 31}\left(\frac{2015}{d} \right)^{\mu(d)} = \frac{2015 \cdot 5 \cdot 13 \cdot 31}{65 \cdot 155 \cdot 403} = 1 \\ f(2016) & = \prod_{d | 2^5 \cdot 3^2 \cdot 7}\left(\frac{2016}{d} \right)^{\mu (d)} = \prod_{d | 2 \cdot 3 \cdot 7}\left(\frac{2016}{d} \right)^{\mu (d)} \\ & = (2016)\left(\frac{2016}{2}\right)^{-1}\left(\frac{2016}{3}\right)^{-1}\left(\frac{2016}{7}\right)^{-1}\left(\frac{2016}{2 \cdot 3}\right)\left(\frac{2016}{2 \cdot 7}\right)\left(\frac{2016}{3 \cdot 7}\right)\left(\frac{2016}{2 \cdot 3 \cdot 7}\right)^{-1} = 1 \\ f(2017) & = \prod_{d | 2017}\left(\frac{2017}{d}\right)^{\mu(d)} = 2017 \end{aligned} Thus, f ( 2015 ) × f ( 2016 ) × f ( 2017 ) = 2017 f(2015) \times f(2016) \times f(2017) = \boxed{2017} .

Nice! (+1) You could further simplify and clarify your work by observing that f ( n ) = d n d μ ( d ) f(n)=\prod_{d|n}d^{-\mu(d)}

Otto Bretscher - 5 years, 5 months ago
Aareyan Manzoor
Dec 30, 2015

take log ln ( n ) = d n ln ( f ( d ) ) \ln(n)=\sum_{d|n}\ln(f(d)) let g ( n ) = ln ( f ( n ) ) g(n)=\ln(f(n)) .and p ( n ) = ln ( n ) p(n)=\ln(n) .then in dirichlet convolution form: p = g u p=g*u . convolute both sides with μ \mu to get: p μ = g I = g p*\mu=g*I=g . in other words: ln ( f ( d ) ) = d n ln ( d ) μ ( n d ) \ln(f(d))=\sum_{d|n} \ln(d)\mu\left(\dfrac{n}{d}\right) it is well known ln ( n ) = d n Λ ( d ) \ln(n)=\sum_{d|n} \Lambda(d) where Λ ( n ) \Lambda(n) is the von mangoldt function . this is easy to prove, try it yourself.

in dirichlet convolution form this is: p = Λ u p=\Lambda*u . convolute bothsides with μ \mu to get: p μ = Λ I = Λ p*\mu=\Lambda*I=\Lambda . in other words d n ln ( d ) μ ( n d ) = Λ ( n ) \sum_{d|n} \ln(d)\mu\left(\dfrac{n}{d}\right)=\Lambda(n) . we get that ln ( f ( n ) ) = Λ ( n ) \ln(f(n))=\Lambda(n) or f ( n ) = e Λ ( n ) f(n)=e^{\Lambda(n)} . the only power of prime among these are 2017 = 201 7 1 2017=2017^1 . we get e 0 × e 0 × e ln ( 2017 ) = 2017 e^0\times e^0\times e^{\ln(2017)}=\boxed{2017} .

a 'bit' copied from my solution here .

Aareyan Manzoor - 5 years, 5 months ago

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 ) f(n) there exists a unique g ( n ) g(n) such that f ( n ) = d n g ( d ) f(n)=\sum_{d|n}g(d) ; you can construct g ( n ) g(n) recursively.

Thus, if we know that ln ( n ) = d n Λ ( d ) \ln(n)=\sum_{d|n}\Lambda(d) , as you assume (small typo there in your formula), and we are given that ln ( n ) = d n ln ( f ( d ) ) , \ln(n)=\sum_{d|n}\ln(f(d)), we can conclude that Λ ( n ) = ln ( f ( n ) ) \Lambda(n)=\ln(f(n)) for all n n , so f ( n ) = e Λ ( n ) = p f(n)=e^{\Lambda(n)}=p if n n is a power of a prime p p , and f ( n ) = 1 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.

Otto Bretscher - 5 years, 5 months ago

Log in to reply

Sir,you forgot my query?

Asad Bhai - 5 years, 5 months ago

part 46, i did try that but wasn't able to solve it. i too am waiting to know how to solve it.

Aareyan Manzoor - 5 years, 5 months ago

Log in to reply

I will give you a hint: Consider Ramanujan Sums

Otto Bretscher - 5 years, 5 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...