A216431 -id:A216431 - cp's OEIS frontend

A233271 a(0)=0; thereafter a(n+1) = a(n) + 1 + number of 0's in binary representation of a(n), counted with A080791.

0, 1, 2, 4, 7, 8, 12, 15, 16, 21, 24, 28, 31, 32, 38, 42, 46, 49, 53, 56, 60, 63, 64, 71, 75, 79, 82, 87, 90, 94, 97, 102, 106, 110, 113, 117, 120, 124, 127, 128, 136, 143, 147, 152, 158, 162, 168, 174, 178, 183, 186, 190, 193, 199, 203, 207, 210, 215, 218, 222

Offset: 0

Antti Karttunen, Dec 12 2013

These are iterates of A233272: a(0)=0, and for n>0, a(n) = A233272(a(n-1)). The difference from A216431 stems from the fact that it uses A023416 to count the 0-bits in the binary expansion of n, while this sequence uses A080791, which results a slightly different start for the iteration, and a much better alignment with sequences related to "infinite trunk of binary beanstalk", A179016.

Apart from term a(2)=2, it seems that each term a(n) >= A179016(n). Please see their ratio plotted with Plot2, and also their differences: A233270.

Antti Karttunen, Table of n, a(n) for n = 0..8727
A. Karttunen Ratio A233271/A179016 plotted with OEIS Plot2-script

Differs from A216431 only in that here 1 has been inserted into position a(1), between 0 and 2.

Cf. A080791, A010062, A233272, A179016, A233270, A218616, A054429, A213710, A218600.

