A number theory puzzle I recently came across the following number theoretic puzzle. Suppose I've infinitely many cards, each with a natural number written on it. Given any $n\in \mathbb N$, the number of cards which have a divisor of $n$ written is exactly equal to $n$. I need to show that every natural number appears on at least one card. Any ideas on how to proceed?
 A: You're looking for a function $f:\mathbb{N}\to\mathbb{N}$ such that $\sum_{d\mid n} f(d) = n$ for all $n$.
The key is that this determines $f(n)$ if you know $f(1), f(2), \ldots ,f(n-1)$ already.  So if you can find any $g$ that does the job, then $f=g$ follows from induction.  How to find such a function?
Hint #1: In a cyclic group with $n$ elements, how many elements of order $d$ are there?
Hint #2: How many $n$-th roots of unity are there?  How many of those are primitive $d$-th roots of unity?
A: I came up with the following formulae, not sure if they are entirely correct:
If i and p (here p is a prime and i is any integer) are coprime then #(ip) = (p-1).#i
Else, #(ip) = p.#i
Where, #k represents the number of cards with number k written on them.
For example, #(1) = 1, #(2) = 1 (in general for a prime q, #q = q-1)
Now assume that k is the smallest of the numbers that are absent on the cards. Basically we assume that for all i < k, #i>0. Now, there are three options for k:
1. k is a prime, in which case, #k = k-1 > 0; or
2. k is of the form, k = ip (p is a prime) where:
         2a. i and p are coprime. Then, #k = (p-1).#i > 0; or
         2b. p divides i. Then, #k = p.#i > 0; or
3. k= 1, where obviously #k = 1 > 0
Since in each case we have a contradiction, our assumption was invalid which means all integers are present at least once.
