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,3

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.

Links

Table of n, a(n) for n=1..72.

Example

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];
   ...

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

Crossrefs

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

Sequence in context: A236269 A010126 A021712 * A309443 A014571 A327320

Adjacent sequences: A307547 A307548 A307549 * A307551 A307552 A307553

Keyword

nonn,tabf

Author

Michel Lagneau, Apr 14 2019

Status

approved