login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A181132
a(0)=0; thereafter a(n) = total number of 0's in binary expansions of 1, ..., n.
4
0, 0, 1, 1, 3, 4, 5, 5, 8, 10, 12, 13, 15, 16, 17, 17, 21, 24, 27, 29, 32, 34, 36, 37, 40, 42, 44, 45, 47, 48, 49, 49, 54, 58, 62, 65, 69, 72, 75, 77, 81, 84, 87, 89, 92, 94, 96, 97, 101, 104, 107, 109, 112, 114, 116, 117, 120, 122, 124, 125, 127, 128, 129, 129, 135, 140, 145
OFFSET
0,5
COMMENTS
The graph of this sequence is a version of the Takagi curve: see Lagarias (2012), Section 9, especially Theorem 9.1. - N. J. A. Sloane, Mar 12 2016
LINKS
Hsien-Kuei Hwang, S. Janson, and T.-H. 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; DOI: 10.1145/3127585.
Jeffrey C. Lagarias, The Takagi function and its properties, arXiv:1112.4205 [math.CA], 2011-2012.
Jeffrey C. Lagarias, The Takagi function and its properties, In Functions in number theory and their probabilistic aspects, 153--189, RIMS Kôkyûroku Bessatsu, B34, Res. Inst. Math. Sci. (RIMS), Kyoto, 2012. MR3014845.
FORMULA
a(n) = A059015(n)-1. - Klaus Brockhaus, Oct 08 2010
From N. J. A. Sloane, Mar 10 2016: (Start)
a(0)=0; thereafter a(2n) = a(n)+a(n-1)+n, a(2n+1) = 2a(n)+n.
G.f.: (1/(1-x)^2) * Sum_{k >= 0} x^(2^(k+1))/(1+x^(2^k)). (End)
MAPLE
a:= proc(n) option remember; `if`(n=0, 0, a(n-1)+add(1-i, i=Bits[Split](n))) end:
seq(a(n), n=0..66); # Alois P. Heinz, Nov 12 2024
MATHEMATICA
Accumulate[Count[IntegerDigits[#, 2], 0]&/@Range[70]] (* Harvey P. Dale, May 16 2012 *)
Join[{0}, Accumulate[DigitCount[Range[70], 2, 0]]] (* Harvey P. Dale, Jun 09 2016 *)
PROG
(Other) microsoft word macro: Sub concatcount() Dim base As Integer Dim digit As Integer Dim counter As Integer Dim standin As Integer Dim max As Integer Let base = 2 Let digit = 0 Let max = 100 Let counter = 0 For n = 1 To max Let standin = n Do While standin > 0 If standin Mod base = digit Then Let counter = counter + 1 Let standin = standin - (standin Mod base) If standin > 0 Then Let standin = standin / base Loop Selection.TypeText Text:=Str(counter) Next n End Sub
(Magma) [ n eq 1 select 0 else Self(n-1)+(#B-&+B) where B is Intseq(n, 2): n in [1..70] ]; // Klaus Brockhaus, Oct 08 2010
(PARI) a(n)=my(m=logint(n, 2)); 1 + (m+1)*(n+1) - 2^(m+1) + sum(j=1, m+1, my(t=floor(n/2^j + 1/2)); (n>>j)*(2*n + 2 - (1 + (n>>j))<<j) - (2*n + 2 - t<<j)*t)/2 \\ Charles R Greathouse IV, Dec 14 2015
(Python)
def A181132(n): return 1+(n+1)*(m:=(n+1).bit_length())-(1<<m)-sum(i.bit_count() for i in range(1, n+1)) # Chai Wah Wu, Mar 02 2023
(Python)
def A181132(n): return 1+(n+1)*((t:=(n+1).bit_length())-n.bit_count())-(1<<t)-(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 11 2024
CROSSREFS
KEYWORD
base,easy,nonn
AUTHOR
Dylan Hamilton, Oct 05 2010
EXTENSIONS
a(0)=0 added by N. J. A. Sloane, Mar 10 2016 (simplifies the recurrence, makes entry consistent with A059015 and other closely related sequences).
STATUS
approved