A256607 -id:A256607 - cp's OEIS frontend

A007733 Period of binary representation of 1/n. Also, multiplicative order of 2 modulo the odd part of n (= A000265(n)).

1, 1, 2, 1, 4, 2, 3, 1, 6, 4, 10, 2, 12, 3, 4, 1, 8, 6, 18, 4, 6, 10, 11, 2, 20, 12, 18, 3, 28, 4, 5, 1, 10, 8, 12, 6, 36, 18, 12, 4, 20, 6, 14, 10, 12, 11, 23, 2, 21, 20, 8, 12, 52, 18, 20, 3, 18, 28, 58, 4, 60, 5, 6, 1, 12, 10, 66, 8, 22, 12, 35, 6, 9, 36, 20, 18, 30, 12, 39, 4, 54, 20, 82, 6

Offset: 1

N. J. A. Sloane, Hal Sampson (hals(AT)easynet.com)

Also sequence of period lengths for n's when you do primality testing and calculate "2^k mod n" from k = 0..n. - Gottfried Helms, Oct 05 2000
Fractal sequence related to A002326: the even terms of this sequence are this sequence itself, constructed on A002326, whose terms are the odd terms of this sequence. - Alexandre Wajnberg, Apr 27 2005
It seems that a(n) is also the sum of the terms in one period of the base-2 MR-expansion of 1/n (see A136042 for definition). - John W. Layman, Jan 22 2009
Indices n such that a(n) divides n are listed in A068563. - Max Alekseyev, Aug 25 2013
a(n) is the smallest k such that x^n - 1 factors into n linear polynomials over GF(2^k). For example, a(12) = 2, and x^12 - 1 = (x - 1)^4*(x - w)^4*(x - (w + 1))^4 in GF(4), where w^2 + w + 1 = 0. - Jianing Song, Jan 20 2019

Simmons, G. J. The structure of the differentiation digraphs of binary sequences. Ars Combin. 35 (1993), A, 71-88, see Table 2. Math. Rev. 95f:05052.

Cf. A136042. - John W. Layman, Jan 22 2009
Cf. A000265, A002326, A256607, A256757.
Positions of records are A139099.

a007733 = a002326 . flip div 2 . subtract 1 . a000265
-- Reinhard Zumkeller, Apr 13 2015

f[n_] := MultiplicativeOrder[2, n/(2^IntegerExponent[n, 2])]; Array[f, 84] (* Robert G. Wilson v, Jun 10 2011 *)

a(n) = znorder(Mod(2, n/2^valuation(n, 2))); \\ Michel Marcus, Apr 11 2015

from sympy.ntheory import n_order
def A007733(n): return n_order(2,n>>(~n & n-1).bit_length()) # Chai Wah Wu, Jul 01 2022

a(n) = A002326((A000265(n) - 1)/2). - Max Alekseyev, Jun 11 2009

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.

Original entry on oeis.org

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

A279186 Maximal entry in n-th row of A279185.

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

Offset: 1

N. J. A. Sloane, Dec 14 2016

nonn

See A256608 for LCM of entries in row n.
From Robert Israel, Dec 15 2016: (Start)
If m and k are coprime then a(m*k) = lcm(a(m), a(k)).
If n is in A061345 and r = A053575(n) is in A167791, then a(n) = A000010(r). (End)

R. J. Mathar, Table of n, a(n) for n = 1..1000

Cf. A000010, A053575, A063145, A167791, A279185.

Start is same as A256607 and A256608. However, all three are different.

A279186 := proc(n)
    local a,k ;
    a := 1 ;
    for k from 0 to n-1 do
        a := max(a,A279185(k,n)) ;
    end do:
    a ;
end proc : # R. J. Mathar, Dec 15 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]];
a[n_] := Table[T[n, k], {k, 0, n - 1}] // Max;
Array[a, 90] (* Jean-François Alcover, Nov 27 2017, after Robert Israel *)

{ A279186(n) = my(r=lcm(znstar(n)[2])); znorder(Mod(2,r>>valuation(r,2))); } \\ Max Alekseyev, Feb 02 2024

