# Wolfram's real-time 1D prime cellular automaton (A New Kind of Science,
# p. 640). 16 states written 0-f, compiled to UTS #35 transform rules.
# A sweep head Q<x><y> carries the previous two cells and rewrites each cell
# in place; one fuel g per generation (spent into s), run halts by itself.
# Cell 0 (1st char after the fuel) is 0 exactly at prime ticks t > 1.
# Run (one g per generation):
#   python3 uts35.py primes.txt gggggggg0a048
#   ICU 78.3
#     0 - Mgggggggg0a048
#     1 - Mgggggggs9604d7
#     2 - Mggggggss06f5d80
#     3 - Mgggggsss0ad3d870
#     4 - Mggggssss96fc0d700
#     5 - Mgggsssss0adb008000
#     6 - Mggssssss96fad087000
#     7 - Mgsssssss0a960f870000
#     8 - Mssssssss9af6f01700000
g } [0123456789abcdefs] > s | L ;
L s > s | L ;
L 0 > | Q00 ;
L 9 > | Q09 ;
Q00 0 > 0 | Q00 ;
Q00 1 > 0 | Q01 ;
Q00 2 > 0 | Q02 ;
Q00 3 > 0 | Q03 ;
Q00 5 > 0 | Q05 ;
Q00 6 > 0 | Q06 ;
Q00 8 > 0 | Q08 ;
Q00 9 > 9 | Q09 ;
Q00 a > 9 | Q0a ;
Q00 b > 0 | Q0b ;
Q00 d > 0 | Q0d ;
Q00 e > 9 | Q0e ;
Q00 f > f | Q0f ;
Q01 7 > 1 | Q17 ;
Q01 8 > 1 | Q18 ;
Q02 8 > 2 | Q28 ;
Q02 d > 2 | Q2d ;
Q03 0 > 3 | Q30 ;
Q03 d > 3 | Q3d ;
Q04 8 > 4 | Q48 ;
Q04 d > 5 | Q4d ;
Q05 d > 3 | Q5d ;
Q06 0 > 6 | Q60 ;
Q06 9 > a | Q69 ;
Q06 f > a | Q6f ;
Q08 0 > 8 | Q80 ;
Q08 7 > 8 | Q87 ;
Q09 0 > 0 | Q90 ;
Q09 6 > 0 | Q96 ;
Q09 9 > 9 | Q99 ;
Q09 a > 9 | Q9a ;
Q09 d > 0 | Q9d ;
Q09 e > 9 | Q9e ;
Q09 f > f | Q9f ;
Q0a 0 > 6 | Qa0 ;
Q0a 9 > a | Qa9 ;
Q0a d > 6 | Qad ;
Q0a e > a | Qae ;
Q0a f > a | Qaf ;
Q0b 0 > a | Qb0 ;
Q0c 0 > b | Qc0 ;
Q0d 0 > 0 | Qd0 ;
Q0d 7 > 0 | Qd7 ;
Q0d 8 > 0 | Qd8 ;
Q0d 9 > 9 | Qd9 ;
Q0d d > 0 | Qdd ;
Q0e 0 > 0 | Qe0 ;
Q0e 9 > 9 | Qe9 ;
Q0f 0 > 0 | Qf0 ;
Q0f 1 > 0 | Qf1 ;
Q0f 2 > 0 | Qf2 ;
Q0f 3 > 0 | Qf3 ;
Q0f 6 > 0 | Qf6 ;
Q0f 8 > 0 | Qf8 ;
Q0f 9 > 9 | Qf9 ;
Q0f a > 9 | Qfa ;
Q17 0 > 8 | Q70 ;
Q18 0 > 8 | Q80 ;
Q18 7 > 8 | Q87 ;
Q28 7 > d | Q87 ;
Q2d 7 > d | Qd7 ;
Q2d 8 > d | Qd8 ;
Q2d d > d | Qdd ;
Q30 0 > 0 | Q00 ;
Q30 d > 0 | Q0d ;
Q3d 8 > 0 | Qd8 ;
Q3d d > 0 | Qdd ;
Q4d 7 > d | Qd7 ;
Q4d 8 > d | Qd8 ;
Q4d d > d | Qdd ;
Q5d 8 > d | Qd8 ;
Q5d d > d | Qdd ;
Q60 0 > 0 | Q00 ;
Q60 4 > f | Q04 ;
Q60 9 > 9 | Q09 ;
Q60 d > 0 | Q0d ;
Q60 e > 9 | Q0e ;
Q60 f > f | Q0f ;
Q69 0 > 0 | Q90 ;
Q69 9 > 9 | Q99 ;
Q69 d > 0 | Q9d ;
Q69 e > 9 | Q9e ;
Q69 f > f | Q9f ;
Q6f 0 > d | Qf0 ;
Q6f 5 > d | Qf5 ;
Q6f 6 > 0 | Qf6 ;
Q6f 9 > e | Qf9 ;
Q6f a > 9 | Qfa ;
Q6f c > d | Qfc ;
Q70 0 > 0 | Q00 ;
Q80 0 > 7 | Q00 ;
Q87 0 > 7 | Q70 ;
Q90 0 > 0 | Q00 ;
Q90 6 > 0 | Q06 ;
Q90 9 > 9 | Q09 ;
Q90 a > 9 | Q0a ;
Q90 d > 0 | Q0d ;
Q90 e > 9 | Q0e ;
Q90 f > f | Q0f ;
Q96 0 > 6 | Q60 ;
Q96 9 > a | Q69 ;
Q96 f > a | Q6f ;
Q99 0 > 0 | Q90 ;
Q99 6 > 0 | Q96 ;
Q99 9 > 9 | Q99 ;
Q99 a > 9 | Q9a ;
Q99 d > 0 | Q9d ;
Q99 e > 9 | Q9e ;
Q99 f > f | Q9f ;
Q9a 0 > 6 | Qa0 ;
Q9a 9 > a | Qa9 ;
Q9a d > 6 | Qad ;
Q9a e > a | Qae ;
Q9a f > a | Qaf ;
Q9d 0 > 0 | Qd0 ;
Q9d 9 > 9 | Qd9 ;
Q9e 0 > 0 | Qe0 ;
Q9e 9 > 9 | Qe9 ;
Q9f 0 > 0 | Qf0 ;
Q9f 6 > 0 | Qf6 ;
Q9f 9 > 9 | Qf9 ;
Q9f a > 9 | Qfa ;
Qa0 0 > 0 | Q00 ;
Qa0 4 > 0 | Q04 ;
Qa0 6 > f | Q06 ;
Qa0 9 > 9 | Q09 ;
Qa0 a > f | Q0a ;
Qa0 d > 0 | Q0d ;
Qa0 e > 9 | Q0e ;
Qa0 f > f | Q0f ;
Qa9 0 > 0 | Q90 ;
Qa9 6 > f | Q96 ;
Qa9 9 > 9 | Q99 ;
Qa9 a > f | Q9a ;
Qa9 d > 0 | Q9d ;
Qa9 e > 9 | Q9e ;
Qa9 f > f | Q9f ;
Qad 0 > 0 | Qd0 ;
Qad 3 > f | Qd3 ;
Qad 6 > f | Qd6 ;
Qad 9 > 9 | Qd9 ;
Qad a > f | Qda ;
Qad b > f | Qdb ;
Qae 0 > 0 | Qe0 ;
Qae 9 > 9 | Qe9 ;
Qaf 0 > d | Qf0 ;
Qaf 6 > d | Qf6 ;
Qaf 9 > e | Qf9 ;
Qaf a > 9 | Qfa ;
Qb0 0 > d | Q00 ;
Qc0 0 > 0 | Q00 ;
Qc0 d > 0 | Q0d ;
Qd0 0 > d | Q00 ;
Qd0 1 > f | Q01 ;
Qd0 2 > f | Q02 ;
Qd0 3 > f | Q03 ;
Qd0 5 > f | Q05 ;
Qd0 6 > f | Q06 ;
Qd0 8 > f | Q08 ;
Qd0 9 > e | Q09 ;
Qd0 a > f | Q0a ;
Qd0 b > f | Q0b ;
Qd3 d > c | Q3d ;
Qd6 f > a | Q6f ;
Qd7 0 > 8 | Q70 ;
Qd8 0 > 8 | Q80 ;
Qd8 7 > d | Q87 ;
Qd9 0 > d | Q90 ;
Qd9 6 > f | Q96 ;
Qd9 9 > e | Q99 ;
Qd9 a > f | Q9a ;
Qda d > 6 | Qad ;
Qda e > a | Qae ;
Qda f > a | Qaf ;
Qdb 0 > a | Qb0 ;
Qdd 7 > d | Qd7 ;
Qdd 8 > d | Qd8 ;
Qdd d > d | Qdd ;
Qe0 0 > d | Q00 ;
Qe0 6 > f | Q06 ;
Qe0 9 > e | Q09 ;
Qe0 a > f | Q0a ;
Qe9 0 > d | Q90 ;
Qe9 6 > f | Q96 ;
Qe9 9 > e | Q99 ;
Qe9 a > f | Q9a ;
Qf0 0 > 0 | Q00 ;
Qf0 1 > 0 | Q01 ;
Qf0 2 > 0 | Q02 ;
Qf0 4 > 0 | Q04 ;
Qf0 6 > 0 | Q06 ;
Qf0 9 > 9 | Q09 ;
Qf0 a > 9 | Q0a ;
Qf0 c > 0 | Q0c ;
Qf1 8 > 2 | Q18 ;
Qf2 d > 4 | Q2d ;
Qf3 0 > c | Q30 ;
Qf3 d > c | Q3d ;
Qf5 d > 3 | Q5d ;
Qf6 0 > 6 | Q60 ;
Qf6 9 > a | Q69 ;
Qf6 f > a | Q6f ;
Qf8 7 > 1 | Q87 ;
Qf9 0 > 0 | Q90 ;
Qf9 6 > 0 | Q96 ;
Qf9 9 > 9 | Q99 ;
Qf9 a > 9 | Q9a ;
Qfa 0 > 6 | Qa0 ;
Qfa 9 > a | Qa9 ;
Qfa d > 6 | Qad ;
Qfa e > a | Qae ;
Qfa f > a | Qaf ;
Qfc 0 > b | Qc0 ;
Q00 > 0 0 ;
Q48 > d 7 ;
Q70 > 0 0 ;
Q80 > 7 0 ;
Qd7 > 8 0 ;