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.

Hi Agnishom;

Hi;

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

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

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

Hi Agnishom;

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

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.

Hi Agnishom;

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

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.

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 23:19:10)

But I entered 997651, and Euler says I am correct

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