A059885 -id:A059885 - cp's OEIS frontend

A212906 Triangle T(n,k) of orders of degree-n irreducible polynomials over GF(3) listed in ascending order.

1, 2, 4, 8, 13, 26, 5, 10, 16, 20, 40, 80, 11, 22, 121, 242, 7, 14, 28, 52, 56, 91, 104, 182, 364, 728, 1093, 2186, 32, 41, 82, 160, 164, 205, 328, 410, 656, 820, 1312, 1640, 3280, 6560, 757, 1514, 9841, 19682, 44, 61, 88, 122, 244, 484, 488, 671, 968, 1342

Offset: 1

Boris Putievskiy, May 29 2012

The elements m of row n, are also solutions to the equation: multiplicative order of 3 mod m = n, with gcd(m,3) = 1, cf. A053446.

			Triangle T(n,k) begins:
1,   2;
4,   8;
13, 26;
5,  10,  16,  20, 40, 80;
11, 22, 121, 242;
7,  14,  28,  52, 56, 91, 104, 182, 364, 728;

R. Lidl and H. Niederreiter, Finite Fields, 2nd ed., Cambridge Univ. Press, 1997, Table C, pp. 555-557.
V. I. Arnol'd, Topology and statistics of formulas of arithmetics, Uspekhi Mat. Nauk, 58:4(352) (2003), 3-28

Alois P. Heinz, Rows n = 1..47, flattened (first 13 rows from Boris Putievskiy)
Eric Weisstein's World of Mathematics, Irreducible Polynomial
XIAO, Polynomial order (computes the order of an irreducible polynomial over a finite field GF(p))

Cf. A053446, A059912, A059885, A058944, A059499, A059886-A059892.
Column k=2 of A212737.
Column k=1 gives: A218356.

with(numtheory):
M:= proc(n) option remember;
      divisors(3^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..15);  # Alois P. Heinz, Jun 02 2012

M[n_] := M[n] = Divisors[3^n - 1] ~Complement~ U[n - 1];
U[n_] := U[n] = If[n == 0, {}, M[n] ~Union~ U[n - 1]];
T[n_] := Sort[M[n]]; Array[T, 15] // Flatten (* Jean-François Alcover, Jun 10 2018, after Alois P. Heinz *)

T(n,k) = k-th smallest element of M(n) with M(n) = {d : d | (3^n-1)} \ (M(1) U M(2) U ... U M(i-1)) for n>1, M(1) = {1,2}.

|M(n)| = Sum_{d|n} mu(n/d)*tau(3^d-1) = A059885(n).

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

Original entry on oeis.org

0, 1, 2, 2, 5, 2, 6, 4, 6, 3, 12, 2, 10, 6, 8, 4, 13, 2, 18, 6, 10, 4, 16, 4, 12, 9, 12, 4, 26, 2, 20, 6, 8, 12, 20, 4, 15, 6, 16, 4, 32, 2, 24, 10, 10, 6, 20, 4, 26, 9, 18, 4, 26, 6, 32, 12, 12, 4, 28, 2, 20, 10, 12, 18, 25, 4, 24, 6, 26, 4, 52, 2, 18, 10, 12, 18, 26, 4, 40, 8, 14, 5, 28

Offset: 1

Vladeta Jovovic, Feb 08 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).

			a(2) = |{3}| = 1, a(3) = |{4,8}| = 2, a(4) = |{5,15}| = 2, a(5) = |{3,6,8,12,24}| = 5, a(6) = |{7,35}| = 2, a(7) = |{4,8,12,16,24,48}| = 6,...

Alois P. Heinz, Table of n, a(n) for n = 1..10000

Cf. A002329, A059908-A059911, A059499, A059885-A059892, A002326, A053446-A053452, A055205, A048691, A048785, A347191.

Row n=2 of A212957. - Alois P. Heinz, Oct 24 2012

with(numtheory):f := n->tau(n^2-1)-tau(n-1):for n from 1 to 100 do printf(`%d,`,f(n)) od:

a[n_] := Subtract @@ DivisorSigma[0, {n^2-1, n-1}]; a[1] = 0; Array[a, 100] (* Amiram Eldar, Jan 25 2025 *)

