A086600 Number of primitive prime factors in the n-th Lucas number A000204(n).

0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 1, 2, 2, 1, 2, 2, 3, 2, 2, 1, 2, 1, 2, 2, 2, 1, 1, 2, 1, 2, 2, 3, 2, 1, 1, 2, 2, 3, 1, 2, 1, 2, 1, 1, 1, 2, 2, 2, 1, 2, 1, 1, 1, 2, 3, 2, 2, 2, 1, 2, 2, 2, 1, 1, 2, 2, 3, 3, 1, 2, 2, 3, 2, 3, 2, 3, 3, 2

Offset: 1

Author

T. D. Noe, Jul 24 2003

Keywords

• hard
• nonn

Comments

A prime factor of Lucas(n) is called primitive if it does not divide Lucas(r) for any r < n. It can be shown that there is at least one primitive prime factor for n > 6. When n is prime, all the prime factors of Lucas(n) are primitive.

Examples

			a(22) = 2 because Lucas(22) = 3*43*307 and neither 43 nor 307 divide a smaller Lucas number.
		

Links

• Max Alekseyev, Table of n, a(n) for n = 1..1411 (first 1000 terms from T. D. Noe)
• Blair Kelly, Fibonacci and Lucas Factorizations,
• Eric Weisstein's World of Mathematics, Lucas Number.

Crossrefs

Cf. A000204 (Lucas numbers), A058036, A086598 (number of distinct prime factors), A086599 (number of prime factors, counting multiplicity), A274333.

Programs

Magma

lst:=[]; pr:=1; for n in [1..105] do pd:=PrimeDivisors(Lucas(n)); d:=1; t:=0; for c in [1..#pd] do f:=pd[c]; if Gcd(pr, f) eq 1 then t+:=1; else d:=d*f; end if; end for; Append(~lst, t); pr:=pr*Truncate(Lucas(n)/d); end for; lst; // Arkadiusz Wesolowski, Jun 22 2016

Mathematica

Lucas[n_] := Fibonacci[n+1] + Fibonacci[n-1]; pLst={}; Join[{0}, Table[f=Transpose[FactorInteger[Lucas[n]]][[1]]; f=Complement[f, pLst]; cnt=Length[f]; pLst=Union[pLst, f]; cnt, {n, 2, 150}]]

Formula

a(n) = Sum{d|n and n/d odd} mu(n/d) a(d) -1 if 6|n and n/6 is a power of 2.