Prime Cuts by IOA

Puzzle solution process

This is one possible solution path. Each row contains seven digits, so the maximum number of primes its partition can have is five, with lengths of {1, 1, 1, 1, 3} in some order (because there are only four one-digit primes), but then the other six rows can only have a maximum of three primes each (of lengths {2, 2, 3}), giving a maximum for the grid of 1×5 + 6×3 = 23 primes, not enough. If there are only three (or fewer) rows with four primes in their partitions, then there must be four (or more) rows with at most three primes, so the maximum number for the whole partition is 3×4 + 4×3 = 24, again not enough. Therefore there must be four rows of four primes, with lengths of {1, 2, 2, 2}, and three rows of three primes, with lengths {2, 2, 3} to give a total of 4×4 + 3×3 = 25 primes.

17dn is the cube root of 16ac, so it’s in the range [10, 21] (223 = 10648 is too big for 16ac). If 16ac ends in 2 then its cube root ends in 8, but 28 is too big for 17dn; so 16ac ends in 1, which means its cube root ends in 1, ie 17dn = 11 and 16ac = 1331.

Every digit in 7dn is the last digit of a prime in the grid partition, so they must all be {1, 3, 7, 9} or 2 (once only) or 5 (once only). This includes the last digit of 9ac, which can’t be 2 (because that would make its square 7dn end in 4) or 5 (which would make 7dn contain two 5s), so 9ac ends in one of {1, 3, 7, 9} and 7dn ends in {1, 9}.

19ac has a non-zero second digit (because 2dn can’t contain a 0), has 1 in the middle, has a fifth digit of one of {0, 1, 4, 5, 6, 9} (because 5dn is square), and ends in 1 or 9. It’s the sum of two powers of primes, so one of the powers must be even, ie 2n; 2 must be the lower of the two primes mentioned in its clue, so 19ac = 8 + pr, where p is an odd prime and r > 3, ie p = (19ac - 8)(1/r). If r = 4 then p is between (1101001 - 8)(1/4) ≈ 32.4 and (9991999 - 8)(1/4) ≈ 56.2, ie one of {37, 41, 43, 47, 53}, but none of the resulting values {1874169, 2825769, 3418809, 4879689, 7890489} has 1 in the middle. If r = 5 then p is between 1100993(1/5) ≈ 16.2 and 9991991(1/5) ≈ 25.1, ie one of {17, 19, 23}, but none of the resulting values {1419865, 2476107, 6436351} fits. If r = 6 then p is between 1100993(1/6) ≈ 10.2 and 9991991(1/6) ≈ 14.7, ie one of {11, 13}, giving values of {1771569, 4826817}, of which only the first is a possibility.

If r = 7 then p is between 1100993(1/7) ≈ 7.3 and 9991991(1/7) ≈ 9.999, but there are no primes in that range. If r = 8 then p is between 1100993(1/8) ≈ 5.7 and 9991991(1/8) ≈ 7.5, ie 7, but 8 + 78 = 5764809 doesn’t fit. If r = 9 then p is between 1100993(1/9) ≈ 4.7 and 9991991(1/8) ≈ 5.99, ie 5, but 8 + 59 = 1953133 doesn’t fit. If r = 10 then p is between 1100993(1/10) ≈ 4.02 and 9991991(1/10) ≈ 5.01, ie 5, but 8 + 510 = 9765633 doesn’t fit. If r = 11 then p is between 1100993(1/11) ≈ 3.5 and 9991991(1/11) ≈ 4.3, but there are no primes in that range. Similarly, r = 12 gives bounds of 3.2 and 3.8, containing no primes. For r = 13 and 14 the only prime in range is 3, but neither of {1594331, 4782977} fits. And for r ≥ 15, p must be ≤ 9991991(1/15) ≈ 2.9, but there are no such odd primes. Thus the only value that fits is 19ac = 1771569 = 23 + 116.

To partition row 7 (19ac) into primes, the final sequences 9 and 69 aren’t prime, so it must end with 569 and have primes of lengths {2, 2, 3}, ie the partition is 17|71|569.

