|
|
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
|
|
LINKS
|
Eric Weisstein's World of Mathematics, Rule 90
|
|
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
|
|
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
(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
|
For right half of triangle (excluding the middle bit) see A245191.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|