A269163 -id:A269163 - cp's OEIS frontend

A269160 Formula for Wolfram's Rule 30 cellular automaton: a(n) = n XOR (2n OR 4n).

0, 7, 14, 13, 28, 27, 26, 25, 56, 63, 54, 53, 52, 51, 50, 49, 112, 119, 126, 125, 108, 107, 106, 105, 104, 111, 102, 101, 100, 99, 98, 97, 224, 231, 238, 237, 252, 251, 250, 249, 216, 223, 214, 213, 212, 211, 210, 209, 208, 215, 222, 221, 204, 203, 202, 201, 200, 207, 198, 197, 196, 195, 194, 193, 448, 455, 462

Offset: 0

Antti Karttunen, Feb 20 2016

nonn

Take n, write it in binary, see what Rule 30 would do to that state, convert it to decimal: that is a(n). For example, we can see in A110240 that 7 = 111_2 becomes 25 = 11001_2 under Rule 30, which is shown here by a(7) = 25. - N. J. A. Sloane, Nov 25 2016
The sequence is injective: no value occurs more than once.
Fibbinary numbers (A003714) give all integers n>=0 for which a(n) = A048727(n) and for which a(n) = A269161(n).

Antti Karttunen, Table of n, a(n) for n = 0..16383
Eric Weisstein's World of Mathematics, Rule 30
Index entries for sequences related to cellular automata
Index to Elementary Cellular Automata

Cf. A003714, A003986, A003987, A057889, A070939.
Cf. A110240 (iterates starting from 1).
Cf. A269162 (left inverse).
Cf. A269163 (same sequence sorted into ascending order).
Cf. A269164 (values missing from this sequence).
Cf. also A048727, A269161.

a[n_] := BitXor[n, BitOr[2n, 4n]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Feb 23 2016 *)

a(n) = bitxor(n, bitor(2*n, 4*n)); \\ Michel Marcus, Feb 23 2016

def A269160(n): return n^(n<<1 | n<<2) # Chai Wah Wu, Jun 29 2022

(define (A269160 n) (A003987bi n (A003986bi (* 4 n) (* 2 n)))) ;; Where A003986bi and A003987bi are implementation of dyadic functions giving bitwise-OR (A003986) and bitwise-XOR (A003987) of their arguments.

a(n) = n XOR (2n OR 4n) = A003987(n, A003986(2*n, 4*n)).
Other identities. For all n >= 0:
a(2*n) = 2*a(n).
a(n) = A057889(A269161(A057889(n))). [Rule 30 is the mirror image of rule 86.]
A269162(a(n)) = n.
For all n >= 1:
A070939(a(n)) - A070939(n) = 2. [The binary length of a(n) is two bits longer than that of n for all nonzero values.]
G.f.: (3*x + 2*x^2 +x^3)/(1 - x^4) + Sum_{k>=1}(2^(k + 1)*x^(2^(k - 1))/((1 + x^(2^(k + 1)))*(1 - x))). - Miles Wilson, Jan 24 2025

A269164 Numbers not in range of A269160; indices of zeros in A269162 from n >= 1 onward.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 55, 57, 58, 59, 60, 61, 62, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96

Offset: 1

Antti Karttunen, Feb 20 2016

nonn

Natural numbers n for which there does not exist any number k such that A269160(k) = n.

These are binary representations (shown in decimal) of Garden of Eden patterns in Wolfram's Rule 30 cellular automaton if infinite predecessors are forbidden.

Antti Karttunen, Table of n, a(n) for n = 1..12285
Eric Weisstein's World of Mathematics, Rule 30
Index entries for sequences related to cellular automata
Index to Elementary Cellular Automata

Complement: A269163.
Indices of zeros in A269162 and A269166 (after the initial zero).
Cf. A269169 (left inverse).
Cf. A269160, A269168.

terms = 100; Clear[f]; f[max_] := f[max] = (s = Sort[Table[BitXor[n, BitOr[2n, 4n]], {n, 0, max}]]; Complement[Range[Last[s]], s][[1 ;; terms ]]); f[terms]; f[max = 2 terms]; While[Print[max]; f[max] != f[max/2], max = 2 max]; A269164 = f[max] (* Jean-François Alcover, Feb 23 2016 *)

Other identities. For all n >= 1:

A269169(a(n)) = n.

A269162 a(0) = 0, for n > 0, a(n) = the least (necessarily also unique) k such that A269160(k) = n, or 0 if no such k exists.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 3, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 6, 5, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 15, 14, 13, 12, 11, 10, 0, 8, 0, 0, 0, 0, 0, 0, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 31, 30, 29, 28, 27, 26, 0, 24, 23, 22, 21, 20, 0, 0, 25

Offset: 0

Antti Karttunen, Feb 20 2016

nonn

If n > 0 and a(n) > 0 then a(n) is the unique finite predecessor of the configuration encoded in the binary representation of n (A007088) when Wolfram's Rule 30 cellular automaton is applied.

Antti Karttunen, Table of n, a(n) for n = 0..16387
Eric Weisstein's World of Mathematics, Rule 30
Index entries for sequences related to cellular automata
Index to Elementary Cellular Automata

