A203907 -id:A203907 - cp's OEIS frontend

A007542 Successive integers produced by Conway's PRIMEGAME.

2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116, 308, 364, 68, 4, 30, 225, 12375, 10875, 28875, 25375, 67375, 79625, 14875, 13650, 2550, 2340, 1980, 1740, 4620, 4060, 10780, 12740, 2380, 2184, 408, 152

Offset: 1

N. J. A. Sloane

Conway's PRIMEGAME produces the terms 2^prime in increasing order.
From Daniel Forgues, Jan 20 2016: (Start)
Pairs (n, a(n)) such that a(n) = 2^k are (1, 2^1), (20, 2^2), (70, 2^3), (282, 2^5), (711, 2^7), (2376, 2^11), (3894, 2^13), (8103, 2^17), ...
Numbers n such that a(n) = 2^k are 1, 20, 70, 282, 711, 2376, 3894, 8103, ... [This is 1 + A007547. - N. J. A. Sloane, Jan 25 2016] (End)

D. Olivastro, Ancient Puzzles. Bantam Books, NY, 1993, p. 21.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n=1..8103
J. H. Conway, FRACTRAN: a simple universal programming language for arithmetic, in T. M. Cover and Gopinath, eds., Open Problems in Communication and Computation, Springer, NY 1987, pp. 4-26.
Richard K. Guy, Conway's prime producing machine, Math. Mag. 56 (1983), no. 1, 26-33. [Gives slightly different version of the program which produces different terms, starting from n=132.]
OEIS Wiki, Conway's PRIMEGAME
Kevin I. Piterman and Leandro Vendramin, Computer algebra with GAP, 2023. See p. 40.
Leandro Vendramin, Mini-couse on GAP - Exercises, Universidad de Buenos Aires (Argentina, 2020).
Eric Weisstein's World of Mathematics, FRACTRAN
Wikipedia, FRACTRAN

Cf. A007546, A007547, A183132, A202138, A203363.

a007542 n = a007542_list !! (n-1)
a007542_list = iterate a203907 2  -- Reinhard Zumkeller, Jan 24 2012

l:= [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]: a:= proc(n) option remember; global l; local p, k; if n=1 then 2 else p:= a(n-1); for k while not type(p*l[k], integer) do od; p*l[k] fi end: seq(a(n), n=1..50); # Alois P. Heinz, Aug 12 2009

conwayFracs := {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}; a[1] = 2; A007542[n_] := A007542[n] = (p = A007542[n - 1]; k = 1; While[ ! IntegerQ[p * conwayFracs[[k]]], k++]; p * conwayFracs[[k]]); Table[A007542[n], {n, 42}] (* Jean-François Alcover, Jan 23 2012, after Alois P. Heinz *)

from fractions import Fraction
nums = [17, 78, 19, 23, 29, 77, 95, 77,  1, 11, 13, 15, 1, 55] # A202138
dens = [91, 85, 51, 38, 33, 29, 23, 19, 17, 13, 11,  2, 7,  1] # A203363
PRIMEGAME = [Fraction(num, den) for num, den in zip(nums, dens)]
def succ(n, program):
  for i in range(len(program)):
    if (n*program[i]).denominator == 1: return (n*program[i]).numerator
def orbit(start, program, steps):
  orb = [start]
  for s in range(1, steps): orb.append(succ(orb[-1], program))
  return orb
print(orbit(2, PRIMEGAME, steps=42)) # Michael S. Branicky, Feb 15 2021

a(n+1) = A203907(a(n)), a(1) = 2. [Reinhard Zumkeller, Jan 24 2012]

A185242 Successive integers produced by Conway's PRIMEGAME, starting with 3 rather than 2.

Original entry on oeis.org

3, 165, 145, 385, 455, 85, 78, 66, 58, 154, 182, 34, 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116, 308, 364, 68, 4, 30, 225, 12375, 10875, 28875, 25375, 67375, 79625, 14875, 13650, 2550

Offset: 1

Alonso del Arte, Jan 24 2012

nonn

2 is nevertheless reached fairly soon, and after that the sequence proceeds exactly the same as A007542.

			After 3, we have 3 * 55 = 165 because none of the other fractions give an integer. Then we can use 29/33, and thus 165 * 29/33 = 145, and so on and so forth.

Wikipedia, Conway's PRIMEGAME

Cf. A007542, A203907, A273091.

a185242 n = a185242_list !! (n-1)
a185242_list = iterate a203907 3
-- Reinhard Zumkeller, Jan 25 2012

(* First run the program for A203907 to define conwayProc *) NestList[conwayProc, 3, 50]

a(n+12) = A007542 (n) for n > 0. - Charles R Greathouse IV, Jan 24 2012

a(n+1) = A203907(a(n)), a(1) = 3. - Reinhard Zumkeller, Jan 25 2012

