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

Author

Reinhard Zumkeller, Jul 16 2002

Keywords

• nonn

Comments

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

Fixed points are { 0 } union { A099627 }. - Alois P. Heinz, Jan 30 2025

Examples

			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'.
		

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
• Index entries for sequences related to binary expansion of n

Crossrefs

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

Programs

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 *)

PARI

a(n) = if(n==0,0, 1<Kevin Ryde, Jun 26 2021

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

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