A076984 Number of Fibonacci numbers that are divisors of the n-th Fibonacci number.

1, 1, 2, 2, 2, 3, 2, 3, 3, 3, 2, 5, 2, 3, 4, 4, 2, 5, 2, 5, 4, 3, 2, 7, 3, 3, 4, 5, 2, 7, 2, 5, 4, 3, 4, 8, 2, 3, 4, 7, 2, 7, 2, 5, 6, 3, 2, 9, 3, 5, 4, 5, 2, 7, 4, 7, 4, 3, 2, 11, 2, 3, 6, 6, 4, 7, 2, 5, 4, 7, 2, 11, 2, 3, 6, 5, 4, 7, 2, 9, 5, 3, 2, 11, 4, 3, 4, 7, 2, 11, 4, 5, 4, 3, 4, 11, 2, 5, 6, 8, 2, 7, 2

Offset: 1

Author

Amarnath Murthy, Oct 25 2002

Keywords

• nonn

Comments

a(A001605(n)) = 2; a(A105802(n)) = n.

It is well known that if k is a divisor of n then F(k) divides F(n). Hence if n has d divisors, one expects that a(n)=d. However because F(1)=F(2)=1, there is one fewer Fibonacci divisor when n is even. So for even n, a(n)=d-1. - T. D. Noe, Jan 18 2006

Examples

			n=12, A000045(12)=144: 5 of the 15 divisors of 144 are also Fibonacci numbers, a(12) = #{1, 2, 3, 8, 144} = 5.
		

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000
• Eric Weisstein's World of Mathematics, Fibonacci Number

Crossrefs

Cf. A000005, A063375, A000045, A105800.

Cf. A076985.

Cf. A068499.

Programs

Maple

with(combinat, fibonacci):a[1] := 1:for i from 2 to 229 do s := 0:for j from 2 to i do if((fibonacci(i) mod fibonacci(j))=0) then s := s+1:fi:od:a[i] := s:od:seq(a[l],l=2..229);

Mathematica

Table[s=DivisorSigma[0, n]; If[OddQ[n], s, s-1], {n, 100}] (Noe)

PARI

{a(n)=if(n<1, 0, numdiv(n)+n%2-1)} /* Michael Somos, Sep 03 2006 */

PARI

{a(n)=if(n<1, 0, sumdiv(n,d, d!=2))} /* Michael Somos, Sep 03 2006 */

Formula

a(n) = A023645(n) + 1. - T. D. Noe, Jan 18 2006

a(n) = tau(n) - [n is even] = A000005(n) - A059841(n). Proof: gcd(Fib(m), Fib(n)) = Fib(gcd(m, n)) and Fib(2) = 1. - Olivier Wittenberg, following a conjecture of Ralf Stephan, Sep 28 2004

The number of divisors of n excluding 2.

a(2n) = A066660(n). a(2n-1) = A099774(n). - Michael Somos, Sep 03 2006

a(3*2^(Prime(n-1)-1)) = 2n + 1 for n > 3. a(3*2^A068499[n]) = 2n + 1, where A068499(n) = {1,2,3,4,6,10,12,16,18,...}. - Alexander Adamchuk, Sep 15 2006

Extensions

Corrected and extended by Sascha Kurz, Jan 26 2003

Edited by N. J. A. Sloane, Sep 14 2006. Some of the comments and formulas may need to be adjusted to reflect the new offset.