11
$\begingroup$

Find the largest positive integer with the following properties:

  • every sum of 5 neighboring digits in its decimal representation is a prime number.
  • those prime numbers get smaller and smaller from left to right.

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

$\endgroup$
4
  • 2
    $\begingroup$ By an integers 'digits' do you mean the digits of its decimal representation? $\endgroup$
    – Servaes
    Jul 16 at 7:21
  • $\begingroup$ yes, digits of decimal representation. $\endgroup$
    – ThomasL
    Jul 16 at 17:52
  • 2
    $\begingroup$ As an aside, the smallest such number is 10001. $\endgroup$
    – tobyink
    Jul 17 at 12:39
  • 2
    $\begingroup$ Actually, the smallest such number is 1. (There are no instances of 5 neighboring digits in its decimal representation so the condition is vacuously true.) I’ll close the door on the way out. $\endgroup$ Jul 17 at 19:33
8
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Computer confirms this is the greatest possible number. $\endgroup$
    – Adayah
    Jul 16 at 20:53
9
$\begingroup$

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

$\endgroup$
3
  • 2
    $\begingroup$ I have found 5 other solutions with 12 primes (non-exhaustive), however, this solution is the largest of the 6. $\endgroup$ Jul 15 at 22:17
  • 1
    $\begingroup$ Neat. A propos nothing in particular, the prime factorization of 9978853522111000 = 2^3×5^3×41×44171×5510101, does any of those have any particular significance? $\endgroup$
    – smci
    Jul 16 at 8:20
  • $\begingroup$ (2*3*5*7)^2 = 44100 which was the old CD sampling rate! $\endgroup$ Jul 16 at 14:25
7
$\begingroup$

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.

$\endgroup$
5
  • 2
    $\begingroup$ you may want to consider 0 as well, so prime 2 = 1+1+0+0+0 is possible as well. $\endgroup$
    – ThomasL
    Jul 15 at 19:30
  • 1
    $\begingroup$ Your solution has only 10 of those 12 primes, not all but one. $\endgroup$ Jul 15 at 19:33
  • $\begingroup$ Aargh, so many mistakes in one answer! $\endgroup$
    – Gareth McCaughan
    Jul 15 at 19:33
  • $\begingroup$ Have you considered starting the greedy algorithm with the digits in a different order? $\endgroup$
    – Servaes
    Jul 16 at 7:26
  • $\begingroup$ This was a great start, except the step "smallest sum is 5x1=5"; 0 is allowed hence 5-digit sums can achieve the primes 3 or 2. $\endgroup$
    – smci
    Jul 16 at 8:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.