A119737 a(n) = Sum_{k=1..n} Fibonacci(floor(n/k)).

1, 2, 4, 6, 9, 14, 20, 30, 45, 69, 104, 165, 255, 405, 642, 1029, 1640, 2645, 4243, 6852, 11040, 17840, 28787, 46567, 75227, 121685, 196725, 318269, 514688, 832760, 1346990, 2179417, 3525722, 5704642, 9229228, 14933176, 24160642, 39092592, 63250500, 102341286, 165587273

Offset

1,2

Links

John Tyler Rascoe, Table of n, a(n) for n = 1..500

Formula

a(n) = n + Sum_{k=1..n-2} Fibonacci(k)*floor(n/(k+2)), for n >= 2.

G.f.: 1/(1-x) * Sum_{i>0} f(x^i) * (1 - x^i) where f(x) is the g.f. of A000045. - John Tyler Rascoe, Feb 02 2026

Maple

a:= n-> add(combinat[fibonacci](floor(n/k)), k=1..n):
seq(a(n), n=1..41);  # Alois P. Heinz, Feb 04 2026

Mathematica

f[n_] := Sum[ Fibonacci@Floor[n/k], {k, n}] (* or *) f[n_] := n + Sum[Fibonacci@k*Floor[n/(k + 2)], {k, n - 2}]; Array[f, 38] (* Robert G. Wilson v, Jun 19 2006 *)

Prog

(Python)
from sympy import fibonacci
def A119737(n):
    c, j = 0, 1
    while j <= n:
        c += fibonacci(k:=n//j)*(-j+(j:=n//k+1))
    return c # Chai Wah Wu, Jan 29 2026
(PARI)
A_x(N) = {my(x='x+O('x^(N+1))); Vec(1/(1-x)*sum(i=1, N, x^i*(1-x^i)/(1-x^i-x^(2*i))))} \\ John Tyler Rascoe, Feb 02 2026

Crossrefs

Cf. A000045, A070964.

Sequence in context: A139135 A097197 A260600 * A038718 A378307 A042942

Adjacent sequences: A119734 A119735 A119736 * A119738 A119739 A119740

Keyword

easy,nonn

Author

Leroy Quet, Jun 15 2006

Extensions

More terms from Robert G. Wilson v and Joshua Zucker, Jun 19 2006

Status

approved