cp's OEIS Frontend

A174605 Partial sums of A011371.

%I A174605 #51 Nov 12 2024 10:59:57
%S A174605 0,0,1,2,5,8,12,16,23,30,38,46,56,66,77,88,103,118,134,150,168,186,
%T A174605 205,224,246,268,291,314,339,364,390,416,447,478,510,542,576,610,645,
%U A174605 680,718,756,795,834,875,916,958,1000,1046,1092,1139,1186,1235,1284,1334
%N A174605 Partial sums of A011371.
%C A174605 Exponent of 2 in the superfactorials, i.e., a(n) = A007814(A000178(n)). - _Ralf Stephan_, Jan 03 2014
%H A174605 Amiram Eldar, <a href="/A174605/b174605.txt">Table of n, a(n) for n = 0..10000</a>
%H A174605 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 A174605 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 A174605 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 A174605 a(n) = Sum_{i=0..n} A011371(i).
%F A174605 From _Kevin Ryde_, Oct 29 2021: (Start)
%F A174605 a(n) = n*(n+1)/2 - A000788(n).
%F A174605 a(n) ~ (n^2)/2 + O(n*log_2(n)). [Lagarias and Mehta, theorem 4.2 with p=2]
%F A174605 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 A174605 (End)
%p A174605 a:= proc(n) option remember; `if`(n<1, 0,
%p A174605       a(n-1)+n-add(i, i=Bits[Split](n)))
%p A174605     end:
%p A174605 seq(a(n), n=0..54);  # _Alois P. Heinz_, Oct 30 2021
%t A174605 Accumulate[Table[n-DigitCount[n,2,1],{n,0,130}]] (* _Harvey P. Dale_, Feb 26 2015 *)
%t A174605 a[n_] := IntegerExponent[BarnesG[n + 2], 2]; Array[a, 100, 0] (* _Amiram Eldar_, Aug 08 2024 *)
%o A174605 (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
%o A174605 (Python)
%o A174605 def A174605(n): return (n*(n+1)>>1)-(n+1)*n.bit_count()-(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))>>1)  # _Chai Wah Wu_, Nov 12 2024
%Y A174605 Cf. A000120, A011371 (first differences).
%Y A174605 Cf. A000178 (superfactorials), A007814 (2-adic valuation), A272011 (binary exponents).
%Y A174605 Cf. A249152 (hyperfactorial valuation), A187059 (binomial valuation), A173345 (superfactorial 10-valuation).
%K A174605 easy,nonn
%O A174605 0,4
%A A174605 _Jonathan Vos Post_, Mar 23 2010