A059499 -id:A059499 - cp's OEIS frontend

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

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

A059913 Triangle T(n,k) of numbers of n degree irreducible polynomials over GF(2) which have order A059912(n,k), k=1..A059499(n).

Original entry on oeis.org

2, 1, 2, 1, 2, 6, 1, 2, 6, 18, 2, 4, 8, 16, 8, 48, 1, 2, 6, 30, 60, 2, 8, 176, 1, 2, 2, 2, 4, 6, 4, 6, 8, 12, 12, 24, 24, 36, 48, 144, 630, 3, 6, 18, 378, 756, 10, 12, 60, 300, 1800, 16, 32, 64, 128, 256, 512, 1024, 2048, 7710, 1, 1, 2, 6, 6, 6, 8, 12, 18, 24

Offset: 1

Vladeta Jovovic, Feb 09 2001

Row sums give A001037.

			There are 9 (cf. A001037) irreducible polynomials of degree 6 over GF(2): 1 of order 9, 2 of order 21 and 6 of order 63 (cf. A059912).
Triangle T(n,k) begins:
  2;
  1;
  2;
  1,  2;
  6;
  1,  2,   6;
  18;
  2,  4,   8, 16;
  8, 48;
  1,  2,   6, 30, 60;
  2,  8, 176;
  ...

Alois P. Heinz, Rows n = 1..71, flattened

Cf. A058943, A059478, A059499, A001037, A059912, A000010.