Now 7dn ends in 9, so its square root 9ac ends in 3 or 7. All squares of numbers ending in 3 or 7 have an even penultimate digit (actually this is true of all odd squares), which for 7dn can only be 2. 5dn is a square ending in 5, so it must end in 25. Now row 6 is 13312_2, which can only be partitioned as 13|31|2_|2, with the incomplete prime being either 23 or 29.

If 9ac ends in 3 then its square 7dn is (10n + 3)2 = 100n2 + 60n + 9, which ends in 29 only if 6n ends in 2, ie n ends in 2 or 7; if 9ac ends in 7, then (10n + 7)2 = 100n2 + 140n + 49 ends in 29 only if 14n + 4 ends in 2, ie n ends in 2 or 7; so 9ac ends in one of {23, 27, 73, 77}. If 9ac ends in 27 or 77 and 7dn starts with 1, then 9ac is between √1711129 ≈ 1308.1 and √1799929 ≈ 1341.6, ie 1327, but 13272 = 1760929, which contains a 6 and 0 that aren’t allowed in 7dn. If 7dn starts with 3, then 9ac is between √3711129 ≈ 1926.4 and √3799929 ≈ 1949.3, ie 1927, but that can’t be partitioned into primes (27 and 927 aren’t primes, and …2|7 would need a prime ending in 2, but 2 is already used in row 6). If 7dn starts with 5, then 9ac is between √5711129 ≈ 2389.8 and √5799929 ≈ 2408.3, but there are no numbers ending in 27 or 77 in that range. If 7dn starts with 7, then 9ac is between √7711129 ≈ 2776.9 and √7799929 ≈ 2792.8, ie 2777, but that can’t be partitioned into primes (the row can’t end with the non-primes 77 or 777, and if it ends with 7 then it must be __|_2|77|7, which contains non-primes). If 7dn starts with 9, then 9ac is between √9711129 ≈ 3116.3 and √9799929 ≈ 3130.5, ie 3127, but 31272 = 9778129 contains an invalid 8. Therefore 9ac ends in 23 or 73.

If 7dn starts with 1, then 9ac is between √1311129 ≈ 1145.05 and √1399929 ≈ 1183.2, ie 1173, which is a possibility. If 7dn starts with 3, then 9ac is between √3311129 ≈ 1819.7 and √3399929 ≈ 1843.9, ie 1823, but 18232 = 3323329 has an invalid extra 2. If 7dn starts with 5, then 9ac is between √5311129 ≈ 2304.6 and √5399929 ≈ 2323.8, ie 2323, but 23232 = 5396329 contains an invalid 6. If 7dn starts with 7, then 9ac is between √7311129 ≈ 2703.9 and √7399929 ≈ 2720.3, but there are no numbers ending in 23 or 73 in that range. If 7dn starts with 9, then 9ac is between √9311129 ≈ 3051.4 and √9399929 ≈ 3065.9, but there are no numbers ending in 23 or 73 in that range. Therefore the only possibility is 9ac = 1173 and 7dn = 1375929. Row 4 now ends in 5 and can only be partitioned as __|__|__|5.

Now 4dn is _1 and is not a prime, so it’s one of {21, 51, 81, 91}. 2dn ends in 37 and is divisible by all of its digits, so it can’t contain 0, 5 or any even digits, which leaves only {1, 3, 7, 9}. 1ac is a seven-digit cube ending in 1, so its cube root ends in 1 and is in the range [111, 211]. Of the 11 possible values, {1367631, 1771561, 2248091, 2803221, 3442951, 4173281, 5000211, 5929741, 6967871}, all have an invalid digit for the start of 2dn or 4dn (or both), except for 1ac = 5929741, which can only be partitioned as 59|29|7|41. Now that 29 is used, row 6 must be 13|31|23|2, making 18ac = 232.

