Lowest sum of primes
Moderator: Michael Wallace
-
- Series 80 Champion
- Posts: 2707
- Joined: Mon Jan 21, 2008 10:07 am
- Location: Sheffield
Lowest sum of primes
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
"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
- Legend
- Posts: 4549
- Joined: Fri Jan 11, 2008 5:05 pm
- Location: North Hykeham
Re: Lowest sum of primes
My first attempt I get 477. I imagine there's some room for refinement in there.
- JimBentley
- Fanatic
- Posts: 2820
- Joined: Fri Jan 11, 2008 6:39 pm
- Contact:
Re: Lowest sum of primes
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 numbersBen Wilson wrote:My first attempt I get 477. I imagine there's some room for refinement in there.
- Ben Wilson
- Legend
- Posts: 4549
- Joined: Fri Jan 11, 2008 5:05 pm
- Location: North Hykeham
Re: Lowest sum of primes
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...JimBentley wrote: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 numbersBen Wilson wrote:My first attempt I get 477. I imagine there's some room for refinement in there.
- Innis Carson
- Devotee
- Posts: 898
- Joined: Sat Nov 15, 2008 3:24 pm
Re: Lowest sum of primes
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.
Re: Lowest sum of primes
I'm in at 1,800. Any advances?
601, 409, 257, 251, 89, 83, 67, 43
601, 409, 257, 251, 89, 83, 67, 43
- Martin Gardner
- Kiloposter
- Posts: 1492
- Joined: Sat Jan 26, 2008 8:57 pm
- Location: Leeds, UK
- Contact:
Re: Lowest sum of primes
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.Ben Wilson wrote: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...JimBentley wrote: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 numbersBen Wilson wrote:My first attempt I get 477. I imagine there's some room for refinement in there.
If you cut a gandiseeg in half, do you get two gandiseegs or two halves of a gandiseeg?
- Innis Carson
- Devotee
- Posts: 898
- Joined: Sat Nov 15, 2008 3:24 pm
Re: Lowest sum of primes
I'd be surprised if you're allowed to do that. Though I tried it anyway, and funnily enough also got 477.
-
- Series 80 Champion
- Posts: 2707
- Joined: Mon Jan 21, 2008 10:07 am
- Location: Sheffield
Re: Lowest sum of primes
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 lookingJimBentley wrote: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 numbersBen Wilson wrote:My first attempt I get 477. I imagine there's some room for refinement in there.
Me and Howard both got the same answer and this can be bettered by over 500Gary Male wrote:I'm in at 1,800. Any advances?
Re: Lowest sum of primes
Right, down to 1,377. The hunt continues
- Joseph Bolas
- Fanatic
- Posts: 2446
- Joined: Mon Jan 21, 2008 9:19 am
- Location: Liverpool, UK
Re: Lowest sum of primes
I assume then, that you focus on 401 and 409, but like others, I too have ended up with 1377:Dinos Sfyris wrote: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 lookingJimBentley wrote: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
409 + 401 + 283 + 89 + 61 + 67 + 53 + 7 + 5 + 2
-
- Kiloposter
- Posts: 1955
- Joined: Mon Jan 21, 2008 9:02 am
- Location: UK
Re: Lowest sum of primes
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.
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
- Fanatic
- Posts: 2446
- Joined: Mon Jan 21, 2008 9:19 am
- Location: Liverpool, UK
Re: Lowest sum of primes
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 + 2Howard Somerset wrote: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.
Re: Lowest sum of primes
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!)
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.Howard Somerset wrote:
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.
- Michael Wallace
- Racoonteur
- Posts: 5458
- Joined: Mon Jan 21, 2008 5:01 am
- Location: London
Re: Lowest sum of primes
I'm glad it's not just me who thought this...Paul Howe wrote: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.
-
- Kiloposter
- Posts: 1955
- Joined: Mon Jan 21, 2008 9:02 am
- Location: UK
Re: Lowest sum of primes
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.Paul Howe wrote: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 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.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.Howard Somerset wrote:
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.
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
- Kiloposter
- Posts: 1492
- Joined: Sat Jan 26, 2008 8:57 pm
- Location: Leeds, UK
- Contact:
Re: Lowest sum of primes
Well, can you prove it then?
If you cut a gandiseeg in half, do you get two gandiseegs or two halves of a gandiseeg?
-
- Kiloposter
- Posts: 1955
- Joined: Mon Jan 21, 2008 9:02 am
- Location: UK
Re: Lowest sum of primes
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.Martin Gardner wrote:Well, can you prove it then?
-
- Kiloposter
- Posts: 1269
- Joined: Wed Jan 30, 2008 9:57 pm
Re: Lowest sum of primes
If you're going to go Ben's way you might as well do it properly. Any advance on 317?
David
David
- Joseph Bolas
- Fanatic
- Posts: 2446
- Joined: Mon Jan 21, 2008 9:19 am
- Location: Liverpool, UK
Re: Lowest sum of primes
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 meHoward Somerset wrote: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.Paul Howe wrote: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!)
Re: Lowest sum of primes
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)
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)
Last edited by JackHurst on Fri Mar 27, 2009 8:03 pm, edited 1 time in total.
Re: Lowest sum of primes
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.
-
- Kiloposter
- Posts: 1269
- Joined: Wed Jan 30, 2008 9:57 pm
Re: Lowest sum of primes
You had to look at a list?
And I haven't seen anyone trying to match my 317, with minimal cheating, yet.
And I haven't seen anyone trying to match my 317, with minimal cheating, yet.
-
- Series 80 Champion
- Posts: 2707
- Joined: Mon Jan 21, 2008 10:07 am
- Location: Sheffield
Re: Lowest sum of primes
Cheers Jack you've pretty much highlighted my entire thought process that I was too lazy to type out!
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?JackHurst wrote: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.
- Joseph Bolas
- Fanatic
- Posts: 2446
- Joined: Mon Jan 21, 2008 9:19 am
- Location: Liverpool, UK
Re: Lowest sum of primes
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 wrote: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?
-
- Series 80 Champion
- Posts: 2707
- Joined: Mon Jan 21, 2008 10:07 am
- Location: Sheffield
Re: Lowest sum of primes
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 wrote: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 wrote: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
- Fanatic
- Posts: 2446
- Joined: Mon Jan 21, 2008 9:19 am
- Location: Liverpool, UK
Re: Lowest sum of primes
I loved that puzzle . This was how I solved it:Dinos Sfyris wrote: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 wrote: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.
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