a(n) = if(n == 1, 0, numdiv(n^2-1) - numdiv(n-1)); \\ Amiram Eldar, Jan 25 2025

a(n) = tau(n^2-1)-tau(n-1), where tau(n) = number of divisors of n A000005. Generally, if b(n, r) = |{m : multiplicative order of n mod m = r}| then b(n, r) = Sum_{d|r} mu(d)*tau(n^(r/d)-1), where mu(n) = Moebius function A008683.

A212486 Triangle T(n,k) of orders of degree-n irreducible polynomials over GF(7) listed in ascending order.

Original entry on oeis.org

1, 2, 3, 6, 4, 8, 12, 16, 24, 48, 9, 18, 19, 38, 57, 114, 171, 342, 5, 10, 15, 20, 25, 30, 32, 40, 50, 60, 75, 80, 96, 100, 120, 150, 160, 200, 240, 300, 400, 480, 600, 800, 1200, 2400, 2801, 5602, 8403, 16806, 36, 43, 72, 76, 86, 129, 144, 152, 172, 228, 258

Offset: 1

Boris Putievskiy, Jun 02 2012

The elements m of row n, are also solutions to the equation: multiplicative order of 7 mod m = n, with gcd(m,7) = 1, cf. A053450.

			Triangle T(n,k) begins:
  1,  2,  3,  6;
  4,  8, 12, 16, 24,  48;
  9, 18, 19, 38, 57, 114, 171, 342;
  5, 10, 15, 20, 25,  30,  32,  40, 50, 60, 75, 80, 96, 100, 120, 150, 160, 200, 240, 300, 400, 480, 600, 800, 1200, 2400;
  ...

R. Lidl and H. Niederreiter, Finite Fields, 2nd ed., Cambridge Univ. Press, 1997, Table C, pp. 560-562.
V. I. Arnol'd, Topology and statistics of formulas of arithmetics, Uspekhi Mat. Nauk, 58:4(352) (2003), 3-28

Boris Putievskiy, Table of n, a(n) for n = 1..102
Eric Weisstein's World of Mathematics, Irreducible Polynomial
Gang Xiao, (computes the order of an irreducible polynomial over a finite field GF(p))

Cf. A053446, A059912, A059885, A058944, A059499, A059886-A059892.
Column k=4 of A212737.
Column k=1 gives: A218358.

with(numtheory):
M:= proc(n) option remember;
      `if`(n=1, {1, 2, 3, 6}, divisors(7^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..7);

M[n_] := M[n] = If[n == 1, {1, 2, 3, 6}, Divisors[7^n - 1] ~Complement~ U[n - 1]];
U[n_] := U[n] = If[n == 0, {}, M[n] ~Union~ U[n - 1]];
T[n_] := Sort[M[n]];
Table[T[n], {n, 1, 7}] // Flatten (* Jean-François Alcover, Sep 24 2022, from Maple code *)

T(n,k) = k-th smallest element of M(n) with M(n) = {d : d | (7^n-1)} \ (M(1) U M(2) U ... U M(i-1)) for n>1, M(1) = {1,2,3,6}.

|M(n)| = Sum_{d|n} mu(n/d)*tau(7^d-1) = A059889(n).

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

Original entry on oeis.org

0, 3, 10, 16, 37, 10, 42, 24, 58, 53, 164, 26, 68, 38, 32, 68, 169, 22, 222, 38, 42, 50, 328, 40, 180, 219, 108, 26, 334, 82, 460, 82, 92, 72, 220, 108, 449, 86, 128, 80, 192, 22, 336, 110, 222, 218, 540, 84, 778, 129, 150, 80, 270, 54, 328, 356, 132, 68, 348, 22

Offset: 1

Vladeta Jovovic, Feb 08 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).

			a(2) = |{9,21,63}| = 3, a(3) = |{7,14,28,52,56,91,104,182,364,728}| = 10, a(4) = |{13,35,39,45,65,91,105,117,195,273,315,455,585,819,1365,4095}| = 16,...

