Location via proxy:   [ UP ]  
[Report a bug]   [Manage cookies]                
Search: a269168 -id:a269168
     Sort: relevance | references | number | modified | created      Format: long | short | data
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.
+10
34
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,2
COMMENTS
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
FORMULA
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)
EXAMPLE
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).
MATHEMATICA
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 *)
PROG
(Haskell)
a110240 = foldl (\v d -> 2 * v + d) 0 . map toInteger . a070950_row
-- Reinhard Zumkeller, Jun 08 2013
(Scheme, with memoization-macro definec)
(definec (A110240 n) (if (zero? n) 1 (A269160 (A110240 (- n 1)))))
;; Antti Karttunen, Feb 20 2016
(PARI)
A269160(n) = bitxor(n, bitor(2*n, 4*n));
A110240(n) = if(!n, 1, A269160(A110240(n-1))); \\ Antti Karttunen, Oct 05 2019
(Python)
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
CROSSREFS
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.
KEYWORD
easy,nonn,base
AUTHOR
EXTENSIONS
More terms from Eric W. Weisstein, Apr 08 2006
Offset corrected by Reinhard Zumkeller, Jun 08 2013
STATUS
approved
Numbers not in range of A269160; indices of zeros in A269162 from n >= 1 onward.
+10
9
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,2
COMMENTS
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.
FORMULA
Other identities. For all n >= 1:
A269169(a(n)) = n.
MATHEMATICA
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 *)
PROG
(Scheme, with Antti Karttunen's IntSeq-library)
(define A269164 (MATCHING-POS 1 1 (lambda (n) (zero? (A269162 n)))))
CROSSREFS
Complement: A269163.
Indices of zeros in A269162 and A269166 (after the initial zero).
Cf. A269169 (left inverse).
KEYWORD
nonn
AUTHOR
Antti Karttunen, Feb 20 2016
STATUS
approved
Permutation of natural numbers: a(1) = 1, a(A269160(n)) = 2*a(n), a(A269164(n+1)) = 1+(2*a(n)).
+10
3
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,2
FORMULA
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).
MATHEMATICA
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 *)
PROG
(Scheme, with memoization-macro definec)
(definec (A269167 n) (cond ((= 1 n) n) ((not (zero? (A269162 n))) (* 2 (A269167 (A269162 n)))) (else (+ 1 (* 2 (A269167 (- (A269169 n) 1)))))))
CROSSREFS
KEYWORD
nonn
AUTHOR
Antti Karttunen, Feb 21 2016
STATUS
approved

Search completed in 0.011 seconds