This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A268289 #200 Nov 11 2024 15:32:59
%S A268289 0,1,1,3,2,3,4,7,5,5,5,7,7,9,11,15,12,11,10,11,10,11,12,15,14,15,16,
%T A268289 19,20,23,26,31,27,25,23,23,21,21,21,23,21,21,21,23,23,25,27,31,29,29,
%U A268289 29,31,31,33,35,39,39,41,43,47,49
%N A268289 a(0)=0; thereafter a(n) = a(n-1) - A037861(n).
%C A268289 The graph of this sequence is related to the Takagi (blancmange) curve: see Lagarias (2012), Section 9, especially Theorem 9.1. [Corrected by _Laura Monroe_, Oct 21 2020]
%C A268289 Theorem: a(n) is the cardinality of the set { 1<= m <= n, ((n-m) mod 2^floor(log_2(m)+1)) < 2^floor(log_2(m)) }. See links.
%C A268289 From _Laura Monroe_, Jun 11 2020: (Start)
%C A268289 Consider a full balanced binary tree with n unlabeled leaves such that for each internal node, the number of leaf descendants of the two children differs by at most 1. Call a tree with this even distribution of leaves "pairwise".
%C A268289 Apply labels to the internal nodes, where an internal node is labeled S if its two children have the same number of leaf descendants, and D if its two children have a different number of leaf descendants, and call this an SD-tree. (For a pairwise tree, this is equivalent to saying that a node is an S-node iff it has an even number of leaf descendants.)
%C A268289 a(n) is then the number of S-nodes on a pairwise SD-tree with n+1 leaves.
%C A268289 This is proved in Props. 17 and 18 of the Monroe et al. article in the links.
%C A268289 One example of such a tree is the summation tree generated by a pairwise summation on n+1 summands (see example below). Another example is the tree representing a neutral single-elimination tournament on n+1 teams, as in A096351.
%C A268289 (End)
%C A268289 From _Laura Monroe_, Oct 23 2020: (Start)
%C A268289 Subtracting a(n) from n gives a sequence of dilations of increasing length on the dyadic rational points of the Takagi function. The number of points in each dilation is 2^k and the scale of each dilation in both the x and y directions is 2^k, where k = floor(log_2(n+1)).
%C A268289 2^(a(n)) is the number of tree automorphisms on the pairwise (i.e., divide-and-conquer) tree with n+1 leaves.
%C A268289 (End)
%H A268289 Laura Monroe, <a href="/A268289/b268289.txt">Table of n, a(n) for n = 0..16383</a> (first 10000 terms from N. J. A. Sloane)
%H A268289 Thomas Baruchel, <a href="https://arxiv.org/abs/1902.08982">Flattening Karatsuba's recursion tree into a single summation</a>, arXiv:1902.08982 [math.NT], 2019. See (5) conjecture of theorem.
%H A268289 Thomas Baruchel, <a href="https://arxiv.org/abs/1908.02250">Properties of the cumulated deficient binary digit sum</a>, arXiv:1908.02250 [math.NT], 2019. See 2.4 proof of theorem.
%H A268289 Thomas Baruchel, <a href="https://doi.org/10.1007/s42979-019-0049-1">Flattening Karatsuba's Recursion Tree into a Single Summation</a>, SN Computer Science (2020) Vol. 1, Article No. 48.
%H A268289 Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, <a href="http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf">Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications</a>, Preprint 2016.
%H A268289 Hsien-Kuei Hwang, S. Janson, and T.-H. 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; DOI: 10.1145/3127585.
%H A268289 Jeffrey C. Lagarias, <a href="https://arxiv.org/abs/1112.4205">The Takagi function and its properties</a>, arXiv:1112.4205 [math.CA], 2011-2012.
%H A268289 Jeffrey C. Lagarias, <a href="http://hdl.handle.net/2433/198081">The Takagi function and its properties</a>, 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.
%H A268289 Laura Monroe, <a href="https://arxiv.org/abs/2111.05996">A Few Identities of the Takagi Function on Dyadic Rationals</a>, arXiv:2111.05996 [math.CO], 2021.
%H A268289 Laura Monroe, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL27/Monroe/monroe2.pdf">Takagi Function Identities on Dyadic Rationals</a>, J. Int. Seq (2024) Vol. 27, Art. 24.2.7.
%H A268289 Laura Monroe and Vanessa Job, <a href="https://arxiv.org/abs/2005.05387">Computationally Inequivalent Summations and Their Parenthetic Forms</a>, arXiv:2005.05387 [cs.DM], 2020. See Prop. 26, the alternate proof.
%F A268289 From _N. J. A. Sloane_, Mar 11 2016: (Start)
%F A268289 a(0)=0; for n > 0, a(n) = a(n-1) + A000120(n) - A023416(n) = A000788(n) - A181132(n).
%F A268289 a(0)=0; thereafter a(2*n) = a(n) + a(n-1), a(2*n+1) = 2*a(n) + 1.
%F A268289 G.f.: (1/(1-x)^2) * Sum_{k >= 0} x^(2^k)*(1-x^(2^k))/(1+x^(2^k)).
%F A268289 a(2^k-1) = 2^k-1, a(3*2^k-1) = 2^(k+1)-1, a(5*2^k-1) = 3*2^k-1, etc.
%F A268289 (End)
%F A268289 From _Laura Monroe_, Jun 11 2020: (Start)
%F A268289 a(n-1) = Sum_{i=0..floor(log_2(n))} (((floor(n/(2^i))+1) mod 2)*(2^i)+(-1)^((floor(n/(2^i))+1) mod 2)*(n mod (2^i))), for n>=1.
%F A268289 This is an explicit formula for this sequence, and is O(log(n)). This formula is proven in Prop. 18, in the Monroe et al. reference in the links. (End)
%F A268289 From _Laura Monroe_, Oct 23 2020: (Start)
%F A268289 a(n) = n - A296062(n).
%F A268289 a(n+1) = (n+1) - (2^k)*tau(x/(2^k)), where tau is the Takagi function and n+1 = (2^k)+x with x < 2^k. (End)
%e A268289 From _Laura Monroe_, Jun 11 2020: (Start)
%e A268289 For n=2, the pairwise summation on 2+1=3 summands takes the form ((a+b)+c). The corresponding summation tree and SD-tree look like:
%e A268289 + D
%e A268289 / \ / \
%e A268289 + c S c
%e A268289 / \ / \
%e A268289 a b a b
%e A268289 and exactly 1 internal node has an even number of leaf descendants, hence is an S-node.
%e A268289 For n=3, the pairwise summation on 3+1=4 summands takes the form ((a+b)+(c+d)). The corresponding summation tree and SD-tree look like:
%e A268289 + S
%e A268289 / \ / \
%e A268289 + + S S
%e A268289 /| |\ /| |\
%e A268289 a b c d a b c d
%e A268289 and exactly 3 internal nodes have an even number of leaf descendants, hence are S-nodes.
%e A268289 (End)
%p A268289 a000120 := proc(n) add(i, i=convert(n, base, 2)) end:
%p A268289 a023416 := proc(n) if n = 0 then 1; else add(1-e, e=convert(n, base, 2)) ; end if; end proc:
%p A268289 a268289:=proc(n) option remember; global a000120, a023416;
%p A268289 if n=0 then 0 else a268289(n-1)+a000120(n)-a023416(n); fi; end;
%p A268289 [seq(a268289(n),n=0..132)];
%p A268289 # _N. J. A. Sloane_, Mar 07 2016
%p A268289 # second Maple program:
%p A268289 a:= proc(n) option remember; `if`(n<0, 0,
%p A268289 a(n-1)+add(2*i-1, i=Bits[Split](n)))
%p A268289 end:
%p A268289 seq(a(n), n=0..60); # _Alois P. Heinz_, Jan 18 2022
%t A268289 Join[{0}, Table[DigitCount[n, 2, 1] - DigitCount[n, 2, 0], {n, 1, 100}] // Accumulate] (* _Jean-François Alcover_, Oct 24 2016 *)
%o A268289 (Python)
%o A268289 def A268289(n): return (sum(i.bit_count() for i in range(1,n+1))<<1)-1-(n+1)*(m:=(n+1).bit_length())+(1<<m) # _Chai Wah Wu_, Mar 01 2023
%o A268289 (Python)
%o A268289 def A268289(n): return sum((n+1)%m if (n+1)&(m:=1<<i) else m-((n+1)%m) for i in range((n+1).bit_length())) # _Chai Wah Wu_, Nov 11 2024
%o A268289 (PARI) a(n) = if (n==0, 0, if (n%2, 2*a((n-1)/2)+1, a(n/2) + a(n/2-1))); \\ _Michel Marcus_, Jun 16 2020
%o A268289 (PARI) a(n) = my(v=binary(n+1),s=-1); for(i=1,#v, v[i]=if(v[i],s++,s--;1)); fromdigits(v,2); \\ _Kevin Ryde_, Jun 16 2020
%o A268289 (C)
%o A268289 int a(int n) {
%o A268289 int m=n+1;
%o A268289 int result=0;
%o A268289 int i=0;
%o A268289 while (n) {
%o A268289 int ith_bit_set = m&(1<<i);
%o A268289 if (ith_bit_set) result += (m%(1<<i));
%o A268289 else result += (1<<i) - (m%(1<<i));
%o A268289 i++;
%o A268289 n >>= 1;
%o A268289 }
%o A268289 return result;
%o A268289 }
%o A268289 /* _Laura Monroe_, Jun 17 2020 */
%o A268289 (Julia)
%o A268289 function A268289List(len)
%o A268289 A = zeros(Int, len)
%o A268289 for n in 1:len-1
%o A268289 a, b, c = n, n & 1, 1
%o A268289 while (a >>= 1) != 0
%o A268289 b += a & 1
%o A268289 c += 1
%o A268289 end
%o A268289 A[n+1] = A[n] + <<(b, 1) - c
%o A268289 end
%o A268289 A
%o A268289 end; println(A268289List(61)) # _Peter Luschny_, Jun 22 2020
%Y A268289 Partial sums of A145037.
%Y A268289 Cf. A000120, A000788, A023416, A037861, A096351, A181132, A269735, A233271, A296062.
%K A268289 nonn,base,hear,nice,look
%O A268289 0,4
%A A268289 _Mark Moore_, Jan 30 2016
%E A268289 Simplified definition following a suggestion from _Michel Marcus_. Corrected start, added more terms. - _N. J. A. Sloane_, Mar 07 2016