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.

%I A279185 #38 Feb 02 2025 21:19:44
%S A279185 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 A279185 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 A279185 1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,1,2,2,1,2,2,2,1
%N 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.
%C A279185 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 A279185 A279186 gives maximal entry in each row.
%C A279185 A037178 gives maximal entry in row p, p = n-th prime.
%C A279185 A279187 gives maximal entry in row c, c = n-th composite number.
%C A279185 A279188 gives maximal entry in row c, c = prime(n)^2.
%C A279185 A256608 gives LCM of entries in row n.
%C A279185 A256607 gives T(2,n).
%H A279185 Robert Israel, <a href="/A279185/b279185.txt">Table of n, a(n) for n = 1..10011</a> (rows 1 to 141, flattened)
%H A279185 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.
%F A279185 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
%e A279185 The triangle begins:
%e A279185 1,
%e A279185 1,1,
%e A279185 1,1,1,
%e A279185 1,1,1,1,
%e A279185 1,1,1,1,1,
%e A279185 1,1,1,1,1,1,
%e A279185 1,1,2,2,2,2,1,
%e A279185 1,1,1,1,1,1,1,1,
%e A279185 1,1,2,1,2,2,1,2,1,
%e A279185 1,1,1,1,1,1,1,1,1,1,
%e A279185 1,1,4,4,4,4,4,4,4,4,1,
%e A279185 ...
%e A279185 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 A279185 := proc(k,n) local g,y,r;
%p A279185   if k = 0 then return 1 fi;
%p A279185   y:= n;
%p A279185   g:= igcd(k,y);
%p A279185   while g > 1 do
%p A279185      y:= y/g;
%p A279185      g:= igcd(k,y);
%p A279185   od;
%p A279185   if y = 1 then return 1 fi;
%p A279185   r:= numtheory:-order(k,y);
%p A279185   r:= r/2^padic:-ordp(r,2);
%p A279185   if r = 1 then return 1 fi;
%p A279185   numtheory:-order(2,r)
%p A279185 end proc:
%p A279185 seq(seq(A279185(k,n),k=0..n-1),n=1..20); # _Robert Israel_, Dec 14 2016
%t A279185 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 A279185 Table[T[n, k], {n, 1, 13}, {k, 0, n-1}] // Flatten (* _Jean-François Alcover_, Nov 27 2017, after _Robert Israel_ *)
%o A279185 (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
%o A279185 ord(k,n) = znorder(Mod(k,remove_factor(k,n)));
%o A279185 T(n,k) = ord(2,ord(k,n)) \\ _Jianing Song_, Feb 02 2025
%Y A279185 Cf. A037178, A256607, A256608, A279186, A279187, A279188.
%Y A279185 See also A141305, A279189, A279190, A279191, A279192.
%K A279185 nonn,tabl
%O A279185 1,24
%A A279185 _N. J. A. Sloane_, Dec 14 2016