## 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.