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