Cf. A059907-A059910, A059499, A059885-A059892, A002326, A053446-A053452, A002329, A055205, A048691, A048785.

a[n_] := Total[{1, -1, -1, 1} * DivisorSigma[0, n^{6, 3, 2, 1} - 1]]; a[1] = 0; Array[a, 100] (* Amiram Eldar, Jan 25 2025*)

a(n) = if(n == 1, 0, numdiv(n^6-1) - numdiv(n^3-1) - numdiv(n^2-1) + numdiv(n-1)); \\ Amiram Eldar, Jan 25 2025

a(n) = tau(n^6-1)-tau(n^3-1)-tau(n^2-1)+tau(n-1), where tau(n) = number of divisors of n A000005. Generally, if b(n, r) = |{m : multiplicative order of n mod m = r}| then b(n, r) = Sum_{d|r} mu(d)*tau(n^(r/d)-1), where mu(n) = Moebius function A008683.

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

Original entry on oeis.org

0, 1, 2, 4, 3, 2, 8, 2, 12, 5, 12, 2, 12, 2, 4, 20, 5, 6, 10, 2, 6, 14, 12, 2, 40, 9, 4, 6, 18, 10, 16, 6, 6, 8, 12, 12, 39, 2, 12, 8, 8, 6, 16, 6, 18, 26, 12, 6, 50, 3, 18, 8, 18, 2, 32, 12, 8, 20, 4, 6, 60, 2, 12, 26, 21, 4, 64, 10, 6, 8, 8, 6, 20, 14, 4, 12, 6, 4, 64, 2, 70, 7, 12, 6, 24

Offset: 1

Vladeta Jovovic, Feb 08 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).

			a(2) = |{7}| = 1, a(3) = |{13,26}| = 2, a(4) = |{7,9,21,63}| = 4, a(5) = |{31,62,124}| = 3, a(6) = |{43,215}| = 2, a(7) = |{9,18,19,38,57,114,171,342}| = 8,...

Alois P. Heinz, Table of n, a(n) for n = 1..10000

Cf. A059907, A059909-A059911, A059499, A059885-A059892, A002326, A053446-A053452, A002329, A055205, A048691, A048785.

Row n=3 of A212957. - Alois P. Heinz, Oct 24 2012

Table[DivisorSigma[0,n^3-1]-DivisorSigma[0,n-1],{n,90}] (* Harvey P. Dale, Feb 03 2015 *)

a(n) = if(n == 1, 0, numdiv(n^3-1) - numdiv(n-1)); \\ Amiram Eldar, Jan 25 2025

a(n) = tau(n^3-1)-tau(n-1), where tau(n) = number of divisors of n A000005. Generally, if b(n, r) = |{m : multiplicative order of n mod m = r}| then b(n, r) = Sum_{d|r} mu(d)*tau(n^(r/d)-1), where mu(n) = Moebius function A008683.

A002591 Largest prime factor of 3^(2n+1) - 1.

Original entry on oeis.org

2, 13, 11, 1093, 757, 3851, 797161, 4561, 34511, 363889, 368089, 1001523179, 391151, 8209, 20381027, 4404047, 2413941289, 2664097031, 17189128703, 797161, 86950696619, 380808546861411923, 927001, 96656723, 131713, 99810171997

Offset: 0

N. J. A. Sloane

nonn

J. Brillhart et al., Factorizations of b^n +- 1. Contemporary Mathematics, Vol. 22, Amer. Math. Soc., Providence, RI, 2nd edition, 1985; and later supplements.
M. Kraitchik, Recherches sur la Théorie des Nombres. Gauthiers-Villars, Paris, Vol. 1, 1924, Vol. 2, 1929, see Vol. 2, p. 28.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Table of n, a(n) for n = 0..344
J. Brillhart et al., Factorizations of b^n +- 1, Contemporary Mathematics, Vol. 22, Amer. Math. Soc., Providence, RI, 3rd edition, 2002.
S. S. Wagstaff, Jr., The Cunningham Project

Together with A274909 forms bisection of A074477.Cf. A057958, A059885, A085028, A133801, A235366.

