Problem 060

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.
User avatar
thedoctar
Posts: 74
Joined: Fri Apr 15, 2011 11:57 am
Location: Sydney, Australia

Re: Problem 060

Post by thedoctar »

real 10m13.156s
user 1m23.329s
sys 8m0.378s

These are the times I got. It only takes 21seconds to find the solution, and the above times are to ensure that it is the only solution. Only used math and itertools, no psyco.

Anyone have faster algos they can pm?

Edit:49seconds using pypy, 5min25sec without
4x Intel(R) Core(TM) i3-2330M CPU @ 2.20GHz
Image
fabas indulcet fames
User avatar
Francky
Posts: 90
Joined: Sat May 07, 2011 3:49 pm
Location: South of France

Re: Problem 060

Post by Francky »

With Python3, no compilation, no psyco, nothing...
100% pure python.
1.47s to find a candidate
12s more to proove it.
ImageEntia non sunt multiplicanda praeter necessitatem
User avatar
thedoctar
Posts: 74
Joined: Fri Apr 15, 2011 11:57 am
Location: Sydney, Australia

Re: Problem 060

Post by thedoctar »

Did you use a prime sieve?

19.855 seconds in pypy
4x Intel(R) Core(TM) i3-2330M CPU @ 2.20GHz
Image
fabas indulcet fames
User avatar
Francky
Posts: 90
Joined: Sat May 07, 2011 3:49 pm
Location: South of France

Re: Problem 060

Post by Francky »

thedoctar wrote:Did you use a prime sieve?

19.855 seconds in pypy
I didn't make any asumption on bounds (nor ...), so I didn't make a sieve.
I start from zéro to infinity until the solution is found and prooved.
ImageEntia non sunt multiplicanda praeter necessitatem
User avatar
thedoctar
Posts: 74
Joined: Fri Apr 15, 2011 11:57 am
Location: Sydney, Australia

Re: Problem 060

Post by thedoctar »

Most of my computation time is used checking whether the number is a prime or not. I put in a set which stored primes that I already checked, and that halved the time to 5 min and 25 sec, but 200 seconds were still used checking primes. I either need to reduce the search range or make a better prime checker/.
4x Intel(R) Core(TM) i3-2330M CPU @ 2.20GHz
Image
fabas indulcet fames
User avatar
Francky
Posts: 90
Joined: Sat May 07, 2011 3:49 pm
Location: South of France

Re: Problem 060

Post by Francky »

I tried pypy (download, uncompress .tar.bz, install dependences)
I used

Code: Select all

pypy PE-060.py
(is it the correct use ????)

