A368427 A permutation related to the Christmas tree pattern map (A367508): a(1) = 1, and for any n > 1, a(n) = A053644(n) + A367562(n-1).

1, 2, 3, 6, 4, 5, 7, 12, 13, 10, 14, 8, 9, 11, 15, 26, 24, 25, 27, 28, 20, 21, 29, 18, 22, 30, 16, 17, 19, 23, 31, 52, 53, 50, 54, 48, 49, 51, 55, 56, 57, 42, 58, 40, 41, 43, 59, 44, 60, 36, 37, 45, 61, 34, 38, 46, 62, 32, 33, 35, 39, 47, 63, 106, 104, 105

Offset: 1

Author

Rémy Sigrist, Dec 24 2023

Keywords

• nonn
• look
• base

Comments

This sequence is a permutation of the positive integers (with inverse A368428):

- the Christmas tree pattern map runs through all finite nonempty binary words,

- by prefixing these words with a 1, we obtain the binary expansions of all integers >= 2,

- hence, with the leading term a(1) = 1, we have a permutation of the positive integers.

Apparently, A088163 \ {0} corresponds to the fixed points.

We can also obtain this sequence by applying the Christmas tree pattern map starting from the chain "1" (instead of "0 1") and converting the resulting binary words to decimal.

Examples

			The first terms, alongside their binary expansion and the corresponding word in the Christmas tree pattern map, are:
  n   a(n)  bin(a(n))  Xmas word
  --  ----  ---------  ---------
   1     1          1        N/A
   2     2         10          0
   3     3         11          1
   4     6        110         10
   5     4        100         00
   6     5        101         01
   7     7        111         11
   8    12       1100        100
   9    13       1101        101
  10    10       1010        010
  11    14       1110        110
  12     8       1000        000
  13     9       1001        001
  14    11       1011        011
  15    15       1111        111
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 1..8191
• Rémy Sigrist, PARI program
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Cf. A053644, A088163, A367508, A367562, A368428 (inverse).

Programs

Mathematica

With[{imax=7},Map[FromDigits[#,2]&,Flatten[NestList[Map[Delete[{If[Length[#]>1,Map[#<>"0"&,Rest[#]],Nothing],Join[{#[[1]]<>"0"},Map[#<>"1"&,#]]},0]&],{{"1"}},imax-1]]]] (* Generates terms up to order 7 *) (* Paolo Xausa, Dec 28 2023 *)

PARI

See Links section.

Python

from itertools import islice
from functools import reduce
def uniq(r): return reduce(lambda u, e: u if e in u else u+[e], r, [])
def agen():  # generator of terms
    R = [["1"]]
    while R:
        r = R.pop(0)
        yield from map(lambda b: int(b, 2), r)
        if len(r) > 1: R.append(uniq([r[k]+"0" for k in range(1, len(r))]))
        R.append(uniq([r[0]+"0", r[0]+"1"] + [r[k]+"1" for k in range(1, len(r))]))
print(list(islice(agen(), 66))) # Michael S. Branicky, Dec 24 2023