A212953 -id:A212953 - cp's OEIS frontend

A059499 a(n) = |{m : multiplicative order of 2 mod m = n}|.

1, 1, 1, 2, 1, 3, 1, 4, 2, 5, 3, 16, 1, 5, 5, 8, 1, 24, 1, 38, 9, 11, 3, 68, 6, 5, 4, 54, 7, 79, 1, 16, 11, 5, 13, 462, 3, 5, 13, 140, 3, 123, 7, 110, 54, 11, 7, 664, 2, 114, 29, 118, 7, 124, 59, 188, 13, 55, 3, 4456, 1, 5, 82, 96, 5, 353, 3, 118, 11, 485, 7

Offset: 1

Vladeta Jovovic, Feb 04 2001

nonn

Also, number of primitive factors of 2^n - 1 (cf. A212953). - Max Alekseyev, May 03 2022
The multiplicative order of a mod m, gcd(a,m)=1, is the smallest natural number d for which a^d = 1 (mod m). See A002326.
a(n) is odd iff n is squarefree, A005117. - Thomas Ordowski, Jan 18 2014
The set S for which a(n) = |S| contains an odd number of prime powers p^k, where k > 0 and p == 3 (mod 4), iff n is squarefree and greater than one. - Isaac Saffold, Dec 28 2019

			a(3) = |{7}| = 1, a(4) = |{5,15}| = 2, a(6) = |{9,21,63}| = 3.

Max Alekseyev, Table of n, a(n) for n = 1..1206 (first 200 terms from Alois P. Heinz)

Column k=2 of A212957.
Primitive factors of b^n - 1: this sequence (b=2), A059885 (b=3), A059886 (b=4), A059887 (b=5), A059888 (b=6), A059889 (b=7), A059890 (b=8), A059891 (b=9), A059892 (b=10).
Cf. A001037, A046801, A058943, A059912, A112927, A212953.

with(numtheory):
a:= n-> add(mobius(n/d)*tau(2^d-1), d=divisors(n)):
seq(a(n), n=1..100);  # Alois P. Heinz, May 31 2012

a[n_] := Sum[ MoebiusMu[n/d] * DivisorSigma[0, 2^d - 1], {d, Divisors[n]}]; Table[a[n], {n, 1, 71} ] (* Jean-François Alcover, Dec 12 2012 *)

a(n) = sumdiv(n, d, moebius(n/d) * numdiv(2^d-1)); \\ Amiram Eldar, Jan 25 2025

a(n) = Sum_{d|n} A008683(n/d) * A046801(d) = Sum_{d|A007947(n)} A008683(d) * A046801(n/d). - Max Alekseyev, May 03 2022

a(n) = 1 iff 2^n-1 is noncomposite. a(prime(n)) = 2^A088863(n)-1. - Thomas Ordowski, Jan 16 2014

More terms from John W. Layman, Mar 22 2002

More terms from Alois P. Heinz, May 31 2012

A003060 Smallest number with reciprocal of period length n in decimal (base 10).

Original entry on oeis.org

1, 3, 11, 27, 101, 41, 7, 239, 73, 81, 451, 21649, 707, 53, 2629, 31, 17, 2071723, 19, 1111111111111111111, 3541, 43, 23, 11111111111111111111111, 511, 21401, 583, 243, 29, 3191, 211, 2791, 353, 67, 103, 71, 1919, 2028119, 909090909090909091

Offset: 0

N. J. A. Sloane

For n > 0, a(n) is the least divisor d > 1 of 10^n - 1 such that the multiplicative order of 10 mod d is n. For prime n > 3, a(n) = A007138(n). - T. D. Noe, Aug 07 2007

For n > 1, a(n) is the smallest positive d such that d divides 10^n - 1 and does not divide any of 10^k - 1 for 0 < k < n. - Maciej Ireneusz Wilczynski, Sep 06 2012, corrected by M. F. Hasler, Jun 28 2022. (For n = 1, d = 1 divides 10^n - 1 and does not divide any 10^k - 1 with 0 < k < n, but a(1) = 3 > 1.)

J. Brillhart et al., Factorizations of b^n +- 1. Contemporary Mathematics, Vol. 22, Amer. Math. Soc., Providence, RI, 2nd edition, 1985; and later supplements.
"Cycle lengths of reciprocals", Popular Computing (Calabasas, CA), Vol. 1 (No. 4, Jul 1973), pp. 12-14.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Smallest primitive divisors of b^n-1: A212953 (b=2), A218356 (b=3), A218357 (b=5), A218358 (b=7), this sequence (b=10), A218359 (b=11), A218360 (b=13), A218361 (b=17), A218362 (b=19), A218363 (b=23), A218364 (b=29).

