Prime generation in CA

[jimmyChen2013]

This is a discussion thread for prime generation algorithms in CA.

Here's one artificial rule I made, it applies the Sieve of Eratosthenes
the components:
a number line
a family of spaceships that carve the number line in n(any) steps
a ship constructor to make and initial the ships
a timer for the constructor to make sure the ships does not hit each other

As i said, it is completely artificial since it's only made to do this
Questions I want to ask:
Non/partial-artificial generation rules? (has other properties)
rules that uses other algorithms?

my rule:

Code: Select all

@RULE Prime

1: column
2: move.down
3: move.right
4: tweak
5: encryptor
6: unmarked number
7: marked prime

8: conversion unit
9: add signal
10: final
11: final2

12: stretcher
13: special one bug fix

14: Timer wire
15: wire extender
16: wire up
17: wire down
18: ender

19: number line extender


@TABLE

n_states:20
neighborhood:Moore
symmetries:none

var a = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18}
var b = {a}
var c = {a}
var d = {a}
var e = {a}
var f = {a}
var g = {a}
var h = {a}

var m = {1,3,4}
var x = {0,1,13,14}
var y = {x}
var z = {x}

var i = {0,6}
var j = {i}
var k = {i}

var o = {0,6,7}
var p = {o}
var q = {o}

var xt = {0,14}
var mt = {15,16}
var xtt = {0,12}

#moving
1,0,m,0,a,b,c,i,0,0
0,m,0,0,a,b,c,1,0,1

1,a,b,0,m,0,0,0,c,0
0,a,0,0,0,m,0,1,b,1

1,3,0,0,i,a,b,0,0,2
3,x,0,0,0,1,0,0,0,1
2,x,0,0,i,1,j,0,0,0
0,0,0,0,0,0,1,2,x,3

#backtrack
2,1,0,0,o,p,q,0,0,0
0,0,0,0,i,j,k,2,1,5
5,a,b,c,d,e,f,g,h,4
4,1,0,0,i,x,j,0,0,1
4,0,0,0,i,1,j,0,0,2
1,a,0,0,i,4,j,0,b,4

#encryption
6,5,a,b,c,d,e,f,g,0

#conversion
6,8,a,b,c,d,e,f,g,7

9,x,0,0,a,8,b,0,0,1
9,x,0,0,a,1,b,0,0,1
9,1,0,0,0,1,0,0,0,1
1,x,0,0,0,9,0,0,0,9
0,0,0,0,0,9,0,0,a,1

1,0,0,0,o,p,q,x,0,0
1,0,0,0,o,p,q,xt,xt,0
1,0,0,0,o,p,q,16,0,0
0,0,x,y,o,p,q,1,0,1
0,0,x,8,o,p,q,1,0,1

x,y,0,0,0,8,1,0,0,9
1,0,9,8,o,p,q,x,0,0
1,0,9,8,o,p,q,14,14,0
1,0,9,8,o,p,q,16,0,0

10,1,0,0,0,8,1,0,0,13
10,0,0,0,0,13,0,0,0,1

1,1,0,0,0,8,0,0,0,10
8,10,0,0,o,p,q,0,0,1
10,1,0,0,0,1,0,0,0,1
10,1,0,0,0,8,0,0,0,1
1,x,0,0,0,10,0,0,0,10

10,0,0,0,0,1,0,0,0,11
11,0,0,0,0,a,0,0,0,0
1,11,0,0,0,x,0,0,0,2

12,0,0,a,o,p,q,x,b,1
12,mt,0,a,o,p,q,x,b,1

0,0,0,0,o,6,0,12,0,8
0,0,0,0,o,6,7,12,0,8
0,0,0,0,o,p,q,12,0,12

#Timer
mt,0,0,0,xtt,0,14,14,14,0
0,0,0,0,0,mt,14,14,xt,mt

0,0,0,0,15,14,0,0,0,14

