More on ϕ \phi in 2016

d 201 6 2 ϕ ( d ) = ? \large {\sum_{d \mid 2016^2}\phi(d) } = \, ?

Notation : ϕ ( x ) \phi(x) denotes the Euler totient function .


Inspiration .


The answer is 4064256.

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

Chew-Seong Cheong
Jan 10, 2016

The function is multiplicative, therefore,

d 201 6 2 ϕ ( d ) = d 2 10 3 4 7 2 ϕ ( d ) = d 2 10 ϕ ( d ) d 3 4 ϕ ( d ) d 7 2 ϕ ( d ) = ( 1 + 1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 + 256 + 512 ) ( 1 + 2 + 6 + 18 + 54 ) ( 1 + 6 + 42 ) = 1024 × 81 × 49 = 4064256 \begin{aligned} \sum_{d|2016^2} \phi (d) & = \sum_{d|2^{10}3^47^2} \phi (d) \\ & = \sum_{d|2^{10}} \phi (d) \sum_{d|3^4} \phi (d) \sum_{d|7^2} \phi (d) \\ & = (1+1+2+4+8+16+32+64 +128+256+512)(1+2+6+18+54)(1+6+42) \\ & = 1024 \times 81 \times 49 = \boxed{4064256} \end{aligned}

same method!

Aareyan Manzoor - 5 years, 5 months ago
Otto Bretscher
Jan 12, 2016

We observe that the function f ( n ) = d n ϕ ( d ) f(n)=\sum_{d|n}\phi(d) is multiplicative, being the Dirichlet convolution of ϕ \phi and the constant function 1. Now we see that f ( p k ) f(p^k) = 1 + ( p 1 ) + ( p 2 p ) + . . . + ( p k p k 1 ) = p k =1+(p-1)+(p^2-p)+...+(p^k-p^{k-1})=p^k for primes p p , so that f ( n ) = d n ϕ ( d ) = n f(n)=\sum_{d|n}\phi(d)=n for all n n . Thus f ( 201 6 2 ) = 201 6 2 = 4064256 f(2016^2)=2016^2=\boxed{4064256}

Trevor Arashiro
Jan 9, 2016

Just for now

d y ϕ ( d ) = y \large {\sum_{d \mid y}\phi(d) = y}

There's an algebraic method, but you can solve this strictly by thinking about what ϕ ( x ) \phi(x) represents. (Hint: ϕ ( x ) \phi(x) represents the number of integers < x <x which are coprime with x x )

We discussed this issue here , and several good solutions were submitted.

Otto Bretscher - 5 years, 5 months ago

Log in to reply

Oh, wow, I never saw that problem. I think I'm gonna delete this problem since it's not original.

Trevor Arashiro - 5 years, 5 months ago

Log in to reply

I think it's good to remind people of this important stuff... I'm sure others have missed it too.

Otto Bretscher - 5 years, 5 months ago

Do not delete , may I suggest you an update for the question? ;)

A Former Brilliant Member - 5 years, 5 months ago

Log in to reply

@A Former Brilliant Member Sure, what do you have in mind?

Trevor Arashiro - 5 years, 5 months ago

Log in to reply

@Trevor Arashiro Do some awesome combinations with Mobius , von mangoldt , liouville etc. ;)

A Former Brilliant Member - 5 years, 5 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...