Problem 050

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
apdwyer51
Posts: 5
Joined: Sun Nov 27, 2011 8:46 pm

Re: Project 50

Post by apdwyer51 »

Thanks everyone. I get it now.

User avatar
rayfil
Administrator
Posts: 1405
Joined: Sun Mar 26, 2006 5:30 am
Location: Quebec, Canada
Contact:

Re: Problem 050

Post by rayfil »

@ apdwyer51
For you information, questions related to specific problems should be posted to the existing topic related to such problem (if one already exists obviously :) ). Those topics have "Problem XXX" as their subject, where XXX is the problem number padded in front with 0's if needed to have three digits. Your posts have thus been merged into the related topic.

In the future, if you search for the proper topic, you may then find answers to your question(s) without the need to post them.

Hope you are enjoying Project Euler and this forum. :D
When you assume something, you risk being wrong half the time.

jozefovovic
Posts: 2
Joined: Fri Jan 27, 2012 11:40 am

Re: Problem 050

Post by jozefovovic »

Hi, can somebody tell me, how many consecutive primes I have to use, I found solution with 539 consecutives primes but it is wrong.

User avatar
hk
Administrator
Posts: 10875
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Problem 050

Post by hk »

That's too short.
Image

User avatar
peedyoJ
Posts: 19
Joined: Sat Aug 11, 2012 3:03 pm

Re: Problem 050

Post by peedyoJ »

Recently I revisited this problem, with the sole purpose of optimizing my code, to my surprise I found a post in the problem thread which asserts solutions to larger instances of the problem....some of which are contradictory to the results I have obtained for higher values......I would be obliged if some members, who have solved the problem, could confirm values of 10^7, 10^8 & 10^9 either on the problem thread or through PM.
"When in doubt, use brute force" - Ken Thompson.

User avatar
hk
Administrator
Posts: 10875
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Problem 050

Post by hk »

It took me some time to find out which post you're possibly refering to reading the thread from page 1 to page 5.
Is it Francky's post on page 5?
Or another post on one of the following pages?
Image

User avatar
peedyoJ
Posts: 19
Joined: Sat Aug 11, 2012 3:03 pm

Re: Problem 050

Post by peedyoJ »

Yes.....thats the one.....
"When in doubt, use brute force" - Ken Thompson.

User avatar
Francky
Posts: 90
Joined: Sat May 07, 2011 3:49 pm
Location: South of France

Re: Problem 050

Post by Francky »

Hi, thanks to pay attention to my code and/or results.

Edit : spoil deleted

You can PM me your results if you want.
Last edited by Francky on Sun Sep 16, 2012 12:37 pm, edited 1 time in total.
ImageEntia non sunt multiplicanda praeter necessitatem

User avatar
peedyoJ
Posts: 19
Joined: Sat Aug 11, 2012 3:03 pm

Re: Problem 050

Post by peedyoJ »

Sorry for the late response.....but guess what.....I dug deeper.....although we got different results, looks like we both are correct (as far as the problem statement is concerned) because, for certain larger instances of the problem the answer is not unique......my old code provides only the lower value & it seems your code provides only the higher value......my new code provides both.
"When in doubt, use brute force" - Ken Thompson.

User avatar
Francky
Posts: 90
Joined: Sat May 07, 2011 3:49 pm
Location: South of France

Re: Problem 050

Post by Francky »

peedyoJ wrote:Sorry for the late response.....but guess what.....I dug deeper.....although we got different results, looks like we both are correct (as far as the problem statement is concerned) because, for certain larger instances of the problem the answer is not unique......my old code provides only the lower value & it seems your code provides only the higher value......my new code provides both.
You're right, my code answer the highest prime that is the longest sum of consecutive primes under limit.
I think I can modify it in order to answer other primes with same length for the sum.

Thanks for pointing that and confront our results. It gave an instructive issue.

Edit : done, it was for 10⁷ and 10¹⁵, isn't it ?
---597 and ---191 for 10⁷, and
---469 and ---119 for 10¹⁵.
ImageEntia non sunt multiplicanda praeter necessitatem

User avatar
peedyoJ
Posts: 19
Joined: Sat Aug 11, 2012 3:03 pm

Re: Problem 050

Post by peedyoJ »

You've got it my friend.....kudos.
"When in doubt, use brute force" - Ken Thompson.

MargaretD
Posts: 1
Joined: Wed Jan 01, 2014 11:58 pm

Re: Problem 050

Post by MargaretD »

"The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953."

Should be "The longest sum of consecutive primes that adds to a prime below 1000..." shouldn't it?

because "The longest sum of consecutive primes below one-thousand that adds to a prime", adds to a prime well above 1000.

