# Conway's Prime Game

Specifically, Conway's PRIMEGAME.

This is an algorithm devised by John H. Conway to generate primes using a sequence of 14 rational numbers:

 A   B   C   D   E   F   G   H   I   J   K   L   M   N
17  78  19  23  29  77  95  77   1  11  13  15  15  55
--  --  --  --  --  --  --  --  --  --  --  --  --  --
91  85  51  38  33  29  23  19  17  13  11  14   2   1


For example, F is the fraction 77/29.

So here's how the algorithm finds the prime numbers. Starting with the number 2, find the first entry in the sequence that when multiplied together produces an integer. Here it's M, 15/2, which produces 15. Then, for that integer 15, find the first entry in the sequence that when multiplied produces an integer. That is the last one, N, or 55/1, which yields 825. Write down the corresponding sequence. (The astute among you may recognize this as a FRACTRAN program.)

After some iterations, you'll get the following:

2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116, 308, 364, 68, 4 ...


Note that the last item listed is 4, or 2^2. Behold our first prime number (the 2 exponent) generated with this algorithm! Eventually, the sequence will look like the following:

2 ... 2^2 ... 2^3 ... 2^5 ... 2^7 ... etc.


Thus, yielding the prime numbers. This is OEIS A007542.

## The Challenge

Given an input number n, either zero- or one-indexed (your choice), either output the first n numbers of this sequence, or output the nth number of this sequence.

## Examples

The below examples are outputting the nth term of the zero-indexed sequence.

 n   output
5   2275
19   4
40   408


## Rules

• If applicable, you can assume that the input/output will fit in your language's native Integer type.
• The input and output can be given by any convenient method.
• Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
• Standard loopholes are forbidden.
• This is so all usual golfing rules apply, and the shortest code (in bytes) wins.
• Perhaps Conway's prime game would be a more descriptive name for this challenge than Let's Play a Game. That would make it easier to find this challenge back in the future.
– Lynn
Apr 19 '18 at 21:54
• Can the output be a float? 408.0 instead of 408 for example. Apr 19 '18 at 23:09
• Unfortunately we don't have a (canonical) "Interpret Fractran" challenge. The one on Stack Overflow is locked. Apr 20 '18 at 1:33
• @dylnan Sure, that's fine. Apr 20 '18 at 12:29

# FRACTRAN, 99 bytes

17/2821 78/2635 19/1581 23/1178 29/1023 77/899 95/713 77/589 1/527 11/403 13/341 15/434 15/62 55/31


Try it online!

The program takes 2*31^n as an input, which is used as the initial state.

All the fractions in the original FRACTRAN program have been divided by 31 (the first unused prime register), so the program stops at the nth iteration.

• Cheeky answer. ;-) Apr 20 '18 at 16:43

# Python 3, 173 165 153 145 144 136 135 127 126 125 108 107 104 bytes

