Which Prime below 1 million can be expressed as the sum of most primes

Agnishom · 2012-08-10 18:02:39

This problem is from project Euler. I am not cheating because I already wrote a code to find out the answer.
My answer is 993589 which can be expressed as the sum of 561 primes starting from the 4th Prime to 565th Prime
But they tell me that my answer is wrong. Please verify and tell me.

Let me know if you want to see my code

careless25 · 2012-08-10 18:12:17

Hey,

I just did this in excel and I get 1074180, if i sum up from the 4th prime to the 565th prime.

SO post your code and lets see where you went wrong.

Also just to make sure we are starting and ending at the same primes: 4th prime is 7 and 565th prime is 4099.

Last edited by careless25 (2012-08-10 18:15:07)

careless25 · 2012-08-10 18:25:04

Btw i just solved it by chance.

Good luck...also i believe after prime 550, the sum come to more than a million, if you start from the 4th prime.

Agnishom · 2012-08-10 19:42:09

But it needs to be less than 1 million

bobbym · 2012-08-10 20:50:30

Hi Agnishom;

careless25 · 2012-08-11 08:40:14

Hi bobbym,

That is not a prime. 997661 = 7*359*397

bobbym · 2012-08-11 09:43:33

Hi;

Sorry, I missed that part that the sum has to be a prime too!

careless25 · 2012-08-11 10:07:22

Agnishom, I will post the answer here but I got it by chance, so I cannot tell you how to code it.

noelevans · 2012-08-11 12:39:15

Hi Agnishom!

The answer is 999983 which is the sum of 499993 primes. (All 2's except for one 3). I didn't see
anything about them having to be distinct primes (ha, ha, ha).

bobbym · 2012-08-11 22:01:43

Hi Agnishom;

Agnishom · 2012-08-13 01:40:12

Is it that the required number should be the largest or should it be made up of maximum number of primes ?

careless25 · 2012-08-13 02:07:11

It should be the largest number which is the sum of the maximum number of distinct primes.

bobbym · 2012-08-13 02:45:57

Hi Agnishom;

I could pseudo-code an answer for you if you need it.

Agnishom · 2012-08-13 04:05:30

Careless, you are confusing me
Yes post the pseudo-code

bobbym · 2012-08-13 04:16:12

Hi Agnishom;

I pseudo code in the old style. Today if you look up pseudo code you will find that it has grown in size and complexity. This is incorrect in my opinion and defeats the purpose of pseudo code.

If you can not state the problem in the language you know best then you can not solve (code) the problem. The language we know best is the one we speak everyday. The language we use to converse with each other. So, all pseudo-code means is writing out the method to solve the problem in plain english.

1) Build an array of all the primes less than 1000000 call it p.

2) Start at the first element of p ( the 2) and add each element to the last one call that s. For instance:

p={2,3,5,7,11,...}

s={2,5,10,17,28...}

You should see that every element of s is a running sum of all the primes before it,

2
2+3=5
2+3+5=10
2+3+5+7 = 17
2+3+5+7+11=28

3) Only running sum while the elements are less than or equal to 1000000 and only keep the ones that are prime. You will generate an array s that should look like this when done:

s={2,5,17,41,197,281,7699,8893,22039,24133,25237,28697,32353,37561,38921,43201,44683,55837,61027,66463,70241,86453,102001,109147,116533,119069,121631,129419,132059,263171,287137,325019,329401,333821,338279,342761,360979,379667,393961,398771,581921,642869,681257,687767,700897,754573,768373,782263,868151,935507,958577}

4)Take the 958577 and check where it is located in p.

5) It is p(536). Meaning it is the 536th prime, so therefore you have made the prime 958577 and used 536 primes to do it!

6) Store 958577 and 536 as the best answer so far.

7) Take p and drop the 2 in front and repeat line 2.

-----------------------------------------------

2) p={3,5,7,11,13...}

s={3,8,15,26,39...}

You should see that every element of s is a running sum of all the primes before it,

3
3+5=8
3+5+7=15
3+5+7+11=26
3+5+7+11+13=39
2+3+5+7+11=28

3) Only running sum while the elements are less than or equal to 1000000 and only keep the ones that are prime. You will generate an array s that should look like this when done:

s={3,127,379,499,6079,6599,8273,9521,11597,13099,22037,33623,34913,49279,52517,54167,64613,92951,101999,116531,182107,222269,225829,240379,255443,283079,356387,360977,448867,535669,541339,552751,611953,624209,655547,768371,810457,817561,860819,920291}

