OFFSET
0,4
COMMENTS
LINKS
Amiram Eldar, Table of n, a(n) for n = 0..10000
Hsien-Kuei Hwang, Svante Janson and Tsung-Hsi Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47. Also first authors' copy, 2016.
Jeffrey C. Lagarias and Harsh Mehta, Products of Binomial Coefficients and Unreduced Farey Fractions, arXiv:1409.4145 [math.NT], 2014, see a(n) = ord_p(N*_n) for p=2 in theorem 4.1.
A. Mir, F. Rossello and L. Rotger, A new balance index for phylogenetic trees, arXiv preprint arXiv:1202.1223 [q-bio.PE], 2012, see proposition 15, a(n) = x(n) = f(n+1).
FORMULA
a(n) = Sum_{i=0..n} A011371(i).
From Kevin Ryde, Oct 29 2021: (Start)
a(n) = n*(n+1)/2 - A000788(n).
a(n) ~ (n^2)/2 + O(n*log_2(n)). [Lagarias and Mehta, theorem 4.2 with p=2]
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).
(End)
MAPLE
a:= proc(n) option remember; `if`(n<1, 0,
a(n-1)+n-add(i, i=Bits[Split](n)))
end:
seq(a(n), n=0..54); # Alois P. Heinz, Oct 30 2021
MATHEMATICA
Accumulate[Table[n-DigitCount[n, 2, 1], {n, 0, 130}]] (* Harvey P. Dale, Feb 26 2015 *)
a[n_] := IntegerExponent[BarnesG[n + 2], 2]; Array[a, 100, 0] (* Amiram Eldar, Aug 08 2024 *)
PROG
(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
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Jonathan Vos Post, Mar 23 2010
STATUS
approved