A086252 -id:A086252 - 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

A086258 a(n) is the smallest k such that 2^k+1 has n primitive prime factors.

Original entry on oeis.org

0, 14, 26, 46, 83, 118, 309, 194, 414, 538, 786, 958

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 rA086257 for the number of primitive prime factors in 2^n+1. It is known that a(8) = 194.

Next term is > 666. - David Wasserman, Feb 25 2005

			a(2) = 14 because 2^14+1 = 5*29*113 and 29 and 113 do not divide 2^r+1 for r < 14.

J. Brillhart et al., Factorizations of b^n +- 1. Contemporary Mathematics, Vol. 22, Amer. Math. Soc., Providence, RI, 3rd edition, 2002.

J. Brillhart et al., Factorizations of b^n +- 1 Available on-line

Cf. A086252, A086257.

More terms from David Wasserman, Feb 25 2005
a(11) from D. S. McNeil, Dec 19 2010
a(12) from Amiram Eldar, Oct 12 2019

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI