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