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

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, 24, 25, 16, 28, 9, 19, 20, 33, 16, 34, 9, 7, 12, 5, 25, 10, 18, 37, 16, 24, 17, 31, 15, 10, 14, 37, 6, 36, 27, 24, 12, 3, 9, 34, 28, 32, 44, 28, 42, 15, 13, 10

Offset: 1

Author

Michel Lagneau, Apr 14 2019

Keywords

• nonn
• tabf

Comments

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.

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.

Examples

			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).
Irregular array starts:
  [1];
  [1];
  [4, 1];
  [2, 4];
  [3, 9, 4, 5];
  [10, 9, 3];
  [15, 4, 16, 1];
   ...
		

Crossrefs

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

Programs

Maple

nn:=30:T:=array(1..280):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:
        else
        r:=r1:lst1:=lst0:
      fi:
     od:
   if lst0 intersect {r1} = {r1}
    then
    j:=j-1:else fi:
od:
print(T):

Mathematica

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 *)