0,15,0,0,0,16,14,14,14,16
15,a,0,0,0,16,14,14,14,18
15,a,0,0,0,18,14,14,xt,0
18,a,b,c,d,e,f,g,h,0

16,0,0,0,0,0,14,14,0,17
17,0,0,0,0,0,14,14,0,0
0,17,0,0,0,0,14,14,14,17
14,0,0,17,0,14,0,0,0,0

0,0,0,0,o,p,0,14,0,12
0,0,0,0,12,14,0,0,0,14
0,0,0,0,0,12,14,0,0,15
15,0,0,0,8,1,14,14,14,0
15,0,0,0,1,1,14,14,14,0
16,0,0,0,o,p,0,14,14,0
0,0,0,1,o,p,0,14,14,16

#line extender
0,0,0,0,0,0,19,6,0,6
0,6,0,0,0,0,0,19,6,19
19,6,6,0,0,0,0,0,6,0


@COLORS
0 0 0 0
1 255 255 255
2 40 40 255
3 40 200 255
4 255 80 30
5 255 30 80
6 128 128 128
7 255 255 0
8 122 20 255
9 255 20 122
10 255 80 80
11 255 80 80
12 0 255 62
13 255 255 255
14 255 128 0
15 255 20 122
16 255 80 30
17 40 40 255
18 255 80 30

and the starting pattern

Code: Select all

x = 9, y = 4, rule = Prime
5.A$N5.D$.2GF.F.2F$8.S!

(Note: my rule is there only for you guys to see. Don't bother to understand or improve it, because I can't most of the time)

[dvgrn]

This is a discussion thread for prime generation algorithms in CA.

Here's one artificial rule I made, it applies the Sieve of Eratosthenes
...
Questions I want to ask:
Non/partial-artificial generation rules? (has other properties)
rules that uses other algorithms?

Wow! This is a really nice new take on a prime-number sieve rule. I really like the way each prime-number length stands itself up and staggers uncertainly along the number line -- much more entertaining to watch than the usual intermittent dots or spaceships or whatever.

I'm not completely clear on what your questions are, but two previous rules that do somewhat similar things are in Golly's pattern collection: Calcyman's two-cell Sieve of Eratosthenes pattern -- Patterns/Life/Miscellaneous/Calcyman-primer.zip -- and Rich Holmes' factorizer rule, Patterns/Other-Rules/factorize-84.zip, also a two-cell pattern.

Would it be okay if I checked in your rule to Golly's collection, in the same folder as the factorizer rule?

Now that I've seen the one-cell Mona Lisa rule, I suppose a rule supporting a single-cell primer pattern is perfectly possible.

[jimmyChen2013]

It is really fun the watch the spaceships .
I made this rule purely for fun, and also as an experiment. I didn’t go for anything like efficient or simpleness, other than its functionality. I’m ok with the rule “as long as it works.”

It can be heavily optimized, but doing that would take me just as long as make the rule itself.

