A005086 Number of Fibonacci numbers 1,2,3,5,... dividing n.

1, 2, 2, 2, 2, 3, 1, 3, 2, 3, 1, 3, 2, 2, 3, 3, 1, 3, 1, 3, 3, 2, 1, 4, 2, 3, 2, 2, 1, 4, 1, 3, 2, 3, 2, 3, 1, 2, 3, 4, 1, 4, 1, 2, 3, 2, 1, 4, 1, 3, 2, 3, 1, 3, 3, 3, 2, 2, 1, 4, 1, 2, 3, 3, 3, 3, 1, 3, 2, 3, 1, 4, 1, 2, 3, 2, 1, 4, 1, 4, 2, 2, 1, 4, 2, 2, 2, 3, 2, 4, 2, 2, 2, 2, 2, 4, 1, 2, 2, 3, 1, 4, 1, 4, 4

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn

Comments

Indices of records are in A129655. - R. J. Mathar, Nov 02 2007

Links

• Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000045, A038663, A051731, A010056, A072649, A079586, A129655.

Programs

Maple

with(combinat): for n from 1 to 200 do printf(`%d,`,sum(floor(n/fibonacci(k))-floor((n-1)/fibonacci(k)), k=2..15)) od:

Mathematica

f[n_] := Block[{k = 1}, While[Fibonacci[k] <= n, k++ ]; Count[ Mod[n, Array[ Fibonacci, k - 1]], 0] - 1]; Array[f, 105] (* Robert G. Wilson v, Dec 10 2006 *)

PARI

isfib(n)=my(k=n^2); k+=(k+1)<<2; issquare(k) || (n>0 && issquare(k-8))
a(n)=sumdiv(n,d,isfib(d)) \\ Charles R Greathouse IV, Nov 06 2014

Python

from sympy import divisors
from sympy.ntheory.primetest import is_square
def A005086(n): return sum(1 for d in divisors(n,generator=True) if is_square(m:=5*d**2-4) or is_square(m+8)) # Chai Wah Wu, Mar 30 2023

Python

from itertools import count, takewhile
def F(f=1, g=1):
    while True:
        f, g = g, f+g;
        yield f
def a(n):
    return sum(1 for f in takewhile(lambda x: x<=n, F()) if n%f == 0)
print([a(n) for n in range(1, 106)]) # Michael S. Branicky, Apr 03 2023

Formula

a(n) <= A072649(n). - Robert G. Wilson v, Dec 10 2006

Equals A051731 * A010056. - Gary W. Adamson, Nov 06 2007

G.f.: Sum_{n>=2} x^F(n)/(1-x^F(n)) where F(n) = A000045(n). - Joerg Arndt, Jan 06 2015

Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = A079586 - 1 = 2.359885... . - Amiram Eldar, Dec 31 2023

Extensions

More terms from James Sellers, Feb 19 2001

Incorrect comment removed by Charles R Greathouse IV, Nov 06 2014