A307551 Number of iterations of the map of quadratic residues x -> x^2 (mod prime(n)) with the initial term x = n^2 (mod prime(n)) needed to reach the end of the cycle.

0, 0, 1, 1, 3, 2, 3, 1, 9, 3, 3, 5, 5, 5, 10, 11, 27, 4, 9, 2, 3, 11, 19, 11, 4, 20, 7, 51, 17, 2, 5, 11, 9, 10, 35, 19, 11, 5, 81, 13, 10, 3, 35, 6, 21, 29, 11, 35, 27, 18, 27, 7, 5, 99, 7, 129, 65, 35, 10, 2, 22, 9, 23, 19, 13, 38, 19, 8, 171, 27, 13, 177, 59

Offset: 1

Author

Michel Lagneau, Apr 14 2019

Keywords

• nonn

Comments

Let L(n) be the number of elements in row n of A307550. Then a(n) = L(n) - 1.

Examples

			a(5) = 3 because prime(5) = 11, and 5^2 (mod 11) = 3 -> 3^2 (mod 11) = 9 ->  9^2 (mod 11) = 4 -> 4^2 (mod 11) = 5 with 3 iterations, where 5 is the last term of the cycle.
		

Crossrefs

Cf. A000040, A000224, A046071, A063987, A096008, A307550.

Programs

Maple

nn:=100:T:=array(1..3000):j:=0 :
for n from 1 to nn do:
p:=ithprime(n):lst0:={}:lst1:={}:ii:=0:r:=n:
for k from 1 to 10^6 while(ii=0) do:
  r1:=irem(r^2,p):lst0:=lst0 union {r1}:j:=j+1:T[j]:=r1:
      if lst0=lst1
       then
        ii:=1: printf(`%d, `,nops(lst0)-1):
        else
        r:=r1:lst1:=lst0:
      fi:
     od:
   if lst0 intersect {r1} = {r1}
    then
    j:=j-1:else fi:
od:

Mathematica

a[n_] := Module[{p = Prime[n]}, f[x_] := Mod[x^2, p]; Length[NestWhileList[f, f[n], Unequal, All]] - 2]; Array[a, 100] (* Amiram Eldar, Jul 05 2019 *)