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.
DiogoRegateiro
Posts: 4
Joined: Sat Nov 01, 2008 11:19 am

Problem 060

Post by 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 :)
User avatar
Tommy137
Posts: 238
Joined: Sun Feb 24, 2008 6:02 pm
Location: Cologne, Germany
Contact:

Re: Problem #60

Post by Tommy137 »

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.
Image
DiogoRegateiro
Posts: 4
Joined: Sat Nov 01, 2008 11:19 am

Re: Problem #60

Post by 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 :)
User avatar
DNS
Posts: 30
Joined: Thu Oct 16, 2008 9:32 am
Location: Ukraine, Nikolaev

Re: Problem #60

Post by 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?
2 x 2 = 4 = true
User avatar
uws8505
Posts: 58
Joined: Tue Sep 30, 2008 3:13 pm
Location: South Korea

Re: Problem #60

Post by uws8505 »

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

1 is NOT a prime number.
Math and Programming are complements
User avatar
DNS
Posts: 30
Joined: Thu Oct 16, 2008 9:32 am
Location: Ukraine, Nikolaev

Re: Problem #60

Post by DNS »

Thanks!
Problem is difficult for me. Nice problem...
2 x 2 = 4 = true
nemoyatpeace
Posts: 10
Joined: Thu Sep 09, 2010 12:24 am

Re: Problem 060

Post by 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!
Image
User avatar
jaap
Posts: 554
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Problem 060

Post by 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
Posts: 10
Joined: Thu Sep 09, 2010 12:24 am

Re: Problem 060

Post by nemoyatpeace »

Thanks, finally got it! Was making some cancellations to my list that were faulty. And I like your signature so I added mine!
Image
Hibernatus34
Posts: 31
Joined: Mon May 16, 2011 7:03 am

Re: Problem 060

Post by 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.
Image Joined PE in May 2011
elr
Posts: 67
Joined: Thu Apr 09, 2009 9:47 am

Re: Problem 060

Post by elr »

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.
just hardcode the primes to your program instead of generating it at runtime
Image
Hibernatus34
Posts: 31
Joined: Mon May 16, 2011 7:03 am

Re: Problem 060

Post by Hibernatus34 »

elr wrote: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.
Image Joined PE in May 2011
TripleM
Posts: 382
Joined: Fri Sep 12, 2008 3:31 am

Re: Problem 060

Post by TripleM »

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.
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)
Last edited by TripleM on Thu May 26, 2011 12:08 pm, edited 2 times in total.
User avatar
hk
Administrator
Posts: 11040
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Problem 060

Post by hk »

0.3 msec? I can't imagine.
Image
User avatar
hk
Administrator
Posts: 11040
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Problem 060

Post by hk »

Hibernatus34 wrote:
elr wrote: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.
Image
elr
Posts: 67
Joined: Thu Apr 09, 2009 9:47 am

Re: Problem 060

Post by elr »

Hibernatus34 wrote:
elr wrote: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
Image
Hibernatus34
Posts: 31
Joined: Mon May 16, 2011 7:03 am

Re: Problem 060

Post by Hibernatus34 »

TripleM 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)
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.
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.
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.
Image Joined PE in May 2011
Hibernatus34
Posts: 31
Joined: Mon May 16, 2011 7:03 am

Re: Problem 060

Post by 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.
Image Joined PE in May 2011
User avatar
Francky
Posts: 90
Joined: Sat May 07, 2011 3:49 pm
Location: South of France

Re: Problem 060

Post by 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.
Last edited by Francky on Tue Jul 12, 2011 7:59 am, edited 2 times in total.
ImageEntia non sunt multiplicanda praeter necessitatem
Hibernatus34
Posts: 31
Joined: Mon May 16, 2011 7:03 am

Re: Problem 060

Post by 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
Last edited by Hibernatus34 on Mon Jul 11, 2011 5:07 pm, edited 2 times in total.
Image Joined PE in May 2011
Post Reply