login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

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 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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 21 03:01 EST 2018. Contains 317427 sequences. (Running on oeis4.)