login
Smallest primitive prime factor of Fibonacci number F(n), or 1 if F(n) has no primitive prime factor.
(Formerly M0603 N0217)
14

%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