A182590 -id:A182590 - cp's OEIS frontend

A086251 Number of primitive prime factors of 2^n - 1.

0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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, 1, 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, 3, 2, 3, 2, 2, 3

Offset: 1

T. D. Noe, Jul 14 2003

A prime factor of 2^n - 1 is called primitive if it does not divide 2^r - 1 for any r < n. Equivalently, p is a primitive prime factor of 2^n - 1 if ord(2,p) = n. Zsigmondy's theorem says that there is at least one primitive prime factor for n > 1, except for n=6. See A086252 for those n that have a record number of primitive prime factors.
Number of odd primes p such that A002326((p-1)/2) = n. Number of occurrences of number n in A014664. - Thomas Ordowski, Sep 12 2017
The prime factors are not counted with multiplicity, which matters for a(364)=4 and a(1755)=6. - Jeppe Stig Nielsen, Sep 01 2020

			a(11) = 2 because 2^11 - 1 = 23*89 and both 23 and 89 have order 11.

Table of n, a(n) for n = 1..1206
Eric Weisstein's World of Mathematics, Zsigmondy Theorem

Cf. A046800, A046051 (number of prime factors, with repetition, of 2^n-1), A086252, A002588, A005420, A002184, A046801, A049093, A049094, A059499, A085021, A097406, A112927, A237043.

Join[{0}, Table[cnt=0; f=Transpose[FactorInteger[2^n-1]][[1]]; Do[If[MultiplicativeOrder[2, f[[i]]]==n, cnt++ ], {i, Length[f]}]; cnt, {n, 2, 200}]]

a(n) = sumdiv(n, d, moebius(n/d)*omega(2^d-1)); \\ Michel Marcus, Sep 12 2017

a(n) = my(m=polcyclo(n, 2)); omega(m/gcd(m,n)) \\ Jeppe Stig Nielsen, Sep 01 2020

a(n) = Sum{d|n} mu(n/d) A046800(d), inverse Mobius transform of A046800.
a(n) <= A182590(n). - Thomas Ordowski, Sep 14 2017
a(n) = A001221(A064078(n)). - Thomas Ordowski, Oct 26 2017

Terms to a(500) in b-file from T. D. Noe, Nov 11 2010
Terms a(501)-a(1200) in b-file from Charles R Greathouse IV, Sep 14 2017
Terms a(1201)-a(1206) in b-file from Max Alekseyev, Sep 11 2022

A001265 Table T(n,k) in which n-th row lists prime factors of 2^n - 1 (n >= 2), with repetition.

Original entry on oeis.org

3, 7, 3, 5, 31, 3, 3, 7, 127, 3, 5, 17, 7, 73, 3, 11, 31, 23, 89, 3, 3, 5, 7, 13, 8191, 3, 43, 127, 7, 31, 151, 3, 5, 17, 257, 131071, 3, 3, 3, 7, 19, 73, 524287, 3, 5, 5, 11, 31, 41, 7, 7, 127, 337, 3, 23, 89, 683, 47, 178481, 3, 3, 5, 7, 13, 17, 241

Offset: 2

N. J. A. Sloane

For n > 1, the length of row n is A046051(n). - T. D. Noe, Aug 06 2007

			Table begins:
 n=2: 3;
 n=3: 7;
 n=4: 3, 5;
 n=5: 31;
 n=6: 3, 3, 7;
 n=7: 127;
 n=8: 3, 5, 17;
  ...

J. Brillhart et al., Factorizations of b^n +- 1. Contemporary Mathematics, Vol. 22, Amer. Math. Soc., Providence, RI, 2nd edition, 1985; and later supplements.

Max Alekseyev, Rows n = 2..1206, flattened (rows 2..500 from T. D. Noe)
Joerg Arndt, Rows n = 1..1200 of triangle (derived from Brillhart et al.; updated by Jon E. Schoenfield)
J. Brillhart et al., Factorizations of b^n +- 1, Contemporary Mathematics, Vol. 22, Amer. Math. Soc., Providence, RI, 3rd edition, 2002.
Jeroen Demeyer, Machine-readable Cunningham Tables
S. S. Wagstaff, Jr., The Cunningham Project
Eric Weisstein's World of Mathematics, Mersenne Number
Chai Wah Wu, Tables from the Cunningham Project in machine-readable JSON format.

