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

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

Author

Alonso del Arte, Apr 23 2016

Keywords

• nonn
• more

Comments

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.

Examples

			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.
		

Crossrefs

Cf. A203907.