Lowest sum of primes

[Dinos Sfyris]

Howard sent me this puzzle from New Scientist, which I quite enjoyed so thought I'd share it with the rest of you:

"Use each of the digits 0 to 9 exactly twice to make a list of prime numbers. Your primes must all be different, and their sum must be as small as possible. Neither 0 nor 1 is a prime, and 0 may not be a leading digit. What is the sum of the prime numbers in your list."

Have fun

Dinos

[Ben Wilson]

My first attempt I get 477. I imagine there's some room for refinement in there.

[JimBentley]

My first attempt I get 477. I imagine there's some room for refinement in there.

Shit, I can't even find a combination that works. I figured that to use the zeroes the best thing would be to go for two from 101, 103, 107 and 109, then work down from there. But then there's all the other even numbers to get rid of and I keep running out of odd numbers

[Ben Wilson]

My first attempt I get 477. I imagine there's some room for refinement in there.

Shit, I can't even find a combination that works. I figured that to use the zeroes the best thing would be to go for two from 101, 103, 107 and 109, then work down from there. But then there's all the other even numbers to get rid of and I keep running out of odd numbers

Admittedly I did cheat with the zeroes somewhat. Then again, what I did wasn't stated to be against the rules in the actual rules themselves...

[Innis Carson]

Took me ages to find any set at all that fits the bill, and the one I've got now has a sum of 2430. I think this might be beatable.

[Gary Male]

I'm in at 1,800. Any advances?

601, 409, 257, 251, 89, 83, 67, 43

[Martin Gardner]

My first attempt I get 477. I imagine there's some room for refinement in there.

Shit, I can't even find a combination that works. I figured that to use the zeroes the best thing would be to go for two from 101, 103, 107 and 109, then work down from there. But then there's all the other even numbers to get rid of and I keep running out of odd numbers

Admittedly I did cheat with the zeroes somewhat. Then again, what I did wasn't stated to be against the rules in the actual rules themselves...

I reckon you've done something like 3.0 and 5.0. That isn't a leading digit and they are prime, so it doesn't break any rules that I can see.

[Innis Carson]

I'd be surprised if you're allowed to do that. Though I tried it anyway, and funnily enough also got 477.

[Dinos Sfyris]

My first attempt I get 477. I imagine there's some room for refinement in there.

Shit, I can't even find a combination that works. I figured that to use the zeroes the best thing would be to go for two from 101, 103, 107 and 109, then work down from there. But then there's all the other even numbers to get rid of and I keep running out of odd numbers

The odd/even thing is useful as primes can only end in 1, 3, 7 and 9 (bar 2 primes of course ) so using up your odds (except 5) as non-terminal digits isn't optimal. You're on the right lines trying to place the zeroes though. Keep looking

I'm in at 1,800. Any advances?

Me and Howard both got the same answer and this can be bettered by over 500

[Gary Male]

Right, down to 1,377. The hunt continues

[Joseph Bolas]

Shit, I can't even find a combination that works. I figured that to use the zeroes the best thing would be to go for two from 101, 103, 107 and 109, then work down from there. But then there's all the other even numbers to get rid of and I keep running out of odd numbers

The odd/even thing is useful as primes can only end in 1, 3, 7 and 9 (bar 2 primes of course ) so using up your odds (except 5) as non-terminal digits isn't optimal. You're on the right lines trying to place the zeroes though. Keep looking

I assume then, that you focus on 401 and 409, but like others, I too have ended up with 1377:

409 + 401 + 283 + 89 + 61 + 67 + 53 + 7 + 5 + 2

[Howard Somerset]

It's been interesting to watch this thread during the weekend, and frustrating not to be able to contribute. I really must try to remember my passwords when I'm away from home.

I like the 477 idea, and agree that it's possible (and the best) if you allow a decimal point to be included. I may even suggest that possibility to New Scientist to see their response.

Interesting too that nobody else has got a total as low as the one that both Dinos and I have come up with quite independently, and I've got no doubt that ours is valid.

[Joseph Bolas]

I like the 477 idea, and agree that it's possible (and the best) if you allow a decimal point to be included. I may even suggest that possibility to New Scientist to see their response.

I've worked out Ben's 477, but without using the 0's as decimal points, I can go down from 1,377 to 1,287: 503 + 401 + 89 + 83 + 67 + 61 + 47 + 29 + 5 + 2

[Paul Howe]

I haven't put any effort into this, but can tell its a cool puzzle and look forward to the solution (which I hope you know, as it will otherwise be difficult to verify!)

I like the 477 idea, and agree that it's possible (and the best) if you allow a decimal point to be included. I may even suggest that possibility to New Scientist to see their response.

