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.

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, 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, 16, 7, 6, 9, 16, 8, 8, 5, 9, 9, 11, 13, 17, 7, 6, 6, 7, 5, 17, 6, 15, 11, 9, 4

Offset

2,1

Comments

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

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.

From Iain Fox, Jul 09 2022: (Start)

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.

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)

Links

Iain Fox, Table of n, a(n) for n = 2..10000

Example

a(8) = 4 because there are 4 cycles for n = 8:
  f_8(0) = 0 (since 0^2 = 0 = 0_8, with digit sum 0),
  f_8(1) = 1 (1^2 = 1 = 1_8, with digit sum 1),
  f_8(4) = 2 (4^2 = 20_8) and f_8(2) = 4 (2^2 = 4_8), and
  f_8(7) = 7 (7^2 = 61_8, with digit sum 7).

Prog

(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

Crossrefs

Cf. A004159, A061903, A159918.

Sequence in context: A372388 A309735 A275726 * A146096 A011310 A075250

Adjacent sequences: A355502 A355503 A355504 * A355506 A355507 A355508

Keyword

base,nonn

Author

Wouter Zandsteeg, Jul 04 2022

Status

approved