cp's OEIS Frontend

A355505 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.

%I A355505 #57 Jul 12 2022 08:28:36
%S A355505 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 A355505 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 A355505 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 A355505 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 A355505 The trajectory from every starting point will enter a cycle given a sufficient number of iterations of f_n.
%C A355505 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 A355505 From _Iain Fox_, Jul 09 2022: (Start)
%C A355505 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 A355505 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 A355505 Iain Fox, <a href="/A355505/b355505.txt">Table of n, a(n) for n = 2..10000</a>
%e A355505 a(8) = 4 because there are 4 cycles for n = 8:
%e A355505   f_8(0) = 0 (since 0^2 = 0 = 0_8, with digit sum 0),
%e A355505   f_8(1) = 1 (1^2 = 1 = 1_8, with digit sum 1),
%e A355505   f_8(4) = 2 (4^2 = 20_8) and f_8(2) = 4 (2^2 = 4_8), and
%e A355505   f_8(7) = 7 (7^2 = 61_8, with digit sum 7).
%o A355505 (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 A355505 Cf. A004159, A061903, A159918.
%K A355505 base,nonn
%O A355505 2,1
%A A355505 _Wouter Zandsteeg_, Jul 04 2022