A307550 - OEIS

%I #21 May 01 2022 01:28:12

%S 1,1,4,1,2,4,3,9,4,5,10,9,3,15,4,16,1,7,11,12,6,13,8,18,2,4,16,3,9,13,

%T 24,25,16,28,9,19,20,33,16,34,9,7,12,5,25,10,18,37,16,24,17,31,15,10,

%U 14,37,6,36,27,24,12,3,9,34,28,32,44,28,42,15,13,10

%N Irregular array of distinct terms read by rows: for n > 0, row n = [r(1),...,r(k)] with r(1) = n^2 (mod prime(n)), r(2) = r(1)^2 (mod prime(n)), ..., r(k) = r(k-1)^2 (mod prime(n)), where r(k) is the last term of the cycle.

%C Consider the map of quadratic residues x -> x^2 (mod prime(n)) with the initial term x = r(1) = n^2 (mod prime(n)) needed to reach the end of the cycle. Row n contains all distinct quadratic residues r(i) such that r(i) = r(j)^2 (mod prime(n)) for some i, j.

%C The corresponding row lengths are given by the sequence {b(n)} = {1, 1, 2, 2, 4, 3, 4, 2, 10, 4, 4, 6, 6, 6, 11, 12, 28, 5, 10, 3, 4, 12, 20, 12, 5, 21, ...} with b(n) = A307551(n) + 1. We observe the following property: if prime(n) = 2p + 1 with p prime, b(n) = p - 1 if 2 is a primitive root mod p; that is, p is in A001122 (see A141305). Example: b(17) = 28 because prime(17) = 59 = 2*29 + 1 with 28 = 29 - 1, and 2 is a primitive root mod 29.

%e Row 5 = [3, 9, 4, 5] because prime(5) = 11, and 3 = 5^2 (mod 11), 9 = 3^2 (mod 11), 4 = 9^2 (mod 11) and 5 = 4^2 (mod 11).

%e Irregular array starts:

%e   [1];

%e   [1];

%e   [4, 1];

%e   [2, 4];

%e   [3, 9, 4, 5];

%e   [10, 9, 3];

%e   [15, 4, 16, 1];

%e    ...

%p nn:=30:T:=array(1..280):j:=0 :

%p for n from 1 to nn do:

%p p:=ithprime(n):lst0:={}:lst1:={}:ii:=0:r:=n:

%p for k from 1 to 10^6 while(ii=0) do:

%p   r1:=irem(r^2,p):lst0:=lst0 union {r1}:j:=j+1:T[j]:=r1:

%p       if lst0=lst1

%p        then

%p         ii:=1:

%p         else

%p         r:=r1:lst1:=lst0:

%p       fi:

%p      od:

%p    if lst0 intersect {r1} = {r1}

%p     then

%p     j:=j-1:else fi:

%p od:

%p print(T):

%t s[n_] := Module[{p = Prime[n]}, f[x_] := Mod[x^2, p]; Most[NestWhileList[f, f[n], Unequal, All]]]; seq = {}; Do[AppendTo[seq, s[n]], {n, 20}]; seq // Flatten (* _Amiram Eldar_, Jul 05 2019 *)

%Y Cf. A000040, A001122, A000224, A046071, A063987, A096008, A141305, A307551.

%K nonn,tabf

%O 1,3

%A _Michel Lagneau_, Apr 14 2019