A233273 -id:A233273 - cp's OEIS frontend

A080791 Number of nonleading 0's in binary expansion of n.

0, 0, 1, 0, 2, 1, 1, 0, 3, 2, 2, 1, 2, 1, 1, 0, 4, 3, 3, 2, 3, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1, 0, 5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1, 4, 3, 3, 2, 3, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1, 0, 6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2, 5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1, 5, 4, 4, 3, 4, 3, 3, 2, 4

Offset: 0

Cino Hilliard, Mar 25 2003

In this version we consider the number zero to have no nonleading 0's, thus a(0) = 0. The variant A023416 has a(0) = 1.

Number of steps required to reach 1, starting at n + 1, under the operation: if x is even divide by 2 else add 1. This is the x + 1 problem (as opposed to the 3x + 1 problem).

			a(4) = 2 since 4 in binary is 100, which has two zeros.
a(5) = 1 since 5 in binary is 101, which has only one zero.

N. J. A. Sloane, Table of n, a(n) for n = 0..10000
Index entries for sequences related to binary expansion of n

Cf. A000120, A007814, A023416, A029837, A036987, A080791-A080801, A048881, A054429, A092339, A102364, A120511, A233271, A233272, A233273.

seq(numboccur(0, Bits[Split](n)), n=0..100); # Robert Israel, Oct 26 2017

{0}~Join~Table[Last@ DigitCount[n, 2], {n, 120}] (* Michael De Vlieger, Mar 07 2016 *)
f[n_] := If[OddQ@ n, f[n -1] -1, f[n/2] +1]; f[0] = f[1] = 0; Array[f, 105, 0] (* Robert G. Wilson v, May 21 2017 *)
Join[{0}, Table[Count[IntegerDigits[n, 2], 0], {n, 1, 100}]] (* Vincenzo Librandi, Oct 27 2017 *)

PARI
```
a(n)=if(n,a(n\2)+1-n%2)
```

A080791(n)=if(n,logint(n,2)+1-hammingweight(n)) \\ M. F. Hasler, Oct 26 2017

def a(n): return bin(n)[2:].count("0") if n>0 else 0 # Indranil Ghosh, Apr 10 2017

;; with memoizing definec-macro from Antti Karttunen's IntSeq-library)
(define (A080791 n) (- (A029837 (+ 1 n)) (A000120 n)))
;; Alternative version based on a simple recurrence:
(definec (A080791 n) (if (zero? n) 0 (+ (A080791 (- n 1)) (A007814 n) (A036987 (- n 1)) -1)))
;; from Antti Karttunen, Dec 12 2013

From Antti Karttunen, Dec 12 2013: (Start)
a(n) = A029837(n+1) - A000120(n).
a(0) = 0, and for n > 0, a(n) = (a(n-1) + A007814(n) + A036987(n-1)) - 1.
For all n >= 1, a(A054429(n)) = A048881(n-1) = A000120(n) - 1.
Equally, for all n >= 1, a(n) = A000120(A054429(n)) - 1.
(End)
Recurrence: a(2n) = a(n) + 1 (for n > 0), a(2n + 1) = a(n). - Ralf Stephan from Cino Hilliard's PARI program, Dec 16 2013. Corrected by Alonso del Arte, May 21 2017 after consultation with Chai Wah Wu and Ray Chandler, "n > 0" added by M. F. Hasler, Oct 26 2017
a(n) = A023416(n) for all n > 0. - M. F. Hasler, Oct 26 2017
G.f. g(x) satisfies g(x) = (1+x)*g(x^2) + x^2/(1-x^2). - Robert Israel, Oct 26 2017

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

A120511 a(n) = min{j>0 : A006949(j) = n}.

Original entry on oeis.org

1, 3, 6, 7, 11, 12, 14, 15, 20, 21, 23, 24, 27, 28, 30, 31, 37, 38, 40, 41, 44, 45, 47, 48, 52, 53, 55, 56, 59, 60, 62, 63, 70, 71, 73, 74, 77, 78, 80, 81, 85, 86, 88, 89, 92, 93, 95, 96, 101, 102, 104, 105, 108, 109, 111, 112, 116, 117, 119, 120, 123, 124, 126, 127, 135

