Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It only takes a minute to sign up.
Sign up to join this community
Find the largest positive integer with the following properties:
For example, 97511513 is such an integer (not the largest), because $9+7+5+1+1=23, 7+5+1+1+5=19, 5+1+1+5+1=13, 1+1+5+1+3=11$ are prime numbers and $23>19>13>11$.
New high score :P
9 998 875 362 111 000
List of possible primes is 43, 41, 37, 31, 29, 23, 19, 17, 13, 11, 7, 5, 3, 2. Distances between those primes are 2, 4, 6, 2, 6, 4, 2, 4, 2, 4, 2, 2, 1.
Now, in these chains, you simply need to add bunches of 5 numbers together: 24626+42424+221.. => 88x4x. x means spots where sum of chains is above 9 - the maximum difference, going from 9 to 0. Therefore, we need to shift some chains.
Which?
We can remove first numbers, last numbers or merge numbers in between. Each of these "costs" a prime and therefore a digit.
The key observation:
You need to align 6 with 2, right now it is aligned with 4. How are you going to do that? If you remove or merge numbers from the end, obviously nothing changes. If you do it from beginning, 6 switches one place to the left... but so does 4, leaving you with the same trouble.
So
You need to merge between the first 6 and corresponding 4. Which merge is that? You shouldn't merge 6 and 2 because you can't add anything to the resulting 8. Merging 4 just under 6 with 2 to the left of it creates 6 which now aligns with 6, which is again not ok. So, you need to merge the left two, ending up with 24626, 64242, (21) - that 2 and 1 don't add to 8 and if you are skipping numbers you need to do it from the edge.
This means
A solution with 13 primes is impossible - we did the required operation but we needed to remove 2 extra primes. Maybe there is a solution with 12 primes, however.
Let's see which options are there:
1.) Remove first prime, leaving you with 46266, 42422, 1. This was found already.
2.) Merge last 42, leaving you with 24626, 64262, 1. Sum is 98888. This one is new and has primes 43, 41, 37, 31, 29, 23, 17, 13, 11, 5, 3, 2.
That should be all.
However, each gap might have many different options for constructing number. I will focus only on the second case that should lead to a new possible prime combination. We are starting from behind. I initially thought that 2 can be obtained only as 11000 or 20000, but you might be able to obtain number 2 also as 02000 and similar - leading to the same number of options as starting from the top. So, this part doesn't actually check all the options. But it doesn't matter.
First one, number is in reverse
00002126267888xxxx nope, we started with 2 so we would obtain 10 now, which isn't working. Obviously. Therefore, we need the other option: 0001112635788999. Which is written in the correct order on the top. This is the highest possible number - the starting number cannot be 99997 because final distances are 98888. Out of numbers with 3x9+2x8, 99988 is the highest, so the total number is the largest too.
Improving upon Gareth's answer (the details of which I will not repeat) with consideration of ThomasL's suggestion, a solution with 12 primes is found:
9,978,853,522,111,000 41 99788 37 97885 31 78853 29 88535 23 85352 17 53522 13 35221 11 52211 7 22111 5 21110 3 11100 2 11000
Two solutions with 11 primes were also found:
999,887,536,211,120 43 99988 41 99887 37 98875 31 88753 29 87536 23 75362 17 53621 13 36211 11 62111 7 21112 5 11120
999,797,535,311,111 43 99979 41 99797 37 97975 31 79753 29 97535 23 75353 17 53531 13 35311 11 53111 7 31111 5 11111
Wrong answer
Well, it might be the right answer for all I currently know, but my argument has multiple errors in it (pointed out by others in comments). I may fix it, but others should feel free to post correct solutions before I do :-).
The largest possible sum of 5 digits is 5x9=45; the smallest is 5x1=5. So the possible primes are 43,41,37,31,29,23,19,17,13,11,7,5. There are 12 of these. They are all odd, so in any string of consecutive digits abcdef a,f must have the same parity, as well as having a>f so that the primes keep getting smaller as required. If we have d digits then there are d-4 groups of 5, so d is at most 16.
If we adopt the obvious greedy algorithm, here is what we get:
43 99997 41 99977 37 99775 31 97753 29 77537 23 75371 19 53713 17 37133 13 7133-
So, why did we run out at that point? Well, the sequence of differences between successive primes starting (downward) from 43 goes 2,4,6,2,6,4,2,4,2,4,2; numbers 5 spaces apart in this sequence get added together, so our chains are 2,4,2; 4,2; 6,4; 2,2; 6,4. We actually have two problematic things here, the two instances of 6,5 which will reduce 9 to -1.
What if anything can we do to cram more numbers in? Note that omitting primes from the middle of the sequence increases the sizes of the gaps, so we must be cautious. There's one obvious thing to try, which is to combine the second 4 in the first chain with the 2 that follows. That means omitting 19, and then we get this:
43 99997 41 99977 37 99775 31 97753 29 77537 23 75371 17 53711 13 37111 11 71111 5 11111
Well, look at that! We've included all the possible primes but one, and that's best possible because if we could use all of them the greedy algorithm would have done it. So our number is 99997753711111.
