This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A109812 a(1)=1; thereafter a(n) = smallest positive integer not among the earlier terms of the sequence such that a(n) and a(n-1) have no common 1-bits 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 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 1-bits 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 1-bit in common with 5 = 101 in binary. PROG (Haskell) import Data.Bits ((.&.)); import Data.List (delete) a109812 n = a109812_list !! (n-1) 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, fractal-like 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified January 22 15:57 EST 2019. Contains 319364 sequences. (Running on oeis4.)