A269162 -id:A269162 - cp's OEIS frontend

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

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.

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

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 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, 1, 1, 1, 2, 2, 2, 0, 1, 1, 1, 1, 1, 0, 0, 3, 1, 0, 0, 0, 0, 0, 0, 1, 0

Offset: 0

Antti Karttunen, Feb 21 2016

nonn

a(n) gives the generational distance to the earliest finite ancestor when the binary expansion of n is interpreted as a pattern in Wolfram's Rule-30 cellular automaton or 0 if that pattern has no finite predecessors.
A110240 gives the record positions (after zero) and particularly, for n > 0, A110240(n) gives the first occurrence of n in this sequence.
See also comments in A269165.

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. A110240, A269160, A269162.
Cf. A269164 (the indices of zeros after the initial zero).
Cf. A269165 (the earliest finite ancestor for n).
Cf. also A268389.

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

If A269162(n) = 0, then a(n) = 0, otherwise a(n) = 1 + a(A269162(n)).
Other identities. For all n >= 0:
a(A110240(n)) = n. [Works as a left inverse of sequence A110240.]

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

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

Original entry on oeis.org

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

A110240 Decimal form of binary integer produced by the ON cells at n-th generation following Wolfram's Rule 30 cellular automaton starting from a single ON-cell represented as 1.

Original entry on oeis.org

1, 7, 25, 111, 401, 1783, 6409, 28479, 102849, 456263, 1641433, 7287855, 26332369, 116815671, 420186569, 1865727615, 6741246849, 29904391303, 107568396185, 477630335215, 1725755276049, 7655529137527, 27537575631497

Offset: 0

Alexandre Wajnberg and Eric Angelini, Sep 06 2005

See A245549 for binary equivalents. See A070952 for number of ON cells. - N. J. A. Sloane, Jul 28 2014
For n > 0: 3 < a(n+1) / a(n) < 5, floor(a(n+1)/a(n)) = A010702(n+1). - Reinhard Zumkeller, Jun 08 2013
Iterates of A269160 starting from a(0) = 1. See also A269168. - Antti Karttunen, Feb 20 2016
Also, the decimal representation of the n-th generation of the "Rule 66847740" 5-neighbors elementary cellular automaton starting with a single ON (black) cell. - Philipp O. Tsvetkov, Jul 17 2019

			a(1)=1 because the automaton begins at first "generation" with one black cell: 1;
a(2)=5 because one black cell, through Rule 30 at 2nd generation, produces three contiguous black cells: 111 (binary), so 7 (decimal);
a(3)=25 because the third generation is "black black white white black" cells: 11001, so 25 (decimal).

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
Erica Jen, Global properties of cellular automata, Journal of Statistical Physics 43 (1986), pp. 219-242.
Antti Karttunen, Terms up to a(255) drawn as binary strings, with 1 bit = 3x3 pixels resolution
Antti Karttunen, Terms up to a(1023) drawn as binary strings, with 1 bit = 1 pixel resolution
N. J. A. Sloane, Illustration of first 20 generations
Eric Weisstein's World of Mathematics, Rule 30.
Stephen Wolfram, Announcing the Rule 30 Prizes, 2019
Index entries for sequences related to cellular automata

Cf. A030101, A070950, A051023, A092539, A092540, A070952 (number of ON cells, the binary weight of terms), A100053, A100054, A100055, A094603, A094604, A000225, A074890, A010702, A245549, A269160, A269162.
Cf. A269165 (indices of ones in this sequence).
Cf. A269166 (a left inverse).
Left edge of A269168.
Cf. also A265281, A328106.
For bitwise XOR (and OR) combinations with other such 1D CA trajectories, see for example: A327971, A327972, A327973, A327976, A328103, A328104.

a110240 = foldl (\v d -> 2 * v + d) 0 . map toInteger . a070950_row
-- Reinhard Zumkeller, Jun 08 2013

rows = 23; ca = CellularAutomaton[30, {{1}, 0}, rows-1]; Table[ FromDigits[ ca[[k, rows-k+1 ;; rows+k-1]], 2], {k, 1, rows}] (* Jean-François Alcover, Jun 07 2012 *)

A269160(n) = bitxor(n, bitor(2*n, 4*n));
A110240(n) = if(!n,1,A269160(A110240(n-1))); \\ Antti Karttunen, Oct 05 2019

def A269160(n): return(n^((n<<1)|(n<<2)))
def genA110240():
    '''Yield successive terms of A110240 (Rule 30) starting from A110240(0)=1.'''
    s = 1
    while True:
       yield s
       s = A269160(s)
def take(n, g):
    '''Returns a list composed of the next n elements returned by generator g.'''
    z = []
    if 0 == n: return(z)
    for x in g:
        z.append(x)
        if n > 1: n = n-1
        else: return(z)
take(30, genA110240())
# Antti Karttunen, Oct 05 2019

;; With memoization-macro definec.
(definec (A110240 n) (if (zero? n) 1 (A269160 (A110240 (- n 1)))))
;; Antti Karttunen, Feb 20 2016

From Antti Karttunen, Feb 20 2016: (Start)
a(0) = 1, for n >= 1, a(n) = A269160(a(n-1)).
a(n) = A030101(A265281(n)). [The rule 30 is the mirror image of the rule 86.]
A269166(a(n)) = n for all n >= 0. (End)
From Antti Karttunen, Oct 05 2019: (Start)
For n >= 1, a(n) = a(n-1) XOR 2*A328104(n-1).
For n >= 1, a(n) = 2*a(n-1) XOR A327973(n). (End)

More terms from Eric W. Weisstein, Apr 08 2006

Offset corrected by Reinhard Zumkeller, Jun 08 2013

A269163 Numbers which have a finite predecessor in Wolfram's Rule 30 cellular automaton; range of A269160 sorted into ascending order.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Feb 20 2016

nonn

Numbers which have a finite predecessor in Wolfram's Rule 30 cellular automaton. The configuration of white and black cells is encoded in the binary representation (A007088) of each number.

The indexing starts from zero, because a(0) = 0 is a special case in this sequence. (Zero is the only number which is its own predecessor).

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

Complement: A269164.

Cf. A007088, A269162.

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

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

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

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

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

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

A110240 Decimal form of binary integer produced by the ON cells at n-th generation following Wolfram's Rule 30 cellular automaton starting from a single ON-cell represented as 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

Scheme

Formula

Extensions

A269163 Numbers which have a finite predecessor in Wolfram's Rule 30 cellular automaton; range of A269160 sorted into ascending order.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

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