This file contains articles about one-dimensional cellular automata mod 3 an\
d mod 5 where the individuality os kept
3 2 n
On the sequence, (x + x + x + 1) , modulo , 3
By Shalosh B. Ekhad
3 2
You raise the polynomial, x + x + x + 1,
to the n-th power, and then take it mod, 3,
and would like to know, for each i from 1 to, 2
the number of times it shows up as a coefficient in that expanded polynomial\
. This article answers this question.
The first, 41, terms staring at n=0, for the number of occurrences of, 1,
are:
[1, 4, 3, 4, 10, 2, 3, 10, 7, 4, 16, 12, 10, 22, 17, 2, 11, 32, 3, 12, 13, 10,
30, 20, 7, 24, 21, 4, 16, 12, 16, 40, 8, 12, 40, 28, 10, 40, 36, 22, 55]
The first, 41, terms staring at n=0, for the number of occurrences of, 2,
are:
[0, 0, 2, 0, 3, 10, 2, 6, 6, 0, 0, 8, 3, 12, 22, 10, 28, 4, 2, 8, 12, 6, 23, 28
, 6, 20, 20, 0, 0, 8, 0, 12, 40, 8, 24, 24, 3, 12, 29, 12, 42]
Just for kicks, for the googol-th term, the number of occurrences of i from \
1 to, 2, are:
[2342718599066881656620345760348398817498486542654925835656495104000000,
2342718599066881656620345760460324303125101028746173368443600896000000]
The first , 40, terms of the sequence, number of occurrences, 1,
i
shows up at the, 3 - 1, places are
[1, 3, 7, 21, 61, 183, 547, 1641, 4921, 14763, 44287, 132861, 398581, 1195743,
3587227, 10761681, 32285041, 96855123, 290565367, 871696101, 2615088301,
7845264903, 23535794707, 70607384121, 211822152361, 635466457083, 1906399371247
, 5719198113741, 17157594341221, 51472783023663, 154418349070987,
463255047212961, 1389765141638881, 4169295424916643, 12507886274749927,
37523658824249781, 112570976472749341, 337712929418248023, 1013138788254744067,
3039416364764232201, 9118249094292696601]
The first , 40, terms of the sequence, number of occurrences, 2,
i
shows up at the, 3 - 1, places are
[0, 2, 6, 20, 60, 182, 546, 1640, 4920, 14762, 44286, 132860, 398580, 1195742,
3587226, 10761680, 32285040, 96855122, 290565366, 871696100, 2615088300,
7845264902, 23535794706, 70607384120, 211822152360, 635466457082, 1906399371246
, 5719198113740, 17157594341220, 51472783023662, 154418349070986,
463255047212960, 1389765141638880, 4169295424916642, 12507886274749926,
37523658824249780, 112570976472749340, 337712929418248022, 1013138788254744066,
3039416364764232200, 9118249094292696600]
Using the found enumerative automaton with, 12,
states, that we omit, it follows that
the (rigorously) PROVED rational generating functions for these sparse subse\
quence are as follows.
The generating function for the sequence for the number of occurrences of, 1,
i
in the sparse, 3 - 1, subseqeunce is
2
3 t - 1
- -------------------------
(t - 1) (3 t - 1) (t + 1)
and in Maple notation
-(3*t^2-1)/(t-1)/(3*t-1)/(t+1)
The generating function for the sequence for the number of occurrences of, 2,
i
in the sparse, 3 - 1, subseqeunce is
2 t
-------------------------
(t - 1) (3 t - 1) (t + 1)
and in Maple notation
2*t/(t-1)/(3*t-1)/(t+1)
This ends this article, that took, 0.039, seconds.
3 2 n
On the sequence, (x + x + x + 1) , modulo , 5
By Shalosh B. Ekhad
3 2
You raise the polynomial, x + x + x + 1,
to the n-th power, and then take it mod, 5,
and would like to know, for each i from 1 to, 4
the number of times it shows up as a coefficient in that expanded polynomial\
. This article answers this question.
The first, 41, terms staring at n=0, for the number of occurrences of, 1,
are:
[1, 4, 2, 4, 4, 4, 16, 2, 4, 16, 2, 8, 9, 10, 10, 4, 16, 10, 14, 22, 4, 16, 11,
14, 19, 4, 16, 8, 16, 16, 16, 64, 8, 16, 64, 2, 8, 18, 25, 16, 4]
The first, 41, terms staring at n=0, for the number of occurrences of, 2,
are:
[0, 0, 2, 2, 0, 0, 0, 2, 5, 2, 2, 8, 8, 8, 10, 2, 8, 12, 12, 10, 0, 0, 12, 12,
0, 0, 0, 8, 8, 0, 0, 0, 8, 20, 8, 2, 8, 26, 20, 10, 5]
The first, 41, terms staring at n=0, for the number of occurrences of, 3,
are:
[0, 0, 2, 2, 0, 0, 0, 14, 14, 2, 2, 8, 8, 8, 8, 2, 8, 10, 8, 8, 0, 0, 12, 12, 0
, 0, 0, 8, 8, 0, 0, 0, 56, 56, 11, 14, 56, 8, 8, 56, 14]
The first, 41, terms staring at n=0, for the number of occurrences of, 4,
are:
[0, 0, 1, 0, 3, 0, 0, 4, 0, 2, 1, 4, 8, 6, 8, 0, 0, 10, 11, 2, 3, 12, 10, 10,
18, 0, 0, 4, 0, 12, 0, 0, 16, 0, 2, 4, 16, 50, 48, 20, 0]
Just for kicks, for the googol-th term, the number of occurrences of i from \
1 to, 4, are:
[192080356189028487266304, 192080355942259435241472, 192080356283328708476928,
192080356036559656452096]
The first , 40, terms of the sequence, number of occurrences, 1,
i
shows up at the, 5 - 1, places are
[1, 4, 19, 94, 469, 2344, 11719, 58594, 292969, 1464844, 7324219, 36621094,
183105469, 915527344, 4577636719, 22888183594, 114440917969, 572204589844,
2861022949219, 14305114746094, 71525573730469, 357627868652344,
1788139343261719, 8940696716308594, 44703483581542969, 223517417907714844,
1117587089538574219, 5587935447692871094, 27939677238464355469,
139698386192321777344, 698491930961608886719, 3492459654808044433594,
17462298274040222167969, 87311491370201110839844, 436557456851005554199219,
2182787284255027770996094, 10913936421275138854980469,
54569682106375694274902344, 272848410531878471374511719,
1364242052659392356872558594, 6821210263296961784362792969]
The first , 40, terms of the sequence, number of occurrences, 2,
i
shows up at the, 5 - 1, places are
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
The first , 40, terms of the sequence, number of occurrences, 3,
i
shows up at the, 5 - 1, places are
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
The first , 40, terms of the sequence, number of occurrences, 4,
i
shows up at the, 5 - 1, places are
[0, 3, 18, 93, 468, 2343, 11718, 58593, 292968, 1464843, 7324218, 36621093,
183105468, 915527343, 4577636718, 22888183593, 114440917968, 572204589843,
2861022949218, 14305114746093, 71525573730468, 357627868652343,
1788139343261718, 8940696716308593, 44703483581542968, 223517417907714843,
1117587089538574218, 5587935447692871093, 27939677238464355468,
139698386192321777343, 698491930961608886718, 3492459654808044433593,
17462298274040222167968, 87311491370201110839843, 436557456851005554199218,
2182787284255027770996093, 10913936421275138854980468,
54569682106375694274902343, 272848410531878471374511718,
1364242052659392356872558593, 6821210263296961784362792968]
Using the found enumerative automaton with, 100,
states, that we omit, it follows that
the GUESSED (but absolutely certain!) rational generating functions for thes\
e sparse subsequence are as follows.
The generating function for the sequence for the number of occurrences of, 1,
i
in the sparse, 5 - 1, subseqeunce is
2 t - 1
- -----------------
(5 t - 1) (t - 1)
and in Maple notation
-(2*t-1)/(5*t-1)/(t-1)
The generating function for the sequence for the number of occurrences of, 2,
i
in the sparse, 5 - 1, subseqeunce is
0
and in Maple notation
0
The generating function for the sequence for the number of occurrences of, 3,
i
in the sparse, 5 - 1, subseqeunce is
0
and in Maple notation
0
The generating function for the sequence for the number of occurrences of, 4,
i
in the sparse, 5 - 1, subseqeunce is
3 t
-----------------
(5 t - 1) (t - 1)
and in Maple notation
3*t/(5*t-1)/(t-1)
This ends this article, that took, 0.243, seconds.
4 2 n
On the sequence, (x + x + x + 1) , modulo , 3
By Shalosh B. Ekhad
4 2
You raise the polynomial, x + x + x + 1,
to the n-th power, and then take it mod, 3,
and would like to know, for each i from 1 to, 2
the number of times it shows up as a coefficient in that expanded polynomial\
. This article answers this question.
The first, 41, terms staring at n=0, for the number of occurrences of, 1,
are:
[1, 4, 2, 4, 12, 4, 2, 8, 10, 4, 16, 8, 12, 32, 13, 4, 17, 20, 2, 8, 20, 8, 26,
31, 10, 34, 29, 4, 16, 8, 16, 48, 16, 8, 28, 34, 12, 48, 32, 32, 84]
The first, 41, terms staring at n=0, for the number of occurrences of, 2,
are:
[0, 0, 4, 0, 2, 9, 4, 13, 12, 0, 0, 16, 2, 10, 24, 9, 25, 25, 4, 16, 16, 13, 43
, 27, 12, 36, 40, 0, 0, 16, 0, 8, 36, 16, 54, 42, 2, 8, 52, 10, 38]
Just for kicks, for the googol-th term, the number of occurrences of i from \
1 to, 2, are:
[1616304250357386794532028281375272361109162732576761810824284614950912000,
1616304250357386794532028281375674630840795926718441806828227014950912000]
The first , 40, terms of the sequence, number of occurrences, 1,
i
shows up at the, 3 - 1, places are
[1, 2, 10, 29, 103, 308, 928, 2783, 8365, 25094, 75286, 225857, 677587, 2032760
, 6098284, 18294851, 54884569, 164653706, 493961122, 1481883365, 4445650111,
13336950332, 40010851000, 120032552999, 360097659013, 1080292977038,
3240878931118, 9722636793353, 29167910380075, 87503731140224, 262511193420676,
787533580262027, 2362600740786097, 7087802222358290, 21263406667074874,
63790220001224621, 191370660003673879, 574111980011021636, 1722335940033064912,
5167007820099194735, 15501023460297584221]
The first , 40, terms of the sequence, number of occurrences, 2,
i
shows up at the, 3 - 1, places are
[0, 4, 12, 40, 102, 310, 930, 2794, 8364, 25096, 75288, 225868, 677586, 2032762
, 6098286, 18294862, 54884568, 164653708, 493961124, 1481883376, 4445650110,
13336950334, 40010851002, 120032553010, 360097659012, 1080292977040,
3240878931120, 9722636793364, 29167910380074, 87503731140226, 262511193420678,
787533580262038, 2362600740786096, 7087802222358292, 21263406667074876,
63790220001224632, 191370660003673878, 574111980011021638, 1722335940033064914,
5167007820099194746, 15501023460297584220]
Using the found enumerative automaton with, 54,
states, that we omit, it follows that
the (rigorously) PROVED rational generating functions for these sparse subse\
quence are as follows.
The generating function for the sequence for the number of occurrences of, 1,
i
in the sparse, 3 - 1, subseqeunce is
4 3 2
15 t - t + 4 t - t + 1
----------------------------------
2
(t - 1) (t + 1) (t + 1) (3 t - 1)
and in Maple notation
(15*t^4-t^3+4*t^2-t+1)/(t-1)/(t+1)/(t^2+1)/(3*t-1)
The generating function for the sequence for the number of occurrences of, 2,
i
in the sparse, 3 - 1, subseqeunce is
3 2
2 t (9 t - 2 t - 2)
- ----------------------------------
2
(t - 1) (t + 1) (3 t - 1) (t + 1)
and in Maple notation
-2*t*(9*t^3-2*t^2-2)/(t-1)/(t^2+1)/(3*t-1)/(t+1)
This ends this article, that took, 0.231, seconds.