A002326 -id:A002326 - cp's OEIS frontend

A081844 Number of irreducible factors of x^(2n+1) - 1 over GF(2).

1, 2, 2, 3, 3, 2, 2, 5, 3, 2, 6, 3, 3, 4, 2, 7, 5, 6, 2, 5, 3, 4, 8, 3, 5, 8, 2, 5, 5, 2, 2, 13, 7, 2, 6, 3, 9, 8, 6, 3, 5, 2, 12, 5, 9, 10, 14, 5, 3, 8, 2, 3, 15, 2, 4, 5, 5, 6, 12, 9, 3, 8, 4, 19, 11, 2, 10, 11, 3, 2, 6, 5, 7, 10, 2, 11, 13, 14, 4, 5, 9, 2, 14, 3, 3, 12, 2, 9, 5, 2, 2, 5, 7, 8, 20, 3, 3, 20

Offset: 0

N. J. A. Sloane, Apr 11 2003

nonn

Also number of nonisomorphic "pure" chain rings with certain parameters.

Number of cycles under doubling map x -> 2*x (mod 2*n+1). - Joerg Arndt, Jan 22 2024

R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, 1983; Theorem 2.47 page 65.

T. D. Noe, Table of n, a(n) for n = 0..10000
Jean-Paul Allouche, Manon Stipulanti, and Jia-Yan Yao, Doubling modulo odd integers, generalizations, and unexpected occurrences, arXiv:2504.17564 [math.NT], 2025.
G. Chassé, Combinatorial cycles of a polynomial map over a commutative field, Discrete Math. 61 (1986), 21-26.
E. W. Clark and J. J. Liang, Enumeration of finite commutative chain rings, J. Algebra 27 (1973), 445-453.
Pieter Moree, Number of irreducible factors of x^n-1 over a finite field, Posting to Number Theory List, Apr 11, 2003.
T. D. Rogers, The graph of the square mapping on the prime fields, Discrete Math. 148 (1996), 317-324
D. Ulmer, Elliptic curves with large rank over function fields, Ann. of Math. 155 (2002), 295-315
D. Ulmer, Elliptic curves with large rank over function fields, arXiv:math/0109163 [math.NT].
Troy Vasiga and Jeffrey Shallit, On the iteration of certain quadratic maps over GF(p), Discrete Mathematics, Volume 277, Issues 1-3, 2004, pages 219-240.

Cf. A001037.
A000374 gives number of factors of x^n-1 for any n.
Cf. A037226 (number of primitive irreducible factors of x^(2n+1) - 1 over integers mod 2).
Cf. A006694 (number of factors of (x^(2*n+1) - 1) / (x - 1) over GF(2) ).

with(numtheory); o := n->if n=1 then 1 else order(2,n); fi; A081844 := proc(n) local d, t1; t1 := 0; for d to n do if n mod d = 0 then t1 := t1 + phi(d)/o(d); end if; end do; t1; end proc;
Factor(x^(2*n+1)-1) mod 2; nops(%);

a[n_] := Length[Factor[x^(2n+1)-1, Modulus->2] ]; a[0]=1; (* or : *)
a[n_] := Sum[ EulerPhi[d] / MultiplicativeOrder[2, d ], {d, Divisors[2n + 1]}]; Table[ a[n], {n, 0, 97}] (* Jean-François Alcover, Dec 14 2011 *)

a(n)=sumdiv(2*n+1,d,eulerphi(d)/znorder(Mod(2,d)));
vector(122,n,a(n-1)) /* Joerg Arndt, Jan 18 2011 */

