cp's OEIS Frontend

A001578 Smallest primitive prime factor of Fibonacci number F(n), or 1 if F(n) has no primitive prime factor.

%I A001578 M0603 N0217 #68 Jan 05 2025 19:51:32
%S A001578 1,1,2,3,5,1,13,7,17,11,89,1,233,29,61,47,1597,19,37,41,421,199,28657,
%T A001578 23,3001,521,53,281,514229,31,557,2207,19801,3571,141961,107,73,9349,
%U A001578 135721,2161,2789,211,433494437,43,109441,139,2971215073,1103,97,101
%N A001578 Smallest primitive prime factor of Fibonacci number F(n), or 1 if F(n) has no primitive prime factor.
%C A001578 A prime factor of F(n) is called primitive if it does not divide F(r) for any r < n.
%C A001578 A Fibonacci number can have more than one primitive factor; the primitive factors of F(19) are 37 and 113.
%C A001578 From _Robert Israel_, Oct 13 2015: (Start)
%C A001578 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 A001578 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 A001578 a(n) = n-1 iff n=2 or n-1 is in A000057.
%C A001578 a(n) = n+1 iff n+1 is a prime in A106535. (End)
%D A001578 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A001578 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A001578 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 A001578 Mansur S. Boase, <a href="https://web.archive.org/web/2024*/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 A001578 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 A001578 D. Jarden, <a href="https://web.archive.org/web/2024*/https://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 A001578 Blair Kelly, <a href="http://mersennus.net/fibonacci//">Fibonacci and Lucas Factorizations</a>
%F A001578 a(n) = 1 if and only if n = 1, 2, 6, or 12, by Carmichael's theorem. - _Jonathan Sondow_, Dec 07 2017
%p A001578 for n from 1 to 350 do
%p A001578   f:= combinat:-fibonacci(n);
%p A001578   if not isprime(n) then
%p A001578     for k in map(t -> n/t, numtheory:-factorset(n)) do
%p A001578        fk:= combinat:-fibonacci(k);
%p A001578        g:= igcd(f,fk);
%p A001578        while g > 1 do
%p A001578          f:= f/g;
%p A001578          g:= igcd(f,fk);
%p A001578        od
%p A001578     od
%p A001578   fi;
%p A001578   if f = 1 then A[n]:= 1; next fi;
%p A001578   F:= map(t -> t[1],ifactors(f,easy)[2]);
%p A001578   p:= select(type, F,integer);
%p A001578   if nops(p) >= 1 then A[n]:= min(p); next fi;
%p A001578   A[n]:= min(numtheory:-factorset(f));
%p A001578 od:
%p A001578 seq(A[i],i=1..350); # _Robert Israel_, Oct 13 2015
%t A001578 prms={}; Table[f=First/@FactorInteger[Fibonacci[n]]; p=Complement[f, prms]; prms=Join[prms, p]; If[p=={}, 1, First[p]], {n, 50}]
%o A001578 (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 A001578 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 A001578 nonn
%O A001578 1,3
%A A001578 _N. J. A. Sloane_
%E A001578 Edited by _T. D. Noe_, Apr 15 2004
%E A001578 Definition clarified at the suggestion of _Joerg Arndt_ by _Jonathan Sondow_, Oct 13 2015