login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A268289 a(0)=0; thereafter a(n) = a(n-1) - A037861(n). 14

%I #197 Mar 09 2024 11:16:41

%S 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 19,20,23,26,31,27,25,23,23,21,21,21,23,21,21,21,23,23,25,27,31,29,29,

%U 29,31,31,33,35,39,39,41,43,47,49

%N a(0)=0; thereafter a(n) = a(n-1) - A037861(n).

%C 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 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 From _Laura Monroe_, Jun 11 2020: (Start)

%C 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 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 a(n) is then the number of S-nodes on a pairwise SD-tree with n+1 leaves.

%C This is proved in Props. 17 and 18 of the Monroe et al. article in the links.

%C 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 (End)

%C From _Laura Monroe_, Oct 23 2020: (Start)

%C 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 2^(a(n)) is the number of tree automorphisms on the pairwise (i.e., divide-and-conquer) tree with n+1 leaves.

%C (End)

%H 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 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 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 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 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 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 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 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 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 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 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 From _N. J. A. Sloane_, Mar 11 2016: (Start)

%F a(0)=0; for n > 0, a(n) = a(n-1) + A000120(n) - A023416(n) = A000788(n) - A181132(n).

%F a(0)=0; thereafter a(2*n) = a(n) + a(n-1), a(2*n+1) = 2*a(n) + 1.

%F G.f.: (1/(1-x)^2) * Sum_{k >= 0} x^(2^k)*(1-x^(2^k))/(1+x^(2^k)).

%F 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 (End)

%F From _Laura Monroe_, Jun 11 2020: (Start)

%F 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 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 From _Laura Monroe_, Oct 23 2020: (Start)

%F a(n) = n - A296062(n).

%F 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 From _Laura Monroe_, Jun 11 2020: (Start)

%e 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 + D

%e / \ / \

%e + c S c

%e / \ / \

%e a b a b

%e and exactly 1 internal node has an even number of leaf descendants, hence is an S-node.

%e 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 + S

%e / \ / \

%e + + S S

%e /| |\ /| |\

%e a b c d a b c d

%e and exactly 3 internal nodes have an even number of leaf descendants, hence are S-nodes.

%e (End)

%p a000120 := proc(n) add(i, i=convert(n, base, 2)) end:

%p a023416 := proc(n) if n = 0 then 1; else add(1-e, e=convert(n, base, 2)) ; end if; end proc:

%p a268289:=proc(n) option remember; global a000120, a023416;

%p if n=0 then 0 else a268289(n-1)+a000120(n)-a023416(n); fi; end;

%p [seq(a268289(n),n=0..132)];

%p # _N. J. A. Sloane_, Mar 07 2016

%p # second Maple program:

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

%p a(n-1)+add(2*i-1, i=Bits[Split](n)))

%p end:

%p seq(a(n), n=0..60); # _Alois P. Heinz_, Jan 18 2022

%t Join[{0}, Table[DigitCount[n, 2, 1] - DigitCount[n, 2, 0], {n, 1, 100}] // Accumulate] (* _Jean-François Alcover_, Oct 24 2016 *)

%o (Python)

%o 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 (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 (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 (C)

%o int a(int n) {

%o int m=n+1;

%o int result=0;

%o int i=0;

%o while (n) {

%o int ith_bit_set = m&(1<<i);

%o if (ith_bit_set) result += (m%(1<<i));

%o else result += (1<<i) - (m%(1<<i));

%o i++;

%o n >>= 1;

%o }

%o return result;

%o }

%o /* _Laura Monroe_, Jun 17 2020 */

%o (Julia)

%o function A268289List(len)

%o A = zeros(Int, len)

%o for n in 1:len-1

%o a, b, c = n, n & 1, 1

%o while (a >>= 1) != 0

%o b += a & 1

%o c += 1

%o end

%o A[n+1] = A[n] + <<(b, 1) - c

%o end

%o A

%o end; println(A268289List(61)) # _Peter Luschny_, Jun 22 2020

%Y Partial sums of A145037.

%Y Cf. A000120, A000788, A023416, A037861, A096351, A181132, A269735, A233271, A296062.

%K nonn,base,hear,nice,look

%O 0,4

%A _Mark Moore_, Jan 30 2016

%E Simplified definition following a suggestion from _Michel Marcus_. Corrected start, added more terms. - _N. J. A. Sloane_, Mar 07 2016

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 03:39 EDT 2024. Contains 371264 sequences. (Running on oeis4.)