User avatar
hulkhomer
Posts: 3
Joined: Mon Jan 06, 2014 7:35 pm

Re: Problem 050

Post by hulkhomer »

I only made a list of the primes below 47620 because the problem gives a sum with 21 primes. Therefore a list of consecutive primes higher than 47620 can not be longer than 21 (while staying under 1.000.000).

I get the correct solution, but was curious what you guys think. I use a rather old laptop and the performance ist way better when the code doesn't have to find all primes below 1M.
Image

User avatar
TheEvil
Posts: 84
Joined: Sun Nov 13, 2011 10:38 am
Location: Szeged, Hungary

Re: Problem 050

Post by TheEvil »

First of all, the 21 terms in the sequence belongs to the largest prime below 1000. I'm almost sure, the longest sum contains more terms than 21, if the limit is 1 million.
Nevertheless your upper limit is wrong, and I want to illustrate on an example. If the limit was 100 and you would have been allowed to use three primes, the upper limit is not 100/3=33. Take the 3 primes to be 29+31+37=97. The largest one among those is bigger than 33.
Image

User avatar
hulkhomer
Posts: 3
Joined: Mon Jan 06, 2014 7:35 pm

Re: Problem 050

Post by hulkhomer »

Ah, I see your point. I took it as granted, that the sum will be longer than 21 (it is :D ), and choose the upper limit for my prime list.

So how about doubling the limit, making it roughly 100.000. That should work and the primes still can be found faster.
Image

User avatar
TheEvil
Posts: 84
Joined: Sun Nov 13, 2011 10:38 am
Location: Szeged, Hungary

Re: Problem 050

Post by TheEvil »

That was years ago when I solved this problem. Of course the longest chain will be at least 21 long. Since there are a lot of primes, you don't have to double your limit, just raise by 1000, or so, since their average has to be around 1000000/21, if the series cointains 21 terms.
Anyway, for later problems you have to develop some method for testing/collecting primes, to 10 or 100 million, so keep on thinking how to do that.
Image

User avatar
hulkhomer
Posts: 3
Joined: Mon Jan 06, 2014 7:35 pm

Re: Problem 050

Post by hulkhomer »

TheEvil wrote:That was years ago when I solved this problem. Of course the longest chain will be at least 21 long. Since there are a lot of primes, you don't have to double your limit, just raise by 1000, or so, since their average has to be around 1000000/21, if the series cointains 21 terms.
Anyway, for later problems you have to develop some method for testing/collecting primes, to 10 or 100 million, so keep on thinking how to do that.
Thank you very much for your input! I'm new at programming (due to the fact that I'm 38 years old I consider myself as a latebloomer ;)) and l'm really glad to get input from seasoned pros ;)
Image

mjollnir357
Posts: 1
Joined: Sun Apr 13, 2014 10:06 pm

Re: Problem 050

Post by mjollnir357 »

I admit to being confused about the language of the problem statement. For the under 1000 section, I got a list of consecutive primes that is 25 long and sums to 281. How can 21 be considered greater than 25?

TripleM
Posts: 382
Joined: Fri Sep 12, 2008 3:31 am

Re: Problem 050

Post by TripleM »

If you had indeed found such a list of primes, it would have contradicted the problem statement, because 25 is greater than 21.

However, it is definitely impossible that you have done so, because the smallest 25 prime numbers (ranging from 2 up to 97) add to a lot more than 281.

Agrentum
Posts: 10
Joined: Tue May 06, 2014 12:44 am

Re: Problem 050

Post by Agrentum »

Hi everybody. I hope you will not mind, but I wanted to benchmark my solution in C++11. Here are my parameters:

Compiler: GCC 4.7.2
CPU: Intel Core i7-3517U, 1.90GHz
Flags used in compilation:
-Wall -Wextra (no output generated)
-g (for debugging purpose, Valgrind returned no problems or leaks)
-Ofast (slight improvement over -O2 and -O3)
-march and -mtune for corei7-avx
-std=gnu++11 (for vector and algorithm support)
-lm

Average runtime is 26.988 seconds. Code returns correct results provided in problem statement and returns correct solution to problem itself. It is not tragic, but regardless one of my slower programs. What bothers me is the fact my solution in C11 (that I feel more proficient with) is only about 2-5 seconds faster. I'm sensing a lot there is to improve but I am stuck since last Monday on it. Could you post your parameters in similar fashion for comparison? If it does not violate rules of competition, I would be happy to exchange my code for sake of running comparison/learning.

Thanks in advance :)
Image - self-demoted from 357, I want to return to this score by solving everything in C/C++.

Post Reply