login
a(n+1) = 1 + a( floor(n/1) ) + a( floor(n/2) ) + ... + a( floor(n/n) ).
(Formerly M1052)
4

%I M1052 #59 Oct 22 2023 00:16:41

%S 1,2,4,7,12,18,28,39,55,74,100,127,167,208,261,322,399,477,581,686,

%T 820,967,1142,1318,1545,1778,2053,2347,2697,3048,3486,3925,4441,4986,

%U 5610,6250,7024,7799,8680,9604,10673,11743,13008,14274,15718,17239,18937,20636

%N a(n+1) = 1 + a( floor(n/1) ) + a( floor(n/2) ) + ... + a( floor(n/n) ).

%C Partial sums of A003238. - _Emeric Deutsch_, Dec 17 2014

%D M. K. Goldberg and É. M. Livshits, Minimal universal trees. (Russian) Mat. Zametki 4 1968 371-379.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D R. C. Read, personal communication.

%H Joerg Arndt, <a href="/A003318/b003318.txt">Table of n, a(n) for n = 1..1000</a>

%H M. K. Gol'dberg and É. M. Livshits, <a href="http://dx.doi.org/10.1007/BF01116454">On minimal universal trees</a>, 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.

%H R. C. Read, <a href="/A003318/a003318.pdf">Letter to N. J. A. Sloane and notes, May 1974</a>

%F 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

%p A[1]:= 1;

%p for n from 1 to 99 do

%p A[n+1]:= 1 + add(A[floor(n/k)],k=1..n)

%p od:

%p seq(A[n],n=1..100); # _Robert Israel_, Aug 24 2014

%t a[1]=1;a[n_]:=1+Sum[a[Floor[(n-1)/k]],{k,n-1}]

%t Array[a,50] (* _Giorgos Kalogeropoulos_, Mar 31 2021 *)

%o (PARI) N=1001;

%o v=vector(N,n,n==1);

%o for(n=1, N-1, v[n+1]=1 + sum(k=1, n, v[floor(n/k)]) );

%o for(n=1, N, print(n," ",v[n])); \\ b-file

%o \\ _Joerg Arndt_, Aug 25 2014

%o (Python)

%o from functools import lru_cache

%o @lru_cache(maxsize=None)

%o def A003318(n):

%o if n == 0:

%o return 1

%o c, j = n+1, 1

%o k1 = (n-1)//j

%o while k1 > 1:

%o j2 = (n-1)//k1 + 1

%o c += (j2-j)*A003318(k1)

%o j, k1 = j2, (n-1)//j2

%o return c-j # _Chai Wah Wu_, Mar 31 2021

%Y Cf. A003238 (first differences).

%K nonn

%O 1,2

%A _N. J. A. Sloane_