cp's OEIS Frontend

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

%I A003318 M1052 #59 Oct 22 2023 00:16:41
%S A003318 1,2,4,7,12,18,28,39,55,74,100,127,167,208,261,322,399,477,581,686,
%T A003318 820,967,1142,1318,1545,1778,2053,2347,2697,3048,3486,3925,4441,4986,
%U A003318 5610,6250,7024,7799,8680,9604,10673,11743,13008,14274,15718,17239,18937,20636
%N A003318 a(n+1) = 1 + a( floor(n/1) ) + a( floor(n/2) ) + ... + a( floor(n/n) ).
%C A003318 Partial sums of A003238. - _Emeric Deutsch_, Dec 17 2014
%D A003318 M. K. Goldberg and É. M. Livshits, Minimal universal trees. (Russian) Mat. Zametki 4 1968 371-379.
%D A003318 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A003318 R. C. Read, personal communication.
%H A003318 Joerg Arndt, <a href="/A003318/b003318.txt">Table of n, a(n) for n = 1..1000</a>
%H A003318 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 A003318 R. C. Read, <a href="/A003318/a003318.pdf">Letter to N. J. A. Sloane and notes, May 1974</a>
%F A003318 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 A003318 A[1]:= 1;
%p A003318 for n from 1 to 99 do
%p A003318   A[n+1]:= 1 + add(A[floor(n/k)],k=1..n)
%p A003318 od:
%p A003318 seq(A[n],n=1..100); # _Robert Israel_, Aug 24 2014
%t A003318 a[1]=1;a[n_]:=1+Sum[a[Floor[(n-1)/k]],{k,n-1}]
%t A003318 Array[a,50] (* _Giorgos Kalogeropoulos_, Mar 31 2021 *)
%o A003318 (PARI) N=1001;
%o A003318 v=vector(N,n,n==1);
%o A003318 for(n=1, N-1, v[n+1]=1 + sum(k=1, n, v[floor(n/k)]) );
%o A003318 for(n=1, N, print(n," ",v[n])); \\ b-file
%o A003318 \\ _Joerg Arndt_, Aug 25 2014
%o A003318 (Python)
%o A003318 from functools import lru_cache
%o A003318 @lru_cache(maxsize=None)
%o A003318 def A003318(n):
%o A003318     if n == 0:
%o A003318         return 1
%o A003318     c, j = n+1, 1
%o A003318     k1 = (n-1)//j
%o A003318     while k1 > 1:
%o A003318         j2 = (n-1)//k1 + 1
%o A003318         c += (j2-j)*A003318(k1)
%o A003318         j, k1 = j2, (n-1)//j2
%o A003318     return c-j # _Chai Wah Wu_, Mar 31 2021
%Y A003318 Cf. A003238 (first differences).
%K A003318 nonn
%O A003318 1,2
%A A003318 _N. J. A. Sloane_