stan@hare.DEC (Stanley Rabinowitz) (08/02/84)
I received the following response to the iterated sum of digits problem from Peter Gilbert (dec-turtle!gilbert) and I am posting it for him with his permission. Let f(x) = the number of prime factors of x f(x) <= log x, where p is the smallest prime factor of x p Let g(x) = the number of divisors of x (including 1 and itself) g(x) <= 2 ^ f(x) g(p^k * y) <= (k+1) * g(y), where p is a prime Let h(x) = the sum of the digits of the divisors of x h(x) <= g(x) * 9 * (1+log x) 10 Let n = 2^p * 3^q * r, where r is not divisible by 2 or 3. We want to choose M such that n >= M implies h(n) < n. We have: h(n) <= (p+1) * (q+1) * 2^log r * 9 * (1+log n) 5 10 2^log r = 2^log (n * 2^-p * 3^-q) 5 5 = n^(log 2) * (2^log 2)^-p * (2^log 3)^-q 5 5 5 (p+1) * (2^log 2)^-p < 1.66 5 (q+1) * (2^log 3)^-q < 1.25 5 h(n) < n^(log 2) * (1+log n) * 1.66 * 1.25 * 9 5 10 < n^(log 2) * (1+log n) * 18.68 5 10 We want to choose M so that n >= M implies: h() < n^(log 2) * (1+log n) * 18.68 < n 5 10 18.68 * (1+log n) < n^(1-log 2) 10 5 This is true if n >= 2268, so we take M = 2500. (a better analysis could reduce 18.68 by about a factor of 2, yielding M < 600, which would put the problem in the paper/pencil/pocket-calculator category). A computer program was used to check 1 <= n <= 2500. The following table summarizes all the cases with h(n) >= n. More values are given in the third column than are needed for a proof; they're FYI. n h(n) h(h(n)), h(h(h(n))), ... 1 1 1 2 3 4, 7, 8,15 3 4 7, 8,15 4 7 8,15 5 6 12,19,11, 3, 4, 7, 8,15 6 12 19,11, 3, 4, 7, 8,15 7 8 15 8 15 15 9 13 5, 6,12,19,11, 3, 4, 7, 8,15 12 19 11, 3, 4, 7, 8,15 14 15 15 15 15 15 16 22 9,13, 5, 6,12,19,11, 3, 4, 7, 8,15 18 30 27,22, 9,13, 5, 6,12,19,11, 3, 4, 7, 8,15 24 33 12,19,11, 3, 4, 7, 8,15 28 29 12,19,11, 3, 4, 7, 8,15 36 46 18,30,27,22, 9,13, 5, 6,12,19,11, 3, 4, 7, 8,15 48 52 26,16,22, 9,13, 5, 6,12,19,11, 3, 4, 7, 8,15 Thus, all numbers > 1 eventually get into the "15" cycle. - Gilbert