A003318 a(n+1) = 1 + a( floor(n/1) ) + a( floor(n/2) ) + ... + a( floor(n/n) ).

1, 2, 4, 7, 12, 18, 28, 39, 55, 74, 100, 127, 167, 208, 261, 322, 399, 477, 581, 686, 820, 967, 1142, 1318, 1545, 1778, 2053, 2347, 2697, 3048, 3486, 3925, 4441, 4986, 5610, 6250, 7024, 7799, 8680, 9604, 10673, 11743, 13008, 14274, 15718, 17239, 18937, 20636

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn

Comments

Partial sums of A003238. - Emeric Deutsch, Dec 17 2014

References

• M. K. Goldberg and É. M. Livshits, Minimal universal trees. (Russian) Mat. Zametki 4 1968 371-379.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
• R. C. Read, personal communication.

Links

• Joerg Arndt, Table of n, a(n) for n = 1..1000
• M. K. Gol'dberg and É. M. Livshits, On minimal universal trees, Mathematical notes of the Academy of Sciences of the USSR, September 1968, Volume 4, Issue 3, pp 713-717, translated from Matematicheskie Zametki, Vol. 4, No. 3, pp. 371-379, September, 1968.
• R. C. Read, Letter to N. J. A. Sloane and notes, May 1974

Crossrefs

Cf. A003238 (first differences).

Programs

Maple

A[1]:= 1;
for n from 1 to 99 do
  A[n+1]:= 1 + add(A[floor(n/k)],k=1..n)
od:
seq(A[n],n=1..100); # Robert Israel, Aug 24 2014

Mathematica

a[1]=1;a[n_]:=1+Sum[a[Floor[(n-1)/k]],{k,n-1}]
Array[a,50] (* Giorgos Kalogeropoulos, Mar 31 2021 *)

PARI

N=1001;
v=vector(N,n,n==1);
for(n=1, N-1, v[n+1]=1 + sum(k=1, n, v[floor(n/k)]) );
for(n=1, N, print(n," ",v[n])); \\ b-file
\\ Joerg Arndt, Aug 25 2014

Python

from functools import lru_cache
@lru_cache(maxsize=None)
def A003318(n):
    if n == 0:
        return 1
    c, j = n+1, 1
    k1 = (n-1)//j
    while k1 > 1:
        j2 = (n-1)//k1 + 1
        c += (j2-j)*A003318(k1)
        j, k1 = j2, (n-1)//j2
    return c-j # Chai Wah Wu, Mar 31 2021

Formula

G.f. A(x) satisfies: A(x) = (x/(1 - x)) * (1 + Sum_{k>=1} (1 - x^k) * A(x^k)). - Ilya Gutkovskiy, Feb 25 2020