Infinitely many cards

Level pending

The natural numbers have been written on infinitely many cards so that all the divisors of the number n n have been written on exactly n n cards. On how many cards has the number 1024 been written on?


The answer is 512.

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.

1 solution

Bogdan Simeonov
Feb 7, 2014

We see that 1 is written once, then 2 is written once, 3 is written two times and 4 is written 2 times etc.It looks as if the number n is written on φ ( n ) \varphi (n) cards.And indeed let it be true for all numbers less than n.Then the divisors of n would be written on

d n , d < n φ ( d ) = d n φ ( d ) φ ( n ) = n φ ( n ) \displaystyle\sum_{d|n,d<n}^{} \varphi (d)=\sum_{d|n}^{} \varphi(d) - \varphi(n)=n-\varphi(n) cards.We used the well-known identity

d n φ ( d ) = n \displaystyle\sum_{d|n}^{} \varphi(d)= n .

Then for n would be left

n ( n φ ( n ) ) = φ ( n ) n-(n-\varphi(n))=\varphi(n) cards.

What we are looking for is φ ( 2 10 ) = 2 9 = 512 \varphi(2^{10})=2^9=\boxed{512}

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...