OFFSET
1,3
COMMENTS
Let f(n) be the sum of powers of 2 where the exponents are the digits of n.
If n is a d-digit number, then f(n) <= 512*n while f(n) >= 10^(n-1). So if d >= 5, f(n) is strictly smaller than n. If d <= 4, then f(n) <= 4*512 = 2048, so if 2048 < n < 10000, f(n) is strictly smaller than n. If n <= 2048, then f(n) <= 3*512 = 1536. So if 1536 < n <= 2048, f(n) is also strictly smaller than n. As a result, the terms of the iteration sequence {n, f(n), f(f(n)), ...} must eventually become no more than 1536, so the iteration sequence itself must be eventually periodic. Use a program we can see that the terms eventually fall into one of the four cycles:
- (148, 274) (length = 2);
- (98, 768, 448, 288, 516) (length = 5);
- (70, 129, 518, 290, 517, 162) (length = 6);
- (5, 32, 12, 6, 64, 80, 257, 164, 82, 260, 69, 576, 224, 24, 20) (length = 15).
For all n <= 1536, the iteration f(f(...(f(n))...)) falls into one of the four cycles after no more than 28 steps (n = 127, 172, 217, 271, 712, 721, 1117, 1171, 1266 requires exactly 28).
LINKS
Index entries for linear recurrences with constant coefficients, signature (0,0,0,0,0,0,0,0,0,0,0,0,0,0,1).
FORMULA
a(n) = a(n-15) for n >= 36.
EXAMPLE
a(2) = 2^0 = 1; a(3) = 2^1 = 2; a(4) = 2^2 = 4; a(5) = 2^4 = 16; a(6) = 2^1 + 2^6 = 66; a(7) = 2^6 + 2^6 = 128 ...
PROG
(PARI) f(n) = if(n, my(d=digits(n)); sum(i=1, #d, 2^d[i]), 1)
a(n) = my(v=vector(n)); v[1] = 0; for(i=2, n, v[i]=f(v[i-1])); v[n]
CROSSREFS
KEYWORD
nonn,base,easy
AUTHOR
Jianing Song, Mar 18 2019
STATUS
approved