I got the answer after 0.56s and the proof at the total time of 4.33s.
(it's only ×3 times better, should I use it with a better way ?)
--

@thedoctar : couls you open a new topic in programmation section to continue explainations on pypy.
Thanks.
ImageEntia non sunt multiplicanda praeter necessitatem
gotube
Posts: 2
Joined: Sat Aug 17, 2013 1:09 am

Re: Problem 060

Post by gotube »

I'm looking for some insight into a reasonably fast algorithm. I had one algorithm that I'm certain is good, but it would have taken a few hundred trillion years to complete (if my arithmetic was good). I made significant improvements, but I'm still in the range of years because it's always O(n^5) in the worst case scenario. Is there a non-brute force way to get at the answer?

Obviously I don't want the code or even an algorithm, just a nudge or two. Thanks.
User avatar
Slaunger
Posts: 40
Joined: Tue Jul 20, 2010 12:23 am

Re: Problem 060

Post by Slaunger »

gotube wrote: I made significant improvements, but I'm still in the range of years because it's always O(n^5) in the worst case scenario. Is there a non-brute force way to get at the answer?

Obviously I don't want the code or even an algorithm, just a nudge or two. Thanks.
No need for O(n^5). You can make an algorithm which is (basically) O(n^2) independent of how many primes shall be concatenated. Yet, this is still (for me at least), the computationally nastiest among problem 1-100. My Python script takes about 18 secs to find the result. For comparison, I can find the results of all problems 1-100 in 49 secs, so this problem alone is eating 1/3 of the time. Also, if you have not already implemented an isPrime function, this may be a good time to do so. :D
Image
jaxl
Posts: 6
Joined: Mon Mar 15, 2010 7:15 pm

Re: Problem 060

Post by jaxl »

gotube wrote:I'm looking for some insight into a reasonably fast algorithm. I had one algorithm that I'm certain is good, but it would have taken a few hundred trillion years to complete (if my arithmetic was good). I made significant improvements, but I'm still in the range of years because it's always O(n^5) in the worst case scenario. Is there a non-brute force way to get at the answer?

Obviously I don't want the code or even an algorithm, just a nudge or two. Thanks.
This is definitely one of the hardest problems < 100 - i was stuck on it for a long time... Move on and try another problem for a little while, its amazing how much a fresh head can help coming back to an old problem..
Image
User avatar
nicolas.patrois
Posts: 118
Joined: Fri Jul 26, 2013 4:54 pm
Contact:

Re: Problem 060

Post by nicolas.patrois »

Ah, I solved this one a long time ago but I’m still stuck on 51. :wink:
Image
gotube
Posts: 2
Joined: Sat Aug 17, 2013 1:09 am

Re: Problem 060

Post by gotube »

Slaunger wrote: No need for O(n^5). You can make an algorithm which is (basically) O(n^2) independent of how many primes shall be concatenated. Yet, this is still (for me at least), the computationally nastiest among problem 1-100. My Python script takes about 18 secs to find the result. For comparison, I can find the results of all problems 1-100 in 49 secs, so this problem alone is eating 1/3 of the time. Also, if you have not already implemented an isPrime function, this may be a good time to do so. :D
That's good to hear. I fail to see how adding primes to the problem doesn't make it exponentially more difficult to solve. Moving on...
benedicfuentes
Posts: 4
Joined: Mon Dec 02, 2013 8:09 am

Wrong Solution of admin

Post by benedicfuentes »

The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.

Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.
The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.
How could that happen?

How about these numbers: 7 9 19 433 the sum is 468?
TripleM
Posts: 382
Joined: Fri Sep 12, 2008 3:31 am

Re: Wrong Solution of admin

Post by TripleM »

Last time I checked, 9 = 3x3.
benedicfuentes
Posts: 4
Joined: Mon Dec 02, 2013 8:09 am

Re: Wrong Solution of admin

Post by benedicfuentes »

Ow I see,, Overlooked at that.
User avatar
mpiotte
Administrator
Posts: 1914
Joined: Tue May 08, 2012 5:40 pm
Location: Montréal, Canada

Re: Problem 060

Post by mpiotte »

Like it says here: Comments, questions and clarifications about PE problems.
Before you start a new topic in this forum, please make sure that a topic for the same problem does not already exist. If such a topic already exists, please post your question or concern in that topic; it's the only way to keep the number of topics manageable and make it possible to easily search for a specific problem.

If there is no previous topic for the specific problem you are trying to solve, you may start a new topic, giving as subject Problem xxx. Please do not use in the Subject-field expressions like "Clarification needed", "problem with the wording", "Correct answer not accepted" etc
Image
srinathmkce
Posts: 5
Joined: Fri Jun 19, 2015 2:50 pm

Re: Problem 060

Post by srinathmkce »

Hello all,

I just need a simple suggestion from you . I am new to programming languages. Am trying to improve my skills . I am solving PE problems one by one . i have solved 1 to 59 and am struck in problem 60 for a month.

Now, am thinking that my logic is having some flaw that i could not find out. i followed the approach below
1. Generated prime numbers till 10000000
2. Generated another set of primes till 10000
3. I compared each number in the list with other numbers ,and checked if it is satisfying the property. If so, push it in list and move on . Each time, i am checking if the condition is satisfied for all the numbers in the list.
For example, lets take 3 . 35 and 53 are not prime. hence , i will move to 7 . 37 and 73 are prime. hence i will push 7 to list. and move to 11. For 11 i will check with 3 and also with 7.
4. i also added a logic like, 3,7,109, 673 . after 673 there is no number within 10000 which follows the property. Hence i will pop 673 and continue the loop with Index + 1 of 673 and simillarly for 109 and 7. So that i wont miss any numbers.
5. If list has 5 numbers i will exit the program after printing it.

Am not really sure , how to do it in a better manner. its taking lot of time. I need suggestions on this or do you recommend to continue with other problems and come back to this later.
AVN
Posts: 13
Joined: Mon Feb 11, 2013 10:00 pm

Re: Problem 060

Post by AVN »

Giving hints is against board policy, but if you allow others to send you a PM, maybe someone will send you a hint or two.
Svartskägg
Posts: 55
Joined: Thu Mar 29, 2012 12:55 pm
Location: Sweden

Re: Problem 060

Post by Svartskägg »

srinathmkce wrote:Am not really sure , how to do it in a better manner. its taking lot of time.
Do you mean your program finishes without finding an answer or that it takes so much time that you abort it before it's done?
Image
320641_5486fc18ea1dcc4e9a8f29c7677a5c19 <-- my friend key
jnash67
Posts: 3
Joined: Wed Jun 23, 2010 11:34 pm

Re: Problem #60

Post by jnash67 »

This is a question about a pretty old post (one of the first in this thread) that says for 5 primes A,B,C,D,E would be below 4/5 N where N is some higher sum that also satisfies the prime pair sets property.

I'm curious what the reasoning is behind this relationship. Looking at the case of 4 primes, the lowest solution is 3 + 7 + 109 + 673 =792 . While it is true that 3 + 7 + 109 < 3/5 * 792, I don't understand why this inequality has to hold?
Tommy137 wrote:
DiogoRegateiro wrote:N is the sum I got before and A, B, C, D, E the primes.
I searched all primes like this:
A < N / 5
A+B < N / 4
A+B+C < N /3
A+B+C+D < N / 2
A+B+C+D+E < N

where A<=B<=C<=D<=E.


This doesn't work for a set of consecutive primes or anything similar so that A+B+C+D+E is less than N, but A+B+C+D is just below 4/5*N and not < N/2.
User avatar
jaap
Posts: 559
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Problem #60

Post by jaap »

Tommy137 was pointing out exactly that - the inequalities that DiogoRegateiro was using while searching for a set of 5 primes were invalid. By using the counterexample of 5 consecutive primes (consecutive so that they are approximately the same size) he showed that four of them would certainly be larger than N/2. Hence the fourth of Diogo's inequalities does not hold in general. Also, it seems to me that N was merely some arbitrary upper bound or search limit for the answer that Diogo was using.
Post Reply