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

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

Comments

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

Links

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.

Formula

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

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

Example

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.

Mathematica

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

Prog

(PARI) 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

Crossrefs

Cf. A001146, A002322, A002326, A007733, A010554, A037178.

First differs from A256607 at n=43.

LCM of entries in row n of A279185.

Sequence in context: A351032 A280726 A256607 * A279186 A164799 A274451

Adjacent sequences: A256605 A256606 A256607 * A256609 A256610 A256611

Keyword

nonn

Author

Ivan Neretin, Apr 04 2015

Extensions

Name changed by Jianing Song, Feb 02 2025

Status

approved