A355505 - OEIS

%I #57 Jul 12 2022 08:28:36

%S 2,5,3,4,4,7,4,3,4,6,4,7,4,8,6,3,3,7,5,7,9,7,4,6,4,7,5,9,5,12,7,3,9,5,

%T 8,9,5,10,9,6,4,16,8,9,8,7,5,7,9,7,7,8,4,9,8,8,11,9,4,14,7,13,11,3,8,

%U 16,7,6,9,16,8,8,5,9,9,11,13,17,7,6,6,7,5,17,6,15,11,9,4

%N a(n) is the number of distinct cycles when iterating the function f_n(x), where f_n(x) is the sum of the digits in base n of x^2.

%C The trajectory from every starting point will enter a cycle given a sufficient number of iterations of f_n.

%C To determine a(n), only starting points 0, 1, 2, ..., n^2 have to be checked for cycles. Larger starting points will always lead to a cycle reached from one (or more) of 0, 1, 2, ..., n^2.

%C From _Iain Fox_, Jul 09 2022: (Start)

%C Since f_n(x) <= (n-1)*(1 + floor(2*log_n(x))), only numbers less than the largest zero of (n-1)*(1 + floor(2*log_n(x))) - x need to be checked.

%C The value mentioned above is less than or equal to (2-2n)*W_{-1}(log(n)/((2-2n)*sqrt(n)))/log(n) where W_k(x) is the k-th branch of the Lambert W function. (End)

%H Iain Fox, <a href="/A355505/b355505.txt">Table of n, a(n) for n = 2..10000</a>

%e a(8) = 4 because there are 4 cycles for n = 8:

%e   f_8(0) = 0 (since 0^2 = 0 = 0_8, with digit sum 0),

%e   f_8(1) = 1 (1^2 = 1 = 1_8, with digit sum 1),

%e   f_8(4) = 2 (4^2 = 20_8) and f_8(2) = 4 (2^2 = 4_8), and

%e   f_8(7) = 7 (7^2 = 61_8, with digit sum 7).

%o (PARI) a(n) = my(d=1); while(d<=logint(((n-1)*d)^2, n)+1, d++); my(l=(n-1)*(d-1)+1, x=vector(l, i, l-i), y=[], z=[], j, c=0); for(i=1, #x, y=setunion(y, z); j=x[i]; z=[]; while(!setsearch(z, j), if(setsearch(y, j), next(2)); z=setunion(z, [j]); j=sumdigits(j^2, n)); c++); c \\ _Iain Fox_, Jul 09 2022

%Y Cf. A004159, A061903, A159918.

%K base,nonn

%O 2,1

%A _Wouter Zandsteeg_, Jul 04 2022