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

Author

Antti Karttunen, Feb 09 1999

Keywords

• nonn

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

Examples

			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
		

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

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.

Programs

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

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 */

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)<Chai Wah Wu, May 02 2023

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