Cf. A060443, A182590.

Array[Flatten[ConstantArray[#1, #2] & @@ # & /@ FactorInteger[2^# - 1]] &, 24] // Flatten (* Michael De Vlieger, Dec 04 2017 *)

row(n)= if (n==1, return ([0])); my(f = factor(2^n-1), v = []); for (i=1, #f~, for (j=1, f[i, 2], v = concat(v, f[i,j]))); v; \\ Michel Marcus, Dec 05 2017

Ambiguous rows 0 and 1 removed by Max Alekseyev, Jul 25 2023

A182591 Number of prime factors of form cn+1 for numbers 3^n-1.

Original entry on oeis.org

0, 1, 1, 2, 2, 1, 1, 1, 3, 2, 2, 1, 2, 1, 2, 2, 3, 2, 2, 2, 4, 2, 2, 2, 2, 4, 3, 3, 4, 3, 2, 1, 5, 2, 4, 2, 4, 4, 2, 3, 5, 2, 3, 3, 3, 4, 5, 5, 4, 2, 4, 3, 6, 3, 2, 5, 6, 2, 3, 2, 5, 2, 2, 4, 5, 3, 3, 2, 3, 1, 4, 4, 5, 3, 5, 4, 9, 3, 3, 3, 5, 4, 5, 4, 3, 4

Offset: 2

Seppo Mustonen, Nov 22 2010

nonn

			For n=6, 3^n-1=728 has two prime factors of the form cn+1, namely 7=n+1 and 13=2n+1. Thus a(6)=2.

Seppo Mustonen, Table of n, a(n) for n = 2..170
S. Mustonen, On prime factors of numbers m^n+-1
Seppo Mustonen, On prime factors of numbers m^n+-1 [Local copy]

m = 3; n = 2; nmax = 170;
While[n <= nmax, {l = FactorInteger[m^n - 1]; s = 0;
     For[i = 1, i <= Length[l],
      i++, {p = l[[i, 1]];
       If[IntegerQ[(p - 1)/n] == True, s = s + l[[i, 2]]];}];
     a[n] = s;} n++;];
Table[a[n], {n, 2, nmax}]

A182595 Number of prime factors of form cn+1 for numbers 2^n+1.

Original entry on oeis.org

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

Offset: 2

Seppo Mustonen, Nov 24 2010

nonn

Repeated prime factors are counted.

			For n=14, 2^n+1=16385=5*29*113 has two prime factors of form, namely 29=2n+1, 113=8n+1. Thus a(14)=2.

Seppo Mustonen, Table of n, a(n) for n = 2..250
S. Mustonen, On prime factors of numbers m^n+-1
Seppo Mustonen, On prime factors of numbers m^n+-1 [Local copy]

m = 2; n = 2; nmax = 250;
While[n <= nmax, {l = FactorInteger[m^n + 1]; s = 0;
     For[i = 1, i <= Length[l],
      i++, {p = l[[i, 1]];
       If[IntegerQ[(p - 1)/n] == True, s = s + l[[i, 2]]];}];
     a[n] = s;} n++;];
Table[a[n], {n, 2, nmax}]
Table[{p, e}=Transpose[FactorInteger[2^n+1]]; Sum[If[Mod[p[[i]], n] == 1, e[[i]], 0], {i, Length[p]}], {n, 2, 50}]

A292079 Composite numbers m such that 2^m - 1 has a single prime factor of the form k*m + 1.

Original entry on oeis.org

4, 6, 8, 9, 12, 20, 24, 27, 33, 49, 69, 77, 145, 425, 447, 567

Offset: 1

Michel Marcus, Sep 12 2017

From Thomas Ordowski, Sep 12 2017: (Start)
Composite numbers m such that A182590(m) = 1.
Problem: are there infinitely many such numbers?
Note that this single prime factor p is the only primitive prime factor of 2^m - 1 for all such m except 6, i.e., the multiplicative order of 2 modulo p is m. (End)
After 567, the only numbers < 1200 that may possibly be terms are 961, 1037, 1111, and 1115. - Jon E. Schoenfield, Dec 03 2017
a(17) > 1206. - Amiram Eldar, Apr 01 2021

Cf. A001265, A002326, A182590.

Select[Range@ 150, And[CompositeQ@ #, Function[{m, p}, Total@ Boole@ Map[Divisible[# - 1, m] &, p] == 1] @@ {#, FactorInteger[2^# - 1][[All, 1]]}] &] (* Michael De Vlieger, Dec 06 2017 *)

lista(nn) = forcomposite(n=1, nn, my(f = factor(2^n-1)); if (sum(k=1, #f~, ((f[k, 1]-1) % n)==0) == 1, print1(n, ", ")));

Erroneous terms 841 and 1127 and possible (but unconfirmed, and not necessarily next) term 1037 deleted by Jon E. Schoenfield, Dec 03 2017

A182592 Number of prime factors of form cn+1 for numbers 5^n-1.

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 1, 2, 3, 1, 2, 1, 3, 3, 2, 2, 3, 3, 3, 3, 4, 2, 3, 4, 3, 4, 3, 3, 5, 2, 3, 3, 4, 6, 3, 3, 6, 3, 5, 2, 6, 2, 3, 4, 4, 1, 2, 1, 6, 5, 3, 3, 7, 5, 3, 2, 5, 2, 7, 3, 5, 6, 4, 4, 7, 5, 8, 6, 8, 2, 3, 3, 6, 5, 5, 3, 7, 3, 4, 2, 6, 3, 3, 3, 6, 4, 4, 6, 5, 3, 2, 5, 4, 7, 5, 3, 4, 5, 7, 3, 10, 4, 5, 8, 6, 5, 2, 4, 7, 3, 6, 8, 5, 10, 2, 3, 6, 5, 7

Offset: 2

Seppo Mustonen, Nov 22 2010

nonn

			For n=10, 5^n-1=9765624=2^3*3*11*71*521 has three prime factors of the form cn+1, namely 11=n+1, 71=7n+1, 521=52n+1. Thus a(10)=3.

S. Mustonen, On prime factors of numbers m^n+-1
Seppo Mustonen, On prime factors of numbers m^n+-1 [Local copy]

m = 5; n = 2; nmax = 120;
While[n <= nmax, {l = FactorInteger[m^n - 1]; s = 0;
     For[i = 1, i <= Length[l],
      i++, {p = l[[i, 1]];
       If[IntegerQ[(p - 1)/n] == True, s = s + l[[i, 2]]];}];
     a[n] = s;} n++;];
Table[a[n], {n, 2, nmax}]
Table[Count[FactorInteger[5^n-1][[All,1]],?(Mod[#,n]==1&)],{n,2,130}] (* _Harvey P. Dale, Dec 11 2016 *)

A182593 Number of prime factors of form c*n+1 for numbers 6^n-1.

Original entry on oeis.org

2, 1, 2, 1, 3, 1, 1, 2, 3, 2, 3, 2, 3, 2, 3, 4, 3, 2, 3, 3, 3, 4, 3, 2, 5, 2, 4, 1, 4, 2, 3, 2, 6, 3, 5, 5, 4, 4, 3, 2, 4, 4, 4, 4, 6, 3, 5, 3, 4, 5, 6, 3, 5, 2, 5, 3, 4, 3, 7, 3, 3, 4, 4, 5, 6, 2, 4, 4, 8, 1, 7, 4, 8, 5, 4, 2, 9, 3, 5, 4, 5, 7, 4, 3, 5, 5, 4, 3, 6, 2, 6, 5, 4, 7, 8, 5, 6, 6, 7, 2, 11, 4, 7, 6, 7, 3, 6, 2, 6, 5, 6, 4, 6, 7, 4, 4, 4, 6, 6

Offset: 2

Seppo Mustonen, Nov 22 2010

nonn

			For n=6, 6^n-1=46655=5*7*31*43 and has three prime factors of form c*n+1, namely 7=n+1, 31=5*n+1, and 43=7*n+1. Thus a(6)=3. [Corrected by _N. J. A. Sloane_, Nov 16 2024]

Seppo Mustonen, On prime factors of numbers m^n+-1
Seppo Mustonen, On prime factors of numbers m^n+-1 [Local copy]

m = 6; n = 2; nmax = 120;
While[n <= nmax, {l = FactorInteger[m^n - 1]; s = 0;
     For[i = 1, i <= Length[l],
      i++, {p = l[[i, 1]];
       If[IntegerQ[(p - 1)/n] == True, s = s + l[[i, 2]]];}];
     a[n] = s;} n++;];
Table[a[n], {n, 2, nmax}]

A182594 Number of prime factors of form c*n+1 for numbers 7^n-1, counted with multiplicity.

Original entry on oeis.org

1, 1, 2, 1, 2, 2, 1, 3, 3, 2, 2, 1, 4, 2, 3, 2, 4, 2, 3, 1, 4, 3, 4, 3, 3, 4, 4, 3, 3, 3, 2, 4, 3, 3, 3, 3, 4, 4, 5, 3, 4, 2, 4, 2, 4, 2, 3, 4, 4, 5, 5, 3, 5, 1, 6, 3, 4, 4, 5, 4, 6, 2, 3, 6, 6, 4, 6, 3, 8, 2, 5, 5, 5, 3, 2, 3, 7, 2, 5, 6, 7, 7, 3, 3, 9, 5, 4, 3, 6, 5, 5, 4, 3, 3, 5, 3, 11, 4, 6

Offset: 2

Seppo Mustonen, Nov 22 2010

nonn

			For n=9, 7^n-1 = 40353606 = 2*3^3*19*37*1063 has three prime factors of form, namely 19 = 2n+1, 37 = 4n+1, 1063 = 118n+1. Thus a(9) = 3.

Seppo Mustonen, On prime factors of numbers m^n+-1
Seppo Mustonen, On prime factors of numbers m^n+-1 [Local copy]

f:= proc(n) local F;
  F:= select(t -> t[1] mod n = 1, ifactors(7^n-1)[2]);
  convert(F[..,2],`+`)
end proc:
map(f, [$2..100]); # Robert Israel, Apr 29 2025

m = 7; n = 2; nmax = 80;
While[n <= nmax, {l = FactorInteger[m^n - 1]; s = 0;
     For[i = 1, i <= Length[l],
      i++, {p = l[[i, 1]];
       If[IntegerQ[(p - 1)/n] == True, s = s + l[[i, 2]]];}];
     a[n] = s;} n++;];
Table[a[n], {n, 2, nmax}]

Definition clarified and more terms from Robert Israel, Apr 29 2025

A182596 Number of prime factors of form cn+1 for numbers 3^n+1.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 2, 1, 2, 1, 1, 2, 3, 1, 3, 2, 2, 2, 3, 2, 1, 4, 2, 2, 2, 2, 3, 1, 2, 1, 4, 2, 1, 2, 3, 2, 5, 2, 2, 2, 1, 3, 3, 2, 3, 2, 2, 3, 6, 2, 2, 2, 3, 3, 5, 2, 2, 5, 2, 3, 5, 1, 2, 1, 2, 3, 6, 3, 5, 3, 2, 3, 6, 4, 1, 2, 3, 4, 7, 3, 4, 5, 4, 5, 8, 3, 3, 3, 6, 2, 6, 2, 4, 4, 3, 5, 6, 3, 2, 5, 3, 4, 6, 4, 3, 7, 4, 4, 7, 7, 3, 4, 3, 3, 6, 1, 2, 5, 4, 4, 6, 2, 3, 4, 4, 5, 6, 3

Offset: 2

Seppo Mustonen, Nov 24 2010

nonn

Repeated prime factors are counted.

			For n=8, 3^n+1=6562=2*17*193 has two prime factors of form, namely 17=2n+1, 193=24n+1. Thus a(8)=2.

S. Mustonen, On prime factors of numbers m^n+-1
Seppo Mustonen, On prime factors of numbers m^n+-1 [Local copy]

m = 3; n = 2; nmax = 130;
While[n <= nmax, {l = FactorInteger[m^n + 1]; s = 0;
     For[i = 1, i <= Length[l],
      i++, {p = l[[i, 1]];
       If[IntegerQ[(p - 1)/n] == True, s = s + l[[i, 2]]];}];
     a[n] = s;} n++;];
Table[a[n], {n, 2, nmax}]
Table[{p, e}=Transpose[FactorInteger[3^n+1]]; Sum[If[Mod[p[[i]], n] == 1, e[[i]], 0], {i, Length[p]}], {n, 2, 50}]

A182597 Number of prime factors of form cn+1 for numbers 5^n+1.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 2, 1, 2, 3, 2, 2, 1, 2, 2, 2, 2, 3, 2, 3, 2, 2, 1, 2, 2, 3, 1, 2, 3, 3, 3, 4, 4, 2, 3, 3, 2, 4, 2, 4, 3, 4, 1, 1, 1, 3, 4, 3, 3, 5, 4, 3, 1, 2, 4, 3, 1, 4, 4, 4, 2, 6, 3, 4, 2, 1, 5, 4, 3, 3, 2, 3, 3, 5, 3, 2, 4, 4, 4, 5, 4, 3, 4, 6, 3, 4, 4, 3, 3, 2, 2, 4, 4, 4, 4, 5, 4, 1, 4, 1, 7, 1, 5, 5, 2, 2

Offset: 2

Seppo Mustonen, Nov 24 2010

nonn

Repeated prime factors are counted.

			For n=11, 5^n+1=48828126=2*3*23*67*5281 has three prime factors of form, namely 23=2n+1, 67=6n+1, 5281=480n+1. Thus a(11)=3.

S. Mustonen, On prime factors of numbers m^n+-1
Seppo Mustonen, On prime factors of numbers m^n+-1 [Local copy]

m = 5; n = 2; nmax = 107;
While[n <= nmax, {l = FactorInteger[m^n + 1]; s = 0;
     For[i = 1, i <= Length[l],
      i++, {p = l[[i, 1]];
       If[IntegerQ[(p - 1)/n] == True, s = s + l[[i, 2]]]; }];
     a[n] = s; } n++; ];
Table[a[n], {n, 2, nmax}]
Table[{p,e}=Transpose[FactorInteger[5^n+1]]; Sum[If[Mod[p[[i]], n] == 1, e[[i]], 0], {i, Length[p]}], {n, 2, 50}]

cp's OEIS Frontend

A086251 Number of primitive prime factors of 2^n - 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A001265 Table T(n,k) in which n-th row lists prime factors of 2^n - 1 (n >= 2), with repetition.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A182591 Number of prime factors of form cn+1 for numbers 3^n-1.

Views

Author

Keywords

Examples

Links

Programs

Mathematica

A182595 Number of prime factors of form cn+1 for numbers 2^n+1.

Views

Author

Keywords

Comments

Examples

Links

Programs

Mathematica

A292079 Composite numbers m such that 2^m - 1 has a single prime factor of the form k*m + 1.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Extensions

A182592 Number of prime factors of form cn+1 for numbers 5^n-1.

Views

Author

Keywords

Examples

Links

Programs

Mathematica

A182593 Number of prime factors of form c*n+1 for numbers 6^n-1.

Views

Author

Keywords

Examples

Links

Programs

Mathematica

A182594 Number of prime factors of form c*n+1 for numbers 7^n-1, counted with multiplicity.

Views

Author

Keywords

Examples

Links

Programs

Maple

Mathematica