|
%I M0603 N0217 #66 Feb 26 2023 20:05:48
%S 1,1,2,3,5,1,13,7,17,11,89,1,233,29,61,47,1597,19,37,41,421,199,28657,
%T 23,3001,521,53,281,514229,31,557,2207,19801,3571,141961,107,73,9349,
%U 135721,2161,2789,211,433494437,43,109441,139,2971215073,1103,97,101
%N Smallest primitive prime factor of Fibonacci number F(n), or 1 if F(n) has no primitive prime factor.
%C A prime factor of F(n) is called primitive if it does not divide F(r) for any r < n.
%C A Fibonacci number can have more than one primitive factor; the primitive factors of F(19) are 37 and 113.
%C From _Robert Israel_, Oct 13 2015: (Start)
%C 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.
%C 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.
%C a(n) = n-1 iff n=2 or n-1 is in A000057.
%C a(n) = n+1 iff n+1 is a prime in A106535. (End)
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Max Alekseyev, <a href="/A001578/b001578.txt">Table of n, a(n) for n = 1..1452</a> (terms 1..1000 from Blair Kelly and T. D. Noe, terms 1409..1422 from Tyler Busby)
%H Mansur S. Boase, <a href="https://www.fq.math.ca/Scanned/39-5/boase.pdf">A Result About the Primes Dividing Fibonacci Numbers</a>, The Fibonacci Quarterly, 39.5 (2001) 386.
%H R. D. Carmichael, <a href="https://doi.org/10.2307%2F1967797">On the numerical factors of the arithmetic forms α^n ± β^n</a>, Annals of Math., 15 (1/4) (1913), 30-70.
%H D. Jarden, <a href="http://www.fq.math.ca/Scanned/1-3/jarden.pdf">On the greatest primitive divisors of Fibonacci and Lucas numbers with prime-power subscripts</a>, Fib. Quart. 1(#3) (1963), 15-31.
%H Blair Kelly, <a href="http://mersennus.net/fibonacci//">Fibonacci and Lucas Factorizations</a>
%F a(n) = 1 if and only if n = 1, 2, 6, or 12, by Carmichael's theorem. - _Jonathan Sondow_, Dec 07 2017
%p for n from 1 to 350 do
%p f:= combinat:-fibonacci(n);
%p if not isprime(n) then
%p for k in map(t -> n/t, numtheory:-factorset(n)) do
%p fk:= combinat:-fibonacci(k);
%p g:= igcd(f,fk);
%p while g > 1 do
%p f:= f/g;
%p g:= igcd(f,fk);
%p od
%p od
%p fi;
%p if f = 1 then A[n]:= 1; next fi;
%p F:= map(t -> t[1],ifactors(f,easy)[2]);
%p p:= select(type, F,integer);
%p if nops(p) >= 1 then A[n]:= min(p); next fi;
%p A[n]:= min(numtheory:-factorset(f));
%p od:
%p seq(A[i],i=1..350); # _Robert Israel_, Oct 13 2015
%t prms={}; Table[f=First/@FactorInteger[Fibonacci[n]]; p=Complement[f, prms]; prms=Join[prms, p]; If[p=={}, 1, First[p]], {n, 50}]
%o (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
%Y Cf. A000045, A000057, A106535, A086597 (number of primitive prime factors in F(n)), A061488 (1's omitted), A262341 (largest primitive prime factor of F(n)).
%K nonn
%O 1,3
%A _N. J. A. Sloane_
%E Edited by _T. D. Noe_, Apr 15 2004
%E Definition clarified at the suggestion of _Joerg Arndt_ by _Jonathan Sondow_, Oct 13 2015
|
