|
|
A001578
|
|
Smallest primitive prime factor of Fibonacci number F(n), or 1 if F(n) has no primitive prime factor.
(Formerly M0603 N0217)
|
|
14
|
|
|
1, 1, 2, 3, 5, 1, 13, 7, 17, 11, 89, 1, 233, 29, 61, 47, 1597, 19, 37, 41, 421, 199, 28657, 23, 3001, 521, 53, 281, 514229, 31, 557, 2207, 19801, 3571, 141961, 107, 73, 9349, 135721, 2161, 2789, 211, 433494437, 43, 109441, 139, 2971215073, 1103, 97, 101
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
A prime factor of F(n) is called primitive if it does not divide F(r) for any r < n.
A Fibonacci number can have more than one primitive factor; the primitive factors of F(19) are 37 and 113.
Since gcd(F(n),F(k)) = F(gcd(n,k)), the non-primitive prime factors of F(n) are factors of F(k) for some proper divisors k of n.
Since prime p divides F(p-1) if p == 1 or 4 (mod 5), F(p+1) if p == 2 or 3 mod 5, F(p) if p = 5, we have a(n) >= n-1 if a(n) > 1.
a(n) = n-1 iff n=2 or n-1 is in A000057.
a(n) = n+1 iff n+1 is a prime in A106535. (End)
|
|
REFERENCES
|
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
|
|
FORMULA
|
a(n) = 1 if and only if n = 1, 2, 6, or 12, by Carmichael's theorem. - Jonathan Sondow, Dec 07 2017
|
|
MAPLE
|
for n from 1 to 350 do
f:= combinat:-fibonacci(n);
if not isprime(n) then
for k in map(t -> n/t, numtheory:-factorset(n)) do
fk:= combinat:-fibonacci(k);
g:= igcd(f, fk);
while g > 1 do
f:= f/g;
g:= igcd(f, fk);
od
od
fi;
if f = 1 then A[n]:= 1; next fi;
F:= map(t -> t[1], ifactors(f, easy)[2]);
p:= select(type, F, integer);
if nops(p) >= 1 then A[n]:= min(p); next fi;
A[n]:= min(numtheory:-factorset(f));
od:
|
|
MATHEMATICA
|
prms={}; Table[f=First/@FactorInteger[Fibonacci[n]]; p=Complement[f, prms]; prms=Join[prms, p]; If[p=={}, 1, First[p]], {n, 50}]
|
|
PROG
|
(PARI) a(n) = {my(v = vector(n, k, fibonacci(k))); my(vf = vector(n, k, factor(v[k])[, 1]~)); for (k=1, n-1, vf[n] = setminus(vf[n], vf[k]); ); if (#vf[n], vecmin(vf[n]), 1); } \\ Michel Marcus, May 11 2021
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|