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

Author

Antti Karttunen, Feb 20 2016

Keywords

• nonn

Comments

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).

Links

• 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

Crossrefs

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.

Programs

Mathematica

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

PARI

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

Python

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

Scheme

(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.

Formula

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