The theory behind Primer?

[paultsui]

Hello everyone!

Shortly after being introduced to Conway's Game of life I came across primer recently (http://conwaylife.com/wiki/Primer).
I am fascinated by how the complexity of the system and the cleverness of Dean Hickerson.

Is there any way to understand why the primer would work? What prime number generating algorithm is involved in primer and what are the purpose of the various components?

Thank you so much indeed!

[calcyman]

It uses a simplified version of the Sieve of Eratosthenes.

[Wojowu]

More details: LWSSes moving to west represent integers 2,3,4... Gliders bouncing between reflectors are deleting LWSSes when they hit lower line of reflectors. In such way nth glider deletes LWSS with number corresponding to numbers divisible by n+1 expect for n+1. First glider deletes number 2,4,6,8..., second one 6,9,12,15... Some numbers are in more then one sequence, but if it is in at least one sequence it is deleted. This leaves LWSSes with numbers 2,3,5,7,11... There are 7 main components: 3 breeders creating glider guns used as reflectors, rake shooting LWSS representing numbers, puffer leaving glider eaters, rake shooting gliders between reflector and last but not least, pentadecathlon in lower left corner. First primer is designed in such way that glider can destroy only every third LWSS. Other ones survive independently on corresponding number. Pentadecathlon allows only every third LWSS. Sometimes it is missing, if corresponding number is composite.

[paultsui]

Wojowu: Thank you so much for your detailed explanation! I seem to have a much clearer understanding to the mechanism of primer : )

However, as you pointed out that the first primer is designed in such way that glider can destroy only every third LWSS - which implies the LWSSes moving to west don't actually represent integers 2, 3, 4... but rather 2, 2.5, 3, 3.66.., 4.33..., 5, 5.66..., 6.33..., 7, 7.66..., 8.33..., 9, ... In other words, even integers (except 2) never truly represented in the first primer. Please correct me if I am wrong!

Since the first primer seems to use some weird representation of numbers, which complicates thing a little bit - Is there any other prime number generating pattern that use better representations? (i.e. with LWSSes moving to west represent integers 2, 3, 4 as you mentioned!)

Thank you so much once again! : D

[Wojowu]

Here you have 4 primer patterns: http://www.radicaleye.com/DRH/primer.html On another topic skomick gave also another primer, for me very interesting

Code: Select all

