login
The OEIS is supported by the many generous donors 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
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 (list; graph; refs; listen; history; text; internal format)
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
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.
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
KEYWORD
nonn
AUTHOR
Antti Karttunen, Feb 09 1999
STATUS
approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 13:42 EDT 2024. Contains 371254 sequences. (Running on oeis4.)