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, 65, 67, 71, 73, 77, 79, 83, 87, 88, 89, 91, 97, 99, 101, 103, 104, 107, 109, 110, 113, 117, 119, 121, 125, 127, 130, 131, 133, 137, 139

Offset

1,2

Comments

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.

From Alonso del Arte, Aug 03 2025: (Start)

The six terms originally listed as "doubtful," 62, 74, 82, 86, 93, 94, are each of the form 2*p except 93 which is 3*p, where p is a prime. These numbers as inputs quickly lead to p * A007542, as Don Reble explained in an e-mail to me a couple of days ago. Having verified this for myself, my uncertainty positioning the previously doubted terms has vanished.

The case of 112 is more interesting. Its sequence eventually leads to 32, thus joining A007542 in progress. Same goes for 120. There are also values like 114 with sequences that lead to 2, and thus include all of A007542 as a subsequence. (End)

Links

Table of n, a(n) for n=1..58.

Example

5 multiplied by 55 gives 275, which then multiplied by 13/11 gives 325, which then 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.
Compare that to 6, which leads to the sequence 6, 45, 2475, 2175, 5775, 5075, 13475, ..., (see A273091) and joins A007542 with the term 12375.

Crossrefs

Cf. A203907.

The fractions of Conway's PRIMEGAME are given by A202138 (numerators) and A203363 (denominators).

Sequence in context: A101550 A320048 A246351 * A322271 A306289 A136801

Adjacent sequences: A272257 A272258 A272259 * A272261 A272262 A272263

Keyword

nonn,more

Author

Alonso del Arte, Apr 23 2016

Extensions

a(29) through a(41) added by Alonso del Arte, Aug 03 2025 after Don Reble explained why six doubtful values could be conclusively ruled out, followed later on by a(42) through a(58).

Status

approved