Lowest sum of primes

Cerebral distractions of every kind, mostly but not exclusively Countdown-related.

Moderator: Michael Wallace

Post Reply
Dinos Sfyris
Series 80 Champion
Posts: 2707
Joined: Mon Jan 21, 2008 10:07 am
Location: Sheffield

Lowest sum of primes

Post by Dinos Sfyris » Sat Mar 21, 2009 1:49 am

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

User avatar
Ben Wilson
Legend
Posts: 4181
Joined: Fri Jan 11, 2008 5:05 pm
Location: North Hykeham

Re: Lowest sum of primes

Post by Ben Wilson » Sat Mar 21, 2009 3:40 pm

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

User avatar
JimBentley
Legend
Posts: 2781
Joined: Fri Jan 11, 2008 6:39 pm
Location: Redcar, UK
Contact:

Re: Lowest sum of primes

Post by JimBentley » Sat Mar 21, 2009 4:23 pm

Ben Wilson wrote: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 :?

User avatar
Ben Wilson
Legend
Posts: 4181
Joined: Fri Jan 11, 2008 5:05 pm
Location: North Hykeham

Re: Lowest sum of primes

Post by Ben Wilson » Sat Mar 21, 2009 4:52 pm

JimBentley wrote:
Ben Wilson wrote: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... :)

User avatar
Innis Carson
Devotee
Posts: 898
Joined: Sat Nov 15, 2008 3:24 pm

Re: Lowest sum of primes

Post by Innis Carson » Sat Mar 21, 2009 5:43 pm

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
Enthusiast
Posts: 283
Joined: Sat Jul 26, 2008 4:25 am
Location: Lincolnshire
Contact:

Re: Lowest sum of primes

Post by Gary Male » Sat Mar 21, 2009 7:34 pm

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

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

User avatar
Martin Gardner
Kiloposter
Posts: 1492
Joined: Sat Jan 26, 2008 8:57 pm
Location: Leeds, UK
Contact:

Re: Lowest sum of primes

Post by Martin Gardner » Sat Mar 21, 2009 7:39 pm

Ben Wilson wrote:
JimBentley wrote:
Ben Wilson wrote: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.
If you cut a gandiseeg in half, do you get two gandiseegs or two halves of a gandiseeg?

User avatar
Innis Carson
Devotee
Posts: 898
Joined: Sat Nov 15, 2008 3:24 pm

Re: Lowest sum of primes

Post by Innis Carson » Sat Mar 21, 2009 11:06 pm

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

Dinos Sfyris
Series 80 Champion
Posts: 2707
Joined: Mon Jan 21, 2008 10:07 am
Location: Sheffield

Re: Lowest sum of primes

Post by Dinos Sfyris » Sun Mar 22, 2009 12:57 am

JimBentley wrote:
Ben Wilson wrote: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 :)
Gary Male wrote:I'm in at 1,800. Any advances?
Me and Howard both got the same answer and this can be bettered by over 500 :P

Gary Male
Enthusiast
Posts: 283
Joined: Sat Jul 26, 2008 4:25 am
Location: Lincolnshire
Contact:

Re: Lowest sum of primes

Post by Gary Male » Sun Mar 22, 2009 1:25 am

Right, down to 1,377. The hunt continues

User avatar
Joseph Bolas
Fanatic
Posts: 2446
Joined: Mon Jan 21, 2008 9:19 am
Location: Liverpool, UK

Re: Lowest sum of primes

Post by Joseph Bolas » Sun Mar 22, 2009 7:56 pm

Dinos Sfyris wrote:
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 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
Kiloposter
Posts: 1955
Joined: Mon Jan 21, 2008 9:02 am
Location: UK

Re: Lowest sum of primes

Post by Howard Somerset » Mon Mar 23, 2009 12:44 am

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.

User avatar
Joseph Bolas
Fanatic
Posts: 2446
Joined: Mon Jan 21, 2008 9:19 am
Location: Liverpool, UK

Re: Lowest sum of primes

Post by Joseph Bolas » Mon Mar 23, 2009 1:09 am

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.
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
Kiloposter
Posts: 1070
Joined: Tue Jan 22, 2008 2:25 pm

