A073137 a(n) is the least number whose binary representation has the same number of 0's and 1's as n.

0, 1, 2, 3, 4, 5, 5, 7, 8, 9, 9, 11, 9, 11, 11, 15, 16, 17, 17, 19, 17, 19, 19, 23, 17, 19, 19, 23, 19, 23, 23, 31, 32, 33, 33, 35, 33, 35, 35, 39, 33, 35, 35, 39, 35, 39, 39, 47, 33, 35, 35, 39, 35, 39, 39, 47, 35, 39, 39, 47, 39, 47, 47, 63, 64, 65, 65, 67, 65, 67, 67, 71, 65

Offset

0,3

Comments

A023416(a(n)) = A023416(n), A000120(a(n)) = A000120(n).

Links

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000

Index entries for sequences related to binary expansion of n

Formula

a(0)=0, a(1)=1; for n > 1, let C = 2^(floor(log_2(n))-1) = A072376(n); then a(n) = a(n-C) + C if n < 3*C; otherwise a(n) = 2*a(n - 2*C) + 1. [corrected by Jon E. Schoenfield, Jun 27 2021]

For n > 0: a(n) = (2^(A000120(n) - 1)) * (2^A023416(n) + 1) - 1. - Corrected by Michel Marcus, Nov 15 2013

Example

a(20)=17, as 20='10100' and 17 is the smallest number having two 1's and three 0's: 17='10001', 18='10010', 20='10100' and 24='11000'.

Maple

a:= n-> (l-> (2^nops(l)+2^add(i, i=l))/2-1)(Bits[Split](n)):
seq(a(n), n=0..100);  # Alois P. Heinz, Jun 26 2021

Mathematica

lnb[n_]:=Module[{sidn=Sort[IntegerDigits[n, 2]]}, FromDigits[Join[{1}, Most[ sidn]], 2]]; Join[{0}, Array[lnb, 80]] (* Harvey P. Dale, Aug 04 2014 *)

Prog

(Python)
def a(n):
    b = bin(n)[2:]; z = b.count('0'); w = len(b) - z
    return int('1'*(w > 0) + '0'*z + '1'*(w-1), 2)
print([a(n) for n in range(73)]) # Michael S. Branicky, Jun 26 2021
(Python)
def a(n): b = bin(n)[2:]; return int(b[0] + "".join(sorted(b[1:])), 2)
print([a(n) for n in range(73)]) # Michael S. Branicky, Jun 26 2021
(PARI) a(n) = if(n==0, 0, 1<<logint(n, 2) + 1<<(hammingweight(n)-1) - 1); \\ Kevin Ryde, Jun 26 2021

Crossrefs

Cf. A007088, A073138, A000523, A073139, A073140, A073141, A072376.

Sequence in context: A306328 A225090 A162683 * A345965 A131233 A136623

Adjacent sequences: A073134 A073135 A073136 * A073138 A073139 A073140

Keyword

nonn

Author

Reinhard Zumkeller, Jul 16 2002

Status

approved