|
|
A003318
|
|
a(n+1) = 1 + a( floor(n/1) ) + a( floor(n/2) ) + ... + a( floor(n/n) ).
(Formerly M1052)
|
|
4
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
|
|
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
|
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.
|
|
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:
|
|
MATHEMATICA
|
a[1]=1; a[n_]:=1+Sum[a[Floor[(n-1)/k]], {k, n-1}]
|
|
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
(Python)
from functools import lru_cache
@lru_cache(maxsize=None)
if n == 0:
return 1
c, j = n+1, 1
k1 = (n-1)//j
while k1 > 1:
j2 = (n-1)//k1 + 1
j, k1 = j2, (n-1)//j2
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|