This is really gevinesque. You want to besmirch the primes, building blocks of the pure and beautiful word of the integers, with a decimal fucking point?! I used to think you were cool Howard.

[Michael Wallace]

This is really gevinesque. You want to besmirch the primes, building blocks of the pure and beautiful word of the integers, with a decimal fucking point?! I used to think you were cool Howard.

I'm glad it's not just me who thought this...

[Howard Somerset]

I haven't put any effort into this, but can tell its a cool puzzle and look forward to the solution (which I hope you know, as it will otherwise be difficult to verify!)

It can be verified. And I have certainly verified it without any artificial computing aid. It's the one that Joseph has now come up with, without any tricks.

I like the 477 idea, and agree that it's possible (and the best) if you allow a decimal point to be included. I may even suggest that possibility to New Scientist to see their response.

This is really gevinesque. You want to besmirch the primes, building blocks of the pure and beautiful word of the integers, with a decimal fucking point?! I used to think you were cool Howard.

It definitely wasn't me who built them with decimal points. I just followed how Ben had got his lower total total, and agree with him that it would be within the rules, just.

As far as I'm concerned though, 1287 is the correct solution.

Extra quick question: In how many ways can the digits be arranged to produce that 1287 solution?

[Martin Gardner]

Well, can you prove it then?

[Howard Somerset]

Well, can you prove it then?

Yes. Having found 1287, I decided to prove that it was the lowest possible total, and believe that I have done so to my satisfaction. Though to do it here would take a long time, and most people would switch off with boredom long before I got even half way through.

[David Williams]

If you're going to go Ben's way you might as well do it properly. Any advance on 317?

David

[Joseph Bolas]

I haven't put any effort into this, but can tell its a cool puzzle and look forward to the solution (which I hope you know, as it will otherwise be difficult to verify!)

It can be verified. And I have certainly verified it without any artificial computing aid. It's the one that Joseph has now come up with, without any tricks.

I've PM'd you a copy of my solution to how I got 1,287, to see if you got the same solution as me

[JackHurst]

Im trying to prove a lower bounds for the optimal solution, i know i have no chance in hell of getting a decent value myself, so i thought it do this instead.

I dont know if an optimal solution can be found by using logic derived form finding a lower bounds.


Firstly, consider the digits 4, 6 and 8. Any number in ending one of these digits is divisible by 2, and is therefore not prime. So if these digits are in their "optimal position", they will be in the tens column followed by another digit which makes them prime.

Now lets consider the digit 5. Any two or more digit number ending in 5 is divisible by five and is therefore not prime. This means that the "optimal positions" for the two fives are with one on its own as the integer 5, and with another of them in the 10's column.

At this point it is time to consider the digits 1, 3, 7 and 9. As these digits can all be the last digits in a prime number, it is logical to put these numbers aside to be the final digits in any primes we make. Because each of these digits are used twice, we can assume that there will be a minimum of 8 prime numbers in the list. Including the 5 on its own, its actually 9.

We also know that with the positioning of the 4's, 6's, 8's and the 5 in the tens columns that we have at best 7 two digit numbers beginning with these digits, that are also prime:

5
4?
4?
5?
6?
6?
8?
8?
?1
?1
?3
?3
?7
?7
?9
?9

leaving us with th digits 0, 0, 2 and 2 to play around with.

It is stated that the 0 digits cannot be at the start of the number. Any number ending in a 0 is divisible by 2 and 5 so is not prime. This means that the best place for a 0 digit to be placed is in the 10's column. The logic behind this is that the 0 will always have to have another digit infront of it, and because no primes end in 0, it is better to put it in the 10's column and shift something from the 10's column into the 100's column rather than placing it in the 100's column and shifting something into the 1000's column.

Now if we consider where to put the first zero, we become close to getting a solution. at first it makes sense to put both the 0's after the two 2's left over, making the digits in the 100's columns as small as possible. But if we do this, it means that we have 7 starts of numbers and 8 ends of numbers, so there are not enough "endings" to fit together with the "startings" to make a full list of prime numbers. The most logical move form here is to consider putting one of the 0's with one of the 4's infront for the same reasons as it first made sense to place the 0's after both the 2's.
This now means that we have 8 "endings" and 7 "startings" with the digits 2,2 and 0 left over. Considering these numbers leads one to realise that it is most efficient to use one of the two's on its own, and create a new "starting" beginning with the digits 20.

This now means that we have 8 "startings" and "endings" which can be pieced together to to form a list of primes. As well as these, we have the 5 and the 2 on their own.

So, having established the best possible way to assign all of the digits to which place value columns, it is possible to calculate the a value which is impossible to beat in this puzzle.

