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

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

Links

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

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

Example

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.

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

Prog

(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

Crossrefs

Cf. A064413, A109812, A115511, A226077.

Sequence in context: A286367 A196047 A106409 * A230598 A245446 A070264

Adjacent sequences: A115507 A115508 A115509 * A115511 A115512 A115513

Keyword

easy,base,nonn

Author

Leroy Quet, Jan 23 2006

Extensions

More terms from Klaus Brockhaus, Jan 24 2006

Status

approved