18
\$\begingroup\$

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.
\$\endgroup\$
  • 11
    \$\begingroup\$ 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. \$\endgroup\$ – Lynn Apr 19 '18 at 21:54
  • \$\begingroup\$ Can the output be a float? 408.0 instead of 408 for example. \$\endgroup\$ – dylnan Apr 19 '18 at 23:09
  • \$\begingroup\$ Unfortunately we don't have a (canonical) "Interpret Fractran" challenge. The one on Stack Overflow is locked. \$\endgroup\$ – user202729 Apr 20 '18 at 1:33
  • \$\begingroup\$ @dylnan Sure, that's fine. \$\endgroup\$ – AdmBorkBork Apr 20 '18 at 12:29

13 Answers 13

6
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Cheeky answer. ;-) \$\endgroup\$ – AdmBorkBork Apr 20 '18 at 16:43
5
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Using Python 2; 153 bytes. \$\endgroup\$ – Jonathan Frech Apr 19 '18 at 20:42
  • \$\begingroup\$ @JonathanFrech Cool, nice trick. Thanks! \$\endgroup\$ – dylnan Apr 19 '18 at 20:43
  • 1
    \$\begingroup\$ Staying in Python 3, 146 bytes! \$\endgroup\$ – Jonathan Frech Apr 19 '18 at 20:48
  • \$\begingroup\$ 144 bytes. \$\endgroup\$ – Jonathan Frech Apr 19 '18 at 20:54
  • \$\begingroup\$ Thanks again, you did more than I did now! \$\endgroup\$ – dylnan Apr 19 '18 at 20:55
4
\$\begingroup\$

Jelly, 49 43 bytes

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

Try it online!

  • -6 bytes thanks to miles
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Pity that 0ọ0¤ is inf, otherwise you could have reduced this to 42 bytes... \$\endgroup\$ – Erik the Outgolfer Apr 20 '18 at 13:01
3
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

MATL, 50 bytes

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

Try it online!

|improve this answer|||||
\$\endgroup\$
  • 3
    \$\begingroup\$ Guess which parts of the code are string literals and which are actual statements... \$\endgroup\$ – Luis Mendo Apr 19 '18 at 20:45
  • 2
    \$\begingroup\$ Hi: ... aww, "Hello" to you too, code. :-) \$\endgroup\$ – AdmBorkBork Apr 20 '18 at 12:32
2
\$\begingroup\$

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

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

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

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

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!

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

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!

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Managed to squeeze out a couple of bytes but can't help thinking I'm missing something: Try it online! \$\endgroup\$ – Neil Apr 19 '18 at 23:35
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Arnauld Apr 20 '18 at 9:28
  • \$\begingroup\$ @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! \$\endgroup\$ – Neil Apr 20 '18 at 9:45
  • \$\begingroup\$ @Arnauld correct, updated :) \$\endgroup\$ – DanielIndie Apr 20 '18 at 10:42
1
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

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!

|improve this answer|||||
\$\endgroup\$
0
\$\begingroup\$

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!

|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.