4)Take the 920291 and check where it is located in p.

5) It is p(526). Meaning it is the 526th prime, so therefore you have made the prime 920291 and used 525 primes to do it!

6) It is not better than 958577 and 536 so discard it.

7)Take p and drop the 2 and 3 in front and repeat line 2.

-----------------------------------------------

2) p={5,7,11,13,17...}

s={5,12,23,36,53...}

You should see that every element of s is a running sum of all the primes before it,

3) Only running sum while the elements are less than or equal to 1000000 and only keep the ones that are prime. You will generate an array s that should look like this when done:

s={5,23,53,233,563,1259,2579,2909,12713,22543,28099,31729,39607,41017,42463,87511,110359,115279,117787,138863,141671,213533,242243,257353,265117,269069,289171,310019,318557,327193,331603,354097,372607,441101,478001,483377,510569,578959,584879,590819,633487,646027,697591,970219,978037}

4)Take the 978037 and check where it is located in p.

5) It is p(539). Meaning it is the 539 th prime, so therefore you have made the prime 978037 and used 536 primes to do it!

6) It is not better than 958577 and 536 so discard it.

7)Take p and drop the 2,3 and 5 in front and repeat line 2.

------------------------------------------------

2) p={7,11,13,17,19...}

s={7,18,31,48,67,...}

You should see that every element of s is a running sum of all the primes before it,

3) Only running sum while the elements are less than or equal to 1000000 and only keep the ones that are prime. You will generate an array s that should look like this when done:

s={7,31,67,271,491,953,1151,1361,1583,2417,3821,4217,4651,5107,10181,12329,13877,15527,23059,28687,36217,46181,47711,72169,78139,111577,121621,132049,137477,148817,157579,166541,172687,182099,204979,215261,218749,225821,240371,244109,303691,325009,338269,351811,370261,408479,433439,448859,576001,605867,674767,727499,747743,796307,824683,831847,875491,905207,943153,981949,997651}

4)Take the 997651 and check where it is located in p.

5) It is p(544). Meaning it is the 546 th prime, so therefore you have made the prime 997651 and used 543 primes to do it!

6) It is better than 958577 and 536 so discard 958577 and 536 and keep 997651 and 543 as the new best found.

7)Take p and drop the 2,3,5 and 7 in front and repeat line 2.

8) Repeat this loop of 2 to 7 until p has run out of elelments.

9) Print the last one found, that is the best!

This is a very long and drawn out explanation. If you get it great! If you do not it will eventually seep into your mind. The algorithm I used here is based on how I think about math and what languages I code in. Eventually these things will shape you, have patience. The Euler project problems are sometimes very difficult. It is no disgrace not to solve them.

Agnishom · 2012-08-17 01:48:20

Hmm..
I support your concept about the pseudocode
How much time will it take if I run the program?

bobbym · 2012-08-17 05:02:15

Hi Agnishom;

It will take longer to write the program then to run it. Computers are fast, humans are slow.

Agnishom · 2012-08-17 14:11:27

May I say something? Can we not have a faster algorithm for this one?

bobbym · 2012-08-17 18:51:58

Hi Agnishom;

May I say something?

Of course.

A brilliant guy I knew wrote an article for a famous computer journal called
"Common Sense, Brute Force and the Computer." It did not get published and it
was a really great article.

The theme of the article was two programmers and their attempt to solve six problems by computer.
The first guy coded using the simplest algorithms each of his programs took several seconds to run.
The second guy used fancy algorithms and all his programs ran twice as fast as the first guy's did.

The second guy declared himself the better programmer because his 6 ran faster. The first guy pointed out
that although they ran faster they took hundreds of times longer to write. His took only minutes while the other guys took days or weeks to write.

The point is this, if someone is waiting for an answer he does not want to wait 3 weeks for you to write a program that runs in a second. He would very much prefer the guy who
takes 10 minutes to write his program and 2 seconds to run it.

Speed is a tradeoff with how long it takes to come up with that faster idea. If it will take days or weeks then you are better off with the simpler but slower one.
I think if you code this one in your favorite language you will find it fast enough. Then you can look around for something better when you have the answer in your hand.

Agnishom · 2012-08-17 23:52:38

