A115510 a(1)=1. a(n) is smallest positive integer not occurring earlier in the sequence such that a(n) and a(n-1) have at least one 1-bit in the same position when they are written in binary.

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

Offset: 1

Author

Leroy Quet, Jan 23 2006

Keywords

• easy
• base
• nonn

Comments

Sequence is a permutation of the positive integers. A115511 is the inverse permutation.

This can be regarded as a set-theoretic analog of A064413. - N. J. A. Sloane, Sep 06 2021

Examples

			a(3) = 2 = 10 in binary. Among the positive integers not occurring among the first 3 terms of the sequence (4 = 100 in binary, 5 = 101 in binary, 6 = 110 in binary,...), 6 is the smallest that shares at least one 1-bit with a(3) when written in binary. So a(4) = 6.
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..1025

Crossrefs

Cf. A064413, A109812, A115511, A226077.

Programs

Mathematica

Block[{a = {1}, k}, Do[k = 1; While[Or[BitAnd[Last@ a, k ] == 0, MemberQ[a, k]], k++]; AppendTo[a, k], {71}]; a] (* Michael De Vlieger, Sep 07 2017 *)

Python

A115510_list, l1, s, b = [1], 1, 2, set()
for _ in range(10**6):
    i = s
    while True:
        if not i in b and i & l1:
            A115510_list.append(i)
            l1 = i
            b.add(i)
            while s in b:
                b.remove(s)
                s += 1
            break
        i += 1 # Chai Wah Wu, Sep 24 2021

Formula

(4,6,5) is a 3-cycle and (2^k,2^k+1) for k = 1 and k > 2 are 2-cycles; all other numbers are fixed points. - Klaus Brockhaus, Jan 24 2006

In other words, a(2^k)=2^k+1 for k >= 3, a(2^k+1) = 2^k for k>=3, and otherwise a(n) = n for n >= 7. - N. J. A. Sloane, Mar 25 2022

Extensions

More terms from Klaus Brockhaus, Jan 24 2006