cp's OEIS Frontend

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.

%I A038183 #83 Feb 16 2025 08:32:38
%S A038183 1,5,17,85,257,1285,4369,21845,65537,327685,1114129,5570645,16843009,
%T A038183 84215045,286331153,1431655765,4294967297,21474836485,73014444049,
%U A038183 365072220245,1103806595329,5519032976645,18764712120593,93823560602965,281479271743489,1407396358717445
%N 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.
%C A038183 Generation n (starting from the generation 0: 1) interpreted as a binary number.
%C A038183 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 A038183 Orbit of 1 under iteration of Rule 90 = A048725 = (n -> n XOR 4n). - _M. F. Hasler_, Oct 09 2017
%H A038183 Vincenzo Librandi, <a href="/A038183/b038183.txt">Table of n, a(n) for n = 0..200</a>
%H A038183 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 A038183 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Rule90.html">Rule 90</a>
%H A038183 Wikipedia, <a href="http://en.wikipedia.org/wiki/Rule_90">Rule 90</a>
%H A038183 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 A038183 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 A038183 <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a>
%F A038183 a(n) = Product_{i>=0} bit_n(n, i)*(2^(2^(i+1)))+1: A direct algebraic formula!
%F A038183 a(n) = Sum_{k=0..n} (C(2*n, 2*k) mod 2)*4^(n-k). - _Paul Barry_, Jan 03 2005
%F A038183 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 A038183 a(n) = A001317(2n). - _Alex Ratushnyak_, May 04 2012
%e A038183 Successive states are:
%e A038183           1
%e A038183          101
%e A038183         10001
%e A038183        1010101
%e A038183       100000001
%e A038183      10100000101
%e A038183     1000100010001
%e A038183    101010101010101
%e A038183   10000000000000001
%e A038183   ...
%e A038183 which when converted from binary to decimal give the sequence. - _N. J. A. Sloane_, Jul 21 2014
%p A038183 bit_n := (x,n) -> `mod`(floor(x/(2^n)),2);
%p A038183 # A recursive, cellular automaton rule version:
%p A038183 sigmaminus := proc(n) option remember: if (0 = n) then (1)
%p A038183 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 A038183 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 A038183 a[ n_] := Sum[ 4^(n - k) Mod[Binomial[2 n, 2 k], 2], {k, 0, n}]; (* _Michael Somos_, Jun 30 2018 *)
%t A038183 a[ n_] := If[ n < 0, 0, Product[ BitGet[n, k] (2^(2^(k + 1))) + 1, {k, 0, n}]]; (* _Michael Somos_, Jun 30 2018 *)
%o A038183 (Python)
%o A038183 a=1
%o A038183 for n in range(55):
%o A038183     print(a, end=",")
%o A038183     a ^= a*4
%o A038183 # _Alex Ratushnyak_, May 04 2012
%o A038183 (Python)
%o A038183 def A038183(n): return sum((bool(~(m:=n<<1)&m-k)^1)<<k for k in range((n<<1)+1)) # _Chai Wah Wu_, May 02 2023
%o A038183 (PARI) vector(100,i,a=if(i>1,bitxor(a<<2,a),1)) \\ _M. F. Hasler_, Oct 09 2017
%o A038183 (PARI) {a(n) = sum(k=0, n, binomial(2*n, 2*k)%2 * 4^(n-k))}; /* _Michael Somos_, Jun 30 2018 */
%Y A038183 Cf. A006977, A006978, A038184, A038185 (other cellular automata), A000215 (Fermat numbers).
%Y A038183 Also alternate terms of A001317. Cf. A048710, A048720, A048757 (same 0/1-patterns interpreted in Fibonacci number system).
%Y A038183 Equals 4*A089893(n)+1.
%Y A038183 For right half of triangle (excluding the middle bit) see A245191.
%Y A038183 Cf. Sierpiński's gasket, A047999.
%K A038183 nonn
%O A038183 0,2
%A A038183 _Antti Karttunen_, Feb 09 1999