from sympy import totient, n_order, divisors
def A081844(n): return sum(totient(d)//n_order(2,d) for d in divisors((n+1<<1)-1,generator=True) if d>1) + 1 # Chai Wah Wu, Apr 09 2024

a(n) = Sum_{ d| 2*n+1 } phi(d)/ord_2(d), where phi = A000010, ord_2 = A002326.
a(n) = A006694(n) + 1. - Joerg Arndt, Apr 01 2019
a(n) = A000374(2*n+1). - Joerg Arndt, Jan 22 2024

A293218 a(n) = A007913(A292270(n)).

Original entry on oeis.org

1, 1, 1, 1, 13, 1, 1, 1, 38, 1, 3, 26, 31, 1, 1, 1, 103, 73, 1, 42, 14, 7, 91, 3, 58, 14, 1, 170, 303, 1, 1, 1, 66, 1, 385, 91, 93, 301, 65, 563, 1093, 1, 11, 355, 38, 118, 83, 1, 1254, 763, 1, 1043, 39, 1, 249, 141, 238, 19, 71, 43, 133, 11, 781, 1, 649, 1, 554, 1081, 614, 1, 1633, 5, 317, 1398, 1, 269, 626, 10, 527, 1285, 1191, 1

Offset: 0

Antti Karttunen, Oct 06 2017

nonn

Antti Karttunen, Table of n, a(n) for n = 0..10000

Cf. A002326, A007913, A292270, A292947, A293219.

Cf. A292938 (gives the positions of ones).

A000265(n) = (n >> valuation(n, 2));
A006519(n) = 2^valuation(n, 2);
A292270(n) = { my(x = n+n+1, z = ((1+x)/A006519(1+x)), m = A000265(1+x)); while(m!=1, z += ((x+m)/A006519(x+m)); m = A000265(x+m)); z; };
A293218(n) = core(A292270(n));

(define (A293218 n) (A007913 (A292270 n)))

a(n) = A007913(A292270(n)).

A003572 Order of 3 mod 3n+2.

Original entry on oeis.org

1, 4, 2, 5, 6, 16, 4, 11, 3, 28, 8, 12, 18, 8, 10, 23, 20, 52, 6, 29, 30, 12, 16, 35, 18, 30, 4, 41, 42, 88, 22, 36, 42, 100, 6, 53, 20, 112, 28, 48, 10, 100, 32, 65, 22, 136, 12, 15, 12, 148, 18, 60, 78, 66, 8, 83, 16, 172

Offset: 0

N. J. A. Sloane

nonn

Jinyuan Wang, Table of n, a(n) for n = 0..10000

Cf. A002326, A003571, A003574, A217852.

List([0..60],n->OrderMod(3,3*n+2)); # Muniru A Asiru, Feb 16 2019

with(numtheory): f := n->order(3,3*n+2);

Table[MultiplicativeOrder[3, 3*n + 2], {n, 0, 57}] (* Jinyuan Wang, Feb 16 2019 *)

a(n) = znorder(Mod(3, 3*n+2)); \\ Michel Marcus, Feb 16 2019

A003574 Order of 4 mod 4n-1.

Original entry on oeis.org

1, 3, 5, 2, 9, 11, 9, 5, 6, 6, 7, 23, 4, 10, 29, 3, 33, 35, 10, 39, 41, 14, 6, 18, 15, 51, 53, 18, 22, 12, 10, 7, 65, 18, 69, 30, 21, 15, 10, 26, 81, 83, 9, 30, 89, 30, 20, 95, 6, 99, 42, 33, 105, 14, 9, 37, 113, 15, 46, 119

Offset: 1

N. J. A. Sloane

nonn

Muniru A Asiru, Table of n, a(n) for n = 1..10000

Cf. A003573. Second bisection of A053447.

Cf. A002326, A003572, A217852.

List([1..70],n->OrderMod(4,4*n-1)); # Muniru A Asiru, Feb 19 2019

with(numtheory): f := n->order(4,4*n-1);

a(n) = znorder(Mod(4, 4*n-1)); \\ Michel Marcus, Feb 22 2019

a(n) = A053447(2*n-1) for n >= 1. - Jianing Song, Oct 03 2022

A014659 Odd numbers that do not divide 2^k + 1 for any k >= 1.

Original entry on oeis.org

7, 15, 21, 23, 31, 35, 39, 45, 47, 49, 51, 55, 63, 69, 71, 73, 75, 77, 79, 85, 87, 89, 91, 93, 95, 103, 105, 111, 115, 117, 119, 123, 127, 133, 135, 141, 143, 147, 151, 153, 155, 159, 161, 165, 167, 175, 183, 187, 189, 191, 195, 199, 203, 207, 213, 215, 217, 219

Offset: 1

N. J. A. Sloane

nonn

This is the subset of odd integers > 1 as (2*n - 1) in A179480 such that A179480(n) is even. Example: A179480(18) = 6, even; corresponding to (2*18 - 1), 35. Then 35 is in A014659. A014657 is the subset of odd terms > 1 corresponding to odd terms in A179480. - Gary W. Adamson, Aug 20 2012
From Wolfdieter Lang, Aug 22 2020: (Start)
These odd numbers are the moduli named 2*n+1 in the definition of A003558(n), for n >= 1, for which the + sign applies. The signs in the definition of A003558 are given in A332433.
These are the odd numbers N >= 3 for which A003558((N-1)/2) = A002326((N+1)/2), the period length P(N) of the cycles {2^k (mod N)}_{k=0}^(P(N)-1). Compare the periods given in A201908((N+1)/2, k). (End)

T. D. Noe, Table of n, a(n) for n = 1..1000
P. Moree, Appendix B, to V. Pless et al., Cyclic Self-Dual Z_4 Codes, Finite Fields Applic., vol. 3 pp. 48-69, 1997.

Cf. A179480, A002326, A003558, A201908, A332433.

Cf. A014657, numbers that divide 2^k + 1 for some k.

More terms from Don Reble, Nov 03 2001

A050975 Haupt-exponents of 3 modulo integers relatively prime to 3.

Original entry on oeis.org

1, 2, 4, 6, 2, 4, 5, 3, 6, 4, 16, 18, 4, 5, 11, 20, 3, 6, 28, 30, 8, 16, 12, 18, 18, 4, 8, 42, 10, 11, 23, 42, 20, 6, 52, 20, 6, 28, 29, 10, 30, 16, 12, 22, 16, 12, 35, 12, 18, 18, 30, 78, 4, 8, 41, 16, 42, 10, 88, 6, 22, 23, 36, 48, 42, 20, 100, 34, 6, 52, 53, 27, 20, 12

Offset: 1

Eric W. Weisstein

nonn

R. J. Mathar, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Multiplicative Order

Cf. A002326, A002329, A053446.

A001651 := proc(n)
        (3*(2*n-1)-(-1)^n)/4 ;
end proc:
A050975 := proc(n)
        local gcd3 ;
        gcd3 := A001651(n+1);
        numtheory[order](3,gcd3) ;
end proc: # R. J. Mathar, Oct 21 2012

A050977 Haupt-exponents of 5 modulo integers relatively prime to 5.

Original entry on oeis.org

1, 2, 1, 2, 6, 2, 6, 5, 2, 4, 6, 4, 16, 6, 9, 6, 5, 22, 2, 4, 18, 6, 14, 3, 8, 10, 16, 6, 36, 9, 4, 20, 6, 42, 5, 22, 46, 4, 42, 16, 4, 52, 18, 6, 18, 14, 29, 30, 3, 6, 16, 10, 22, 16, 22, 5, 6, 72, 36, 9, 30, 4, 39, 54, 20, 82, 6, 42, 14, 10, 44, 12, 22, 6, 46, 8, 96, 42, 30, 25, 16

Offset: 1

Eric W. Weisstein

nonn

R. J. Mathar, Table of n, a(n) for n = 1..7999
Eric Weisstein's World of Mathematics, Multiplicative Order

Cf. A002326 (base 2), A050975 (base 3), A002329.

n := 1 :
for i from 2 to 10000 do
    if igcd(i,5) = 1 then
        printf("%d %d\n",n,numtheory[order](5,i)) ;
        n := n+1 ;
    end if;
end do: # R. J. Mathar, Oct 14 2014

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.

A108989 Composite numbers k with primitive root 2; i.e., the order of 2 modulo k is phi(k).

Original entry on oeis.org

9, 25, 27, 81, 121, 125, 169, 243, 361, 625, 729, 841, 1331, 1369, 2187, 2197, 2809, 3125, 3481, 3721, 4489, 6561, 6859, 6889, 10201, 11449, 14641, 15625, 17161, 19321, 19683, 22201, 24389, 26569, 28561, 29929, 32041, 32761, 38809, 44521, 50653

Offset: 1

Douglas Stones (dssto1(AT)student.monash.edu.au), Jul 28 2005

nonn

There exist no even numbers with primitive root 2. All entries are odd. They are all the powers of odd primes. - V. Raman, Nov 20 2012

			Modulo 9: 2^1 == 2, 2^2 == 4, 2^3 == 8, 2^4 == 7, 2^5 == 5, 2^6 == 1 and phi(9) == 6.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..100 from Alois P. Heinz)

