|
| |
|
|
A086251
|
|
Number of primitive prime factors of 2^n - 1.
|
|
11
|
|
|
|
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.
The prime factors are not counted with multiplicity, which matters for a(364)=4 and a(1755)=6. - Jeppe Stig Nielsen, Sep 01 2020
|
|
|
LINKS
|
|
|
|
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}]]
|
|
|
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, A002588, A005420, A002184, A046801, A049093, A049094, A059499, A085021, A097406, A112927, A237043.
|
|
|
KEYWORD
|
hard,nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Terms to a(500) in b-file from T. D. Noe, Nov 11 2010
|
|
|
STATUS
|
approved
|
| |
|
|
