Conway's Prime Game

Question

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 code-golf so all usual golfing rules apply, and the shortest code (in bytes) wins.

Answer 1

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"NM_M\r7",b"[U3&!\r")if f(n-1)*t%d<1][0]

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.

Answer 2

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.

Answer 3

Jelly, 49 43 bytes

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

Try it online!

• -6 bytes thanks to miles

Answer 4

Python 3, 107 bytes

f=lambda n,k=2:n and f(n-1,[k*a//b for a,b in zip(b"NM_M\r7",b"[U3&!\r")if k*a%b<1][0])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.

Answer 5

MATL, 50 bytes

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

Try it online!

Answer 6

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

Answer 7

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

Answer 8

JavaScript (Node.js), 106 95 bytes

• thanks to @Arnauld and @Neil for reducing by 11 bytes

(n,N=2,I=13,B=Buffer(`[U3&!\rNM_M\r7`))=>n--?f(n,N/B.find(x=>N%x<!!++I)*B[I]):N

Try it online!

Answer 9

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][1]);a

Try it online!

Answer 10

Retina, 213 bytes

K`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¶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:

K`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¶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.

Answer 11

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.

Answer 12

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!

Answer 13

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

Golfed :

$t=2;for(;@$i++<$argv[1];){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[1];){
    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!