login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 11

%I

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

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

%U 1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,1,2,2,1,2,2,2,1

%N 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.

%C 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.

%C A279186 gives maximal entry in each row.

%C A037178 gives maximal entry in row p, p = n-th prime.

%C A279187 gives maximal entry in row c, c = n-th composite number.

%C A279188 gives maximal entry in row c, c = prime(n)^2.

%C A256608 gives LCM of entries in row n.

%C A256607 gives T(2,n).

%H Robert Israel, <a href="/A279185/b279185.txt">Table of n, a(n) for n = 1..10011</a> (rows 1 to 141, flattened)

%H Haifeng Xu, <a href="http://arxiv.org/abs/1601.06509">The largest cycles consist by the quadratic residues and Fermat primes</a>, arXiv:1601.06509 [math.NT], 2016.

%e The triangle begins:

%e 1,

%e 1,1,

%e 1,1,1,

%e 1,1,1,1,

%e 1,1,1,1,1,

%e 1,1,1,1,1,1,

%e 1,1,2,2,2,2,1,

%e 1,1,1,1,1,1,1,1,

%e 1,1,2,1,2,2,1,2,1,

%e 1,1,1,1,1,1,1,1,1,1,

%e 1,1,4,4,4,4,4,4,4,4,1,

%e ...

%e 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.

%p A279185 := proc(k,n) local g,y,r;

%p if k = 0 then return 1 fi;

%p y:= n;

%p g:= igcd(k,y);

%p while g > 1 do

%p y:= y/g;

%p g:= igcd(k,y);

%p od;

%p if y = 1 then return 1 fi;

%p r:= numtheory:-order(k,y);

%p r:= r/2^padic:-ordp(r,2);

%p if r = 1 then return 1 fi;

%p numtheory:-order(2,r)

%p end proc:

%p seq(seq(A279185(k,n),k=0..n-1),n=1..20); # _Robert Israel_, Dec 14 2016

%t 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]];

%t Table[T[n, k], {n, 1, 13}, {k, 0, n-1}] // Flatten (* _Jean-Fran├žois Alcover_, Nov 27 2017, after _Robert Israel_ *)

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

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

%K nonn,tabl

%O 1,24

%A _N. J. A. Sloane_, Dec 14 2016

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 24 23:25 EDT 2021. Contains 346273 sequences. (Running on oeis4.)