login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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.
14
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
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
KEYWORD
easy,base,nonn
AUTHOR
Leroy Quet, Jan 23 2006
EXTENSIONS
More terms from Klaus Brockhaus, Jan 24 2006
STATUS
approved