A269168 Rule 30 binary tree permutation: a(1) = 1, a(2n) = A269160(a(n)), a(2n+1) = A269164(1+a(n)).

1, 7, 2, 25, 9, 14, 3, 111, 33, 63, 11, 50, 18, 13, 4, 401, 143, 231, 41, 193, 79, 53, 15, 222, 66, 126, 22, 51, 17, 28, 5, 1783, 529, 945, 175, 825, 295, 223, 55, 839, 257, 497, 95, 203, 69, 49, 19, 802, 286, 462, 82, 386, 158, 106, 30, 221, 67, 119, 21, 100, 36, 27, 6, 6409, 2295, 3703, 657, 3159, 1201, 849, 233

Offset

1,2

Comments

This sequence can be represented as a binary tree. Each left hand child is produced as A269160(n), and each right hand child as A269164(1+n), when the parent node contains n:

|

...................1...................

7 2

25......../ \........9 14......../ \........3

/ \ / \ / \ / \

/ \ / \ / \ / \

/ \ / \ / \ / \

111 33 63 11 50 18 13 4

401 143 231 41 193 79 53 15 222 66 126 22 51 17 28 5

etc.

Each maximal leftward branch (e.g. 1, 7, 25, ... (= A110240) or 9, 63, 193, ... or 2, 14, 50, ...) gives a trajectory of Rule 30 cellular automaton starting from a particular "seed configuration" which are given in A269164.

Links

Antti Karttunen, Table of n, a(n) for n = 1..1023

Antti Karttunen, Entanglement Permutations, 2016-2017

Index entries for sequences that are permutations of the natural numbers

Formula

a(1) = 1, after which, a(2n) = A269160(a(n)), a(2n+1) = A269164(1+a(n)).

Mathematica

nmax = (* sequence length *) 100; terms (* from A269164 *) = 2000; Clear[a, f]; A269160[n_] := BitXor[n, BitOr[2 n, 4 n]]; f[max_] := f[max] = (s = Sort[Table[A269160[n], {n, 0, max}]]; Complement[Range[Last[s]], s][[1 ;; terms]]); f[terms]; f[max = 2 terms]; While[f[max] != f[max/2], max = 2 max]; A269164[n_Integer] := If[n > Length[f[max]], 0, f[max][[n]]]; a[1] = 1; a[n_] := a[n] = If[EvenQ[n], A269160[a[n/2]], A269164[1 + a[(n - 1)/2]]]; A269168 = Table[a[n], {n, 1, nmax}] (* Jean-François Alcover, Feb 23 2016 *)

Prog

(Scheme, with memoization-macro definec)
(definec (A269168 n) (cond ((= 1 n) n) ((even? n) (A269160 (A269168 (/ n 2)))) (else (A269164 (+ 1 (A269168 (/ (- n 1) 2)))))))

Crossrefs

Inverse: A269167.

Cf. A269160, A269164.

Cf. A110240 (the left edge).

Sequence in context: A213836 A340801 A338284 * A279943 A279999 A217366

Adjacent sequences: A269165 A269166 A269167 * A269169 A269170 A269171

Keyword

nonn,tabf,look

Author

Antti Karttunen, Feb 21 2016

Status

approved