Cf. A007138, A057951, A005422, A176973.

a[n_] := First[ Select[ Divisors[10^n - 1], MultiplicativeOrder[10, #] == n &, 1]]; a[0] = 1; a[1] = 3; Table[a[n], {n, 0, 38}] (* Jean-François Alcover, Jul 13 2012, after T. D. Noe *)

apply( {A003060(n)=!fordiv(10^n-!!n, d, d>1 && znorder(Mod(10,d))==n && return(d))}, [0..50]) \\ M. F. Hasler, Jun 28 2022

Comment corrected by T. D. Noe, Apr 15 2010
More terms from T. D. Noe, Apr 15 2010
b-file truncated at uncertain term a(439) by Max Alekseyev, Apr 30 2022

A085021 Number of prime factors of cyclotomic(n,2), which is A019320(n), the value of the n-th cyclotomic polynomial evaluated at x=2.

Original entry on oeis.org

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

Offset: 1

T. D. Noe, Jun 19 2003

nonn

The Mobius transform of this sequence yields A046051, the number of prime factors of Mersenne number 2^n-1.

The number of prime factors in the primitive part of 2^n-1. - T. D. Noe, Jul 19 2008

			a(11) = 2 because cyclotomic(11,2) = 2047, which has two factors: 23 and 89.

Max Alekseyev, Table of n, a(n) for n = 1..1206 (first 500 term from T. D. Noe)
Vjekoslav Kovač and Florian Luca, On the number of divisors of Mersenne numbers, arXiv:2506.04883 [math.NT], 2025. See Table 2 p. 9.
H. Mishima, Factorization of Cyclotomic Numbers
Eric Weisstein's World of Mathematics, Cyclotomic Polynomial
Eric Weisstein's World of Mathematics, Möbius Transform

omega(Phi(n,x)): this sequence (x=2), A085028 (x=3), A085029 (x=4), A085030 (x=5), A085031 (x=6), A085032 (x=7), A085033 (x=8), A085034 (x=9), A085035 (x=10).

Cf. A005420, A019320, A046051, A046801, A059499, A064078, A112927, A212953.

Join[{0}, Table[Plus@@Transpose[FactorInteger[Cyclotomic[n, 2]]][[2]], {n, 2, 100}]]

a(n) = #factor(polcyclo(n, 2))~; \\ Michel Marcus, Mar 06 2015

A213224 Minimal order A(n,k) of degree-n irreducible polynomials over GF(prime(k)); square array A(n,k), n>=1, k>=1, read by antidiagonals.

Original entry on oeis.org

1, 1, 3, 1, 4, 7, 1, 3, 13, 5, 1, 4, 31, 5, 31, 1, 3, 9, 13, 11, 9, 1, 7, 7, 5, 11, 7, 127, 1, 3, 9, 16, 2801, 7, 1093, 17, 1, 4, 307, 5, 25, 36, 19531, 32, 73, 1, 3, 27, 5, 30941, 9, 29, 32, 757, 11, 1, 3, 7, 16, 88741, 63, 43, 64, 19, 44, 23

Offset: 1

Alois P. Heinz, Jun 06 2012

Maximal order of degree-n irreducible polynomials over GF(prime(k)) is prime(k)^n-1 and thus A(n,k) < prime(k)^n.

			A(4,1) = 5: The degree-4 irreducible polynomials p over GF(prime(1)) = GF(2) are 1+x+x^2+x^3+x^4, 1+x+x^4, 1+x^3+x^4. Their orders (i.e., the smallest integer e for which p divides x^e+1) are 5, 15, 15, and the minimal order is 5. (1+x+x^2+x^3+x^4) * (1+x) == x^5+1 (mod 2).
Square array A(n,k) begins:
    1,    1,     1,    1,   1,       1,        1,   1, ...
    3,    4,     3,    4,   3,       7,        3,   4, ...
    7,   13,    31,    9,   7,       9,      307,  27, ...
    5,    5,    13,    5,  16,       5,        5,  16, ...
   31,   11,    11, 2801,  25,   30941,    88741, 151, ...
    9,    7,     7,   36,   9,      63,        7,   7, ...
  127, 1093, 19531,   29,  43, 5229043, 25646167, 701, ...
   17,   32,    32,   64,  32,      32,      128,  17, ...

Alois P. Heinz, Antidiagonals n = 1..45, flattened
Eric Weisstein's World of Mathematics, Irreducible Polynomial
Eric Weisstein's World of Mathematics, Polynomial Order

Columns k=1-10 give: A212953, A218356, A218357, A218358, A218359, A218360, A218361, A218362, A218363, A218364.
Columns k=1-10 are first columns of: A059912, A212906, A212485, A212486, A218336, A218337, A218338, A218339, A218340, A218341.
Cf. A212737 (all orders).

with(numtheory):
M:= proc(n, i) option remember;
      divisors(ithprime(i)^n-1) minus U(n-1, i)
    end:
U:= proc(n, i) option remember;
      `if`(n=0, {}, M(n, i) union U(n-1, i))
    end:
A:= (n, k)-> min(M(n, k)[]):
seq(seq(A(n, d+1-n), n=1..d), d=1..14);

M[n_, i_] := M[n, i] = Divisors[Prime[i]^n - 1] ~Complement~ U[n-1, i]; U[n_, i_] := U[n, i] = If[n == 0, {}, M[n, i] ~Union~ U[n-1, i]]; A[n_, k_] := Min[M[n, k]]; Table[Table[A[n, d+1-n], {n, 1, d}], {d, 1, 14}] // Flatten (* Jean-François Alcover, Dec 13 2013, translated from Maple *)

A(n,k) = min(M(n,k)) with M(n,k) = {d : d|(prime(k)^n-1)} \ U(n-1,k) and U(n,k) = M(n,k) union U(n-1,k) for n>0, U(0,k) = {}.

A059912 Triangle T(n,k) of orders of n degree irreducible polynomials over GF(2) listed in ascending order, k=1..A059499(n).

Original entry on oeis.org

1, 3, 7, 5, 15, 31, 9, 21, 63, 127, 17, 51, 85, 255, 73, 511, 11, 33, 93, 341, 1023, 23, 89, 2047, 13, 35, 39, 45, 65, 91, 105, 117, 195, 273, 315, 455, 585, 819, 1365, 4095, 8191, 43, 129, 381, 5461, 16383, 151, 217, 1057, 4681, 32767, 257, 771, 1285, 3855

Offset: 1

Vladeta Jovovic, Feb 09 2001

A permutation of the odd positive numbers; namely, order each odd number d by the multiplicative order of 2 modulo d (in case of a tie, smaller d go first). - Jeppe Stig Nielsen, Feb 13 2020

			There are 18 (cf. A001037) irreducible polynomials of degree 7 over GF(2) which all have order 127.
Triangle T(n,k) begins:
    1;
    3;
    7;
    5,   15;
   31;
    9,   21,  63;
  127;
   17,   51,  85, 255;
   73,  511;
   11,   33,  93, 341, 1023;
  ...

Alois P. Heinz, Rows n = 1..71, flattened
Eric Weisstein's World of Mathematics, Irreducible Polynomial
XIAO Gang, Polynomial order: computes the order of an irreducible polynomial over a finite field GF(p), WIMS.

Cf. A058943, A059478, A059499, A001037, A059913.
Cf. A212906, A212485, A212486.
Column k=1 of A212737.
Column k=1 gives: A212953.
Last elements of rows give: A000225.
Cf. A108974.

with(numtheory):
M:= proc(n) option remember;
      divisors(2^n-1) minus U(n-1)
    end:
U:= proc(n) option remember;
      `if`(n=0, {}, M(n) union U(n-1))
    end:
T:= n-> sort([M(n)[]])[]:
seq(T(n), n=1..20);  # Alois P. Heinz, May 31 2012

m[n_] := m[n] = Complement[ Divisors[2^n - 1], u[n - 1]]; u[0] = {}; u[n_] := u[n] = Union[ m[n], u[n - 1]]; t[n_, k_] := m[n][[k]]; Flatten[ Table[t[n, k], {n, 1, 16}, {k, 1, Length[ m[n] ]}]] (* Jean-François Alcover, Jun 14 2012, after Alois P. Heinz *)

maxDegree=26;for(n=1,maxDegree,forstep(d=1,2^n,2,znorder(Mod(2,d))==n&&print1(d,", "))) \\ inefficient, Jeppe Stig Nielsen, Feb 13 2020

T(n,k) = k-th smallest element of M(n) = {d : d|(2^n-1)} \ U(n-1) with U(n) = M(n) union U(n-1) if n>0, U(0) = {}. - Alois P. Heinz, Jun 01 2012

cp's OEIS Frontend

A059499 a(n) = |{m : multiplicative order of 2 mod m = n}|.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A003060 Smallest number with reciprocal of period length n in decimal (base 10).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A085021 Number of prime factors of cyclotomic(n,2), which is A019320(n), the value of the n-th cyclotomic polynomial evaluated at x=2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A213224 Minimal order A(n,k) of degree-n irreducible polynomials over GF(prime(k)); square array A(n,k), n>=1, k>=1, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A059912 Triangle T(n,k) of orders of n degree irreducible polynomials over GF(2) listed in ascending order, k=1..A059499(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula