Solution: ‘The Prime Rib Problem’
In last month’s Insights puzzle, I concocted a fanciful story about a culinary delicacy made by grilling the ribs of a long serpent, using a special system of grilling frames. This system was my attempt to imagine a physical version of the Sieve of Eratosthenes, the ancient Greek algorithm for identifying prime numbers. Creating the grilling contraption was a fun exercise, not least because of the arbitrary constraints imposed on the physical object — such as rings in the grilling frames that have to be evenly spaced with no offsetting — in order to faithfully embody the abstract principles of prime numbers. Let us leave those complications aside now and look at the puzzle itself, because it is a fascinating open prime number problem in its own right. In discussing the solutions here, I’ll restate the underlying questions in plain mathematical language with just parenthetical references to the snake grilling.
Problem 1
What is the longest sequence of consecutive integers such that each is divisible by any of a set of five numbers, specifically chosen to maximize the answer? What are the smallest numbers for such a sequence? (In the original problem, the longest sequence of consecutive integers corresponded to the largest portion of well-cooked ribs, and the final integer of the first such sequence corresponded to the smallest snake that could yield a portion of this size.)
It is clear that to maximize the number of consecutive integers for a given set of divisors, your set of chosen divisors should include only prime numbers. Using a composite number, such as 6, is just not efficient — you can achieve the same result by using either of its prime factors, such as 2 or 3, which are smaller and will divide many more integers. (In snake-grilling parlance, a grill frame with rings that are 6 inches apart can be dispensed with if you use a grill frame with rings that are 2 inches apart — the former adds nothing more, and leaves many ribs improperly grilled.)
Let us approach the problem as carefully as we would approach a venomous snake by starting with the smallest set of prime divisors. For one prime, the answer of course is trivial — with one prime you cannot divide more than one consecutive number, and the smallest such number is the first prime itself: 2. With the first two primes, 2 and 3, you can divide three consecutive numbers such as 2, 3 and 4, and no more. It is obvious that the longest sequence must start and end with an even number, because if it doesn’t, you can always append the adjacent even number or numbers at either end to make an even longer sequence. Therefore, the length of the longest sequences is always an odd number. If we continue our pattern for the first three primes — 2, 3 and 5, we find that they divide the five consecutive numbers 2, 3, 4, 5 and 6. Can three primes divide a sequence of seven numbers? A sequence of seven will have four even numbers leaving three odd numbers, which we can label n, n + 2 and n + 4. It is obvious that the numbers 3 and 5 cannot divide more than one each of these odd numbers. So a sequence of seven is impossible for three primes, and five is the longest sequence they can divide. In a similar way, we can show that four primes cannot support more than nine consecutive integers, and once again a sequence of this type is seen in the nine numbers from 2 through 10, which can be divided by the first four primes 2, 3, 5 and 7. This seems to be absurdly easy! And then suddenly for the set of five primes, things start to go awry in two different ways. (Funny how the puzzle asked for five divisors.)
If we follow our familiar pattern, we find that the first primes 2, 3, 5, 7 and 11 divide the 11 numbers from 2 through 12. However, using the same kind of analysis as above, we can show that it should be possible for five primes to divide 13 integers. As Rainer aus dem Spring first pointed out, the five primes do divide the 13 consecutive integers beginning with 114: 114 (2), 115 (5), 116 (2), 117 (3), 118 (2), 119 (7), 120 (2), 121 (11), 122 (2), 123 (3), 124 (2), 125 (5) and 126 (2). This clearly breaks our simple pattern, but it turns out there’s an even more startling surprise: A smaller consecutive sequence of 13 integers is also divisible by a different set of five prime factors. As Rainer aus dem Spring posted two weeks after his initial comment, the smallest such sequence starts at the integer 24: 24 (2), 25 (5), 26 (2), 27 (3), 28 (2), 29 (29), 30 (2), 31 (31), 32 (2), 33 (3), 34 (2), 35 (5) and 36 (2). For snake rib fans, the smallest snake that yields a 13-rib well-cooked portion using five grills is just 36 inches long. And this snake has just bitten us on the backside!
So, is this just something arbitrary that has to be discovered by computer searches, or is there some method that we can apply to discover the answers? I promised you that cleverness will be rewarded, so here’s a clever heuristic method.
First, notice the similarity between the divisor patterns in the above two instances. In particular, the primes 7 and 11 appear just once each in the sequence from 114 to 126. The primes that contribute more substantially are: 2, which divides seven of the integers, and 3 and 5, which each divide two more. So the last two primes, 7 and 11, are just contributing the bare minimum of one extra integer each. Like unskilled labor, they can therefore be replaced by any two other primes whatsoever. Here’s how. Just for a moment, treat the number 114 as though it were zero, and replace the subsequent integers by their offset from 114. Now, if we take any set of 13 integers such that 2 divides the zeroth one, 3 divides the one with an offset of 3 (and therefore also the zeroth one), and 5 divides the one with offset 1, these three primes are guaranteed to divide 11 integers of the next 13. The remaining two integers must be either primes themselves or have prime factors other than 2, 3 and 5.
So all we have to do to find the smallest such sequence is to find an integer that is divisible by 2 and 3 and leaves a remainder of 4 when divided by 5 (because 5 has to divide the number with offset 1, so its remainder for the zeroth number is 5 – 1 = 4). Fortunately for us, this problem of finding the smallest integer that leaves a specified set of remainders for a given set of prime numbers was posed, with specific examples, by Sun Tsu Suan-Ching, the fourth-century Chinese mathematician, and an algorithm for its solution was described by Aryabhata, the sixth-century Indian mathematician. This is an instance of what is known as the Chinese Remainder Theorem, in honor of the complete solution generalized by Qin Jiushao in 1247. To go into this method would take us too far afield — for now, we can just make use of one of the modern mathematician’s miraculous helpers, Wolfram Alpha. We just type “chineseremainder((0,0,4),(2,3,5))” into Wolfram Alpha and out pops the answer: 24. Presto! We’ve found the place where the smallest sequence of 13 integers starts (and hence the length of the smallest snake, which is the 13th integer from 24, or 36 inches). The two extra primes turn out to be 29 and 31.
We can now generalize the above and come up with a heuristic procedure to find the shortest snake. Since the smallest prime numbers divide the most integers, start out with them. As Rainer aus dem Spring pointed out with a link to a paper from the journal Mathematics of Computation, the smallest primes are not absolutely guaranteed to always give the largest possible portion: Sometimes, a set of different primes can do better. However, such counterexamples are very, very rare, and the first known one takes place for a set of 24 prime numbers, which is beyond the largest set required in our problems.
Now let’s develop our general heuristic method for figuring out the answers, which we can call “lazy prime substitution.” The following is a demonstration of lazy prime substitution to find the first maximal sequence of 21 consecutive integers divisible by six primes. We will start, as usual, with the first six primes: 2, 3, 5, 7, 11 and 13.
First, write the numbers 0 through 20 in order. We are going to use them to find the best offsets for our chosen primes. Since the sequence zero must start on an even number, cross out all the even numbers, and add the subscript 2 to the number 0. You should now have:
02 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Next, find the new “uncrossed range” by subtracting the smallest uncrossed number from the largest, which gives 19 – 1 = 18. Does the next highest prime (3) divide it? If not, try the next highest prime (5). If that doesn’t work either, go back to the smaller prime and use the offset that crosses out the most new numbers. In this case, 3 does divide 18, so cross out the first uncrossed number, add the subscript 3 to it and cross out all the numbers that are offset from this first number by multiples of 3. This will result in crossing out 1, 7, 13 and 19. Find the uncrossed range again. It is now 17 – 3 = 14. So select the next prime number (7) that divides 14, and repeat the above procedure. Repeat the above until the number of uncrossed numbers remaining are equal to the number of unused primes. You should end up with the following:
02 13 2 37 4 55 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Two numbers, 9 and 11, are uncrossed, and two primes, 11 and 13, are unused. As you might have surmised, our heuristic procedure is designed to most densely fill the integers using primes that contribute at least two divisors each. Now we will substitute the noncontributing lazy primes (in this case 11 and 13) by using the Chinese Remainder theorem with just the contributing primes. We can find the remainders for each of these primes by subtracting the crossed integer from the subscript (and taking the modulo, if necessary). In this case, we have remainders of 0 for 2, 2 for 3, 4 for 7 and 0 for 5. Type “chineseremainder((0,2,4,0),(2,3,7,5))” into Wolfram Alpha and out pops the number 200, which indeed starts the smallest consecutive sequence of 21 integers divisible by six primes. We only have four of these primes, but it is easy enough to find the two others just by inspection. The additional primes are 209 and 211.
This heuristic method with some tweaking works for up to about 10 primes. After that it gets unwieldy and may need computer augmentation. This kind of heuristic thinking can also determine the maximum sequence length for a given number of primes as we saw above. This is, however, a solved problem, and we can use sequence A058989 in the On-Line Encyclopedia of Integer Sequences as a shortcut.
The correct answers for Problem 1 for up to 10 primes were given by Rainer aus dem Spring using a computer search, which is the only way to prove that they are in fact the lowest valued sequences. They are as follows:
2 primes (2, 3): Sequence length 3, Start 2
3 primes (2, 3, 5): Sequence length 5, Start 2
4 primes (2, 3, 5, 7): Sequence length 9, Start 2
5 primes (2, 3, 5, 29, 31): Sequence length 13, Start 24
6 primes (2, 3, 5, 7, 209, 211): Sequence length 21, Start 200
7 primes (2, 3, 5, 7, 11, 2309, 2311): Sequence length 25, Start 2298
8 primes (2, 3, 5, 7, 11, 13, 59, 30029): Sequence length 33, Start 30014
9 primes (2, 3, 5, 7, 11, 13, 37, 41, 2179): Sequence length 39, Start 2162
10 primes (2, 3, 5, 7, 11, 13, 17, 19, 53, 347): Sequence length 45, Start 9699668
Problem 2
Problem 2 was essentially the inverse of the same problem that asked for the maximum number of primes required for sequence lengths of 50, 100 and 150.
Here are the current candidates provided by readers:
Sequence length 50, Start 9699668: 11 primes (2, 3, 5, 7, 11, 13, 19, 71, 195157, 195161, 195163) submitted by halyavin
Sequence length 100, Start 74651409074: 16 primes (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 43, 59, 257, 1523, 4831) submitted by Rainer aus dem Spring
Sequence length 150, Start 11102324540952552: 19 primes (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 1051, 1047649, 2822011) submitted by halyavin
I am fairly confident that the first two are indeed the correct smallest sequences in their class. From halyavin’s description of his method — “the beam search to find combinations of modules which cover as much of the interval as possible followed by small sieve and exhaustive search of combinations of primes which cover more than 2 places” — it seems to be similar to the heuristic method outlined above, augmented by a computer search. So in the case of the final sequence, there may be a possibility that a sequence with smaller numbers could be found.
Can anyone do better, or prove by a brute search that no lower valued sequence exists?
The Quanta T-shirt for the Prime Rib puzzle goes to Rainer aus dem Spring, for his many contributions and for his persistence. Congratulations! Thank you to all who contributed. See you soon for new insights.
