|
%I #82 May 03 2023 17:09:33
%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,281479271743489,1407396358717445
%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, end=",")
%o a ^= a*4
%o # _Alex Ratushnyak_, May 04 2012
%o (Python)
%o 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 (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
|
