Problem 060
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.
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
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
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.
Re: Problem 060
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
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) i32330M CPU @ 2.20GHz
fabas indulcet fames
fabas indulcet fames
Re: Problem 060
With Python3, no compilation, no psyco, nothing...
100% pure python.
1.47s to find a candidate
12s more to proove it.
100% pure python.
1.47s to find a candidate
12s more to proove it.
Entia non sunt multiplicanda praeter necessitatem
Re: Problem 060
Did you use a prime sieve?
19.855 seconds in pypy
19.855 seconds in pypy
4x Intel(R) Core(TM) i32330M CPU @ 2.20GHz
fabas indulcet fames
fabas indulcet fames
Re: Problem 060
I didn't make any asumption on bounds (nor ...), so I didn't make a sieve.thedoctar wrote:Did you use a prime sieve?
19.855 seconds in pypy
I start from zéro to infinity until the solution is found and prooved.
Entia non sunt multiplicanda praeter necessitatem
Re: Problem 060
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) i32330M CPU @ 2.20GHz
fabas indulcet fames
fabas indulcet fames
Re: Problem 060
I tried pypy (download, uncompress .tar.bz, install dependences)
I used
(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.
I used
Code: Select all
pypy PE060.py
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.
Entia non sunt multiplicanda praeter necessitatem
Re: Problem 060
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 nonbrute force way to get at the answer?
Obviously I don't want the code or even an algorithm, just a nudge or two. Thanks.
Obviously I don't want the code or even an algorithm, just a nudge or two. Thanks.
Re: Problem 060
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 1100. My Python script takes about 18 secs to find the result. For comparison, I can find the results of all problems 1100 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.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 nonbrute force way to get at the answer?
Obviously I don't want the code or even an algorithm, just a nudge or two. Thanks.
Re: Problem 060
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..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 nonbrute force way to get at the answer?
Obviously I don't want the code or even an algorithm, just a nudge or two. Thanks.
 nicolas.patrois
 Posts: 118
 Joined: Fri Jul 26, 2013 4:54 pm
 Contact:
Re: Problem 060
Ah, I solved this one a long time ago but I’m still stuck on 51.
Re: Problem 060
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...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 1100. My Python script takes about 18 secs to find the result. For comparison, I can find the results of all problems 1100 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.

 Posts: 4
 Joined: Mon Dec 02, 2013 8:09 am
Wrong Solution of admin
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.
How could that happen?The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.
How about these numbers: 7 9 19 433 the sum is 468?
Re: Wrong Solution of admin
Last time I checked, 9 = 3x3.

 Posts: 4
 Joined: Mon Dec 02, 2013 8:09 am
Re: Wrong Solution of admin
Ow I see,, Overlooked at that.
Re: Problem 060
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 Subjectfield expressions like "Clarification needed", "problem with the wording", "Correct answer not accepted" etc

 Posts: 5
 Joined: Fri Jun 19, 2015 2:50 pm
Re: Problem 060
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.
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.
Re: Problem 060
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.

 Posts: 55
 Joined: Thu Mar 29, 2012 12:55 pm
 Location: Sweden
Re: Problem 060
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?srinathmkce wrote:Am not really sure , how to do it in a better manner. its taking lot of time.
320641_5486fc18ea1dcc4e9a8f29c7677a5c19 < my friend key
Re: Problem #60
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?
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.
Re: Problem #60
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.
_{Jaap's Puzzle Page}