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,1

Comments

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

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

Example

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.

Prog

(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

Crossrefs

Cf. A007814, A023416, A140977, A094510.

Sequence in context: A209422 A361944 A320386 * A283838 A228146 A328013

Adjacent sequences: A112408 A112409 A112410 * A112412 A112413 A112414

Keyword

base,easy,nonn

Author

Leroy Quet, Dec 08 2005

Extensions

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

Status

approved