A210770 a(1) = 1, a(2) = 2; for n > 1, a(2*n+2) = smallest number not yet seen, a(2*n+1) = a(2*n) + a(2*n+2).

1, 2, 5, 3, 7, 4, 10, 6, 14, 8, 17, 9, 20, 11, 23, 12, 25, 13, 28, 15, 31, 16, 34, 18, 37, 19, 40, 21, 43, 22, 46, 24, 50, 26, 53, 27, 56, 29, 59, 30, 62, 32, 65, 33, 68, 35, 71, 36, 74, 38, 77, 39, 80, 41, 83, 42, 86, 44, 89, 45, 92, 47, 95, 48, 97, 49, 100

Offset: 1

Author

Reinhard Zumkeller, Mar 25 2012

Keywords

• nonn

Comments

Permutation of natural numbers with inverse A210771.

From Jeffrey Shallit, Jun 18 2021: (Start)

This sequence is "2-sychronized"; there is a 23-state finite automaton that recognizes the base-2 representations of n and a(n), in parallel.

It obeys the identities

a(4n+3) = a(2n+1) - a(4n) + 2 a(4n+2)

a(8n) = 2a(4n)

a(8n+1) = a(2n+1) + 3a(4n)

a(8n+2) = a(2n+1) + 2 a(4n) - a(4n+1) + a(4n+2)

a(8n+4) = a(2n+1) + a(4n+2)

a(8n+5) = 3a(2n+1) - a(4n) +2a(4n+2)

a(8n+6) = 2a(2n+1) - a(4n) + a(4n+2). (End)

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Cf. A064736.

Programs

Haskell

import Data.List (delete)
a210770 n = a210770_list !! (n-1)
a210770_list = 1 : 2 : f 1 2 [3..] where
   f u v (w:ws) = u' : w : f u' w (delete u' ws) where u' = v + w

Python

def aupton(terms):
    alst, seen = [1, 2], {1, 2}
    for n in range(2, terms, 2):
        anp1 = alst[-1] + 1
        while anp1 in seen: anp1 += 1
        an = alst[n-1] + anp1
        alst, seen = alst + [an, anp1], seen | {an, anp1}
    return alst[:terms]
print(aupton(67)) # Michael S. Branicky, Jun 18 2021

Formula

a(2*n-1) = A022441(n-1); a(2*n) = A055562(n-1).

Extensions

Definition corrected by Jeffrey Shallit, Jun 18 2021