Offset: 1

Frank Ruskey and Chris Deugau (deugaucj(AT)uvic.ca), Jun 20 2006

nonn

Antti Karttunen, Table of n, a(n) for n = 1..10000
C. Deugau and F. Ruskey, Complete k-ary Trees and Generalized Meta-Fibonacci Sequences
C. Deugau and F. Ruskey, Complete k-ary Trees and Generalized Meta-Fibonacci Sequences, J. Integer Seq., Vol. 12. [This is a later version than that in the GenMetaFib.html link]
B. Jackson and F. Ruskey, Meta-Fibonacci Sequences, Binary Trees and Extremal Compact Codes, Electronic Journal of Combinatorics, 13 (2006), R26.
Index entries for sequences related to binary expansion of n

Cf. A006949, A120522, A007814, A023416, A036987, A080791, A005408.
a(n) = one less than A233273(n-1).
Cf. A241218.

import Data.List (elemIndex); import Data.Maybe (fromJust)
a120511 = (+ 1) . fromJust . (`elemIndex` (tail a006949_list))
-- Reinhard Zumkeller, Apr 17 2014

p := proc(n)
if n=1 then return 1; end if;
for j from p(n-1)+1 to infinity do
if A006949(j) = n then return j; fi; od;
end proc;

a[n_] := 2 n - 1 + DigitCount[2 n - 1, 2, 0]; Array[a, 100] (* Jean-François Alcover, Feb 01 2018, after Reinhard Zumkeller *)