Intersection of A002808 and A167791.

Cf. A000010, A001122, A002326, A216838, A216848, A219030.

for i in [2..100000] do if not IsPrime(i) then if IsPrimitiveRootMod(2,i) then Display(i); fi; fi; od;

nn=51000; Select[Complement[Range[2, nn], Prime[Range[PrimePi[nn]]]], PrimitiveRoot[#] == 2&] (* Harvey P. Dale, Jul 25 2011 *)
seq[max_] := Module[{ps = Select[Range[2, Floor[Sqrt[max]]], PrimeQ], s = {}}, Do[s = Join[s, Select[p^Range[2, Floor[Log[p, max]]], PrimitiveRoot[#] == 2 &]], {p, ps}]; Sort[s]]; seq[10^5] (* Amiram Eldar, Nov 10 2023 *)

for(n=3,100000,if(n%2==1&&isprime(n)==0&&znorder(Mod(2,n))==eulerphi(n),print1(n","))) /* V. Raman, Nov 20 2012 */

A122929 Multiplicative order of 2 mod A141232(n).

Original entry on oeis.org

11, 28, 36, 52, 48, 60, 52, 148, 76, 68, 51, 52, 29, 92, 156, 92, 29, 179, 166, 100, 44, 102, 239, 156, 50, 25, 51, 364, 224, 204, 244, 166, 66, 346, 194, 388, 618, 92, 388, 102, 660, 371, 388, 29, 772, 828, 239, 460, 55, 292, 431, 166, 882, 1060, 532, 155, 68

Offset: 1

Vladimir Shevelev, Jul 05 2008, Jul 12 2008, Jul 23 2008

nonn

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A141232, A002326, A001262, A141216.

a137576(n)=my(t); sumdiv(2*n+1, d, eulerphi(d)/(t=znorder(Mod(2, d))))*t-t+1;
lista(nn) = {forcomposite(n=1, nn, if ((n % 2) && (a137576((n-1)/2) == n), print1(znorder(Mod(2, n)), ", ");););} \\ Michel Marcus, Feb 09 2015

More terms from Michel Marcus, Feb 09 2015

cp's OEIS Frontend

A081844 Number of irreducible factors of x^(2n+1) - 1 over GF(2).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A293218 a(n) = A007913(A292270(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Scheme

Formula

A003572 Order of 3 mod 3n+2.

Views

Author

Keywords

Links

Crossrefs

Programs

GAP

Maple

Mathematica

PARI

A003574 Order of 4 mod 4n-1.

Views

Author

Keywords

Links

Crossrefs

Programs

GAP

Maple

PARI

Formula

A014659 Odd numbers that do not divide 2^k + 1 for any k >= 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A050975 Haupt-exponents of 3 modulo integers relatively prime to 3.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

A050977 Haupt-exponents of 5 modulo integers relatively prime to 5.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs