|
| |
|
|
A086251
|
|
Number of primitive prime factors of 2^n-1.
|
|
6
| |
|
|
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; 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.
|
|
|
LINKS
| T. D. Noe, Table of n, a(n) for n=1..500 (using data from A001265)
Eric Weisstein's World of Mathematics, Zsigmondy Theorem
|
|
|
FORMULA
| a(n) = Sum{d|n} mu(n/d) A046800(d), inverse Mobius transform of A046800.
|
|
|
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}]]
|
|
|
CROSSREFS
| Cf. A046800, A046051 (number of prime factors, with repetition, of 2^n-1), A086252.
Sequence in context: A204162 A043285 A146291 * A177121 A092931 A147300
Adjacent sequences: A086248 A086249 A086250 * A086252 A086253 A086254
|
|
|
KEYWORD
| hard,nonn
|
|
|
AUTHOR
| T. D. Noe (noe(AT)sspectra.com), Jul 14 2003
|
| |
|
|