I am fine with anyone doing anything with it. I’ll be more than happy if you can put it inside Golly’s collection (if I understand it correctly and that's what you mean. English is not my first language).

Im sure a one-celled pattern can be done, but what’s the point

[dani]

I suppose a rule supporting a single-cell primer pattern is perfectly possible.

A single cell primer has always been possible, by simply adding an extra state to the default 'Primes' rule.

Code: Select all

@RULE Primes-1Cell

@TABLE

n_states:11
neighborhood:Moore
symmetries:none

#State 0: Empty Space
#State 1: Up spaceship
#State 2: Down spaceship
#State 3: Up spaceship on reflector
#State 4: Down spaceship on reflector
#State 5: Reflector
#State 6: Reflector in initial state
#State 7: NW spaceship
#State 8: E puffer
#State 9: SE puffer
#States 10: Generates the primer from one cell.

var a={0,1,2,3,4,5,6,7,8,9}
var b={0,1,2,3,4,5,6,7,8,9}
var c={0,1,2,3,4,5,6,7,8,9}
var d={0,1,2,3,4,5,6,7,8,9}
var e={0,1,2,3,4,5,6,7,8,9}
var f={0,1,2,3,4,5,6,7,8,9}
var g={0,1,2,3,4,5,6,7,8,9}
var h={0,1,2,3,4,5,6,7,8,9}

var i={2,4}
var j={1,3,6}

var k={0,1,2,4,5,6,7,8,9}

0,i,a,b,c,d,e,f,g,2
5,i,a,b,c,d,e,f,g,3
0,a,b,c,d,j,e,f,g,1
5,a,b,c,d,j,e,f,g,4

0,a,b,k,7,c,d,e,f,7

0,9,a,b,c,d,e,f,g,7

8,a,b,c,d,e,f,g,h,5
9,a,b,c,d,e,f,g,h,6
0,9,a,b,c,d,e,f,g,7

0,a,b,c,d,e,f,8,g,8
0,a,b,c,d,e,f,g,9,9

1,a,b,c,d,e,f,g,h,0
2,a,b,c,d,e,f,g,h,0
7,a,b,c,d,e,f,g,h,0

3,a,b,c,d,e,f,g,h,5
4,a,b,c,d,e,f,g,h,5
6,a,b,c,d,e,f,g,h,5

#Describes the transition for one state 10 cell, a trivial addition.

10,0,0,0,0,0,0,0,0,0
0,10,0,0,0,0,0,0,0,9
0,0,0,0,0,10,0,0,0,8


@COLORS

1 255 0 0
2 0 255 0
3 255 128 128
4 128 255 128
5 128 128 128
6 192 192 192
7 128 128 255
8 128 255 255
9 255 255 128
10 255 255 255

Code: Select all

x = 1, y = 1, rule = Primes-1Cell
J!

[jimmyChen2013]

Im thinking of CA generation of other sequences
how about fibonacci,
or Kolakoski sequence?
that would be a challenge

[jimmyChen2013]

There. a single-celled fibonacci generator

Code: Select all

@RULE Fibonacci
1: on
2: f(n-1) duplicator
3: f(n-2) duplicator main down
4: f(n-2) duplicator main up
5: f(n-2) duplicator sub

6: instructor-active
7: instructor-disabled

@TABLE

n_states:8
neighborhood:Moore
symmetries:none

var a = {0,1,2,3,4,5,6,7}
var b = {a}
var c = {a}
var d = {a}
var e = {a}
var f = {a}
var g = {a}
var h = {a}

var x = {0,1}
var y = {x}
var z = {x}
var w = {x}
var t = {x}
var s = {x}

#f(n-1) dupe
1,2,x,0,0,y,z,s,a,2
2,a,b,c,d,e,f,g,h,1
0,x,0,0,0,0,y,2,a,1


#f(n-2) dupe
1,3,a,b,1,c,d,e,f,3
3,t,a,b,c,0,x,y,z,4
3,a,b,c,d,e,f,g,h,1

4,a,b,c,d,e,f,g,h,1
1,a,b,1,1,4,c,d,e,4

1,a,b,1,c,d,e,4,f,5
5,a,b,c,d,e,f,g,h,1
1,a,0,0,0,b,y,5,c,5
1,5,0,0,0,a,y,z,w,5
0,5,0,0,0,0,x,y,z,1

#instructor
1,0,6,1,1,x,y,z,0,3
1,6,0,0,0,x,y,z,0,2
6,0,0,0,0,2,3,0,0,7

7,0,0,0,1,1,a,0,0,0
0,0,0,0,0,1,1,7,0,7
7,0,0,0,0,5,1,0,0,6

#one cell
0,0,6,0,0,0,0,0,0,3
0,6,0,0,0,0,0,0,0,2

@COLORS
0 0 0 0
1 255 255 255
2 100 255 100
3 255 70 70
4 255 70 70
5 255 130 130
6 140 40 255
7 100 10 255

start from 6