Prepend[Table[Map[EulerPhi[#]/n &, Complement[Divisors[2^n - 1],Union[Flatten[Table[Divisors[2^k - 1], {k, 1, n - 1}]]]]], {n, 2,20}], {2}] // Grid (* Geoffrey Critzer, Dec 02 2019 *)

T(n,k) = phi(A059912(n,k))/n, where phi = Euler totient function A000010.

A059892 a(n) = |{m : multiplicative order of 10 mod m is equal to n}|.

Original entry on oeis.org

3, 3, 5, 6, 9, 53, 9, 36, 12, 33, 9, 186, 21, 33, 111, 144, 9, 564, 3, 330, 239, 273, 3, 1756, 84, 165, 76, 714, 93, 16167, 21, 5952, 111, 177, 363, 4288, 21, 15, 99, 5724, 45, 48807, 45, 4314, 1140, 183, 9, 14192, 36, 2940, 495, 1338, 45, 11572, 747, 11484

Offset: 1

Vladeta Jovovic, Feb 06 2001

The multiplicative order of a mod m, gcd(a,m)=1, is the smallest natural number d for which a^d = 1 (mod m).
The number of unit fractions 1/k having a decimal expansion of period n and with k coprime to 10. - T. D. Noe, May 18 2007
Also, number of primitive factors of 10^n - 1 (cf. A003060). - Max Alekseyev, May 03 2022
a(n) is odd if and only if n is squarefree. Proof: Note that 10^d - 1 == 3 (mod 4) for d >= 2, so 10^d - 1 is a square if and only if d = 1. From the formula we can see that a(n) is odd if and only if mu(n) is nonzero, or n is squarefree. - Jianing Song, Jun 15 2021

Table of n, a(n) for n = 1..352

Number of primitive factors of b^n - 1: A059499 (b=2), A059885(b=3), A059886 (b=4), A059887 (b=5), A059888 (b=6), A059889 (b=7), A059890 (b=8), A059891 (b=9), this sequence (b=10).
Cf. A000005, A008683, A002329, A007138, A005422, A057951, A058946, A070528.
Column k=10 of A212957.

with(numtheory):
a:= n-> add(mobius(n/d)*tau(10^d-1), d=divisors(n)):
seq(a(n), n=1..30);  # Alois P. Heinz, Oct 12 2012

f[n_, d_] := MoebiusMu[n/d]*Length[Divisors[10^d - 1]]; a[n_] := Total[(f[n, #] & ) /@ Divisors[n]]; Table[a[n], {n, 1, 56}] (* Jean-François Alcover, Mar 21 2011 *)

j=[]; for(n=1,10,j=concat(j,sumdiv(n,d,moebius(n/d)*numdiv(10^d-1)))); j

from sympy import divisors, mobius, divisor_count
def a(n): return sum(mobius(n//d)*divisor_count(10**d - 1) for d in divisors(n)) # Indranil Ghosh, Apr 23 2017

a(n) = Sum_{d|n} mu(n/d)*tau(10^d-1), (mu(n) = Moebius function A008683, tau(n) = number of divisors of n A000005).

More terms from Jason Earls, Aug 06 2001.
Terms to a(280) in b-file from T. D. Noe, Oct 01 2013
a(281)-a(322) in b-file from Ray Chandler, May 03 2017
a(323)-a(352) in b-file from Max Alekseyev, May 03 2022

A212957 A(n,k) is the number of moduli m such that the multiplicative order of k mod m equals n; square array A(n,k), n>=1, k>=1, read by antidiagonals.

Original entry on oeis.org

0, 1, 0, 2, 1, 0, 2, 2, 1, 0, 3, 2, 2, 2, 0, 2, 5, 4, 6, 1, 0, 4, 2, 3, 4, 4, 3, 0, 2, 6, 2, 12, 6, 10, 1, 0, 4, 4, 8, 4, 9, 16, 2, 4, 0, 3, 6, 2, 26, 4, 37, 6, 14, 2, 0, 4, 3, 12, 18, 4, 10, 3, 8, 4, 5, 0, 2, 12, 5, 14, 6, 42, 2, 28, 26, 16, 3, 0

Offset: 1

Alois P. Heinz, Jun 01 2012

			A(4,3) = 6: 3^4 = 81 == 1 (mod m) for m in {5,10,16,20,40,80}.
Square array A(n,k) begins:
  0,  1,  2,  2,  3,  2,  4,  2, ...
  0,  1,  2,  2,  5,  2,  6,  4, ...
  0,  1,  2,  4,  3,  2,  8,  2, ...
  0,  2,  6,  4, 12,  4, 26, 18, ...
  0,  1,  4,  6,  9,  4,  4,  6, ...
  0,  3, 10, 16, 37, 10, 42, 24, ...
  0,  1,  2,  6,  3,  2, 12, 10, ...
  0,  4, 14,  8, 28,  8, 48, 72, ...

Alois P. Heinz, Antidiagonals n = 1..60
Wikipedia, Multiplicative order.

Columns k=1-10 give: A000004, A059499, A059885, A059886, A059887, A059888, A059889, A059890, A059891, A059892.
Rows n=1-10 give: A000005, A059907, A059908, A059909, A059910, A059911, A218256, A218257, A218258, A218259.
Main diagonal gives A252760.
Cf. A000005, A008683.

with(numtheory):
A:= (n, k)-> add(mobius(n/d)*tau(k^d-1), d=divisors(n)):
seq(seq(A(n, 1+d-n), n=1..d), d=1..15);

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

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

A(n,k) = |{m : multiplicative order of k mod m = n}|.

A(n,k) = Sum_{d|n} mu(n/d)*tau(k^d-1), mu = A008683, tau = A000005.

A059885 a(n) = |{m : multiplicative order of 3 mod m = n}|.

Original entry on oeis.org

2, 2, 2, 6, 4, 10, 2, 14, 4, 16, 6, 58, 2, 10, 16, 88, 6, 108, 6, 150, 10, 54, 6, 290, 18, 10, 56, 138, 14, 716, 14, 144, 22, 118, 40, 1088, 6, 54, 90, 670, 14, 730, 6, 570, 356, 22, 30, 13864, 124, 342, 54, 138, 14, 3912, 116, 1362, 118, 238, 6, 22058, 6, 110

Offset: 1

Vladeta Jovovic, Feb 06 2001

nonn

The multiplicative order of a mod m, GCD(a,m)=1, is the smallest natural number d for which a^d = 1 (mod m). a(n) = number of orders of degree-n monic irreducible polynomials over GF(3).

Also, number of primitive factors of 3^n - 1 (cf. A218356). - Max Alekseyev, May 03 2022

			a(2) = |{4,8}| = 2, a(4) = |{5,10,16,20,40,80}| = 6, a(6) = |{7,14,28,52,56,91,104,182,364,728}| = 10.

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

Primitive factors of b^n - 1: A059499 (b=2), this sequence (b=3), A059886 (b=4), A059887 (b=5), A059888 (b=6), A059889 (b=7), A059890 (b=8), A059891 (b=9), A059892 (b=10).
Cf. A000005, A008683, A027376, A057958, A058944, A074477, A143663, A212906, A218356.
Column k=3 of A212957.

with(numtheory); A059885 := proc(n) local d,s; s := 0; for d in divisors(n) do s := s+mobius(n/d)*tau(3^d-1); od; RETURN(s); end;

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

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

a(n) = Sum_{ d divides n } mu(n/d)*tau(3^d-1), (mu(n) = Moebius function A008683, tau(n) = number of divisors of n A000005).

A059887 a(n) = |{m : multiplicative order of 5 mod m=n}|.

Original entry on oeis.org

3, 5, 3, 12, 9, 37, 3, 28, 18, 47, 3, 180, 3, 53, 81, 176, 9, 446, 21, 564, 39, 117, 9, 884, 180, 53, 360, 244, 21, 5959, 9, 800, 39, 111, 369, 9536, 21, 483, 39, 5476, 9, 18289, 9, 1140, 2958, 111, 3, 9424, 6, 3852, 177, 884, 21, 81048, 561, 1188, 69, 227, 9

Offset: 1

Vladeta Jovovic, Feb 06 2001

nonn

The multiplicative order of a mod m, gcd(a,m)=1, is the smallest natural number d for which a^d = 1 (mod m). a(n) = number of orders of degree-n monic irreducible polynomials over GF(5).

Also, number of primitive factors of 5^n - 1 (cf. A218357). - Max Alekseyev, May 03 2022

Max Alekseyev, Table of n, a(n) for n = 1..502

Number of primitive factors of b^n - 1: A059499 (b=2), A059885(b=3), A059886 (b=4), this sequence (b=5), A059888 (b=6), A059889 (b=7), A059890 (b=8), A059891 (b=9), A059892 (b=10).
Cf. A000005, A008683, A001692, A053447, A057956, A058945, A074479, A143665, A212485, A218357
Column k=5 of A212957.

with(numtheory):
a:= n-> add(mobius(n/d)*tau(5^d-1), d=divisors(n)):
seq(a(n), n=1..50);  # Alois P. Heinz, Oct 12 2012

a[n_] := Sum[MoebiusMu[n/d]*DivisorSigma[0, 5^d-1], {d, Divisors[n]}];
Table[a[n], {n, 1, 60}] (* Jean-François Alcover, Dec 13 2024, after Alois P. Heinz *)

a(n) = sumdiv(n, d, moebius(n/d)*numdiv(5^d-1)); \\ Michel Marcus, Dec 13 2024

a(n) = Sum_{d|n} mu(n/d)*tau(5^d-1), (mu(n) = Moebius function A008683, tau(n) = number of divisors of n A000005).

A059889 a(n) = |{m : multiplicative order of 7 mod m=n}|.

Original entry on oeis.org

4, 6, 8, 26, 4, 42, 12, 48, 52, 66, 12, 778, 4, 138, 80, 300, 12, 528, 12, 1430, 72, 138, 28, 15216, 24, 66, 1216, 966, 28, 3630, 28, 1344, 360, 58, 108, 16988, 28, 138, 176, 12752, 28, 7398, 12, 4422, 1900, 122, 12, 131028, 240, 536, 744, 1046, 28, 23744, 44

Offset: 1

Vladeta Jovovic, Feb 06 2001

nonn

The multiplicative order of a mod m, gcd(a,m)=1, is the smallest natural number d for which a^d = 1 (mod m).
a(n) = number of orders of degree n monic irreducible polynomials over GF(7).
Also, number of primitive factors of 7^n - 1 (cf. A218358). - Max Alekseyev, May 03 2022

Max Alekseyev, Table of n, a(n) for n = 1..388

Number of primitive factors of b^n - 1: A059499 (b=2), A059885(b=3), A059886 (b=4), A059887 (b=5), A059888 (b=6), this sequence (b=7), A059890 (b=8), A059891 (b=9), A059892 (b=10).
Cf. A000005, A008683, A058946, A053450, A057954, A058946, A074249, A212486, A218358
Column k=7 of A212957.

with(numtheory):
a:= n-> add(mobius(n/d)*tau(7^d-1), d=divisors(n)):
seq(a(n), n=1..40);  # Alois P. Heinz, Oct 12 2012

a[n_] := DivisorSum[n, MoebiusMu[n/#] * DivisorSigma[0, 7^#-1] &]; Array[a, 60] (* Amiram Eldar, Jan 25 2025 *)

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

a(n) = Sum_{d|n} mu(n/d)*tau(7^d-1), (mu(n) = Moebius function A008683, tau(n) = number of divisors of n A000005).

A059886 a(n) = |{m : multiplicative order of 4 mod m=n}|.

Original entry on oeis.org

2, 2, 4, 4, 6, 16, 6, 8, 26, 38, 14, 68, 6, 54, 84, 16, 6, 462, 6, 140, 132, 110, 14, 664, 120, 118, 128, 188, 62, 4456, 6, 96, 364, 118, 498, 7608, 30, 118, 180, 568, 30, 9000, 30, 892, 3974, 494, 62, 5360, 24, 8024, 1524, 892, 62, 9600, 3050, 1784, 372, 446

Offset: 1

Vladeta Jovovic, Feb 06 2001

nonn

The multiplicative order of a mod m, GCD(a,m)=1, is the smallest natural number d for which a^d = 1 (mod m).
a(n) is the number of orders of degree-n monic irreducible polynomials over GF(4).
Also, number of primitive factors of 4^n - 1. - Max Alekseyev, May 03 2022

			a(1) = |{1,3}| = 2, a(2) = |{5,15}| =2, a(3) = |{7,9,21,63}| =4, a(4) = |{17,51,85,255}| = 4.

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

Number of primitive factors of b^n - 1: A059499 (b=2), A059885(b=3), this sequence (b=4), A059887 (b=5), A059888 (b=6), A059889 (b=7), A059890 (b=8), A059891 (b=9), A059892 (b=10).
Cf. A000005, A008683, A027377, A053447, A057957, A058948, A112092, A274906.
Column k=4 of A212957.

with(numtheory):
a:= n-> add(mobius(n/d)*tau(4^d-1), d=divisors(n)):
seq(a(n), n=1..60);  # Alois P. Heinz, Oct 12 2012

a[n_] := DivisorSum[n, MoebiusMu[n/#]*DivisorSigma[0, 4^# - 1]&]; Array[a, 100] (* Jean-François Alcover, Nov 11 2015 *)

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

a(n) = Sum_{ d divides n } mu(n/d)*tau(4^d-1), (mu(n) = Moebius function A008683, tau(n) = number of divisors of n A000005).

A059888 a(n) = |{m : multiplicative order of 6 mod m=n}|.

Original entry on oeis.org

2, 2, 2, 4, 4, 10, 2, 8, 12, 40, 6, 108, 6, 42, 40, 48, 30, 100, 6, 332, 10, 22, 30, 376, 26, 118, 48, 332, 2, 1436, 6, 448, 54, 222, 88, 7952, 62, 54, 54, 2680, 6, 698, 30, 476, 1476, 222, 14, 7632, 28, 438, 478, 1916, 14, 1872, 84, 11896, 118, 58, 14, 784452

Offset: 1

Vladeta Jovovic, Feb 06 2001

nonn

The multiplicative order of a mod m, GCD(a,m)=1, is the smallest natural number d for which a^d = 1 (mod m).

Also, number of primitive factors of 6^n - 1. - Max Alekseyev, May 03 2022

Max Alekseyev, Table of n, a(n) for n = 1..430

Number of primitive factors of b^n - 1: A059499 (b=2), A059885(b=3), A059886 (b=4), A059887 (b=5), this sequence (b=6), A059889 (b=7), A059890 (b=8), A059891 (b=9), A059892 (b=10).
Column k=6 of A212957.
Cf. A000005, A008683, A053449, A057955, A274907.

with(numtheory):
a:= n-> add(mobius(n/d)*tau(6^d-1), d=divisors(n)):
seq(a(n), n=1..50);  # Alois P. Heinz, Oct 12 2012

a[n_] := DivisorSum[n, MoebiusMu[n/#] * DivisorSigma[0, 6^#-1] &]; Array[a, 60] (* Amiram Eldar, Jan 25 2025 *)

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

a(n) = Sum_{ d divides n } mu(n/d)*tau(6^d-1), (mu(n) = Moebius function A008683, tau(n) = number of divisors of n A000005).

A059890 a(n) = |{m : multiplicative order of 8 mod m = n}|.

Original entry on oeis.org

2, 4, 2, 18, 6, 24, 10, 72, 4, 84, 14, 462, 14, 128, 54, 672, 30, 124, 14, 4494, 82, 364, 14, 7608, 120, 172, 56, 9054, 62, 3920, 6, 5376, 238, 1500, 1518, 9600, 62, 364, 494, 69048, 30, 5892, 30, 24174, 956, 364, 62, 253280, 52, 12072, 222, 147246, 254, 12072

Offset: 1

Vladeta Jovovic, Feb 06 2001

nonn

The multiplicative order of a mod m, gcd(a,m)=1, is the smallest natural number d for which a^d = 1 (mod m). a(n) = number of orders of degree-n monic irreducible polynomials over GF(8).

Also, number of primitive factors of 8^n - 1. - Max Alekseyev, May 03 2022

Max Alekseyev, Table of n, a(n) for n = 1..500

Number of primitive factors of b^n - 1: A059499 (b=2), A059885(b=3), A059886 (b=4), A059887 (b=5), A059888 (b=6), A059889 (b=7), this sequence (b=8), A059891 (b=9), A059892 (b=10).
Cf. A000005, A008683, A027380, A053451, A057953, A058946, A274908.
Column k=8 of A212957.

with(numtheory):
a:= n-> add(mobius(n/d)*tau(8^d-1), d=divisors(n)):
seq(a(n), n=1..40);  # Alois P. Heinz, Oct 12 2012

a[n_] := Sum[MoebiusMu[n/d]*DivisorSigma[0, 8^d-1], {d, Divisors[n]}];
Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Jan 13 2025, after Alois P. Heinz *)

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

a(n) = Sum_{ d divides n } mu(n/d)*tau(8^d-1), (mu(n) = Moebius function A008683, tau(n) = number of divisors of n A000005).

cp's OEIS Frontend

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

A059913 Triangle T(n,k) of numbers of n degree irreducible polynomials over GF(2) which have order A059912(n,k), k=1..A059499(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A059892 a(n) = |{m : multiplicative order of 10 mod m is equal to n}|.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A212957 A(n,k) is the number of moduli m such that the multiplicative order of k mod m equals n; square array A(n,k), n>=1, k>=1, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A059885 a(n) = |{m : multiplicative order of 3 mod m = n}|.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A059887 a(n) = |{m : multiplicative order of 5 mod m=n}|.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A059889 a(n) = |{m : multiplicative order of 7 mod m=n}|.

Views

Author

Keywords