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,4

Comments

Exponent of 2 in the superfactorials, i.e., a(n) = A007814(A000178(n)). - Ralf Stephan, Jan 03 2014

Links

Table of n, a(n) for n=0..54.

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 *)

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

Cf. A000120, A011371 (first differences).

Cf. A000178 (superfactorials), A007814 (2-adic valuation), A272011 (binary exponents).

Cf. A249152 (hyperfactorial valuation), A187059 (binomial valuation), A173345 (superfactorial 10-valuation).

Sequence in context: A213707 A229154 A362601 * A108577 A272719 A297834

Adjacent sequences: A174602 A174603 A174604 * A174606 A174607 A174608

Keyword

easy,nonn

Author

Jonathan Vos Post, Mar 23 2010

Status

approved