cp's OEIS Frontend

A077071 Row sums of A077070.

%I A077071 #54 Nov 13 2024 16:43:21
%S A077071 0,2,8,16,30,46,66,88,118,150,186,224,268,314,364,416,478,542,610,680,
%T A077071 756,834,916,1000,1092,1186,1284,1384,1490,1598,1710,1824,1950,2078,
%U A077071 2210,2344,2484,2626,2772,2920,3076,3234,3396,3560,3730,3902,4078,4256
%N A077071 Row sums of A077070.
%C A077071 Conjecture: given n balls, all of which are initially in the first of n numbered boxes, a(n-1) is the number of steps of the following process required to move them all to the last box. A step consists of first identifying j, the lowest numbered box which has at least one ball. If it has only one ball then move it to box j+1; otherwise move half its balls rounded down to box j+1 and (unless it's the first box) half its balls rounded down to box j-1. See also A356254. - _Mikhail Kurkov_, Nov 24 2022
%H A077071 Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, <a href="http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf">Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications</a>, preprint, 2016.
%H A077071 Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, <a href="http://doi.org/10.1145/3127585">Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications</a>, ACM Transactions on Algorithms 13:4 (2017), #47.
%H A077071 Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences with (relatively) simple generating functions</a>, 2004.
%H A077071 Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions (ps file)</a>.
%H A077071 Ralf Stephan, <a href="/A067699/a067699.pdf">Table of generating functions (pdf file)</a>.
%F A077071 a(n) is asymptotic to 2*n^2 and it seems that a(n) = 2*n^2 + O(n^(3/2)) (where O(n^(3/2))/n^(3/2) is bounded and O(n^(3/2)) < 0). - _Benoit Cloitre_, Oct 30 2002
%F A077071 G.f.: (1/(1-x)^2) * Sum_{k>=0} t/(1-t) where t = x^2^k. Twice the value of the partial sum of A005187. a(0) = 0, a(2n) = a(n) + a(n-1) + 4*n^2 + 2*n, a(2n+1) = 2*a(n) + 4*n^2 + 6*n + 2. - _Ralf Stephan_, Sep 12 2003
%F A077071 a(n) = 2*n*(n+1) - 2*A000788(n) and therefore asymptotically a(n) = 2*n^2 - n*log_2(n) + O(n). - _Peter J. Taylor_, Dec 21 2022
%o A077071 (PARI) {a(n) = sum( k=0, n, -valuation( polcoeff( pollegendre(2*n), 2*k), 2))}
%o A077071 (PARI) a(n)=my(P=pollegendre(2*n)); -sum(k=0,n,valuation(polcoeff(P,2*k), 2)) \\ _Charles R Greathouse IV_, Apr 12 2012
%o A077071 (Python)
%o A077071 def A077071(n): return ((n+1)*(n-n.bit_count())<<1)-sum((m:=1<<j)*((k:=n>>j)-(r if n<<1>=m*(r:=k<<1|1) else 0)) for j in range(1,n.bit_length()+1)) # _Chai Wah Wu_, Nov 12 2024
%Y A077071 Cf. A077070, A356254.
%K A077071 nonn
%O A077071 0,2
%A A077071 _Michael Somos_, Oct 25 2002