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

Author

N. J. A. Sloane, Dec 14 2016

Keywords

• nonn
• tabl

Comments

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

Examples

			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.
		

Links

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

Crossrefs

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

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

Programs

Maple

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

Mathematica

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

PARI

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

Formula

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