login
Partial sums of A119387.
3

%I #34 Oct 01 2024 08:50:57

%S 0,0,1,1,3,4,6,6,9,11,14,15,18,20,23,23,27,30,34,36,40,43,47,48,52,55,

%T 59,61,65,68,72,72,77,81,86,89,94,98,103,105,110,114,119,122,127,131,

%U 136,137,142,146,151,154,159,163,168,170,175,179,184,187,192

%N Partial sums of A119387.

%H Antoine Mathys, <a href="/A373709/b373709.txt">Table of n, a(n) for n = 0..9999</a>

%H Project Euler, <a href="https://projecteuler.net/problem=704">Problem 704 - Factors of Two in Binomial Coefficients</a>.

%F a(n) = Sum_{m = 0..n} A119387(m).

%F a(n) = (n+2)*d - 2*n - 2^d + p - 1, with d = bit_width(n+1) = A070939(n+1) and p = popcount(n+1) = A000120(n+1).

%F a(n) = A001855(n+2) - A005187(n+1).

%p a:= proc(n) option remember; `if`(n<0, 0,

%p a(n-1)+ilog2(n+1)-padic[ordp](n+1, 2))

%p end:

%p seq(a(n), n=0..60); # _Alois P. Heinz_, Jun 23 2024

%t Accumulate[Table[BitLength[k] - 1 - IntegerExponent[k, 2], {k, 100}]] (* _Paolo Xausa_, Oct 01 2024 *)

%o (PARI)

%o bit_width(n)=logint(n,2)+1;

%o a(n)=my(d=bit_width(n+1),p=hammingweight(n+1));(n+2)*d-2*n-2^d+p-1;

%Y Cf. A000120, A001855, A005187, A070939, A119387.

%K nonn,base,easy

%O 0,5

%A _Antoine Mathys_, Jun 14 2024