a[0] = 0; a[n_] := a[n] = If[n == 1, 1, # + 1 + Last@ DigitCount[#, 2] &@ a[n - 1]]; Table[a@ n, {n, 0, 59}] (* or *)
Insert[NestList[# + 1 + DigitCount[#, 2, 0] &, 0, nn], 1, 2] (* Michael De Vlieger, Mar 07 2016, the latter after Harvey P. Dale at A216431 *)

a(0)=0, and for n>0, a(n) = A233272(a(n-1)).
a(0)=0, and for n>0, a(n) = a(n-1) + 1 + A080791(a(n-1)).
a(n) = A054429(A218616(n)) = A054429(A179016(A218602(n))) [This sequence can be mapped to the infinite trunk of "binary beanstalk" with involutions A054429 & A218602].
For all n, a(A213710(n)) = 2^n = A000079(n).
For n>=3, a(A218600(n)) = A000225(n).

A257806 a(n) = A257808(n) - A257807(n).

Original entry on oeis.org

0, -1, 0, 1, 0, 1, 2, 1, 2, 1, 2, 3, 2, 3, 4, 5, 6, 5, 4, 5, 6, 5, 6, 5, 4, 3, 4, 3, 4, 5, 4, 5, 6, 7, 6, 5, 6, 7, 6, 7, 8, 7, 6, 7, 8, 9, 10, 11, 12, 11, 12, 13, 12, 11, 10, 9, 10, 9, 10, 11, 10, 11, 12, 13, 12, 11, 12, 13, 12, 13, 12, 13, 14, 13, 12, 11, 10, 9, 10, 11, 12, 11, 10, 9, 10, 11, 12, 13, 14, 15, 14, 15, 16, 15, 16, 15, 14

Offset: 0

Antti Karttunen, May 12 2015

Alternative description: Start with a(0) = 0, and then to obtain each a(n), look at each successive term in the infinite trunk of inverted binary beanstalk, from A233271(1) onward, subtracting one from a(n-1) if A233271(n) is odd, and adding one to a(n-1) if A233271(n) is even.
In other words, starting from zero, iterate the map x -> {x + 1 + number of nonleading zeros in the binary representation of x}, and note each time whether the result is odd or even: With odd results go one step down, and even results go one step up.
After the zeros at a(0), a(2) and a(4) and -1 at a(1), the terms stay strictly positive for a long time, although from the terms of A257805 it can be seen that the sequence must again fall to the negative side somewhere between n = 541110611 and n = 1051158027 (i.e., A218600(33) .. A218600(34)). Indeed the fourth zero occurs at n = 671605896, and the second negative term right after that as a(671605897) = -1.
The maximum positive value reached prior to the slide into negative territory is 2614822 for a(278998626) and a(278998628). - Hans Havermann, May 23 2015

			We consider 0 to have no nonleading zeros, so first we get to 0 -> 0+1+0 = 1, and 1 is odd, so we go one step down from the starting value a(0)=0, and thus a(1) = -1.
1 has no nonleading zeros, so we get 1 -> 1+1+0 = 2, and 2 is even, so we go one step up, and thus a(2) = 0.
2 has one nonleading zero in binary "10", so we get 2 -> 2+1+1 = 4, and 4 is also even, so we go one step up, and thus a(3) = 1.
4 has two nonleading zeros in binary "100", so we get 4 -> 4+2+1 = 7, 7 is odd, so we go one step down, and thus a(4) = 0.

Antti Karttunen, Table of n, a(n) for n = 0..8727
Hans Havermann, Graph of 2*10^9 terms
Hans Havermann, Detail graph of the eventual crossover to negative terms and a listing of its associated zeros
Wikipedia, Blancmange curve

Cf. A218600, A233271, A233272, A257807, A257808, A257803, A257804, A257805.

Cf. also A218542, A218543, A218789 and A233270 (compare the scatter plots).

A070939 = n->#binary(n)+!n; \\ From M. F. Hasler
A080791 = n->if(n<1,0,(A070939(n)-hammingweight(n)));
A233272 = n->(n + A080791(n) + 1);
A257806_write_bfile(up_to_n) = { my(n,a_n=0,b_n=0); for(n=0, up_to_n, write("b257806.txt", n, " ", a_n); b_n = A233272(b_n); a_n += ((-1)^b_n)); };
A257806_write_bfile(8727);

def A257806_print_upto(n):
  a = 0
  b = 0
  for n in range(n):
     print(b, end=", ")
     ta = a
     c0 = 0
     while ta>0:
         c0 += 1-(ta&1)
         ta >>= 1
     a += 1 + c0
     b += ((2*(1-(a&1))) - 1)
# By Antti Karttunen after Alex Ratushnyak's Python-code for A216431.

(define (A257806 n) (- (A257808 n) (A257807 n)))

;; Using memoizing definec-macro.
(definec (A257806 n) (if (zero? n) n (+  (expt -1 (A233271 n)) (A257806 (- n 1)))))

a(n) = A257808(n) - A257807(n).
a(0) = 0; and for n >= 1, a(n) = a(n-1) + (-1)^A233271(n).
Other identities. For all n >= 0:
a(A218600(n+1)) = -A257805(n).

A233272 a(n) = n + 1 + number of nonleading zeros in binary representation of n (A080791).

Original entry on oeis.org

1, 2, 4, 4, 7, 7, 8, 8, 12, 12, 13, 13, 15, 15, 16, 16, 21, 21, 22, 22, 24, 24, 25, 25, 28, 28, 29, 29, 31, 31, 32, 32, 38, 38, 39, 39, 41, 41, 42, 42, 45, 45, 46, 46, 48, 48, 49, 49, 53, 53, 54, 54, 56, 56, 57, 57, 60, 60, 61, 61, 63, 63, 64, 64, 71, 71, 72

Offset: 0

Antti Karttunen, Dec 12 2013

From Antti Karttunen, Jan 30 2022: (Start)
Write n in binary: 1ab..xyz, then a(n) = (1+1ab..xy) + (1+1ab..x) + ... + (1+1ab) + (1+1a) + (1+1) + (1+0) + 1. This method was found by LODA miner, see the assembly program at C. Krause link.
Proof: Compare to a similar formula given for A011371, with a(n) = a(floor(n/2)) + floor(n/2) to the new formula for this sequence which is a(n) = 1 + a(floor(n/2)) + floor(n/2), for n > 0 and a(0) = 1. It is easy to see that the difference between these, a(n) - A011371(n) = 1+A070939(n), for n > 0. As A011371(n) = n minus (number of 1's in binary expansion of n), then a(n) = 1 + (number of digits in binary expansion of n) + (n minus number of 1's in binary expansion of n) = 1 + n + (number of nonleading 0's in binary expansion of n), which indeed is the definition of this sequence.
(End)

Antti Karttunen, Table of n, a(n) for n = 0..8192
Christian Krause, et al, A mined LODA assembly source for this sequence
Index entries for sequences related to binary expansion of n

Bisection: A233273 (A120511 + 1). Iterates: A233271, A216431.

Cf. A000120, A005187, A011371, A054429, A070939, A080791, A092391.

DigitCount[#, 2, 0] + # + 1 & [Range[0, 100]] (* Paolo Xausa, Mar 01 2024 *)

A233272(n) = { my(s=1); while(n, n>>=1; s+=(1+n)); (s); }; \\ (After a LODA-assembly program found by a miner) - Antti Karttunen, Jan 30 2022

(define (A233272 n) (+ 1 n (A080791 n)))
;; Alternatively:
(define (A233272 n) (if (zero? n) 1 (+ n (A000120 (A054429 n)))))

a(n) = n + A080791(n) + 1.
For all n>=1, a(n) = n + A000120(A054429(n)).
a(0) = 1; for n > 1, a(n) = 1 + floor(n/2) + a(floor(n/2)). - (Found by LODA miner, see comments) - Antti Karttunen, Jan 30 2022

A269381 Least monotonic left inverse of A233271.

Original entry on oeis.org

0, 1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 5, 6, 6, 6, 7, 8, 8, 8, 8, 8, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 12, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 19, 19, 19, 19, 20, 20, 20, 21, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 24, 24, 24, 24, 25, 25, 25, 26

Offset: 0

Antti Karttunen, Mar 05 2016

nonn

a(n) = number of nonzero terms of A233271 <= n.

Antti Karttunen, Table of n, a(n) for n = 0..8192

Cf. A233271.

Cf. also A269391.

nn = 90; s = NestList[# + 1 + DigitCount[#, 2, 0] &, 1, nn]; Table[Count[Take[s, n + 1], k_ /; k <= n], {n, 0, nn}]  (* Michael De Vlieger, Mar 07 2016, after Harvey P. Dale at A216431 *)

Other identities. For all n >= 0:

a(A233271(n)) = n.

cp's OEIS Frontend

A233271 a(0)=0; thereafter a(n+1) = a(n) + 1 + number of 0's in binary representation of a(n), counted with A080791.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A257806 a(n) = A257808(n) - A257807(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

Scheme

Scheme

Formula

A233272 a(n) = n + 1 + number of nonleading zeros in binary representation of n (A080791).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Scheme

Formula

A269381 Least monotonic left inverse of A233271.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula