A112411 a(n) = smallest positive integer, not occurring earlier in the sequence and not equal to n, that has the same number of (non-leading) 0's in its binary representation as n.

3, 5, 1, 9, 2, 11, 15, 17, 4, 12, 6, 10, 14, 13, 7, 33, 8, 20, 21, 18, 19, 25, 27, 35, 22, 28, 23, 26, 30, 29, 63, 65, 16, 36, 24, 34, 38, 37, 43, 48, 42, 41, 39, 49, 46, 45, 55, 40, 44, 52, 53, 50, 51, 57, 47, 71, 54, 60, 61, 58, 59, 95, 31, 129, 32, 68, 69, 66, 67, 73, 56, 80

Offset: 1

Author

Leroy Quet, Dec 08 2005

Keywords

• base
• easy
• nonn

Comments

Sequence is a permutation of the positive integers. It is its own inverse permutation.

Examples

			Among positive integers not among the first 8 terms of the sequence, 4 (100 in binary) is the smallest positive integer which has the same number of non-leading zeros in its binary representation as 9 (1001 in binary). So a(9) = 4.
		

Links

• John Tyler Rascoe, Table of n, a(n) for n = 1..10000
• Index entries for sequences that are permutations of the natural numbers
• Index entries for sequences related to binary expansion of n

Crossrefs

Cf. A007814, A023416, A140977, A094510.

Programs

Python

from itertools import islice
def val(n): return (~n & n-1).bit_length() # From Chai Wah Wu in A007814
def next0(n):
    z = val(n)
    f = (n|(2**z)-1) + 1
    w = val(f)
    if f != 2**w: z+=1
    return(f|(2**(w-z)-1))
def a_gen():
    B,n = [],1
    while True:
        f = 0
        for i in B:
            if i[0] == n:
                f+=1; n+=1; yield(i[1]); B.remove(i); break
        if f < 1:
            B.append((next0(n),n)); yield(next0(n)); n+=1
A112411_list = list(islice(a_gen(), 100)) # John Tyler Rascoe, Mar 20 2024

Extensions

More terms from R. J. Mathar, Feb 08 2008