Problem 060

[DiogoRegateiro]

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

[Tommy137]

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.

[DiogoRegateiro]

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

[DNS]

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?

[uws8505]

The primes shown may or may not be included in the new set of 5 primes.

1 is NOT a prime number.

[DNS]

Thanks!
Problem is difficult for me. Nice problem...

[nemoyatpeace]

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!

[jaap]

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.

[nemoyatpeace]

Thanks, finally got it! Was making some cancellations to my list that were faulty. And I like your signature so I added mine!

[Hibernatus34]

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.

[elr]

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.

just hardcode the primes to your program instead of generating it at runtime

[Hibernatus34]

just hardcode the primes to your program instead of generating it at runtime

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

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.

[TripleM]

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.

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)

[hk]

0.3 msec? I can't imagine.

[hk]

just hardcode the primes to your program instead of generating it at runtime

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

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.

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.

[elr]

just hardcode the primes to your program instead of generating it at runtime

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

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.

what i suggested is not the same as hardcoding the answer
because finding primes is not the core of the question

[Hibernatus34]

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)

Thanks. I've seen somebody had 88 ms in 2008, which is motivating Edit : He didn't count prime numbers generation
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.

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.

Does it mean you solve this problem in about 0.6 sec on a 7 year old machine ?
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.

[Hibernatus34]

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.

[Francky]

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.

[Hibernatus34]

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