#CPrime number sieve.
#CN is prime if a glider is between the long boats at gen N*60.
#CBy Jason Summers, 14 Jan 09
x = 431, y = 259, rule = B3/S23
39bo6bo$38bobo4bobo$38bobo4bobo$39bo6bo$38bobo4bobo$38bobbobbobbo$38bo
bbobbobbo$$38bob6obo$40bo4bo$37b3o6b3o$37bo10bo$$35b3o10b3o$$37bo10bo$
37boo8boo$37bobo6bobo$37bobo6bobo$38boo6boo$38boo6boo$41b4o$39bo6bo$
37bob8obo$37boboo4boobo$37bobo6bobo$$37bobo6bobo$36booboo4booboo$36bo
3bo4bo3bo133boo$181booboo13boo$181b4o13b4o$182boo14booboo$200boo$$353b
obbo$181bo4boo169bo$172bo7b3o3boo9boo154bo3bo$173boo4booboo12bobbo154b
4o13b4o$172boo4b3ob3o11bobboo169bo3bo$178b3oboo11bobboo150boo22bo$180b
obo12b4o150bo20bobbo$167bo181bo$159boo7boo178boo$156b3oboo5boo30boo
164boo3boo$156b5o29b4o4b4o161bo6bobo37b4o$157b3o22bobbo3bo3bo4booboo
141bo17bobbo6bo36bo3bo12bobbo$162bo23bo6bo6boo140bobo16boo7b3o40bo16bo
$163boo4boo11bo3bobbobbo137bo12boo17boo45bobbo13bo3bo$162boo7bo11b4o
141bo3bo94b4o$166bo7boobb3o152bo72b3o$165bo8boobb3o147bo4bo5bo$157bo8b
o7boobb3o148b5o3bobo24boo5b4o30bobbo14boo$158boo11bo11b4o151boo16boo4b
ooboo3bo3bo30bobo18bo$157boo10boo11bo3bo168b4o3b4o8bo25bo20boo4boo$
186bo156bo11booboo3boo5bobbo27bo18boo6bo$182bobbo148bo6boobo3bobbo5boo
40b3o17boo7bo$43b3o130boo154bobo4b5o4bo3bo67bo3bobbo$43bobbo30b3o23b4o
67booboo13boo38bobbo97boo4bobbo4bo4boo71bo$43bo33bo24bo3bo67b4o13b4o
41bo102b5o4bo3bo42bo$43bo3bo30bo19bo7bo68boo14booboo36bo3bo104boobo3bo
bbo5boo37bo22boo5bobbo$43bo49b7obbobbo52b4o31boo38b4o13b4o89bo11booboo
34b3o21b4o8bo$44bobo45bobb3oboo56b6o86bo3bo101b4o59booboo3bo3bo$77bo5b
oo8b7obbobbo51b4oboo3bo21bo39boo22bo94boo6boo62boo5b4o$76bobbobboo14bo
7bo54boo5boo17bo28b6o6bo20bobbo94b4o39bo$77bobobboo5boo11bo3bo6boo5b4o
43boo14bo3bobboo23bo5bo6bo118booboo39bo18b4o$78bo8bobo13b4o4booboo3bo
3bo55bobb3obo5bo28bo5boo120boo15boo21b3o17bo3bo12bobbo$87bo23b4o8bo18b
o35bob5obbobobboo21bo4bo23boo3boo113booboo44bo16bo$89bo22boo5bobbo20b
oo17bo14booboo5bo3boo24boo23bo6bobo25boo85b4o26boo13bobbo13bo3bo$37boo
49bo53boo19boo13bobbo7b3o31bo17bobbo6bo24b4o54boo29boo18bo6bo4bo29b4o$
37bo80bo43boo52bo4bobo16boo7b3o24booboo49b4oboo49bo11bo$27bo7bobo75bo
3bobbo58boo34bobo4boo17boo35boo15boo22bo10b6o17boo29b3o5bo5bo$25bobo7b
oo55b3o17boo7bo70boo20bobbo75booboo19bobo11b4o3bobo6b3o3boo9bo28b6o9b
3o3boo$15boo6boo69bo18boo6bo35bo25b4o4b4o14boobboo78b4o21boo19boo6b3o
14boo35bo5bo3bobboo9boo$14bo3bo4boo68bo20boo4boo34bobo17boo4bo3bo4boob
oo11b4obboobbo45boo29boo43bo6bo3bo12boboo13bo21bo3bo5bo11bobboo$13bo5b
o3boo73bobo18bo36boboo14booboo7bo6boo11bo3boboo18bobbo7boo5b4o5b4oboo
80b4o13bobo15bo18b3o9bo10b3obbo$3boo8bo3boboo4bobo8boo48b6o6bobbo14boo
40boobb3o5bo3b4o4bobbo19bobbo8bo18bo4booboo3bo3bo5b6o3bobo13bo3bo58b3o
13boo14b3o24bo5bo10bo4bo$3boo8bo5bo7bo8boo47bo5bo70b3o3boobo3boo28bo3b
ooboobbo3bo11bo3bo4b4o8bo6b4o5boo13boo5b3o39bobo72boboo11b5o$14bo3bo
72bo7b3o56boobo6bo3bo32bobboobobboobbobbo11b4o5boo5bobbo16bo9boo9bob3o
39boo59boo27boo$15boo20bo47bo4bo29b4o35bobb3o3boobo3boo33boo5bo6boobb
3o47bo6bo8boo38bo20bobbo16bo20boo$36bobo48boo13bobbo13bo3bo38b3o5bo3b
4o30b3o6bo6boobb3o46bo3bo3b8obo32bo20boo9bo6boo8bo18b3o21boo5bobbo$27b
oo6bobbo8bo58bo16bo50booboo29bo4boobbo6boobb3o32bobo12bo3bo7b4o33boo
18b4o4bo3bo4booboo5b3o10b5o3bo22b4o8bo$27boo5bobbo8b3o53bo3bo12bobbo
53boo30bo3bobbobbobbo11b4o27boo16bo8bo36boo7bo9booboo4b4o4b4o18b10o14b
4o4booboo3bo3bo$45boobo54b4o105bobbo4bo11bo3bo27bo63b3o6bo11boo14boo
18bo4bo4bo3bo9bo3bo6boo5b4o$34bobbo7b3o48boo115boo21bo47bobbo36boobboo
3bobboo4bobo25bo20boobo5boo11bo$36boo7b3o49bo134bobbo41boo9bo6boo28boo
boo3bo7bobboo25bo19boo4b3o5boobbobbo$21boo22b3o49bobo95bo62bo17b4o4bo
3bo4booboo6bo21b3o4bobboo4bobo24b3o19boo3b3o6b3o$9bobo10boo22boo50boo
93bo4bo57b3obobo13booboo4b4o4b4o5bobo22bo9bo11boo36bobboboo3b3o5boobbo
bbo$9bobbo8bo11bobo156bo63boo9b3oboo5boo14boo7boo32bo9booboo35b8o5boo
11bo$oo10boo11boo7boo130b3o24boobobo3bo53boboo6boo5bo73b4o37boo5bo3bo
9bo3bo$oo8bo3boo8bobo7bo10bo151bobbo3bo52boo6bo7boo73boo42b3o15b4o$5b
oo5boo9bo20b3o158bo60boo5bo118boo$4bo4bobbo10bobbo17boboo152bo4bo61b3o
boo5boo93bo$9bobo11bo21b3o32bo120b5o70booboo91bo$24bobo5boo11b3o33boo
193b4o80bo11b3o$25boo5bobo10b3o31boo196boo82bo$34bo10boo34bo277b3o$34b
oo65boo118boo58boo$69b4o27b4o116b4o56b4o$68b6o25booboo92b6o17booboo32b
6o17booboo32b6o33bo$67b8o25boo94bo5bo17boo34bo5bo17boo34bo5bo33bo$66b
oo6boo120bo59bo59bo47bo$67b8o122bo4bo54bo4bo54bo4bo31boo8boo$34boo32b
6o125boo58boo58boo42bobo$34bo34b4o$25boo5bobo173boo144b5o$24bobo5boo
69b3o101boob3o113b4o23bo4bo36b4o$10bo12b3o78bo103b5o102bo9bo3bo28bo24b
o10bo3bo$5bo4b4o8b3o31boo54boo95b3o104boo11bo23bo3bo24bobo4boo7bo$5bo
5b4o8b3o31bo45b3o5bobo199b3o5boobbobbo26bo24boobbo3b4obbobbo$oo9bobbo
9bobo7boo21bobo8bo33bo3bo4bo200b3o6b3o54boobo5bo3boo$oo9b4o10boo6bobo
22boo8bobo30bo5bobboo193bo7b3o5boobbobbo45bo5boobbo3b4obbobbo$10b4o8bo
12bo33bobo7bo21bobobobo128bo68boo9boo11bo44boo6bobo4boo7bo$10bo12bo30b
oo13bobbo6boo19booboboboo126b3ob3o23boo37bobo8bo9bo3bo12boo29bobo7bo
10bo3bo12boo$21b3o30bobo12bobobboo4boo20boboobbo125bo3b4o22b4o58b4o3b
4o4b4o50b4o3b4o4b4o$36boo16bo13bobo3boo4b3o19bo3bo128b3obbobo21booboo
63bo3bo4booboo55bo3bo4booboo$36boo30bo5boo4boo19boo3boo128bo18b3oboo5b
oo34boo6bo25bo6boo34bo25bo6boo$79boo7boo164boo5bo37b3oboo5boo20bobbo
43boo20bobbo$27boo50bo8bobo162bo7boo36b5o5bobo27bo38bobo27bo$27boo6boo
bo28bo22bo6bobo154boo5bo38b3o34bo68bo$36bobo15boo10bo23boo6boo124b3o
12bo15b3oboo5boo14boo41bo11bobboo52bo11bobboo$15bo21bo16boo10b3o29bo
127bo11bobo23booboo4b4o4b4o30bo10bo9bo5bo41bo10bo9bo5bo$14boo20boo187b
o11boo25b4o4bo3bo4booboo29boo8b3o9bobobboo40boo8b3o9bobobboo$3boo8boo
4boo5bo9boo25boo185bo14boo9bo6boo29bobo8b3o9bo3boo40bobo8b3o9bo3boo$3b
oo7b3o4boo3bobo9boo15boboo6boo185boo20bobbo45b5ob3o9b3o48b5ob3o9b3o$
13boo4boobbobo27bobo193bobo27bo42b3o3boo61b3o3boo$14boo6bobbo28bo22bob
o197bo45bo68bo$15bo7bobo28boo13b3o5bo3bo183bo11bobboo60boo67boo$24bobo
8boo17boo8boobbobbobo7bo5boo166bo10bo9bo5bo58b4o65b4o$26bo8bobo16boo6b
obbobboo7bo4bo4boo166boo8b3o9bobobboo57booboo64booboo$37bo23bo19bo172b
obo8b3o9bo3boo43boo15boo50boo15boo$37boo22bo10b3obbo3bo166b4o9b5ob3o9b
3o42booboo64booboo$61bo15bobo167b6o9b3o3boo54b4o65b4o$55boo5bobbo181b
4oboo9bo61boo67boo$54bobo7boo185boo29boo$38boo14bo184b3o39b4o$38bo14b
oo186bo39booboo$27bobo6bobo201bo25boo15boo$27bobbo5boo226booboo$12bo6b
o10boo21boo209b4o$11bobo5bo8bo3boo20bo210boo$10boboo6bo9boo15bo6bobo7b
o209boo$4boo3booboo9boobbobbo6boo7b3o6boo4b4o198bo8booboo$4boo4boboo5b
3obbobbobo7boo6boobo11b4o16bo180bobo4bo3b4o$11bobo7b4o20b3o12bobbo8boo
5bobo178bobbo5bo3boo$12bo9boo21b3o12b4o14bo3boo176bo6bobbo$38boo5b3o6b
oo5b4o3boobobo4bo3boo3boo162bo8bobbo5bo3boo$36boboo6boo6boo8bobbo3boo
5bo3boo3boo161boo9bobo4bo3b4o$36bo31bo10bobo181bo8booboo$25boo3bo5bo
31bobbo8bo46bobo117bo26boo5boo5b4o$26boo3boo3bobbo5bo7b3o72boo115bo3bo
4b3o22booboo3bo3bo$25bo4boo5boo5b3o6boo73bo121bo5bo22b4o8bo$44boboo8b
oo187bo4bo4bo24boo5bobbo$12boo31b3o7b3o3bo3b3o178b5o$10bobbo31b3o6bobo
3bo4bo212bo$boo6bo7b3o3bo21b3o6boo4b3o3bo192b3o15boo8boo$boo6bo6bo3b5o
20boo214bo14bo9bobbo$9bo7bo3booboo53boo179bo16b5o4bobbo$10bobbo3bo3boo
b3o47bo4boo197b4o3booboo$12boo5b4oboo42boob5o6boo6boo189bo4boo$21b4o8b
oo32bo4boobbo5b3o5boo172b3o$23bo9bobo30bo8boo5boo182bo$35bo30bo7bo4boo
184bo$35boo29bo12boo207b4o$58boo7bo74bobo125bobbo13bo3bo$57bobo8boo73b
oo129bo16bo$57bo85bo126bo3bo12bobbo$56boo213b4o$$56boo$57bo$57bobo9bo$
35boo21boo8b4o$35bo31boob4o5boo$26boo5bobo30b3oboo3bo3bobbo$25b3o5boo
32booboo3bo7bo$13bo8boboo42b5o3bo6bo6boo$13bobo6bobbo43bo3b3o7bo6boo$
14bobo5boboo53bobbo$boo11bobbo7b3o51boo$boo11bobo9boo$13bobo38boo11bo$
13bo9bo30bobbo7boo$24boo39b3o$23boo12boo15bobbo5b3o$36bobbo13bobbo6boo
$28boo6bo16bobo$29boo5bo17bo14boo9bo$28bo7boboo28b4o7bobo$38boo14boo7b
obobbobb3o5boobo4boo89bo$15boo37boo6bobbobboo9booboo3boo88bobo$13bobbo
44boo9bo6boobo93bobo$4boo6bo7b3o3bo10boo20boo3bo8bo5bobo94boo$4boo6bo
6bo3b5o9boo22boo10bo6bo$12bo7bo3booboo26boo5bobbo$13bobbo3bo3boob3o24b
obo6bobo$15boo5b4oboo25bo$24b4o8boo15boo$26bo9bobo130boo$38bo129bobo$
38boo16boo109bobo$57bo110bo$57bobo4bo$58boo3bobo$62boboo15boo$61booboo
14bobo$62boboo13bo6boo$57boo4bobo13bobbobbobboboo$57boo5bo5bo8bo6boobb
oo$70bobo7bobo$45bo24boo9boo$44b3o9boobo$44boboo9bobo$45b3o10bo$45b3o
9boo$45b3o9boo$45boo10boo$$83bobo$75b3o5bo3bo$70boobbobbobo7bo5boo$68b
obbobboo7bo4bo4boo$67bo19bo$67bo10b3obbo3bo$67bo15bobo$61boo5bobbo$60b
obo7boo$39boo19bo$38bobo18boo$39bo$56boo$40bobbo13bo$39bo17bobo7bo$37b
oo19boo4b4o$34bo6boobo18b4o16bo$37bo3bobbo18bobbo8boo5bobo$37b3obo3bo
17b4o14bo3boo$34bo11bo17b4o3boobobo4bo3boo3boo$35bo3bob3o23bobbo3boo5b
o3boo3boo$36bobbo3bo27bo10bobo$36boboo6bo24bobbo8bo$42boo$41bo12boo$
37bobbo13boo3$53boboo$53bobo10boo$54bo11bobo9boo$54boo10bo10b3o$54boo
6bo11boboo9boo$54boo6boo10bobbo4bo5bo$58boo3boo9boboo5bo$63b3o11b3o3bo
3bo$63boo13boo5bo$55boo5boo$54bobo5bo$54bo$53boo!

