|
|
A269168
|
|
Rule 30 binary tree permutation: a(1) = 1, a(2n) = A269160(a(n)), a(2n+1) = A269164(1+a(n)).
|
|
4
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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)
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|