A273091 Successive integers produced by Conway's PRIMEGAME, starting with 6 rather than 2.

Original entry on oeis.org

6, 45, 2475, 2175, 5775, 5075, 13475, 15925, 2975, 2730, 510, 468, 396, 348, 924, 812, 2156, 2548, 476, 28, 210, 1575, 225, 12375, 10875, 28875, 25375, 67375, 79625, 14875, 13650, 2550, 2340, 1980, 1740, 4620, 4060, 10780, 12740, 2380, 2184, 408, 152, 92, 380, 230, 950, 575, 2375, 9625

Offset: 1

Alonso del Arte, May 14 2016

Upon reaching 225, this sequence becomes the same as A007542, having skipped over 4 (which corresponds to the prime 2) and then goes on to 8 (which corresponds to the prime 3).

			Multiply 6 by 15/2 to obtain 45. Then for 45, multiplying by the first thirteen fractions fails to produce an integer, so 45 * 55 = 2475.

Cf. A185242.

(* First run the program for A203907 to define conwayProc *) NestList[conwayProc, 6, 50]

A273099 Successive integers produced by Conway's PRIMEGAME, starting with 12 rather than 2.

Original entry on oeis.org

12, 90, 675, 37125, 32625, 86625, 76125, 202125, 177625, 471625, 557375, 104125, 95550, 17850, 16380, 3060, 2808, 2376, 2088, 5544, 4872, 12936, 11368, 30184, 35672, 6664, 392, 2940, 22050, 165375, 23625, 3375, 185625, 163125, 433125, 380625, 1010625, 888125, 2358125, 2786875

Offset: 1

Alonso del Arte, May 15 2016

After 240 steps, this sequence reaches 32 = 2^5.

			Multiply 12 by 15/2 to obtain 90. Then for 90, we can multiply 90 by 15/2 also to obtain 675.

Alonso del Arte, Table of n, a(n) for n = 1..250

Cf. A185242, A273091.

(* First run the program for A203907 to define conwayProc *) NestList[conwayProc, 12, 50]

A272260 Numbers that cause an infinite loop in Conway's PRIMEGAME.

Original entry on oeis.org

1, 5, 7, 11, 13, 17, 19, 22, 25, 26, 29, 31, 33, 35, 37, 39, 41, 43, 44, 47, 49, 51, 52, 53, 55, 57, 59, 61

Offset: 1

Alonso del Arte, Apr 23 2016

The following values are certainly in the sequence: 65, 67, 71, 73, 77, 79, 83, 87, 88, 89, 91, 97, 99, 101. The following values are doubtful: 62, 74, 82, 86, 93, 94.
Conway's PRIMEGAME (also called "Conway's prime producing machine") is a fascinating (and very inefficient) method for obtaining the prime numbers.
The "machine" takes in a number, and tries multiplying it by each of fourteen fractions one by one to find the first one that produces an integer. Then that integer is multiplied by each of the fourteen fractions one by one to find the first one that produces another integer. The goal is to find powers of 2; these powers of 2 have a binary logarithm that is a prime number.
The fractions of Conway's PRIMEGAME are 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.
The "machine" was designed to take 2 as its first input, which gives us the sequence A007542, and from that sequence we can pick out the sequence 2^prime(n) (A034785).
But there are other numbers that can be used as a first input. If the process is started with 3, the process eventually leads to 2 (see A185242). So starting with 3 just delays the process.
However, the numbers in this sequence taken as first inputs do much worse than delay the process, they get the program stuck in an endless loop.
A lot, but not all, of the numerators of the Conway fractions are in this sequence. Specifically, all except 78, 23, 95, 15. As for denominators, all of them except 85, 38, 23, 2 are in this sequence.
All prime numbers greater than 29 are in this sequence. Given a prime number p > 29, we see that multiplying by the first thirteen fractions results in a rational but non-integer value, so the process gives 55p for the first step. Then 55p * 13/11 = 65p and 65p * 11/13 = 55p, hence an infinite loop.
In fact, the only primes that can be used to start the process without leading to an infinite loop are 2, 3, 23.

			5 multiplied by 55 gives 275.
275 multiplied by 13/11 gives 325.
325 multiplied by 11/13 gives 275.
Since 275 has occurred before, this means that 5 leads the process to get stuck on bouncing between 275 and 325, and so 5 is in this sequence.

Cf. A203907.

cp's OEIS Frontend

A007542 Successive integers produced by Conway's PRIMEGAME.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Python

Formula

A185242 Successive integers produced by Conway's PRIMEGAME, starting with 3 rather than 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

A273091 Successive integers produced by Conway's PRIMEGAME, starting with 6 rather than 2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A273099 Successive integers produced by Conway's PRIMEGAME, starting with 12 rather than 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A272260 Numbers that cause an infinite loop in Conway's PRIMEGAME.

Views

Author

Keywords

Comments

Examples

Crossrefs