Expect for first one on Dean Hickerson's site all ships represent exact numbers, without any fractions. All use same prime number sieve as first primer. It is easiest approach, another ones include testing divisibility by 2,3 and all 6n±1, yet another one is testing 30n±a for a=1,7,11,13, and most efficient one (in computer science, not Life) is testing divisibility by primes smaller than sqrt(n), but Life pattern doing that probably must use Universal Computer. Another primality test possible in life uses Wilson's theorem (http://en.wikipedia.org/wiki/Wilson%27s_theorem) but it is veeery slow one for big numbers. Probabilistic tests are unimportant for us, and any other tests (like AKS or deterministic Miller-Rabin) really need Computer, mainly because of almost simultaneous logarithms, powers, roots, floors, modulus and totient function. I don't always write such long posts, but when I do, I always exhaust a subject

[paultsui]

I got it now!
Thank you so much Wojowu

[Jason Summers]

Some more details:

The prime number patterns all work by testing odd numbers for odd factors. None of them tests even numbers. Some small numbers, like 2, are handled as special cases (i.e., totally faked).

They work by constructing a row of oscillators (or oscillating components) of ever-increasing periods, each representing an odd factor. The oscillators consist of a glider bouncing between two reflectors, so the period can be increased simply by lengthening the glider's path. One of the reflectors is designed so that a passing spaceship can be deleted when a reflection occurs.

Assuming the "slowdown factor" is 60, we need:

- A "3" oscillator, which deletes spaceships representing 9, 15, 21, .... (15-9)*60 = 360, so it should have period 360.

- A "5" oscillator, which deletes spaceships representing 15, 25, 35, .... (period 600)

- A "7" oscillator, which deletes spaceships representing 21, 35, 49, .... (period 840)

- A "9" oscillator, which deletes spaceships representing 27, 45, 63, .... (period 1080)

Etc.

Note that each oscillator is needed only a finite number of times, up to the spaceship representing its square. The "3" oscillator is needed only once, for the number 9, so it's probably not worth constructing it at all. 9 is handled as a special case.

The hardest part of building such a pattern is actually the mundane business of finding a usable pair of 180-degree glider reflectors. There are a lot of requirements they must satisfy.

[Tropylium]

and most efficient one (in computer science, not Life) is testing divisibility by primes smaller than sqrt(n), but Life pattern doing that probably must use Universal Computer.

Not necessarily — a fairly compact sqrtgun has been built, an array of them just needs to be converted into a slide-factory setting up the sieve.

(Probably most things that can be done with a universal computer, can be also done with a specialized apparatus that is smaller or faster.)

[Quantum-mechanics]

P30 osc is a kind of has 2, 3 and 5 common factor.