OFFSET
1,2
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
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
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 *)
PROG
(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
CROSSREFS
KEYWORD
nonn
AUTHOR
STATUS
approved