Table[FactorInteger[3^(2n-1)-1][[-1,1]],{n,30}] (* Harvey P. Dale, Oct 19 2022 *)

a(n) = A074477(2n+1). - Max Alekseyev, May 22 2022

Corrected and extended by Jud McCranie, Jan 03 2001
Terms up to a(307) in b-file from Sean A. Irvine, Apr 20 2014
a(0) prepended and a(308)-a(344) added to b-file by Max Alekseyev, Apr 24 2019, Sep 10 2020, Aug 26 2021, May 22 2022

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

Original entry on oeis.org

0, 2, 6, 4, 12, 4, 26, 18, 14, 6, 24, 12, 64, 8, 16, 8, 66, 20, 36, 8, 64, 24, 76, 6, 28, 12, 64, 24, 48, 12, 100, 40, 50, 48, 36, 8, 96, 40, 28, 8, 104, 12, 208, 36, 24, 36, 200, 18, 48, 36, 36, 24, 128, 8, 152, 16, 172, 24, 48, 12, 48, 36, 56, 72, 40, 8, 128, 56, 48, 40

Offset: 1

Vladeta Jovovic, Feb 08 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).

			a(2) = |{5, 15}| = 2, a(3) = |{5, 10, 16, 20, 40, 80}| = 6, a(4) = |{17, 51, 85, 255}| = 4, a(5) = |{13, 16, 26, 39, 48, 52, 78, 104, 156, 208, 312, 624}| = 12, ...

Cf. A059907, A059908, A059910-A059911, A059499, A059885-A059892, A002326, A053446-A053452, A002329, A055205, A048691, A048785.

Table[DivisorSigma[0,n^4-1]-DivisorSigma[0,n^2-1],{n,70}] (* Harvey P. Dale, Nov 30 2011 *)

a(n) = if(n == 1, 0, numdiv(n^4-1) - numdiv(n^2-1)); \\ Amiram Eldar, Jan 25 2025

a(n) = tau(n^4-1)-tau(n^2-1), where tau(n) = number of divisors of n A000005. More generally, if b(n, r) = |{m : multiplicative order of n mod m = r}| then b(n, r) = Sum_{d|r} mu(d)*tau(n^(r/d)-1), where mu(n) = Moebius function A008683.

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

Original entry on oeis.org

0, 1, 4, 6, 9, 4, 4, 6, 20, 9, 8, 2, 6, 6, 12, 44, 5, 6, 18, 14, 12, 4, 4, 2, 56, 13, 20, 4, 6, 2, 40, 6, 18, 12, 12, 44, 63, 6, 28, 4, 16, 14, 8, 2, 18, 12, 28, 14, 70, 3, 42, 12, 42, 6, 24, 8, 56, 44, 60, 6, 60, 2, 4, 90, 21, 20, 24, 2, 18, 60, 88, 6, 12, 2, 28, 26, 6, 28, 8, 14, 170

Offset: 1

Vladeta Jovovic, Feb 08 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).

Cf. A059907-A059909, A059911, A059499, A059885-A059892, A002326, A053446-A053452, A002329, A055205, A048691, A048785.

a[n_] := Subtract @@ DivisorSigma[0, {n^5-1, n-1}]; a[1] = 0; Array[a, 100] (* Amiram Eldar, Jan 25 2025 *)

a(n) = if(n == 1, 0, numdiv(n^5-1) - numdiv(n-1)); \\ Amiram Eldar, Jan 25 2025

a(n) = tau(n^5-1)-tau(n-1), where tau(n) = number of divisors of n A000005. Generally, if b(n, r) = |{m : multiplicative order of n mod m = r}| then b(n, r) = Sum_{d|r} mu(d)*tau(n^(r/d)-1), where mu(n) = Moebius function A008683.

cp's OEIS Frontend

A212906 Triangle T(n,k) of orders of degree-n irreducible polynomials over GF(3) listed in ascending order.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A212486 Triangle T(n,k) of orders of degree-n irreducible polynomials over GF(7) listed in ascending order.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A002591 Largest prime factor of 3^(2n+1) - 1.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples