A022307 Number of distinct prime factors of n-th Fibonacci number.

0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 1, 2, 1, 2, 3, 3, 1, 3, 2, 4, 3, 2, 1, 4, 2, 2, 4, 4, 1, 5, 2, 4, 3, 2, 3, 5, 3, 3, 3, 6, 2, 5, 1, 5, 5, 3, 1, 6, 3, 5, 3, 4, 2, 6, 4, 6, 5, 3, 2, 8, 2, 3, 5, 6, 3, 5, 3, 5, 5, 7, 2, 8, 2, 4, 5, 5, 4, 6, 2, 9, 7, 3, 1, 9, 4, 3, 4, 9, 2, 10, 4, 6, 4, 2, 6, 9, 4, 5, 6

Offset: 0

Author

Clark Kimberling

Keywords

• nonn

Comments

Although every prime divides some Fibonacci number, this is not true for the Lucas numbers. Exactly 1/3 of all primes do not divide any Lucas number. See Lagarias and Moree for more details. - Jonathan Vos Post, Dec 06 2006

First occurrence of k: 0, 3, 8, 15, 20, 30, 40, 70, 60, 80, 90, 140, 176, 120, 168, 180, 324, 252, 240, 378, ..., . - Robert G. Wilson v, Dec 10 2006 [Other than 0, this is sequence A060320. - Jon E. Schoenfield, Dec 30 2016]

Row lengths of table A060442. - Reinhard Zumkeller, Aug 30 2014

If k properly divides n then a(n) >= a(k) + 1, except for a(6) = a(3) = 1. - Robert Israel, Aug 18 2015

References

• Alfred Brousseau, Fibonacci and Related Number Theoretic Tables, The Fibonacci Association, 1972, pages 1-8.

Links

• Max Alekseyev, Table of n, a(n) for n = 0..1422 (terms 0..1000 and 1001..1408 from T. D. Noe and Amiram Eldar, respectively).
• Blair Kelly, Fibonacci and Lucas Factorizations
• J. C. Lagarias, The set of primes dividing the Lucas numbers has density 2/3, Pacific J. Math., 118. No. 2, (1985), 449-461.
• J. C. Lagarias, Errata to: The set of primes dividing the Lucas numbers has density 2/3, Pacific J. Math., 162, No. 2, (1994), 393-396.
• Hisanori Mishima, WIFC (World Integer Factorization Center), Fibonacci numbers (n = 1 to 100, n = 101 to 200, n = 201 to 300, n = 301 to 400, n = 401 to 480).
• Pieter Moree, Counting Divisors of Lucas Numbers, Pacific J. Math, Vol. 186, No. 2, 1998, pp. 267-284.
• Eric Weisstein's World of Mathematics, Fibonacci Number

Crossrefs

Cf. A038575 (number of prime factors, counting multiplicity), A086597 (number of primitive prime factors).

Cf. A000032, A000040, A000045, A001221, A053028.

Cf. A060442, A086598 (omega(Lucas(n))).

Cf. A060320. - Jon E. Schoenfield, Dec 30 2016

Programs

Haskell

a022307 n = if n == 0 then 0 else a001221 $ a000045 n
-- Reinhard Zumkeller, Aug 30 2014

Magma

[0] cat [#PrimeDivisors(Fibonacci(n)): n in [1..100]]; // Vincenzo Librandi, Jul 26 2017

Mathematica

Table[Length[FactorInteger[Fibonacci[n]]], {n, 150}]

PARI

a(n)=omega(fibonacci(n)) \\ Charles R Greathouse IV, Feb 03 2014

Formula

a(n) = Sum{d|n} A086597(d), Mobius transform of A086597.

a(n) = A001221(A000045(n)) = omega(F(n)). - Jonathan Vos Post, Dec 06 2006