Re: Lowest sum of primes

Post by Paul Howe » Mon Mar 23, 2009 1:54 am

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!)
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.
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. :evil:

User avatar
Michael Wallace
Racoonteur
Posts: 5458
Joined: Mon Jan 21, 2008 5:01 am
Location: London

Re: Lowest sum of primes

Post by Michael Wallace » Mon Mar 23, 2009 2:12 am

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. :evil:
I'm glad it's not just me who thought this...

Howard Somerset
Kiloposter
Posts: 1955
Joined: Mon Jan 21, 2008 9:02 am
Location: UK

Re: Lowest sum of primes

Post by Howard Somerset » Mon Mar 23, 2009 8:03 am

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 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.
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.
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. :evil:
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?

User avatar
Martin Gardner
Kiloposter
Posts: 1492
Joined: Sat Jan 26, 2008 8:57 pm
Location: Leeds, UK
Contact:

Re: Lowest sum of primes

Post by Martin Gardner » Mon Mar 23, 2009 9:23 am

Well, can you prove it then?
If you cut a gandiseeg in half, do you get two gandiseegs or two halves of a gandiseeg?

Howard Somerset
Kiloposter
Posts: 1955
Joined: Mon Jan 21, 2008 9:02 am
Location: UK

Re: Lowest sum of primes

Post by Howard Somerset » Mon Mar 23, 2009 9:48 am

Martin Gardner wrote: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
Kiloposter
Posts: 1054
Joined: Wed Jan 30, 2008 9:57 pm

Re: Lowest sum of primes

Post by David Williams » Mon Mar 23, 2009 10:27 am

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

David

User avatar
Joseph Bolas
Fanatic
Posts: 2446
Joined: Mon Jan 21, 2008 9:19 am
Location: Liverpool, UK

Re: Lowest sum of primes

Post by Joseph Bolas » Mon Mar 23, 2009 10:53 am

Howard Somerset wrote:
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 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 :D

JackHurst
Series 63 Champion
Posts: 1439
Joined: Tue Jan 20, 2009 8:40 pm
Location: Leics

Re: Lowest sum of primes

Post by JackHurst » Fri Mar 27, 2009 7:52 pm

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)
Last edited by JackHurst on Fri Mar 27, 2009 8:03 pm, edited 1 time in total.

JackHurst
Series 63 Champion
Posts: 1439
Joined: Tue Jan 20, 2009 8:40 pm
Location: Leics

Re: Lowest sum of primes

Post by JackHurst » Fri Mar 27, 2009 8:05 pm

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
Kiloposter
Posts: 1054
Joined: Wed Jan 30, 2008 9:57 pm

Re: Lowest sum of primes

Post by David Williams » Fri Mar 27, 2009 11:52 pm

You had to look at a list?

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

Dinos Sfyris
Series 80 Champion
Posts: 2707
Joined: Mon Jan 21, 2008 10:07 am
Location: Sheffield

Re: Lowest sum of primes

Post by Dinos Sfyris » Sat Mar 28, 2009 1:14 am

Cheers Jack you've pretty much highlighted my entire thought process that I was too lazy to type out!
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.
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?

User avatar
Joseph Bolas
Fanatic
Posts: 2446
Joined: Mon Jan 21, 2008 9:19 am
Location: Liverpool, UK

Re: Lowest sum of primes

Post by Joseph Bolas » Sat Mar 28, 2009 6:42 pm

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?
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
Series 80 Champion
Posts: 2707
Joined: Mon Jan 21, 2008 10:07 am
Location: Sheffield

Re: Lowest sum of primes

Post by Dinos Sfyris » Sat Mar 28, 2009 6:44 pm

Joseph Bolas wrote:
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?
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.

User avatar
Joseph Bolas
Fanatic
Posts: 2446
Joined: Mon Jan 21, 2008 9:19 am
Location: Liverpool, UK

Re: Lowest sum of primes

Post by Joseph Bolas » Sat Mar 28, 2009 6:47 pm

Dinos Sfyris wrote:
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.
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 :D. 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

Post Reply

Who is online

Users browsing this forum: No registered users and 13 guests