Cf. A110240, A269160, A269163, A269164 (indices of zeros), A269165, A269166.

(* empirical *) a[n_] := Module[{k}, For[k = Floor[n/7], k <= Ceiling[n/3], k++, If[BitXor[k, BitOr[2k, 4k]] == n, Return[k]]]; 0]; Table[a[n], {n, 0, 16387}] (* Jean-François Alcover, Feb 23 2016 *)

(define (A269162 n) (let loop ((p 0)) (cond ((= n (A269160 p)) p) ((> p n) 0) (else (loop (+ 1 p)))))) ;; Very slow implementation.
(define (A269162 n) (if (zero? n) n (let ((nwid-2 (- (A000523 n) 2))) (let loop ((p (if (< n 4) 0 (A000079 nwid-2)))) (let ((k (A269160 p))) (cond ((= n k) p) ((> (A000523 p) nwid-2) 0) (else (loop (+ 1 p))))))))) ;; Somewhat optimized.

Other identities. For all n >= 0:
a(A269160(n)) = n. [This sequence works as a left inverse of A269160.]
a(A110240(n+1)) = A110240(n).

A269165 If A269162(n) = 0, then a(n) = n, otherwise a(n) = a(A269162(n)).

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 1, 8, 9, 10, 11, 12, 3, 2, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 1, 6, 5, 4, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 15, 2, 3, 12, 11, 10, 55, 8, 57, 58, 59, 60, 61, 62, 9, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81

Offset: 0

Antti Karttunen, Feb 21 2016

nonn

a(n) is the earliest finite ancestor pattern n in Rule-30 or n itself if n has no finite predecessors.
Starting from k = a(n) with any n and iterating map k -> A269160(k) exactly A269166(n) times yields n back.
Apart from zero no terms of A269163 occur so all terms after zero are in A269164. Each term of A269164 occurs an infinitely many times.

Antti Karttunen, Table of n, a(n) for n = 0..32767
Eric Weisstein's World of Mathematics, Rule 30
Index entries for sequences related to cellular automata
Index to Elementary Cellular Automata

Cf. A269160, A269163, A269164, A269166 (for a distance in A269162-steps to the ancestor pattern).
Cf. A110240 (indices of ones in this sequence).
Cf. also A268669.

;; This implementation is based on given recurrence and utilitizes the memoization-macro definec:
(definec (A269165 n) (let ((p (A269162 n))) (if (zero? p) n (A269165 p))))
;; This one computes the same with tail-recursive iteration:
(define (A269165 n) (let loop ((n n) (p (A269162 n))) (if (zero? p) n (loop p (A269162 p)))))

If A269162(n) = 0, then a(n) = n, otherwise a(n) = a(A269162(n)).

A269167 Permutation of natural numbers: a(1) = 1, a(A269160(n)) = 2a(n), a(A269164(n+1)) = 1+(2a(n)).

Original entry on oeis.org

1, 3, 7, 15, 31, 63, 2, 127, 5, 255, 11, 511, 14, 6, 23, 1023, 29, 13, 47, 2047, 59, 27, 95, 4095, 4, 126, 62, 30, 119, 55, 191, 8191, 9, 253, 125, 61, 239, 111, 383, 16383, 19, 507, 251, 123, 479, 223, 767, 32767, 46, 12, 28, 1022, 22, 510, 39, 254, 1015, 503, 247, 959, 447, 1535, 10, 65535, 93, 25, 57, 2045, 45

Offset: 1

Antti Karttunen, Feb 21 2016

nonn

Antti Karttunen, Table of n, a(n) for n = 1..12285
Index entries for sequences that are permutations of the natural numbers

Inverse: A269168.

Cf. A269160, A269162, A269163, A269164, A269169.

terms = 100; 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_] := f[max][[n]]; a[1]=1; eq[n_] := a[A269160[n]] == 2*a[n] && a[A269164[n+1]] == 1 + 2*a[n]; A269167 = Array[a, terms-1] /. Solve[Array[eq, terms-1]] // First (* Jean-François Alcover, Feb 23 2016 *)

a(1) = 1, for n > 1, if A269162(n) > 0 [when n is in A269163], a(n) = 2*a(A269162(n)), otherwise [when n is in A269164], a(n) = 1 + 2*a(A269169(n)-1).

cp's OEIS Frontend

A269160 Formula for Wolfram's Rule 30 cellular automaton: a(n) = n XOR (2n OR 4n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Scheme

Formula

A269164 Numbers not in range of A269160; indices of zeros in A269162 from n >= 1 onward.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A269162 a(0) = 0, for n > 0, a(n) = the least (necessarily also unique) k such that A269160(k) = n, or 0 if no such k exists.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Scheme

Formula

A269165 If A269162(n) = 0, then a(n) = n, otherwise a(n) = a(A269162(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Scheme

Formula

A269167 Permutation of natural numbers: a(1) = 1, a(A269160(n)) = 2*a(n), a(A269164(n+1)) = 1+(2*a(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A269167 Permutation of natural numbers: a(1) = 1, a(A269160(n)) = 2a(n), a(A269164(n+1)) = 1+(2a(n)).