Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

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

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

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

careless25
Real Member
Registered: 2008-07-24
Posts: 560

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

Hey,

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

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

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

careless25
Real Member
Registered: 2008-07-24
Posts: 560

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

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

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

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

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

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

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

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

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

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

careless25
Real Member
Registered: 2008-07-24
Posts: 560

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

Hi bobbym,

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

Offline

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

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

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

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

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

careless25
Real Member
Registered: 2008-07-24
Posts: 560

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

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

Offline

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

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

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

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


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

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

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

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

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

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

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

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

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

careless25
Real Member
Registered: 2008-07-24
Posts: 560

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

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

Offline

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

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

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

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

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

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

Careless, you are confusing me
Yes post the pseudo-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

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

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

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

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.


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

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

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

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


'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

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

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

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

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

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

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

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


'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

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

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

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

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

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

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

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)


'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

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

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

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)


'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

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

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

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

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

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

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

But I entered 997651, and Euler says I am correct


'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

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

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

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

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

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

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

-Maybe you are right-
But would you 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

Board footer

Powered by FluxBB