A141305 -id:A141305 - cp's OEIS frontend

A279185 Triangle read by rows: T(n,k) (n >= 1, 0 <= k <= n-1) is the length of the period of the sequence obtained by starting with k and repeatedly squaring mod n.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 2, 2, 1, 2, 2, 2, 1

Offset: 1

N. J. A. Sloane, Dec 14 2016

Fix n. Start with k (0 <= k <= n-1) and repeatedly square and reduce mod n until this repeats; T(n,k) is the length of the cycle that is reached.
A279186 gives maximal entry in each row.
A037178 gives maximal entry in row p, p = n-th prime.
A279187 gives maximal entry in row c, c = n-th composite number.
A279188 gives maximal entry in row c, c = prime(n)^2.
A256608 gives LCM of entries in row n.
A256607 gives T(2,n).

			The triangle begins:
1,
1,1,
1,1,1,
1,1,1,1,
1,1,1,1,1,
1,1,1,1,1,1,
1,1,2,2,2,2,1,
1,1,1,1,1,1,1,1,
1,1,2,1,2,2,1,2,1,
1,1,1,1,1,1,1,1,1,1,
1,1,4,4,4,4,4,4,4,4,1,
...
For example, if n=11 and k=2, repeatedly squaring mod 11 gives the sequence 2, 4, 5, 3, 9, 4, 5, 3, 9, 4, 5, 3, ..., which has period T(11,2) = 4.

Robert Israel, Table of n, a(n) for n = 1..10011 (rows 1 to 141, flattened)
Haifeng Xu, The largest cycles consist by the quadratic residues and Fermat primes, arXiv:1601.06509 [math.NT], 2016.

Cf. A037178, A256607, A256608, A279186, A279187, A279188.

See also A141305, A279189, A279190, A279191, A279192.

A279185 := proc(k,n) local g,y,r;
  if k = 0 then return 1 fi;
  y:= n;
  g:= igcd(k,y);
  while g > 1 do
     y:= y/g;
     g:= igcd(k,y);
  od;
  if y = 1 then return 1 fi;
  r:= numtheory:-order(k,y);
  r:= r/2^padic:-ordp(r,2);
  if r = 1 then return 1 fi;
  numtheory:-order(2,r)
end proc:
seq(seq(A279185(k,n),k=0..n-1),n=1..20); # Robert Israel, Dec 14 2016

T[n_, k_] := Module[{g, y, r}, If[k == 0, Return[1]]; y = n; g = GCD[k, y]; While[g > 1, y = y/g; g = GCD[k, y]]; If[y == 1, Return[1]]; r = MultiplicativeOrder[k, y]; r = r/2^IntegerExponent[r, 2]; If[r == 1,  Return[1]]; MultiplicativeOrder[2, r]];
Table[T[n, k], {n, 1, 13}, {k, 0, n-1}] // Flatten (* Jean-François Alcover, Nov 27 2017, after Robert Israel *)

remove_factor(k,n) = while(gcd(n,k)>1, n=n/gcd(n,k)); n; \\ gives the largest divisor of n that is coprime to k
ord(k,n) = znorder(Mod(k,remove_factor(k,n)));
T(n,k) = ord(2,ord(k,n)) \\ Jianing Song, Feb 02 2025

T(n,k) = ord'(2, ord'(k, n)), where ord'(k, n) is the order of k modulo the largest divisor of n that is coprime to k. - Jianing Song, Feb 02 2025

A037178 Longest cycle when squaring modulo n-th prime.

Original entry on oeis.org

1, 1, 1, 2, 4, 2, 1, 6, 10, 3, 4, 6, 4, 6, 11, 12, 28, 4, 10, 12, 6, 12, 20, 10, 2, 20, 8, 52, 18, 3, 6, 12, 8, 22, 36, 20, 12, 54, 82, 14, 11, 12, 36, 2, 21, 30, 12, 36, 28, 18, 28, 24, 4, 100, 1, 130, 66, 36, 22, 12, 46, 9, 24, 20, 12, 39, 20, 6, 172, 28, 10, 178, 60, 10, 18

Offset: 1

Jud McCranie

nonn

a(n)=1 for Fermat primes, A019434. a(n)=2 for primes in A039687. a(n)=3 for primes in A050527. Sequence A141305 gives those primes p > 3 having the longest possible cycle, (p-3)/2. - T. D. Noe, Jun 24 2008

T. D. Noe, Table of n, a(n) for n=1..10000
E. L. Blanton, Jr., S. P. Hurd and J. S. McCranie, On a digraph defined by squaring modulo n, Fibonacci Quart. 30 (Nov. 1992), 322-333.
Haifeng Xu, The largest cycles consist by the quadratic residues and Fermat primes, arXiv:1601.06509 [math.NT], 2016. See table on page 2.

Cf. A002322, A007733, A256608.
Cf. A019434, A039687, A050527, A141305.
Cf. A037179, A037180.
a(n) = maximal entry in row p of A278185.

a[n_] := Module[{p = Prime[n], k}, k = (p-1)/2^IntegerExponent[p-1, 2]; MultiplicativeOrder[2, k]]; Array[a, 100] (* Jean-François Alcover, Jan 28 2016, after T. D. Noe *)

a(n) = {ppn = prime(n) - 1; k = ppn >> valuation(ppn, 2); znorder(Mod(2, k));} \\ Michel Marcus, Nov 11 2015

rpsi(n) = lcm(znstar(n)[2]); \\ A002322
pb(n) = znorder(Mod(2, n/2^valuation(n, 2))); \\ A007733
a(n) = pb(rpsi(prime(n))); \\ Michel Marcus, Jan 28 2016

Let p=prime(n) and k=A000265(p-1), the odd part of p-1. Then a(n) = ord(2,k), that is, the smallest positive integer x such that 2^x = 1 (mod k). - T. D. Noe, Jun 24 2008
a(n) = A007733(A002322(prime(n))). - Michel Marcus, Jan 28 2016
a(n) = A256608(prime(n)).

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.

Original entry on oeis.org

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

Michel Lagneau, Apr 14 2019

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.

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

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

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

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

cp's OEIS Frontend

A279185 Triangle read by rows: T(n,k) (n >= 1, 0 <= k <= n-1) is the length of the period of the sequence obtained by starting with k and repeatedly squaring mod n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A037178 Longest cycle when squaring modulo n-th prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

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.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica