|
%I #24 Oct 28 2022 08:57:58
%S 0,1,4,8,16,25,36,48,68,89,112,136,164,193,224,256,304,353,404,456,
%T 512,569,628,688,756,825,896,968,1044,1121,1200,1280,1392,1505,1620,
%U 1736,1856,1977,2100,2224,2356,2489,2624,2760,2900,3041
%N a(0)=0, a(2*n) = 2*a(n) + 2*a(n-1) + n^2 + n, a(2*n+1) = 4*a(n) + (n+1)^2.
%H G. C. Greubel, <a href="/A022560/b022560.txt">Table of n, a(n) for n = 0..5000</a>
%H Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, <a href="https://arxiv.org/abs/2210.10968">Identities and periodic oscillations of divide-and-conquer recurrences splitting at half</a>, arXiv:2210.10968 [cs.DS], 2022, pp. 39-40, 44, 51, 60.
%H R. Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>
%H R. Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>
%F Let a(i, n) = 2^(i-1)*floor(1/2 + n/2^i); sequence is a(n) = Sum_{i=1} a(i, n)*(n - a(i, n)).
%F Second differences give A006519.
%F Also a(1)=0 and a(n) = floor(n^2/4) + a(floor(n/2)) + a(ceiling(n/2)).
%F G.f.: 1/(1-x)^2 * (x/(1-x) + Sum_{k>=1} 2^(k-1)*x^2^k/(1-x^2^k)). - _Ralf Stephan_, Apr 17 2003
%F a(0)=0, a(2n) = 2*a(n) + 2*a(n-1) + n^2 + n, a(2n+1) = 4a(n)+(n+1)^2. - _Ralf Stephan_, Sep 13 2003
%t a[n_]:= If[n==0, 0, If[Mod[n, 2]==0, 2*a[n/2] + 2*a[n/2-1] +(n/2)^2 +(n/2), 4*a[(n-1)/2] +((n+1)/2)^2]]; Table[a[n], {n, 0, 50}] (* _G. C. Greubel_, Feb 26 2018 *)
%o (PARI) a(n) = if (n==0, 0, if (n % 2, my(nn = (n-1)/2); 4*a(nn)+(nn+1)^2, my(nn = n/2); 2*a(nn)+2*a(nn-1)+nn^2+nn)) \\ _Michel Marcus_, Jun 27 2013
%o (Sage)
%o def a(n):
%o if (n==0): return 0
%o elif (n%2==0): return 2*a(n/2) + 2*a(n/2 -1) +(n/2)^2 +(n/2)
%o else: return 4*a((n-1)/2) +((n+1)/2)^2
%o [a(n) for n in (0..50)] # _G. C. Greubel_, Jun 13 2019
%Y First differences are in A006520.
%Y Cf. A070263.
%K nonn
%O 0,3
%A Andre Kundgen (kundgen(AT)math.uiuc.edu)
%E More terms from _Ralf Stephan_, Sep 13 2003
|
