You are not logged in.

- Topics: Active | Unanswered

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

'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

I'm not crazy, my mother had me tested.

Offline

**careless25****Real Member**- Registered: 2008-07-24
- Posts: 559

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

Offline

**careless25****Real Member**- Registered: 2008-07-24
- Posts: 559

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.

Offline

But it needs to be less than 1 million

'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

I'm not crazy, my mother had me tested.

Offline

**bobbym****bumpkin**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606

Hi Agnishom;

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.**** Always satisfy the Prime Directive of getting the right answer above all else.**

Offline

**careless25****Real Member**- Registered: 2008-07-24
- Posts: 559

Hi bobbym,

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

Offline

**bobbym****bumpkin**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606

Hi;

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

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.**** Always satisfy the Prime Directive of getting the right answer above all else.**

Offline

**careless25****Real Member**- Registered: 2008-07-24
- Posts: 559

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

Offline

**noelevans****Member**- Registered: 2012-07-20
- Posts: 236

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

Writing "pretty" math (two dimensional) is easier to read and grasp than LaTex (one dimensional).

LaTex is like painting on many strips of paper and then stacking them to see what picture they make.

Offline

**bobbym****bumpkin**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606

Hi Agnishom;

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.**** Always satisfy the Prime Directive of getting the right answer above all else.**

Offline

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

'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

I'm not crazy, my mother had me tested.

Offline

**careless25****Real Member**- Registered: 2008-07-24
- Posts: 559

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

Offline

**bobbym****bumpkin**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606

Hi Agnishom;

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

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.**** Always satisfy the Prime Directive of getting the right answer above all else.**

Offline

Careless, you are confusing me

Yes post the pseudo-code

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

I'm not crazy, my mother had me tested.

Offline

**bobbym****bumpkin**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606

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,

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.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.**** Always satisfy the Prime Directive of getting the right answer above all else.**

Offline

Hmm..

I support your concept about the pseudocode

How much time will it take if I run the program?

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

I'm not crazy, my mother had me tested.

Offline

**bobbym****bumpkin**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606

Hi Agnishom;

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

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.**** Always satisfy the Prime Directive of getting the right answer above all else.**

Offline

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

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

I'm not crazy, my mother had me tested.

Offline

**bobbym****bumpkin**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606

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.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.**** Always satisfy the Prime Directive of getting the right answer above all else.**

Offline

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

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

I'm not crazy, my mother had me tested.

Offline

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

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

I'm not crazy, my mother had me tested.

Offline

**bobbym****bumpkin**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606

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.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.**** Always satisfy the Prime Directive of getting the right answer above all else.**

Offline

But I entered 997651, and Euler says I am correct

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

I'm not crazy, my mother had me tested.

Offline

**bobbym****bumpkin**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606

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.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.**** Always satisfy the Prime Directive of getting the right answer above all else.**

Offline

-Maybe you are right-

But would you see my code?

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

I'm not crazy, my mother had me tested.

Offline