login
a(1) = 0; a(n) is the sum of powers of 2 where the exponents are the digits of a(n-1).
1

%I #13 Mar 31 2019 02:23:00

%S 0,1,2,4,16,66,128,262,72,132,14,18,258,292,520,37,136,74,144,34,24,

%T 20,5,32,12,6,64,80,257,164,82,260,69,576,224,24,20,5,32,12,6,64,80,

%U 257,164,82,260,69,576,224,24,20,5,32,12,6,64,80,257,164,82,260,69,576,224

%N a(1) = 0; a(n) is the sum of powers of 2 where the exponents are the digits of a(n-1).

%C Let f(n) be the sum of powers of 2 where the exponents are the digits of n.

%C 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:

%C - (148, 274) (length = 2);

%C - (98, 768, 448, 288, 516) (length = 5);

%C - (70, 129, 518, 290, 517, 162) (length = 6);

%C - (5, 32, 12, 6, 64, 80, 257, 164, 82, 260, 69, 576, 224, 24, 20) (length = 15).

%C 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).

%H <a href="/index/Rec#order_15">Index entries for linear recurrences with constant coefficients</a>, signature (0,0,0,0,0,0,0,0,0,0,0,0,0,0,1).

%F a(n) = a(n-15) for n >= 36.

%e 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 ...

%o (PARI) f(n) = if(n, my(d=digits(n)); sum(i=1, #d, 2^d[i]), 1)

%o a(n) = my(v=vector(n)); v[1] = 0; for(i=2, n, v[i]=f(v[i-1])); v[n]

%K nonn,base,easy

%O 1,3

%A _Jianing Song_, Mar 18 2019