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
Harvey P. Dale, Table of n, a(n) for n = 0..1000
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint 2016.
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,changed
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