### 10th Putnam 1950

Problem A5

Let N be the set of natural numbers {1, 2, 3, ... }. Let Z be the integers. Define d : N → Z by d(1) = 0, d(p) = 1 for p prime, and d(mn) = m d(n) + n d(m) for any integers m, n. Determine d(n) in terms of the prime factors of n. Find all n such that d(n) = n. Define d1(m) = d(m) and dn+1(m) = d(dn(m)). Find limn→∞ dn(63).

Solution

d(pa) = a pa-1 by a trivial induction on a. Hence for n = paqb ... we have d(n) = n ( a/p + b/q + ... ) by a trivial induction on the number of primes.

Hence d(n) = n iff a/p + b/q + ... = 1. Multiplying through by all the prime denominators gives integral terms. All but the first are clearly divisible by p, so the first must be also. Hence a/p = 1 and b/q etc are zero. In other words, n = pp for some prime p.

We find d1(63) = 51, d2(63) = 20, d3(63) = 24, d4(63) = 44, d5(63) = 48. Now suppose n is divisible by 16. Then n = 2kpaqb ... , where p, q, ... are all odd and k >= 4. Hence d(n) = n( 4/2 + a/p + b/q + ... ). Now all of 2n, na/p, nb/q, ... are integral and multiples of 16. So d(n) is at least twice n and a multiple of 16. So if we have dk(m) divisible by 16, then dh+k(m) ≥ 2h which diverges. Hence dk(63) tends to infinity.