Problem 060

[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

[Francky]

With Python3, no compilation, no psyco, nothing...
100% pure python.
1.47s to find a candidate
12s more to proove it.

[thedoctar]

Did you use a prime sieve?

19.855 seconds in pypy

[Francky]

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.

[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/.

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

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

[Slaunger]

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.

[jaxl]

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

[nicolas.patrois]

Ah, I solved this one a long time ago but I’m still stuck on 51.

[gotube]

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.

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]

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]

Last time I checked, 9 = 3x3.

[benedicfuentes]

Ow I see,, Overlooked at that.

[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

[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]

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]

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?

[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?

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.

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