A174605 Partial sums of A011371.
0, 0, 1, 2, 5, 8, 12, 16, 23, 30, 38, 46, 56, 66, 77, 88, 103, 118, 134, 150, 168, 186, 205, 224, 246, 268, 291, 314, 339, 364, 390, 416, 447, 478, 510, 542, 576, 610, 645, 680, 718, 756, 795, 834, 875, 916, 958, 1000, 1046, 1092, 1139, 1186, 1235, 1284, 1334
Offset: 0
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).
Crossrefs
Programs
-
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 *) -
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
-
Python
def A174605(n): return (n*(n+1)>>1)-(n+1)*n.bit_count()-(sum((m:=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)
Comments