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.

 Posts: 4
 Joined: Sat Nov 01, 2008 11:19 am
Problem 060
I'm already tying to solve this one for almost a month with no luck... so I need some clarifications.
I have to find 5 primes and if I put two of them toguether in any order, it must produce another prime. Right?
Ex: the prime 7 and 109, procude 7109 and 1097 by putting them toguether and these numbers are also prime.
I think I got essence of the problem very well (if not tell me please) because I used my program to find only 4 primes and the first set that came up was the one on the problem (3, 7, 109, 673), then I "upgraded" my program to find 5 primes with this property.
I got a set of five primes but the sum was not the answer. So I though that the answer would be smaller than the one I got and I did this:
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.
The program started and ended without giving a thing, please if there is something with my reasoning that isn't right point it out.
PS: I'm not an expert in the area of programing so I still use the basics, however I did all problems before this one... oh and sorry for the long post and for the english
I have to find 5 primes and if I put two of them toguether in any order, it must produce another prime. Right?
Ex: the prime 7 and 109, procude 7109 and 1097 by putting them toguether and these numbers are also prime.
I think I got essence of the problem very well (if not tell me please) because I used my program to find only 4 primes and the first set that came up was the one on the problem (3, 7, 109, 673), then I "upgraded" my program to find 5 primes with this property.
I got a set of five primes but the sum was not the answer. So I though that the answer would be smaller than the one I got and I did this:
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.
The program started and ended without giving a thing, please if there is something with my reasoning that isn't right point it out.
PS: I'm not an expert in the area of programing so I still use the basics, however I did all problems before this one... oh and sorry for the long post and for the english
Re: Problem #60
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.

 Posts: 4
 Joined: Sat Nov 01, 2008 11:19 am
Re: Problem #60
You're right! Stupid me >_> I was working with the sums and the primes at the same time, of course it couldn't work... Going to try this out then... thanks.
Edit: It worked, thank you so much
Edit: It worked, thank you so much
Re: Problem #60
Is it possible to hint?
Are the primes, shown in problem, included in the new set?
I stuck in this problem... By addition fifth prime to given four I obtain wrong result.
I try the idea that 1 is prime number, and saw wrong result one more time.
Can someone help me?
Are the primes, shown in problem, included in the new set?
I stuck in this problem... By addition fifth prime to given four I obtain wrong result.
I try the idea that 1 is prime number, and saw wrong result one more time.
Can someone help me?
2 x 2 = 4 = true
Re: Problem #60
The primes shown may or may not be included in the new set of 5 primes.
1 is NOT a prime number.
1 is NOT a prime number.
Math and Programming are complements

 Posts: 10
 Joined: Thu Sep 09, 2010 12:24 am
