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.

1, 5, 17, 85, 257, 1285, 4369, 21845, 65537, 327685, 1114129, 5570645, 16843009, 84215045, 286331153, 1431655765, 4294967297, 21474836485, 73014444049, 365072220245, 1103806595329, 5519032976645, 18764712120593, 93823560602965, 281479271743489, 1407396358717445

Offset

0,2

Comments

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

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

Orbit of 1 under iteration of Rule 90 = A048725 = (n -> n XOR 4n). - M. F. Hasler, Oct 09 2017

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..200

A. J. Macfarlane, Generating functions for integer sequences defined by the evolution of cellular automata..., Fig.9

Eric Weisstein's World of Mathematics, Rule 90

Wikipedia, Rule 90

Stephen Wolfram, Geometry of Binomial Coefficients, Amer. Math. Monthly, Volume 91, Number 9, November 1984, pages 566-571.

S. Wolfram, O. Martin, and A.M. Odlyzko, Algebraic Properties of Cellular Automata (1984), Communications in Mathematical Physics, 93 (March 1984) 219-258.

Index entries for sequences related to cellular automata

Formula

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

a(n) = Sum_{k=0..n} (C(2*n, 2*k) mod 2)*4^(n-k). - Paul Barry, Jan 03 2005

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

a(n) = A001317(2n). - Alex Ratushnyak, May 04 2012

Example

Successive states are:
          1
         101
        10001
       1010101
      100000001
     10100000101
    1000100010001
   101010101010101
  10000000000000001
  ...
which when converted from binary to decimal give the sequence. - N. J. A. Sloane, Jul 21 2014

Maple

bit_n := (x, n) -> `mod`(floor(x/(2^n)), 2);
# A recursive, cellular automaton rule version:
sigmaminus := proc(n) option remember: if (0 = n) then (1)
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:

Mathematica

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 *)
a[ n_] := Sum[ 4^(n - k) Mod[Binomial[2 n, 2 k], 2], {k, 0, n}]; (* Michael Somos, Jun 30 2018 *)
a[ n_] := If[ n < 0, 0, Product[ BitGet[n, k] (2^(2^(k + 1))) + 1, {k, 0, n}]]; (* Michael Somos, Jun 30 2018 *)

Prog

(Python)
a=1
for n in range(55):
    print(a, end=", ")
    a ^= a*4
# Alex Ratushnyak, May 04 2012
(Python)
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
(PARI) vector(100, i, a=if(i>1, bitxor(a<<2, a), 1)) \\ M. F. Hasler, Oct 09 2017
(PARI) {a(n) = sum(k=0, n, binomial(2*n, 2*k)%2 * 4^(n-k))}; /* Michael Somos, Jun 30 2018 */

Crossrefs

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

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

Equals 4*A089893(n)+1.

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

Cf. Sierpiński's gasket, A047999.

Sequence in context: A365878 A363163 A002020 * A149756 A036756 A149757

Adjacent sequences: A038180 A038181 A038182 * A038184 A038185 A038186

Keyword

nonn,changed

Author

Antti Karttunen, Feb 09 1999

Status

approved