a(n) = A007733(A002322(n)). - Max Alekseyev, Feb 02 2024

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

A256757 Number of iterations of A007733 required to reach 1.

Original entry on oeis.org

0, 1, 2, 1, 2, 2, 3, 1, 3, 2, 3, 2, 3, 3, 2, 1, 2, 3, 4, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 2, 3, 1, 3, 2, 3, 3, 4, 4, 3, 2, 3, 3, 4, 3, 3, 4, 5, 2, 4, 3, 2, 3, 4, 4, 3, 3, 4, 4, 5, 2, 3, 3, 3, 1, 3, 3, 4, 2, 4, 3, 4, 3, 4, 4, 3, 4, 3, 3, 4, 2, 5, 3, 4, 3, 2, 4, 4, 3, 4, 3, 3, 4, 3, 5, 4, 2, 3, 4, 3, 3

Offset: 1

Ivan Neretin, Apr 09 2015

In other words, the minimal height (not counting k) of the power tower 2^(2^(...^(2^k)...)) required to make it eventually constant modulo n (=A245970(n)) for sufficiently large k.

a(n) <= A227944(n) + 1. - Max Alekseyev, Oct 11 2016

Ivan Neretin, Table of n, a(n) for n = 1..10000

Cf. A007733, A256607 (second iteration), A256758 (positions of records), A003434, A227944 (similarly built upon the totient function).

a256757 n = fst $ until ((== 1) . snd)
            (\(i, x) -> (i + 1, fromIntegral $ a007733 x)) (0, n)
-- Reinhard Zumkeller, Apr 13 2015

A007733 = Function[n, MultiplicativeOrder[2, n/(2^IntegerExponent[n, 2])]];
a = Function[n, k = 0; m = n; While[m > 1, m = A007733[m]; k++]; k];
Table[a[n], {n, 100}] (* Ivan Neretin, Apr 13 2015 *)

a(n) = {if (n==1, return(0)); nb = 1; while((n = znorder(Mod(2, n/2^valuation(n, 2)))) != 1, nb++); nb;} \\ Michel Marcus, Apr 11 2015

For n>1, a(n) = a(A007733(n)) + 1.

A348062 Primes p such that the length of the (eventual) period of the sequence {2^(2^k) mod p: k >= 0} is odd.

Original entry on oeis.org

2, 3, 5, 17, 29, 43, 47, 113, 127, 179, 197, 257, 277, 283, 293, 317, 383, 439, 449, 467, 479, 509, 569, 641, 659, 719, 797, 863, 1013, 1069, 1289, 1373, 1399, 1427, 1439, 1487, 1579, 1627, 1657, 1753, 1823, 1913, 1933, 1949, 2063, 2203, 2207, 2213, 2273, 2339, 2351

Offset: 1

Arkadiusz Wesolowski, Sep 26 2021

nonn

Of these numbers only 3 and 5 are elite primes (A102742). (Aigner)

Every prime of the form A036259(n)*2^m + 1, with m, n >= 1, is in this sequence.

Alexander Aigner, Über Primzahlen, nach denen (fast) alle Fermatzahlen quadratische Nichtreste sind, Monatsh. Math., Vol. 101 (1986), pp. 85-93; alternative link.

Supersequence of A023394.

Cf. A102742 (elite primes), A256607.

L=List([2]); forprime(p=3, 2351, z=znorder(Mod(2, p)); if(znorder(Mod(2, z/2^valuation(z, 2)))%2, listput(L, p))); Vec(L)

cp's OEIS Frontend

A007733 Period of binary representation of 1/n. Also, multiplicative order of 2 modulo the odd part of n (= A000265(n)).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

Formula

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

A279186 Maximal entry in n-th row of A279185.

Views

Author

Keywords

Comments

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

A256757 Number of iterations of A007733 required to reach 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

A348062 Primes p such that the length of the (eventual) period of the sequence {2^(2^k) mod p: k >= 0} is odd.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI