%I #42 Oct 30 2021 17:02:08
%S 0,0,1,2,5,8,12,16,23,30,38,46,56,66,77,88,103,118,134,150,168,186,
%T 205,224,246,268,291,314,339,364,390,416,447,478,510,542,576,610,645,
%U 680,718,756,795,834,875,916,958,1000,1046,1092,1139,1186,1235,1284,1334
%N Partial sums of A011371.
%C Exponent of 2 in the superfactorials, i.e., a(n) = A007814(A000178(n)). - _Ralf Stephan_, Jan 03 2014
%H Hsien-Kuei Hwang, Svante Janson and Tsung-Hsi Tsai, <a href="https://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. Also <a href="http://algo.stat.sinica.edu.tw/hk/?p=1043">first authors' copy</a>, 2016.
%H Jeffrey C. Lagarias and Harsh Mehta, <a href="http://arxiv.org/abs/1409.4145">Products of Binomial Coefficients and Unreduced Farey Fractions</a>, arXiv:1409.4145 [math.NT], 2014, see a(n) = ord_p(N*_n) for p=2 in theorem 4.1.
%H A. Mir, F. Rossello and L. Rotger, <a href="http://arxiv.org/abs/1202.1223">A new balance index for phylogenetic trees</a>, arXiv preprint arXiv:1202.1223 [q-bio.PE], 2012, see proposition 15, a(n) = x(n) = f(n+1).
%F a(n) = Sum_{i=0..n} A011371(i).
%F From _Kevin Ryde_, Oct 29 2021: (Start)
%F a(n) = n*(n+1)/2 - A000788(n).
%F a(n) ~ (n^2)/2 + O(n*log_2(n)). [Lagarias and Mehta, theorem 4.2 with p=2]
%F a(n) = ( (n+1)^2 - Sum_{i=1..k} (e[i]+2*i-1) * 2^e[i] )/2, where binary expansion n+1 = 2^e[1] + ... + 2^e[k] with descending exponents e[1] > e[2] > ... > e[k] (A272011).
%F (End)
%p a:= proc(n) option remember; `if`(n<1, 0,
%p a(n-1)+n-add(i, i=Bits[Split](n)))
%p end:
%p seq(a(n), n=0..54); # _Alois P. Heinz_, Oct 30 2021
%t Accumulate[Table[n-DigitCount[n,2,1],{n,0,130}]] (* _Harvey P. Dale_, Feb 26 2015 *)
%o (PARI) a(n) = n++; my(v=binary(n),t=#v-1); for(i=1,#v, if(v[i],v[i]=t++,t--)); (n^2 - fromdigits(v,2))>>1; \\ _Kevin Ryde_, Oct 29 2021
%Y Cf. A000120, A011371 (first differences).
%Y Cf. A000178 (superfactorials), A007814 (2-adic valuation), A272011 (binary exponents).
%Y Cf. A249152 (hyperfactorial valuation), A187059 (binomial valuation), A173345 (superfactorial 10-valuation).
%K easy,nonn
%O 0,4
%A _Jonathan Vos Post_, Mar 23 2010
|