{ A120511(n) = local(t,k); t=binary(n); k=valuation(n,2); 2*n + #t - sum(i=1,#t,t[i]) - k - (n==2^k) } /* Max Alekseyev, Sep 18 2009 */

(define (A120511 n) (+ n n (A080791 n) (- (A007814 n)) (- (A036987 (- n 1)))))
(define (A120511 n) (+ (A005408 (- n 1)) (A080791 (- n 1))))
;; Based on above PARI-program and its further reduction, from Antti Karttunen, Dec 12 2013

G.f.: P(z) = (z/(1-z)) * (1 + Sum_{k=0..ceiling(n/2)} z^(2^m) * (1 + 1/(1 - z^(2^m)))).
It appears that a(n) = a(ceiling(n/2)) + n. - Georgi Guninski, Sep 08 2009
From Max Alekseyev, Sep 08 2009: (Start)
This can be proved as follows. Let b=A006949. It is known that b(n) = b(n-1-b(n-1)) + b(n-2-b(n-2)) and b(n-1) <= b(n) <= b(n-1)+1.
The following claims are trivial:
Claim 1. For any n, b(a(n))=n.
Claim 2. If m=a(n) for some n, then a(b(m))=m.
Claim 3. Let m=a(n). Then b(m)=n and b(m-1)=n-1, implying that b(m+1) = b(m-b(m)) + b(m-1-b(m-1)) = 2*b(m-n) is an even number.
Claim 4. Each even number in A006949 is repeated at least two times while each odd number in A006949 appears only once.
Proof. If n is even, then for m=a(n), we have b(m)=n and b(m+1)=n (from Claim 3), i.e., n is repeated at least twice. If n is odd, then for m=a(n), we cannot have b(m+1)=n since by Claim 3 b(m+1) must be even. QED
Consider two cases:
1) If n is odd, then b(m+1) = n+1 = 2*b(m-n), i.e., b(m-n) = (n+1)/2. Claim 4 also implies b(m-2) = n-1. Therefore n = b(m) = b(m-1-b(m-1)) + b(m-2-b(m-2)) = b(m-n) + b(m-n-1). Since n is odd, we have b(m-n-1) < b(m-n) and thus a(b(m-n)) = m-n.
2) If n is even, then b(m+1) = n = 2*b(m-n), i.e., b(m-n) = n/2. Claim 4 also implies b(m-3) = b(m-2) = n-2. Therefore n-1 = b(m-1) = b(m-2-b(m-2)) + b(m-3-b(m-3)) = b(m-n) + b(m-n-1). Since n-1 is odd, we have b(m-n-1) < b(m-n) and thus a(b(m-n)) = m-n.
Combining these two cases, we have b(m-n) = ceiling(n/2) and furthermore m-n = a(b(m-n)) = a(ceiling(n/2)) or a(n) = a(ceiling(n/2)) + n.
QED
This implies explicit formulas for both sequences.
Let z(n) be the number of zero bits in the binary representation of n. Then
A120511(n) = 2n + z(n) - k - [n==2^k], where k = valuation(n,2), i.e., the maximum power of 2 dividing n.
Note that k <= z(n) <= log_2(n)-1, implying that 2n-1 <= A120511(n) <= 2n + log_2(n) - 1.
Since A006949(m) equals the largest n such that A120511(n) <= m (and thus A120511(n+1) > m), from 2n-1 <= A120511(n) <= m it follows that A006949(m) <= (m+1)/2. Similarly, from m < A120511(n+1) < 2(n+1) + log_2(n+1) - 1 <= 2(n+1) + log_2((m+1)/2+1) - 1, it follows that A006949(m) >= (m - log_2(m+3)) / 2. Therefore | A006949(m) - m/2 | <= log_2(m+3)/2, which gives an interval of just logarithmic length to search for the value of A006949(m).
(End)
From p. 25 of the revised version of the Deugau-Ruskey paper, we have p(n) = s*ceiling(log_k n) + (kn-d-1)/(k-1) where d is the sum of the digits of the k-ary expression of n-1. In the present case s = 1 and k = 2. - Frank Ruskey, Sep 11 2009
From Antti Karttunen, Dec 12 2013: (Start)
a(n) = 2n + A080791(n) - A007814(n) - A036987(n-1) [This is essentially Max Alekseyev's above formula represented with A-numbers].
a(n) = A005408(n-1) + A080791(n-1) = A233273(n-1) - 1. [The above formula reduces to this, because A080791(n) - A080791(n+1) = 1 - (A007814(n+1) + A036987(n)) and A080791(2n+1) = A080791(n).]
(End)
a(n) = 2*n - 1 + A023416(2*n-1). - Reinhard Zumkeller, Apr 17 2014

Edited by Max Alekseyev, Sep 16 2009

More terms from Max Alekseyev, Sep 18 2009

A270200 a(0) = 0; for n >= 1, a(n) = A054429(A005187(1+A054429(n-1))).

Original entry on oeis.org

0, 1, 2, 4, 7, 8, 12, 13, 15, 16, 21, 22, 24, 25, 28, 29, 31, 32, 38, 39, 41, 42, 45, 46, 48, 49, 53, 54, 56, 57, 60, 61, 63, 64, 71, 72, 74, 75, 78, 79, 81, 82, 86, 87, 89, 90, 93, 94, 96, 97, 102, 103, 105, 106, 109, 110, 112, 113, 117, 118, 120, 121, 124, 125, 127, 128, 136, 137, 139, 140, 143, 144, 146, 147, 151

Offset: 0

Antti Karttunen, May 31 2016

After the initial zero, numbers that occur in the range of A233272.

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

Complement: A270198.
Cf. A005187, A054429, A233272, A233273.
Cf. also A233271 (a subsequence).

s = Range[2^(# + 1) - 1, 2^#, -1] & /@ Range[0, 12] // Flatten; {0, 1}~Join~Table[s[[2 # - DigitCount[2 #, 2, 1] &[1 + s[[n - 1]]]]], {n, 2, 74}] (* Michael De Vlieger, Jun 01 2016, after Harvey P. Dale at A005187 and A054429 *)

a(0) = 0; for n >= 1, a(n) = A054429(A005187(1+A054429(n-1))).
Other identities. For all >= 0:
A233273(n) = a(n+2).

cp's OEIS Frontend

A080791 Number of nonleading 0's in binary expansion of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

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

A120511 a(n) = min{j>0 : A006949(j) = n}.

Views

Author

Keywords

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Scheme

Formula

Extensions

A270200 a(0) = 0; for n >= 1, a(n) = A054429(A005187(1+A054429(n-1))).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula