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,2

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

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

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 *)

Prog

(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

Crossrefs

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

Sequence in context: A063473 A096859 A301304 * A358333 A237168 A350959

Adjacent sequences: A005083 A005084 A005085 * A005087 A005088 A005089

Keyword

nonn

Author

N. J. A. Sloane

Extensions

More terms from James A. Sellers, Feb 19 2001

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

Status

approved