A290845 a(1) = 1; a(n) = Sum_{k=1..n} a(ceiling((n-1)/k)).

1, 2, 4, 8, 14, 24, 36, 56, 78, 110, 148, 200, 254, 334, 416, 522, 644, 798, 954, 1162, 1372, 1640, 1934, 2284, 2636, 3090, 3556, 4106, 4694, 5394, 6096, 6972, 7850, 8882, 9972, 11220, 12500, 14048, 15598, 17360, 19208, 21346, 23486, 26016, 28548, 31436, 34478, 37874, 41272, 45246

Offset: 1

Author

Ilya Gutkovskiy, Aug 12 2017

Keywords

• nonn

Examples

			a(1) = 1;
a(2) = a(ceiling(1/1)) + a(ceiling(1/2)) = a(1) + a(1) = 2;
a(3) = a(ceiling(2/1)) + a(ceiling(2/2)) + a(ceiling(2/3)) = a(2) + a(1) + a(1) = 4, etc.
		

Crossrefs

Cf. A003318, A025523, A068336 (first differences), A078346.

Programs

Mathematica

a[1] = 1; a[n_] := a[n] = Sum[a[Ceiling[(n - 1)/k]], {k, 1, n}]; Table[a[n], {n, 50}]

Python

from functools import lru_cache
@lru_cache(maxsize=None)
def A290845(n):
    if n == 1:
        return 1
    c, j, k1 = n, 1, n-2
    while k1 > 1:
        j2 = (n-2)//k1 + 1
        c += (j2-j)*A290845(k1+1)>>1
        j, k1 = j2, (n-2)//j2
    return c-j<<1 # Chai Wah Wu, Apr 29 2025

Formula

a(n) = 2*A003318(n-1) for n > 1.