f=lambda n:2>>n*2or[f(n-1)*t//d for t,d in zip(b"NM_M\r7",b"[U3&!\r")if f(n-1)*t%d<1]


Try it online!

• -30 bytes thanks to Jonathan Frech!
• -3 bytes thanks to Lynn!

2>>n*2 is 2 for n==0 and 0 otherwise.

103 bytes if we can return floats.

• Using Python 2; 153 bytes. Apr 19 '18 at 20:42
• @JonathanFrech Cool, nice trick. Thanks! Apr 19 '18 at 20:43
• Staying in Python 3, 146 bytes! Apr 19 '18 at 20:48
• Apr 19 '18 at 20:54
• Thanks again, you did more than I did now! Apr 19 '18 at 20:55

# Jelly, 49 43 bytes

×“×NŒçøM_M¢¿ÆÐÐ7‘“[U3&!øçŒ×Æ¿Ç£¢‘:@xḍɗḢ
2Ç¡


Try it online!

• -6 bytes thanks to miles
• Pity that 0ọ0¤ is inf, otherwise you could have reduced this to 42 bytes... Apr 20 '18 at 13:01

# Python 3, 107 bytes

f=lambda n,k=2:n and f(n-1,[k*a//b for a,b in zip(b"NM_M\r7",b"[U3&!\r")if k*a%b<1])or k


Try it online!

Encodes the list of fractions by ziping two bytestrings containing unprintable low-ASCII characters.

If n is zero, we return the argument k; otherwise we recurse with new parameters. Our new k is the first value k*a//b corresponding to some fraction (a, b) in the list such that k*a//b is an integer, i.e. k*a%b<1.

# MATL, 50 bytes

Hi:"'0m26<l~l *,..V'31-*'{uSFA=731-+."!'32-&\w~)1)


Try it online!

• Guess which parts of the code are string literals and which are actual statements... Apr 19 '18 at 20:45
• Hi: ... aww, "Hello" to you too, code. :-) Apr 20 '18 at 12:32

# J, 116 110 bytes

g=.3 :0
((1047856500267924709512946135x%&(96#.inv])5405040820893044303890643137x)([:({.@I.@(=<.){[)*)])^:y 2
)


Try it online!

0-indexed; returns the n-th number

Some bytes can be saved by making the verb tacit, but I have problems making ^: work.

## Explanation:

J describes the rational numbers in the form NrD, where N is the numerator and D is the denominator, for example 17r91 78r85 19r51 23r38... I created 2 separate lists for the numerators and denominators and made 2 base-96 numbers from them.

1047856500267924709512946135x%&(96#.inv])5405040820893044303890643137x converts the base-96 numbers to lists and constructs a list of fractions by divinding the two lists.

   1047856500267924709512946135x%&(96#.inv])5405040820893044303890643137x
17r91 78r85 19r51 23r38 29r33 77r29 95r23 77r19 1r17 11r13 13r11 15r14 15r2 55


2 start with 2

^:y repeat the verb on its left n times (y is the argument to the function)

] the right argument (starts at 2, and then uses the result of each iteration)

* multiply the list of fractions by the right argument

(=<.) are the results integer (compare each number with its floor)

{.@I.@ finds the index I. of the first {. of the integers

{[ uses the index to retrieve the number

• 62 bytes: ('0m26<l~l *,..V'%&(31x-~3&u:)'ztRE@<620,*-! ')&(0{*#~0=1|*)2: Apr 20 '18 at 14:48
• @miles Thanks, I think you must post your solution, it's way better than mine. Apr 20 '18 at 15:09

# 05AB1E,  44  43 bytes

0-indexed

2sF•Ë₁ǝßÌ?ƒ¥"h2ÔδD‡béαA5À>,•тв2äŠ*s‰ʒθ_}нн


Try it online!

Explanation

2                                             # initialize stack with 2
sF                                           # input times do:
•Ë₁ǝßÌ?ƒ¥"h2ÔδD‡béαA5À>,•                  # push a base-255 compressed large number
тв                # convert to a list of base-100 digits
2ä             # split in 2 parts to stack
Š            # move denominators to bottom of stack
*           # multiply the last result by the numerators
s‰         # divmod with denominators
ʒθ_}     # filter, keep only those with mod result 0
нн   # get the div result


The large number pushed is 17781923297795770111131515559185513833292319171311140201

# Pari/GP, 121 bytes

n->a=2;for(i=1,n,a=[x|x<-a*[17/91,78/85,19/51,23/38,29/33,77/29,95/23,77/19,1/17,11/13,13/11,15/14,15/2,55],x\1==x]);a


Try it online!

# JavaScript (Node.js), 106 95 bytes

• thanks to @Arnauld and @Neil for reducing by 11 bytes
(n,N=2,I=13,B=Buffer([U3&!\rNM_M\r7))=>n--?f(n,N/B.find(x=>N%x<!!++I)*B[I]):N


Try it online!

• Managed to squeeze out a couple of bytes but can't help thinking I'm missing something: Try it online!
– Neil
Apr 19 '18 at 23:35
• @Neil There's no need to use the spread operator on Buffer. Also, I think it's safe to put all data in a single buffer: 95 bytes. Apr 20 '18 at 9:28
• @Arnauld The OP used the spread operator (I'm unfamiliar with Buffer so I didn't know any better) but that's a great move with the single Buffer!
– Neil
Apr 20 '18 at 9:45
• @Arnauld correct, updated :) Apr 20 '18 at 10:42

# Retina, 213 bytes

K17/91¶78/85¶19/51¶23/38¶29/33¶77/29¶95/23¶77/19¶1/17¶11/13¶13/11¶15/2¶1/7¶55/1¶17/91¶78/85¶19/51¶23/38¶29/33¶77/29¶95/23¶77/19¶1/17¶11/13¶13/11¶15/2¶1/7¶55/1¶2
\d+
*
"$+"+((_+)/(_+)¶(.+¶)*)(\3)+$
$1$#5*$2 r_\G  Try it online! Explanation: K17/91¶78/85¶19/51¶23/38¶29/33¶77/29¶95/23¶77/19¶1/17¶11/13¶13/11¶15/2¶1/7¶55/1¶17/91¶78/85¶19/51¶23/38¶29/33¶77/29¶95/23¶77/19¶1/17¶11/13¶13/11¶15/2¶1/7¶55/1¶2  Replace the input with a list of all the fractions, plus the initial integer. \d+ *  Convert everything to unary. "$+"+


Repeat the substitution the number of times given by the original input.

((_+)/(_+)¶(.+¶)*)(\3)+$ Find a denominator that evenly divides the integer. $1$#5*$2


Replace the integer with the result of the division multiplied by the numerator.

r_\G


Convert the integer to decimal and output the result.

# Attache, 81 bytes

Nest<~{Find[Integral,_*&//=>Chop[Ords!"0zmt2R6E<@l<~6l2 0*,,*.-.!V "-31,2]]},2~>


Try it online! Outputs a fraction over 1. For example, input 5 returns 2275/1. This can be fixed with plus 2 bytes by prepending N@ to the program.

## Explanation

This is a curried function, which curries Nest with two predefined arguments:

{Find[Integral,_*&//=>Chop[Ords!"0zmt2R6E<@l<~6l2 0*,,*.-.!V "-31,2]]}


and 2. This last argument is simply the initial seed, and the argument that is passed to this function is the number of iterations to nest the given function.

The following is used to encode PRIMEGAME:

&//=>Chop[Ords!"0zmt2R6E<@l<~6l2 0*,,*.-.!V "-31,2]]


This is evaluated as such:

A> "0zmt2R6E<@l<~6l2 0*,,*.-.!V "
"0zmt2R6E<@l<~6l2 0*,,*.-.!V "
A> Ords!"0zmt2R6E<@l<~6l2 0*,,*.-.!V "
[48, 122, 109, 116, 50, 82, 54, 69, 60, 64, 108, 60, 126, 54, 108, 50, 32, 48, 42, 44, 44, 42, 46, 45, 46, 33, 86, 32]
A> Ords!"0zmt2R6E<@l<~6l2 0*,,*.-.!V "-31
[17, 91, 78, 85, 19, 51, 23, 38, 29, 33, 77, 29, 95, 23, 77, 19, 1, 17, 11, 13, 13, 11, 15, 14, 15, 2, 55, 1]
A> Chop[Ords!"0zmt2R6E<@l<~6l2 0*,,*.-.!V "-31,2]
17 91
78 85
19 51
23 38
29 33
77 29
95 23
77 19
1 17
11 13
13 11
15 14
15  2
55  1
A> &//=>Chop[Ords!"0zmt2R6E<@l<~6l2 0*,,*.-.!V "-31,2]
[(17/91), (78/85), (19/51), (23/38), (29/33), (77/29), (95/23), (77/19), (1/17), (11/13), (13/11), (15/14), (15/2), (55/1)]


Let's replace this expression with G in the explanation. Our first function becomes:

{Find[Integral,_*G]}


This performs a single iteration of FRACTRAN code over _, the input to the function. It Finds an Integral member (one which is an integer) of the array _*G, which is the input _ multiplied with each member of G. Nest simply applies this transformation the given number of times.

## Attache, 42 bytes

I implemented parts of the $langs library, being inspired by this challenge, so I mark this section non-competing. Needs[$langs]2&FRACTRAN_EXAMPLES.prime.run


This simply queries the list of FRACTRAN_EXAMPLES I have. Each example is a FractranExample instance, which calls the inbuilt FRACTRAN function. The prime example is Conway's PRIMEGAME.

# F# (Mono), 215 bytes

let q m=
let rec i x y=
if y=m then x
else[17;91;78;85;19;51;23;38;29;33;77;29;95;23;77;19;1;17;11;13;13;11;15;14;15;2;55;1]|>List.chunkBySize 2|>List.find(fun[n;d]->x*n%d=0)|>fun[n;d]->i(x*n/d)(y+1)
i 2 0


Try it online!

## PHP, 183 bytes (189 with "php" tag)

Golfed :

$t=2;for(;@$i++<$argv;){foreach([17/91,78/85,19/51,23/38,29/33,77/29,95/23,77/19,1/17,11/13,13/11,15/14,15/2,55/1]as$n){$a=$t*$n;if(preg_match('/^\d+$/',$a)){$t=$a;break;}}}echo$t;


Ungolfed:

<?php
$t=2; for(;@$i++<$argv;){ foreach([17/91,78/85,19/51,23/38,29/33,77/29,95/23,77/19,1/17,11/13,13/11,15/14,15/2,55/1] as$n){
$a=$t*$n; if(preg_match('/^\d+$/',$a)){$t=$a;break; } } } echo$t;


Try it online!

# MMIX, 84 bytes (14 instrs + 28 data bytes)

jxd (everything from 5b553326 ([U3&) on is data)

00000000: e3010002 f7010000 5a000002 f8020000  ẉ¢¡£ẋ¢¡¡Z¡¡£ẏ£¡¡
00000010: f402000a 83030200 1e040103 feff0006  ṡ£¡½³¤£¡œ¥¢¤“”¡©
00000020: 23020201 5bfffffc 8303020d 1a010304  #££¢[””‘³¤£Æȷ¢¤¥
00000030: 27000001 f1fffff5 5b553326 211d1713  '¡¡¢ȯ””ṫ[U3&!øçŒ
00000040: 110d0b0e 0201114e 13171d4d 5f4d010b  ×Æ¿Ç£¢×NŒçøM_M¢¿
00000050: 0d0f0f37                             ÆĐĐ7


Disassembly and explanation:

primegm SET  $1,2 // i = 2 PUT rD,0 // prep for division 0H PBNZ$0,1F          // loop: if(steps) goto pass
POP  2,0            // return i
1H      GETA $2,0F // pass: den = &denoms 1H LDBU$3,$2 // try: d = *den DIVU$4,$1,$3       // n = i / d
GET  $255,rR // r = i % d ADDU$2,$2,1 // den++ PBNZ$255,1B        // if(r) goto try
LDBU $3,$2,13       // d = den (the numerator)
MULU $1,$3,$4 // i = n * d SUBU$0,\$0,1        // steps--
JMP  0B             // goto loop
0H      BYTE 91,85,51,38,33,29,23,19,17,13,11,14,2,1    // denoms: [BYTES]
BYTE 17,78,19,23,29,77,95,77,1,11,13,15,15,55   // nums: [BYTES]


It's quite useful that every single numerator and denominator fits into one byte. Else I'd have needed to use much more space to fit them.