Re: Problem 060
Hi, I'm late to the game and have been diligently solving problems for the last few months trying to get caught up. I'm currently blocked on 2 of the sub 100 questions and this is one of them. I feel I have a pretty good algorithm, but can never seem to find a fifth match. Is it ok for me to confirm my top range? (I made the text white so it is hidden.)I've been under the assumption that all 5 would be under 10000. My code takes a LONG time to run, but it doesn't find anything under that mark. The number is somewhat arbitrary, but I saw it on another site where someone was talking about this problem. I have tried higher numbers as well, but would like to know if I have an error in my algorithm before I let me computer just run on til it finds a prime list that works after a few hours!
Thanks for any insight you care to give and all the fun problems!
Thanks for any insight you care to give and all the fun problems!
Re: Problem 060
nemoyatpeace, your assumption is correct, so there must be something wrong with your program.
It sounds to me that your algorithm is not as good as it could be. My own program takes only seconds to check all possibilities in that range, not hours.
It sounds to me that your algorithm is not as good as it could be. My own program takes only seconds to check all possibilities in that range, not hours.
_{Jaap's Puzzle Page}

 Posts: 10
 Joined: Thu Sep 09, 2010 12:24 am
Re: Problem 060
Thanks, finally got it! Was making some cancellations to my list that were faulty. And I like your signature so I added mine!

 Posts: 31
 Joined: Mon May 16, 2011 7:03 am
Re: Problem 060
Hello,
I need some motivation to optimize my program.
What processing time can i expect with good optimizations ?
It currently takes 1.60 s to solve on a core i5 3.1 GHz, primes generation included.
I didn't care to optimize it so far, but if you tell me it can be done much faster, i'll try to find how!
Thanks.
I need some motivation to optimize my program.
What processing time can i expect with good optimizations ?
It currently takes 1.60 s to solve on a core i5 3.1 GHz, primes generation included.
I didn't care to optimize it so far, but if you tell me it can be done much faster, i'll try to find how!
Thanks.
Joined PE in May 2011
Re: Problem 060
just hardcode the primes to your program instead of generating it at runtimeHibernatus34 wrote:Hello,
I need some motivation to optimize my program.
What processing time can i expect with good optimizations ?
It currently takes 1.60 s to solve on a core i5 3.1 GHz, primes generation included.
I didn't care to optimize it so far, but if you tell me it can be done much faster, i'll try to find how!
Thanks.

 Posts: 31
 Joined: Mon May 16, 2011 7:03 am
Re: Problem 060
Thanks for the idea, but i don't want to do that because i find it more interesting to learn faster ways to generate them.elr wrote:just hardcode the primes to your program instead of generating it at runtime
And if you allow this kind of optimization, then why not write the following ?
Code: Select all
int SolveProblem442(void)
{
// I've already found this, so there is no need to calculate it anymore
// Runs in less than a nanosecond
return 42;
}
Joined PE in May 2011
Re: Problem 060
Have you read the problem forum for this problem? That's where people post their code, along with how fast their program is, plus generalisations.Hibernatus34 wrote:Hello,
I need some motivation to optimize my program.
What processing time can i expect with good optimizations ?
It currently takes 1.60 s to solve on a core i5 3.1 GHz, primes generation included.
I didn't care to optimize it so far, but if you tell me it can be done much faster, i'll try to find how!
Thanks.
(edit  whoops, quoted wrong number)
Last edited by TripleM on Thu May 26, 2011 12:08 pm, edited 2 times in total.
Re: Problem 060
0.3 msec? I can't imagine.
Re: Problem 060
I don't know how your program works but prime generation and primality checking take most of the time in my prog.Hibernatus34 wrote:Thanks for the idea, but i don't want to do that because i find it more interesting to learn faster ways to generate them.elr wrote:just hardcode the primes to your program instead of generating it at runtime
And if you allow this kind of optimization, then why not write the following ?I could use low level optimizations and parallel computing too (OpenMP), but it would be like buying a processor that is 4 times faster : not as interesting as algorithm optimizations.Code: Select all
int SolveProblem442(void) { // I've already found this, so there is no need to calculate it anymore // Runs in less than a nanosecond return 42; }
(0.534 sec on a seven year old machine. A modern one would be about 3 times faster).
You might invest time in a fast primesieve up to higher limits. It may pay off with other problems.
Re: Problem 060
what i suggested is not the same as hardcoding the answerHibernatus34 wrote:Thanks for the idea, but i don't want to do that because i find it more interesting to learn faster ways to generate them.elr wrote:just hardcode the primes to your program instead of generating it at runtime
And if you allow this kind of optimization, then why not write the following ?I could use low level optimizations and parallel computing too (OpenMP), but it would be like buying a processor that is 4 times faster : not as interesting as algorithm optimizations.Code: Select all
int SolveProblem442(void) { // I've already found this, so there is no need to calculate it anymore // Runs in less than a nanosecond return 42; }
because finding primes is not the core of the question

 Posts: 31
 Joined: Mon May 16, 2011 7:03 am
Re: Problem 060
Thanks. I've seen somebody had 88 ms in 2008, which is motivating Edit : He didn't count prime numbers generationTripleM wrote: Have you read the problem forum for this problem? That's where people post their code, along with how fast their program is, plus generalisations.
(edit  whoops, quoted wrong number)
I usually don't read these forums as they're old and full of hard to read and brute force code.
I also don't want to find ideas there, at least not too early.
Does it mean you solve this problem in about 0.6 sec on a 7 year old machine ?hk wrote: I don't know how your program works but prime generation and primality checking take most of the time in my prog.
(0.534 sec on a seven year old machine. A modern one would be about 3 times faster).
You might invest time in a fast primesieve up to higher limits. It may pay off with other problems.
This could be motivating too.
Edit: I've optimized a little and got 400 ms, still including prime numbers generation which takes 220 ms (prime sieve for numbers bellow 50 000 000). That's still disappointing.
Joined PE in May 2011

 Posts: 31
 Joined: Mon May 16, 2011 7:03 am
Re: Problem 060
Thanks to hk's help i realized i could improve my sieve generation and make a big enough sieve to make the whole function faster.
Now it takes 265 ms, among which 215 ms are taken by the sieve alone.
Now it takes 265 ms, among which 215 ms are taken by the sieve alone.
Joined PE in May 2011
Re: Problem 060
I have a Python solution which not presuppose any bounds for prime nor sum to find.
It take me 12.5s (nothing is compiled), I would know if experts had a more efficient solution which didn't presuppose any bounds for primes nor sum.
I'm proud of it, but I'm sure that it exists a better purist solution.
The solution is given in 1.2s, and it take 11.3s to proove that I got the answer with the minimal sum.
Not any bound is presupposed in my solution ; so, no sieve.
It take me 12.5s (nothing is compiled), I would know if experts had a more efficient solution which didn't presuppose any bounds for primes nor sum.
I'm proud of it, but I'm sure that it exists a better purist solution.
The solution is given in 1.2s, and it take 11.3s to proove that I got the answer with the minimal sum.
Not any bound is presupposed in my solution ; so, no sieve.
Last edited by Francky on Tue Jul 12, 2011 7:59 am, edited 2 times in total.
Entia non sunt multiplicanda praeter necessitatem

 Posts: 31
 Joined: Mon May 16, 2011 7:03 am
Re: Problem 060
I've talked with Francky about that, and he's right, my algorithm was cheating.
I've fixed it (until Francky proves me wrong ), and now it takes 5.80 s. Edit : 2.45 s
I've fixed it (until Francky proves me wrong ), and now it takes 5.80 s. Edit : 2.45 s
Last edited by Hibernatus34 on Mon Jul 11, 2011 5:07 pm, edited 2 times in total.
Joined PE in May 2011