Solitary primes
2,
5

Beginnings of primes
4?
5?
6?
6?
8?
8?
20?
40?

The ? denotes that the digit(s) is/are followed by one more digit form the "endings" list.

Ending of primes:
x1
x1
x3
x3
x7
x7
x9
x9
the x dontes that the digit is at the end of 1 or 2 digits form the "startings" list

If its is possible to assemble the form the last two list together placing them ?-x then the best solution is

2+5+40+50+60+80+80+200+400+1+1+3+3+7+7+9+9=957

I have to go now, so in my absence, if anyone sees this post, feel free to see if its possible to fix the "startings" and "endings" together to get a list of primes and thus attaining the best possible solution to the puzzle.

Please note that if its possible to prove that the "startings and endings" cannot be put together in such a way as to yield a list of primes (without repitition ofc), then it easy to extend this argument, to show that the minimum total is higher than 957.

Feel free to pick any holes in this argument, I know it has loads. Thats why i've not called it a proof (well i tried not to, if i did type it out anywhere above, it was a mistake to have done so)

[JackHurst]

I just looked at a list of primes, and no three digit prime number begins with 20, so my argument is flawed. Might fix it later.

[David Williams]

You had to look at a list?

And I haven't seen anyone trying to match my 317, with minimal cheating, yet.

[Dinos Sfyris]

Cheers Jack you've pretty much highlighted my entire thought process that I was too lazy to type out!

I just looked at a list of primes, and no three digit prime number begins with 20, so my argument is flawed. Might fix it later.

Aye and you can't have a 30X either as this uses up an odd outside the units column, and I couldn't find any solutions involving 2 such 40X primes so you extend to 40X and 50X where such a solution exists. As you pointed out, the remaining primes are 2, 5 and 6 two-digit numbers. I don't have my solution to hand. Does anyone want to reveal the answer?

[Joseph Bolas]

Aye and you can't have a 30X either as this uses up an odd outside the units column, and I couldn't find any solutions involving 2 such 40X primes so you extend to 40X and 50X where such a solution exists. As you pointed out, the remaining primes are 2, 5 and 6 two-digit numbers. I don't have my solution to hand. Does anyone want to reveal the answer?

If the answer is 1,287, I posted this solution above: 503 + 401 + 89 + 83 + 67 + 61 + 47 + 29 + 5 + 2, but I have been told that there is another way to make 1,287.

[Dinos Sfyris]

Aye and you can't have a 30X either as this uses up an odd outside the units column, and I couldn't find any solutions involving 2 such 40X primes so you extend to 40X and 50X where such a solution exists. As you pointed out, the remaining primes are 2, 5 and 6 two-digit numbers. I don't have my solution to hand. Does anyone want to reveal the answer?

If the answer is 1,287, I posted this solution above: 503 + 401 + 89 + 83 + 67 + 61 + 47 + 29 + 5 + 2, but I have been told that there is another way to make 1,287.

That was it. You can also swap the final digits of 503 and 29 and instead have 509 and 23. This is the other solution Howard mentioned.

[Joseph Bolas]

If the answer is 1,287, I posted this solution above: 503 + 401 + 89 + 83 + 67 + 61 + 47 + 29 + 5 + 2, but I have been told that there is another way to make 1,287.

That was it. You can also swap the final digits of 503 and 29 and instead have 509 and 23. This is the other solution Howard mentioned.

I loved that puzzle . This was how I solved it:

I first focused on the 2, 4, 6 and 8 and found all the prime numbers under 100 that began with 2, 4, 6 and 8. These were: 23, 29, 41, 43, 47, 61, 67, 83 and 89. Two of the numbers end in '1', another two end in '7' and another two end in '9', so these made up the first 6 numbers: 41, 61, 47, 67, 29 and 89. This then left the numbers 23, 43 and 83. 83 is the only one using the 8, so that was the next number I came up with.

Numbers left over: 002355

From the numbers left over I saw that you could have 2, 3 and 5, but if you did that, you had a 5 left over, so I looked for a number using either a 2 and 5 or a 3 and 5 and found 53. This then left 2 and 5 which became the last two numbers.

So I had: 89 + 83 + 67 + 61 + 53 + 47 + 41 + 29 + 5 + 2 = 477 (which I assume is how Ben got 477, using the 0's as decimal numbers)

I then had the 0's left over and I looked at the numbers to see if any two could have a '0' inserted to make a prime number and you could insert one in 51 and 43 to get 501 and 403.

So I had: 503 + 401 + 89 + 83 + 67 + 61 + 47 + 29 + 5 + 2 = 1,287