login
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.
4

%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