cp's OEIS Frontend

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

%I A269168 #16 Dec 10 2019 12:10:02
%S A269168 1,7,2,25,9,14,3,111,33,63,11,50,18,13,4,401,143,231,41,193,79,53,15,
%T A269168 222,66,126,22,51,17,28,5,1783,529,945,175,825,295,223,55,839,257,497,
%U A269168 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
%N A269168 Rule 30 binary tree permutation: a(1) = 1, a(2n) = A269160(a(n)), a(2n+1) = A269164(1+a(n)).
%C A269168 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:
%C A269168                                      |
%C A269168                   ...................1...................
%C A269168                  7                                       2
%C A269168       25......../ \........9                  14......../ \........3
%C A269168       / \                 / \                 / \                 / \
%C A269168      /   \               /   \               /   \               /   \
%C A269168     /     \             /     \             /     \             /     \
%C A269168   111      33         63       11         50       18         13       4
%C A269168 401 143  231 41    193  79   53  15    222  66  126  22     51  17   28 5
%C A269168 etc.
%C A269168 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.
%H A269168 Antti Karttunen, <a href="/A269168/b269168.txt">Table of n, a(n) for n = 1..1023</a>
%H A269168 Antti Karttunen, <a href="/A135141/a135141.pdf">Entanglement Permutations</a>, 2016-2017
%H A269168 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F A269168 a(1) = 1, after which, a(2n) = A269160(a(n)), a(2n+1) = A269164(1+a(n)).
%t A269168 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 *)
%o A269168 (Scheme, with memoization-macro definec)
%o A269168 (definec (A269168 n) (cond ((= 1 n) n) ((even? n) (A269160 (A269168 (/ n 2)))) (else (A269164 (+ 1 (A269168 (/ (- n 1) 2)))))))
%Y A269168 Inverse: A269167.
%Y A269168 Cf. A269160, A269164.
%Y A269168 Cf. A110240 (the left edge).
%K A269168 nonn,tabf,look
%O A269168 1,2
%A A269168 _Antti Karttunen_, Feb 21 2016