Fruitful Fractions

In my first week of college, John Conway gave a lecture on one of his beautiful inventions, fourteen fruitful fractions, to attract freshmen to become math majors. This post is about these fractions.

Here are the 14 fractions, in order: 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

Here's what you do with them. Start with the number 2, and keep multiplying your number by the first fraction on this list that produces an integer. (Note this is always possible because the last "fraction" is just 55.) Every time you see a power of 2 produced by this procedure, write down the exponent.

For example, if you start with the number 2, you get the sequence: 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, 92, 380, 230, 950, 575, 2375, 9625, 11375, 2125, 1950, 1650, 1450, 3850, 4550, 850, 780, 660, 580, 1540, 1820, 340, 312, 264, 232, 616, 728, 136, 8, 60, ..., 928, 2464, 2912, 544, 32, ...

I've underlined the first three powers of two that appear on the list: 4, 8, 32. Their corresponding exponents (of two) are 2, 3, 5. If you keep going, these exponents generate the prime numbers, and I really mean all the prime numbers, and only the prime numbers, in order! This looks very much like magic.

There has been a long history of research into finding a formula for efficiently generating prime numbers -- this is beyond the scope of this post. But the fourteen fruitful fractions, fun as they are, in some sense aren't as exciting as one might hope. The problem with these fractions is that it takes a huge number of multiplications to get each additional prime, and it gets worse and worse the further you go. Suffice it to say, this is not an efficient method.

But isn't it surprising that such a list exists at all? Yes and no. Mathematicians found this surprising, and it is indeed very surprising until you look at it from the point of view of computer science. You see, this procedure is a prime-generating algorithm, and these fractions and the list they create correspond to a Turing machine (properly programmed for this task), with states, memory, and all. To a computer scientist, that this happens is very natural, and it has to do with the Church-Turing thesis.

Maybe these fractions could be better used to entice freshmen into computer science?

These fractions make an appearance in Conway's Book of Numbers.

Shorter fruitful sequences have since been found, but as far as I understand, finding the shortest such sequence remains open!