A268289 a(0)=0; thereafter a(n) = a(n-1) - A037861(n).
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, 19, 20, 23, 26, 31, 27, 25, 23, 23, 21, 21, 21, 23, 21, 21, 21, 23, 23, 25, 27, 31, 29, 29, 29, 31, 31, 33, 35, 39, 39, 41, 43, 47, 49
Offset: 0
Examples
From _Laura Monroe_, Jun 11 2020: (Start)
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:
+ D
/ \ / \
+ c S c
/ \ / \
a b a b
and exactly 1 internal node has an even number of leaf descendants, hence is an S-node.
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:
+ S
/ \ / \
+ + S S
/| |\ /| |\
a b c d a b c d
and exactly 3 internal nodes have an even number of leaf descendants, hence are S-nodes.
(End)
Links
- Laura Monroe, Table of n, a(n) for n = 0..16383 (first 10000 terms from N. J. A. Sloane)
- Thomas Baruchel, Flattening Karatsuba's recursion tree into a single summation, arXiv:1902.08982 [math.NT], 2019. See (5) conjecture of theorem.
- Thomas Baruchel, Properties of the cumulated deficient binary digit sum, arXiv:1908.02250 [math.NT], 2019. See 2.4 proof of theorem.
- Thomas Baruchel, Flattening Karatsuba's Recursion Tree into a Single Summation, SN Computer Science (2020) Vol. 1, Article No. 48.
- 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.
- Laura Monroe, A Few Identities of the Takagi Function on Dyadic Rationals, arXiv:2111.05996 [math.CO], 2021.
- Laura Monroe, Takagi Function Identities on Dyadic Rationals, J. Int. Seq (2024) Vol. 27, Art. 24.2.7.
- Laura Monroe and Vanessa Job, Computationally Inequivalent Summations and Their Parenthetic Forms, arXiv:2005.05387 [cs.DM], 2020. See Prop. 26, the alternate proof.
Crossrefs
Programs
-
C
int a(int n) { int m=n+1; int result=0; int i=0; while (n) { int ith_bit_set = m&(1< -
Julia
function A268289List(len) A = zeros(Int, len) for n in 1:len-1 a, b, c = n, n & 1, 1 while (a >>= 1) != 0 b += a & 1 c += 1 end A[n+1] = A[n] + <<(b, 1) - c end A end; println(A268289List(61)) # Peter Luschny, Jun 22 2020
-
Maple
a000120 := proc(n) add(i, i=convert(n, base, 2)) end: a023416 := proc(n) if n = 0 then 1; else add(1-e, e=convert(n, base, 2)) ; end if; end proc: a268289:=proc(n) option remember; global a000120, a023416; if n=0 then 0 else a268289(n-1)+a000120(n)-a023416(n); fi; end; [seq(a268289(n),n=0..132)]; # N. J. A. Sloane, Mar 07 2016 # second Maple program: a:= proc(n) option remember; `if`(n<0, 0, a(n-1)+add(2*i-1, i=Bits[Split](n))) end: seq(a(n), n=0..60); # Alois P. Heinz, Jan 18 2022
-
Mathematica
Join[{0}, Table[DigitCount[n, 2, 1] - DigitCount[n, 2, 0], {n, 1, 100}] // Accumulate] (* Jean-François Alcover, Oct 24 2016 *) -
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
-
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
-
Python
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<
-
Python
def A268289(n): return sum((n+1)%m if (n+1)&(m:=1<
Formula
From N. J. A. Sloane, Mar 11 2016: (Start)
a(0)=0; thereafter a(2*n) = a(n) + a(n-1), a(2*n+1) = 2*a(n) + 1.
G.f.: (1/(1-x)^2) * Sum_{k >= 0} x^(2^k)*(1-x^(2^k))/(1+x^(2^k)).
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.
(End)
From Laura Monroe, Jun 11 2020: (Start)
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.
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)
From Laura Monroe, Oct 23 2020: (Start)
a(n) = n - A296062(n).
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)
Extensions
Simplified definition following a suggestion from Michel Marcus. Corrected start, added more terms. - N. J. A. Sloane, Mar 07 2016
Comments