Yes! You are correct and it seems so
Very Nice Explanation Indeed
May I get a link to the article

Last edited by Agnishom (2012-08-18 00:39:00)

Agnishom · 2012-08-18 01:09:50

Let me do the calculations for a smaller number first
Whats the answer if the upperbound is 300 instead of 1000,000?

Doing with 1,000,000:
My First answer: 997651
My Second Answer: 99857
My Third Answer: 999721

Now the question is Do we want the sum to be larger? or Do we want to be composed of Maximum number of Primes

Last edited by Agnishom (2012-08-18 01:19:10)

bobbym · 2012-08-18 07:33:30

Hi Agnishom;

Agnishom wrote:

Now the question is Do we want the sum to be larger? or Do we want to be composed of Maximum number of Primes

This is how the problem is posted there:

Which prime, below one-million, can be written as the sum of the most consecutive primes?

They want the one with the most terms.

Agnishom wrote:

My First answer: 997651

That is not correct. The first answer is 958577 and it takes 536 primes to make it.

Agnishom wrote:

May I get a link to the article

That is not possible as it is lost forever. The author became discouraged over the fact that they would not publish it and trashed it.

You are suggesting 300, I could use that or something even smaller until you get the hang of it.

Agnishom · 2012-08-18 17:42:25

But I entered 997651, and Euler says I am correct

bobbym · 2012-08-18 19:44:10

Hi;

It is the correct answer but it is not the first answer in the sense that it is

7+11+13+17+19+...+

the fourth prime onwards. If you run my program it is actually the fourth answer,
that is what I meant.

Agnishom · 2012-08-22 01:14:13

-Maybe you are right-
But would you see my code?

Math Is Fun Forum

#1 2012-08-10 18:02:39

Which Prime below 1 million can be expressed as the sum of most primes

#2 2012-08-10 18:12:17

Re: Which Prime below 1 million can be expressed as the sum of most primes

#3 2012-08-10 18:25:04

Re: Which Prime below 1 million can be expressed as the sum of most primes

#4 2012-08-10 19:42:09

Re: Which Prime below 1 million can be expressed as the sum of most primes

#5 2012-08-10 20:50:30

Re: Which Prime below 1 million can be expressed as the sum of most primes

#6 2012-08-11 08:40:14

Re: Which Prime below 1 million can be expressed as the sum of most primes

#7 2012-08-11 09:43:33

Re: Which Prime below 1 million can be expressed as the sum of most primes

#8 2012-08-11 10:07:22

Re: Which Prime below 1 million can be expressed as the sum of most primes

#9 2012-08-11 12:39:15

Re: Which Prime below 1 million can be expressed as the sum of most primes

#10 2012-08-11 22:01:43

Re: Which Prime below 1 million can be expressed as the sum of most primes

#11 2012-08-13 01:40:12

Re: Which Prime below 1 million can be expressed as the sum of most primes

#12 2012-08-13 02:07:11

Re: Which Prime below 1 million can be expressed as the sum of most primes

#13 2012-08-13 02:45:57

Re: Which Prime below 1 million can be expressed as the sum of most primes

#14 2012-08-13 04:05:30

Re: Which Prime below 1 million can be expressed as the sum of most primes

#15 2012-08-13 04:16:12

Re: Which Prime below 1 million can be expressed as the sum of most primes

#16 2012-08-17 01:48:20

Re: Which Prime below 1 million can be expressed as the sum of most primes

#17 2012-08-17 05:02:15

Re: Which Prime below 1 million can be expressed as the sum of most primes

#18 2012-08-17 14:11:27

Re: Which Prime below 1 million can be expressed as the sum of most primes

#19 2012-08-17 18:51:58

Re: Which Prime below 1 million can be expressed as the sum of most primes

#20 2012-08-17 23:52:38

Re: Which Prime below 1 million can be expressed as the sum of most primes

#21 2012-08-18 01:09:50

Re: Which Prime below 1 million can be expressed as the sum of most primes

#22 2012-08-18 07:33:30

Re: Which Prime below 1 million can be expressed as the sum of most primes

#23 2012-08-18 17:42:25

Re: Which Prime below 1 million can be expressed as the sum of most primes

#24 2012-08-18 19:44:10

Re: Which Prime below 1 million can be expressed as the sum of most primes

#25 2012-08-22 01:14:13

Re: Which Prime below 1 million can be expressed as the sum of most primes

Board footer