A269168 - OEIS

A269168

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

%I #16 Dec 10 2019 12:10:02

%S 1,7,2,25,9,14,3,111,33,63,11,50,18,13,4,401,143,231,41,193,79,53,15,

%T 222,66,126,22,51,17,28,5,1783,529,945,175,825,295,223,55,839,257,497,

%U 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 Rule 30 binary tree permutation: a(1) = 1, a(2n) = A269160(a(n)), a(2n+1) = A269164(1+a(n)).

%C 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 |

%C ...................1...................

%C 7 2

%C 25......../ \........9 14......../ \........3

%C / \ / \ / \ / \

%C 111 33 63 11 50 18 13 4

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

%C etc.

%C 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 Antti Karttunen, <a href="/A269168/b269168.txt">Table of n, a(n) for n = 1..1023</a>

%H Antti Karttunen, <a href="/A135141/a135141.pdf">Entanglement Permutations</a>, 2016-2017

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

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

%t 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 (Scheme, with memoization-macro definec)

%o (definec (A269168 n) (cond ((= 1 n) n) ((even? n) (A269160 (A269168 (/ n 2)))) (else (A269164 (+ 1 (A269168 (/ (- n 1) 2)))))))

%Y Inverse: A269167.

%Y Cf. A269160, A269164.

%Y Cf. A110240 (the left edge).

%K nonn,tabf,look

%O 1,2

%A _Antti Karttunen_, Feb 21 2016