login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A086251 Number of primitive prime factors of 2^n - 1. 9
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,11

COMMENTS

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

LINKS

Charles R Greathouse IV, Table of n, a(n) for n = 1..1200 (first 500 terms from T. D. Noe)

Eric Weisstein's World of Mathematics, Zsigmondy Theorem

FORMULA

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

EXAMPLE

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

MATHEMATICA

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}]]

PROG

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

CROSSREFS

Cf. A046800, A046051 (number of prime factors, with repetition, of 2^n-1), A086252.

Sequence in context: A043285 A245690 A146291 * A177121 A092931 A147300

Adjacent sequences:  A086248 A086249 A086250 * A086252 A086253 A086254

KEYWORD

hard,nonn

AUTHOR

T. D. Noe, Jul 14 2003

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 16 09:19 EST 2019. Contains 320161 sequences. (Running on oeis4.)