5dn is now 71___25. Its square root is between √7111125 ≈ 2666.7 and √7199925 ≈ 2683.3, ie 2675, so 5dn = 7155625 = 26752. Row 3 ends with 5_7 and its partition can’t end with 7 (already used in row 1) or _7 (preceded by a non-prime ending in 5, as the single-digit 5 is used in row 4), so row 3 is partitioned as __|__|5_7. The penultimate digit can’t be any of {0, 3, 6, 9}, which would make 5_7 a multiple of 3, or 5 or 7, because 10ac has no repeated digit; of the remainder, 517 = 11×47 and 527 = 17×31 aren’t primes, which leaves {547, 587}. Row 4 is partitioned as __|__|5_|5, and 59 is already used in row 1, so the third prime here must be 53, making 14ac = 35. 6dn is now 47_3_36 and is a multiple of 9; to make the sum of its digits a multiple of 9, the two missing ones must add up to 4 or 13. The third digit is either 4 or 8; if it’s 4 then the fifth digit is 9, but 15ac can’t end in 699 because it doesn’t have any repeated digits. Therefore 6dn = 4783536.

In the partition, we have three rows containing a three-digit prime (rows 3, 5 and 7), and single-digit primes 7 in row 1, 5 in row 4 and 2 in row 6, which means 3 must be used in row 2. Row 2 can’t be partitioned as __|_1|17|3 because 17 is already used in row 7, so it’s either 3|__|11|73 or __|3|11|73. Rows 3 and 5 are partitioned as __|__|587 and __|__|659, so the first and last digits of 11dn are the last digits of primes and must be one of {1, 3} (not 7 because there’s already a 7 in 10ac, or 9 because there’s already a 9 in 15ac). The partition so far includes {11, 31, 41, 71}, so the only available two-digit prime ending in 1 is 61, but if 11dn starts and ends with 1 then we need two such primes; therefore 11dn is 3_3. The only primes matching _3 that aren’t already used in the partition are {43, 83}, and 10ac already contains an 8, so row 3 must be __|43|587 and row 5 is __|83|659. The first prime in row 5 must end in 1 or 7 (because 15ac already contains 3 and 9); the only prime matching _1 is 61, but we already have a 6 in 15ac, so the second digit must be 7. The partition already has 17 in row 7, so row 5 must start with one of {37, 47, 67, 97}, but 15ac already contains 3, 6 and 9, so 15ac = 4783659, partitioned as 47|83|659.

2dn is 9___737, it’s a multiple of 9 and 7, its second and fourth digits are in {1, 3, 7, 9} and the third digit is 1 or 9 (not 3 or 7 because they already occur in 10ac). It’s a multiple of 9, and the known digits add up to 26, so the unknown digits must add up to 1, 10 or 19. If the third digit is 1 then the only possibility is 9919737, but that’s not a multiple of 7, so the third digit is 9. The first prime in row 3 is then _9 and the only available primes are {19, 79, 89}; but 10ac already contains 7 and 8, so 10ac = 1943587, partitioned as 19|43|587.

13ac ends in 5 and is one less than a square, so the square must be one of {196, 256, 576, 676}. Row 4 is partitioned as __|__|53|5, so the first two digits of 13ac form a prime, restricting it to {196, 676}; but 19 is already used in the partition of row 3, so 13ac = 675.

2dn is now 9_9_737, and the two unknown digits must add up to 10. Of the four possibilities, {9199737, 9397737, 9793737, 9991737}, the only multiple of 7 is 2dn = 9991737. 12ac is the first prime in the partition of row 4, and the only available prime matching _1 is 12ac = 61. The grid is now complete apart from two digits in 8ac, one of which is the single-digit 3 in the partition. The sum of grid digits so far is 221, and 18ac tells us the digits must add up to 232, so the missing digits are 3 and 8. 8ac can’t be partitioned as 3|98 (because 98 isn’t a prime), so 8ac = 893, completing the grid and making 1dn = 5816411 = 61×95351 (a multiple of 12ac) and 3dn = 2346837 = 3×782279 (not a prime).

Back to 2019 menu