A037178 -id:A037178 - 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

A256608 Longest eventual period of a^(2^k) mod n for all a.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 4, 1, 2, 2, 1, 1, 1, 2, 6, 1, 2, 4, 10, 1, 4, 2, 6, 2, 3, 1, 4, 1, 4, 1, 2, 2, 6, 6, 2, 1, 4, 2, 6, 4, 2, 10, 11, 1, 6, 4, 1, 2, 12, 6, 4, 2, 6, 3, 28, 1, 4, 4, 2, 1, 2, 4, 10, 1, 10, 2, 12, 2, 6, 6, 4, 6, 4, 2, 12, 1, 18, 4, 20, 2, 1, 6

Offset: 1

Ivan Neretin, Apr 04 2015

nonn

a(n) is a divisor of phi(phi(n)) (A010554).

			In other words, eventual period of {0..n-1} under the map x -> x^2 mod n.
For example, with n=10 the said map acts as follows. Read down the columns: the column headed 2 for example means that (repeatedly squaring mod 10), 2 goes to 4 goes to 16 = 6 (mod 10) goes to 36 = 6 mod 10 --- and has reached a fixed point.
0 1 2 3 4 5 6 7 8 9
0 1 4 9 6 5 6 9 4 1
0 1 6 1 6 5 6 1 6 1
0 1 6 1 6 5 6 1 6 1
and thus every number reaches a fixed point. This means the eventual common period is 1, hence a(10)=1.

Ivan Neretin, Table of n, a(n) for n = 1..10000
Haifeng Xu, The largest cycles consist by the quadratic residues and Fermat primes, arXiv:1601.06509 [math.NT], 2016.

Cf. A001146, A002322, A002326, A007733, A010554, A037178.
First differs from A256607 at n=43.
LCM of entries in row n of A279185.

a[n_] := With[{lambda = CarmichaelLambda[n]}, MultiplicativeOrder[2, lambda / (2^IntegerExponent[lambda, 2])]]; Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Jan 28 2016 *)

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

a(n) = A007733(A002322(n)).

a(prime(n)) = A037178(n). - Michel Marcus, Jan 27 2016

Name changed by Jianing Song, Feb 02 2025

A141305 Primes p such that q=(p-1)/2 is also prime and 2 is a primitive root mod q; that is, q is in A001122.

Original entry on oeis.org

7, 11, 23, 59, 107, 167, 263, 347, 359, 587, 839, 887, 983, 1019, 1307, 1319, 2039, 2459, 2903, 2999, 3467, 3803, 3863, 3947, 4139, 4283, 4679, 4919, 5099, 5387, 5399, 5483, 5639, 5879, 5927, 6599, 6827, 6983, 7079, 7559, 7607, 7703, 8039, 8699, 8747

Offset: 1

T. D. Noe, Jun 24 2008

nonn

These primes are a subset of the safe primes, A005385. These primes produce the longest possible cycles, (p-3)/2, in the squaring mod p map. See A037178.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Caroline Lucheta, Eli Miller and Clifford Reiter, Digraphs from Powers Modulo p, Fibonacci Quarterly, Volume 34, Number 3, June-July 1996. See p. 9.
Troy Vasiga and Jeffrey Shallit, On the iteration of certain quadratic maps over GF(p), Discrete Mathematics, Volume 277, Issues 1-3, 28 February 2004, Pages 219-240. See p.9.

Cf. A001122, A005385, A037178.

Select[Range[10^4], PrimeQ[#] && PrimeQ[(q = (# - 1)/2)] && PrimitiveRoot[q] == 2 &] (* Amiram Eldar, Oct 09 2021 *)

isok(p) = isprime(p) && (p%2) && isprime(q=(p-1)/2) && (q%2) && (znorder(Mod(2, q))==(q-1)); \\ Michel Marcus, Jan 30 2016

Incorrect term 5 removed by Michel Marcus, Jan 30 2016

A037179 Number of cycles when squaring modulo n-th prime.

Original entry on oeis.org

2, 2, 2, 3, 3, 3, 2, 4, 3, 4, 6, 4, 3, 7, 4, 3, 3, 6, 6, 7, 4, 6, 4, 3, 3, 4, 9, 3, 5, 4, 14, 8, 4, 7, 3, 9, 6, 6, 3, 5, 10, 9, 6, 3, 6, 9, 16, 6, 6, 6, 3, 10, 6, 5, 2, 3, 3, 12, 7, 7, 7, 10, 14, 15, 6, 4, 15, 7, 3, 6, 3, 3, 6, 15, 21, 4, 4, 9, 4, 9, 6, 16, 12, 5, 19, 13, 4, 6, 7, 16, 10, 4, 7, 11, 6

Offset: 1

Jud McCranie

nonn

Note that Rogers and Shallit give the formula for F*p and Rogers has a table with a(n)-1. - Michel Marcus, Jan 30 2016

Amiram Eldar, 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. See p. 9.
Thomas D. Rogers, The graph of the square mapping on the prime fields, Discrete Mathematics, Volume 148, Issues 1-3, 15 January 1996, Pages 317-324. See p. 4.
Troy Vasiga and Jeffrey Shallit, On the iteration of certain quadratic maps over GF(p), Discrete Mathematics, Volume 277, Issues 1-3, 28 February 2004, Pages 219-240. See theorem 6 p. 6.

Cf. A000265, A037178, A037180.

odd[n_] := n/2^IntegerExponent[n,2]; a[n_] := 1 + DivisorSum[odd[Prime[n]-1], EulerPhi[#]/MultiplicativeOrder[2, #] &]; Array[a, 100] (* Amiram Eldar, Aug 29 2023 *)

rho(p) = {my(m = p-1); m >> valuation(m, 2);}
a(n) = {my(r = rho(prime(n))) ; 1+ sumdiv(r, d, eulerphi(d)/znorder(Mod(2,d)));} \\ Michel Marcus, Jan 30 2016

a(n) = 1+ Sum_{d|rho} phi(d)/ord(2,d) with rho the largest odd factor of prime(n)-1 (rho = A000265(p-1)). The 1 corresponds to the sink 0. - Michel Marcus, Jan 30 2016

A037180 Number of different cycle lengths when squaring modulo n-th prime.

Original entry on oeis.org

1, 1, 1, 2, 2, 2, 1, 3, 2, 2, 3, 3, 2, 4, 2, 2, 2, 3, 3, 4, 3, 3, 2, 2, 2, 3, 3, 2, 4, 2, 4, 3, 2, 4, 2, 4, 3, 5, 2, 2, 2, 5, 4, 2, 3, 5, 6, 3, 2, 3, 2, 4, 3, 4, 1, 2, 2, 7, 4, 4, 4, 2, 5, 4, 3, 2, 5, 4, 2, 3, 2, 2, 3, 4, 5, 2, 2, 5, 3, 3, 4, 6, 4, 4, 4, 4, 2, 3, 4, 6, 2, 2, 6, 6, 3, 2, 2, 3, 5, 7, 5, 2

Offset: 1

Jud McCranie

nonn

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.

Cf. A037178, A037179.

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

A256608 Longest eventual period of a^(2^k) mod n for all a.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A141305 Primes p such that q=(p-1)/2 is also prime and 2 is a primitive root mod q; that is, q is in A001122.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A037179 Number of cycles when squaring modulo n-th prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A037180 Number of different cycle lengths when squaring modulo n-th prime.

Views

Author

Keywords

Links

Crossrefs