

A109812


a(1)=1; thereafter a(n) = smallest positive integer not among the earlier terms of the sequence such that a(n) and a(n1) have no common 1bits in their binary representations.


13



1, 2, 4, 3, 8, 5, 10, 16, 6, 9, 18, 12, 17, 14, 32, 7, 24, 33, 20, 11, 36, 19, 40, 21, 34, 13, 48, 15, 64, 22, 41, 66, 25, 38, 65, 26, 37, 72, 23, 96, 27, 68, 35, 28, 67, 44, 80, 39, 88, 128, 29, 98, 129, 30, 97, 130, 45, 82, 132, 42, 69, 50, 73, 52, 74, 49, 70, 56, 71, 136, 51
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Theorem: Sequence is a permutation of the positive integers.  Leroy Quet, Aug 16 2005
Proof of theorem: It is clear that the sequence is infinite.
Suppose M is the smallest number than does not occur. Choose n_0 such that for all n > n_0, a(n) > M. Let M_1 = max {a(i), 1 <= i <= n_0}, and let 2^k be smallest power of 2 > M_1.
For some n > n__0, a(n) >= 2^k. The first such term will be a(n) = 2^k. Then a(n+1) = smallest number not among a(1), ..., a(n), which is M. Contradiction. QED  N. J. A. Sloane, Jun 02 2018
Inverse permutation = A113233; A113232 = a(a(n)).  Reinhard Zumkeller, Oct 19 2005
The only known fixed points are 1, 2, 12, 14, 37. Are there any others?  N. J. A. Sloane, Jun 02 2018


LINKS

Paul Tek, 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


FORMULA

It would be nice to have a formula or recurrence.  N. J. A. Sloane, Jun 02 2018


EXAMPLE

a(6) = 5, which is 101 in binary. Of the terms not among (1,2,4,3,8,5), the earlier terms of the series, 10 (decimal) = 1010 (binary) is the smallest positive integer with no common 1bits with the binary representation of 5.
Of the other positive integers not occurring earlier in the sequence (6 = 110 binary, 7 = 111 binary, 9 = 1001 binary), each has at least one 1bit in common with 5 = 101 in binary.


PROG

(Haskell)
import Data.Bits ((.&.)); import Data.List (delete)
a109812 n = a109812_list !! (n1)
a109812_list = f 0 [1..] :: [Int] where
f v ws = g ws where
g (x:xs) = if v .&. x == 0 then x : f x (delete x ws) else g xs
 Reinhard Zumkeller, Sep 15 2014
(Python)
A109812_list, l1, s, b = [1], 1, 2, set()
for _ in range(10**6):
i = s
while True:
if not (i in b or i & l1):
A109812_list.append(i)
l1 = i
b.add(i)
while s in b:
b.remove(s)
s += 1
break
i += 1 # Chai Wah Wu, Jun 04 2018


CROSSREFS

Cf. A115510, A113232, A113233, A113234.
For positions of powers of 2 see A305370.
See also A305369.
The graphs of A109812, A252867, A305369, A305372 all have roughly the same, mysterious, fractallike structure.  N. J. A. Sloane, Jun 03 2018
Sequence in context: A053211 A131390 A131395 * A137622 A118783 A242706
Adjacent sequences: A109809 A109810 A109811 * A109813 A109814 A109815


KEYWORD

nonn,look


AUTHOR

Leroy Quet, Aug 16 2005


EXTENSIONS

More terms from John W. Layman, Aug 18 2005
Edited by N. J. A. Sloane, Jun 02 2018


STATUS

approved



