login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A038183 One-dimensional cellular automaton 'sigma-minus' (Rule 90): 000,001,010,011,100,101,110,111 -> 0,1,0,1,1,0,1,0. 25

%I

%S 1,5,17,85,257,1285,4369,21845,65537,327685,1114129,5570645,16843009,

%T 84215045,286331153,1431655765,4294967297,21474836485,73014444049,

%U 365072220245,1103806595329,5519032976645,18764712120593,93823560602965

%N One-dimensional cellular automaton 'sigma-minus' (Rule 90): 000,001,010,011,100,101,110,111 -> 0,1,0,1,1,0,1,0.

%C Generation n (starting from the generation 0: 1) interpreted as a binary number.

%C Observation: for n <= 15, a(n) = smallest number whose Euler totient is divisible by 4^n. This is not true for n = 16. - _Arkadiusz Wesolowski_, Jul 29 2012

%C Orbit of 1 under iteration of Rule 90 = A048725 = (n -> n XOR 4n). - _M. F. Hasler_, Oct 09 2017

%H Vincenzo Librandi, <a href="/A038183/b038183.txt">Table of n, a(n) for n = 0..200</a>

%H A. J. Macfarlane, <a href="http://www.damtp.cam.ac.uk/user/ajm/Papers2016/GFsForCAsOfEvenRuleNo.ps">Generating functions for integer sequences defined by the evolution of cellular automata...</a>, Fig.9

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Rule90.html">Rule 90</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Rule_90">Rule 90</a>

%H Stephen Wolfram, <a href="http://www.jstor.org/stable/2323743">Geometry of Binomial Coefficients</a>, Amer. Math. Monthly, Volume 91, Number 9, November 1984, pages 566-571.

%H S. Wolfram, O. Martin, and A.M. Odlyzko, <a href="http://www.stephenwolfram.com/publications/articles/mathematics/84-properties/index.html">Algebraic Properties of Cellular Automata (1984)</a>, Communications in Mathematical Physics, 93 (March 1984) 219-258.

%H <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a>

%F a(n) = Product_{i>=0} bit_n(n, i)*(2^(2^(i+1)))+1: A direct algebraic formula!

%F a(n) = sum_{k=0..n} (C(2*n, 2*k) mod 2)*4^(n-k). - _Paul Barry_, Jan 03 2005

%F a(2*n+1) = 5*a(2n); a(n+1) = a(n) XOR 4*a(n) where XOR is binary exclusive OR operator. - _Philippe Deléham_, Jun 18 2005

%F a(n) = A001317(2n). - _Alex Ratushnyak_, May 04 2012

%e Successive states are:

%e 1

%e 101

%e 10001

%e 1010101

%e 100000001

%e 10100000101

%e 1000100010001

%e 101010101010101

%e 10000000000000001

%e ...

%e which when converted from binary to decimal give the sequence. - _N. J. A. Sloane_, Jul 21 2014

%p bit_n := (x,n) -> `mod`(floor(x/(2^n)),2);

%p # A recursive, cellular automaton rule version:

%p sigmaminus := proc(n) option remember: if (0 = n) then (1)

%p else sum('((bit_n(sigmaminus(n-1),i)+bit_n(sigmaminus(n-1),i-2)) mod 2)*(2^i)', 'i'=0..(2*n)) fi: end:

%t r = 24; c = CellularAutomaton[90, {{1}, 0}, r - 1]; Table[FromDigits[c[[k, r - k + 1 ;; r + k - 1]], 2], {k, r}] (* _Arkadiusz Wesolowski_, Jun 09 2013 *)

%t a[ n_] := Sum[ 4^(n - k) Mod[Binomial[2 n, 2 k], 2], {k, 0, n}]; (* _Michael Somos_, Jun 30 2018 *)

%t a[ n_] := If[ n < 0, 0, Product[ BitGet[n, k] (2^(2^(k + 1))) + 1, {k, 0, n}]]; (* _Michael Somos_, Jun 30 2018 *)

%o (Python)

%o a=1

%o for n in range(55):

%o . print a,

%o . a ^= a*4

%o # _Alex Ratushnyak_, May 04 2012

%o (PARI) vector(100,i,a=if(i>1,bitxor(a<<2,a),1)) \\ _M. F. Hasler_, Oct 09 2017

%o (PARI) {a(n) = sum(k=0, n, binomial(2*n, 2*k)%2 * 4^(n-k))}; /* _Michael Somos_, Jun 30 2018 */

%Y Cf. A006977, A006978, A038184, A038185 (other cellular automata), A000215 (Fermat numbers).

%Y Also alternate terms of A001317. Cf. A048710, A048720, A048757 (same 0/1-patterns interpreted in Fibonacci number system).

%Y Equals 4*A089893(n)+1.

%Y For right half of triangle (excluding the middle bit) see A245191.

%Y Cf. Sierpiński's gasket, A047999.

%K nonn

%O 0,2

%A _Antti Karttunen_, Feb 09 1999

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 15 21:17 EDT 2019. Contains 328038 sequences. (Running on oeis4.)