programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Ron McLeod
• Junilu Lacar
• Paul Clapham
• Liutauras Vilda
Sheriffs:
• Jeanne Boyarsky
• Rob Spoor
• Bear Bibeault
Saloon Keepers:
• Tim Moores
• Tim Holloway
• Piet Souris
• Carey Brown
• Stephan van Hulst
Bartenders:
• Frits Walraven
• fred rosenberger
• salvin francis

# Problem 5 in Project Euler

Ranch Hand
Posts: 78
• Number of slices to send:
Optional 'thank-you' note:
Hi !!!
I have written an algorithm in Java to solve the problem 5 in project euler.

Problem 5
-----------

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Below is my code

I am pretty sure the algorithm is correct, because it gives the correct answer for the first part. (i.e 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.). But I feel my algorithm is not efficient. I googled the problem and found that 232792560 is the smallest number can be evenly divided by 1-20. So this is a very big value. Why my algorithm does not give the answer. I let the program to run a long time and waited till I get the desired result, but at some point the program got stuck.

is there anything wrong in my logic ? or not efficient?

Bartender
Posts: 4568
9
• Number of slices to send:
Optional 'thank-you' note:
Well, a serial search like that is a very inefficient approach of solving it. You might want to read up about methods for calculating a Least Common Multiple. But in terms of the logic: don't you need to reset count for each new number?

(I'm also not sure why you've put i++ inside both branches of your if statement, instead of inside the loop statement as usual, but that doesn't affect the logic, just the readability).

Ranch Hand
Posts: 78
• Number of slices to send:
Optional 'thank-you' note:

Matthew Brown wrote:Well, a serial search like that is a very inefficient approach of solving it. You might want to read up about methods for calculating a Least Common Multiple. But in terms of the logic: don't you need to reset count for each new number?

(I'm also not sure why you've put i++ inside both branches of your if statement, instead of inside the loop statement as usual, but that doesn't affect the logic, just the readability).

Thank you. yes I should reset the count variable for each new number.
Well I could have incremented i variable in the for loop itself without changing it in if-else conditions. As you said yes this is really inefficient. I will go through LCM. Thanks.

Ranch Hand
Posts: 80
1
• Number of slices to send:
Optional 'thank-you' note:
Also, to make this a little more efficient you could end the current loop iteration the first time % != 0 to prevent testing all the other cases unnecessarily.

You should look at the Java continue keyword.

Ranch Hand
Posts: 78
• Number of slices to send:
Optional 'thank-you' note:

Marc Cracco wrote:Also, to make this a little more efficient you could end the current loop iteration the first time % != 0 to prevent testing all the other cases unnecessarily.

You should look at the Java continue keyword.

Thanks

lowercase baba
Posts: 12992
66
• Number of slices to send:
Optional 'thank-you' note:
how do you know the program got stuck? Some of the Project Euler problems can require a long time, if you don't use a clever method to reduce the steps. Maybe your program is just churning away...

The whole POINT of Project Euler is to get you to think about the problems...not to get the right answer.

fred rosenberger
lowercase baba
Posts: 12992
66
• Number of slices to send:
Optional 'thank-you' note:
looking at your code...one simple optimization is to not increment the number you are testing by 1 each time. Why would you bother testing 21 to see if it is divisible by 20? or 22? or 23? You know you only need to test multiples of 20, so increment by that.

Another easy optimization: Why bother starting with 20 (or 21?) You know 2520 is the smallest divisible by 1-10, so there is no need to test anything below that...

Marshal
Posts: 73263
332
• Number of slices to send:
Optional 'thank-you' note:

fred rosenberger wrote: . . . Project Euler problems can require a long time, if you don't use a clever method to reduce the steps. . . .

The whole idea behind Project Euler is to reduce the problem to something simple which can be executed in a minute or under. I managed that problem 5 in about 1 minute — by hand, but with a calculator. If your program is churning, you have used a wrong algorithm and should start again.

Paper, pencil and eraser. That is what you need. Let the computer churn for hours; you can work out the correct algorithm in less time.

Ranch Hand
Posts: 78
• Number of slices to send:
Optional 'thank-you' note:

Campbell Ritchie wrote:

fred rosenberger wrote: . . . Project Euler problems can require a long time, if you don't use a clever method to reduce the steps. . . .

The whole idea behind Project Euler is to reduce the problem to something simple which can be executed in a minute or under. I managed that problem 5 in about 1 minute — by hand, but with a calculator. If your program is churning, you have used a wrong algorithm and should start again.

Paper, pencil and eraser. That is what you need. Let the computer churn for hours; you can work out the correct algorithm in less time.

Thank you

Saloon Keeper
Posts: 4546
166
• Number of slices to send:
Optional 'thank-you' note:

Campbell Ritchie wrote:The whole idea behind Project Euler is to reduce the problem to something simple which can be executed in a minute or under. I managed that problem 5 in about 1 minute — by hand, but with a calculator.(...)
Paper, pencil and eraser. That is what you need. (...)

Or, like in your case, a hand and a calculator...

@Gihan:

We know that 2520 is divisable by the numbers 1, 2, ..., 10.
Let's call 2520 D0.

The next divisor is 11. Now, that is a prime number. If we are lucky then D0 is divisable by 11. Unfortunately, it is not.
Then, as a consequence, the next smallest number will be D0 * 11 = D1.

Then look at divisor 12. Since we know that D0 is divisable by 2 and 6, it is automatically divisble by 12. So, D1 is divisable by
the numbers 1 ... 12.

Then, what about 13? It is also a prime number. Is D1 divisable by 13? If not, how do we proceed?

Can you see a pattern emerging? Do you think coding is necessary here? And, whether that next smallest number

Greetz,
Piet

Piet Souris
Saloon Keeper
Posts: 4546
166
• Number of slices to send:
Optional 'thank-you' note:
Blundering here...

Of course, 18 is divisible by 2 and 6, but not by 12... this miserable Number Theory again.

So, while using prime numbers, there's no escape in checking the divisibility of in between
non-prime numbers. And if there's a fraction popping up, then multiply again by the smallest number
to get rid of that fraction. So, yes, these guys at google were right, after all...

fred rosenberger
lowercase baba
Posts: 12992
66
• Number of slices to send:
Optional 'thank-you' note:
you can look at the prime factorization of each possible divisor. Once you have those, it's pretty simple to calculate the LCM.

Piet Souris
Saloon Keeper
Posts: 4546
166
• Number of slices to send:
Optional 'thank-you' note:
Indeed, but I was hoping to avoid this, because it is not such an easy thing to do, and anyway much more work
than needed.

I was hinting at simply putting this in a spreadsheet, where you will solve it in a minute. This was probably
what Campbell was hinting at.

When I did this, the cells where I checked the divisions were formatted as integers...

fred rosenberger
lowercase baba
Posts: 12992
66
• Number of slices to send:
Optional 'thank-you' note:

Piet Souris wrote:Indeed, but I was hoping to avoid this, because it is not such an easy thing to do, and anyway much more work than needed.

ALL of Project Euler is not such an easy thing to do. That's kind of the fun of it.

:-)

Campbell Ritchie
Marshal
Posts: 73263
332
• Number of slices to send:
Optional 'thank-you' note:

Piet Souris wrote:. . . This was probably what Campbell was hinting at. . . .

Oh, no he wasn't. (British readers will understand that it is now December ‍).

I did the calculations on paper. Well, virtual paper on a WP program. Not a spreadsheet. Then I used the computer's calculator for all the multiplication, and I got 232792560 (well actually 2.3279256e+08!)

Piet Souris
Saloon Keeper
Posts: 4546
166
• Number of slices to send:
Optional 'thank-you' note:
Since it is obvious to all readers now, I might as well confess: never did any of this Euler project

Campbell Ritchie
Marshal
Posts: 73263
332
• Number of slices to send:
Optional 'thank-you' note:
I never signed up for Project Euler, either. Only, that question looked easy.

Matthew Brown
Bartender
Posts: 4568
9
• Number of slices to send:
Optional 'thank-you' note:

Campbell Ritchie wrote:I never signed up for Project Euler, either. Only, that question looked easy.

They start off very easy and get progressively harder. The first question is adding up multiples of 3 and 5. By the 7th you're generating prime numbers. They get a lot harder - there are over 400 and some of the later ones involve some very heavy mathematics.

For example (and I haven't tried this one - I've completed 93 of them), this is no. 442:

An integer is called eleven-free if its decimal expansion does not contain any substring representing a power of 11 except 1.

For example, 2404 and 13431 are eleven-free, while 911 and 4121331 are not.

Let E(n) be the nth positive eleven-free integer. For example, E(3) = 3, E(200) = 213 and E(500 000) = 531563.

Find E(10^18).

Piet Souris
Saloon Keeper
Posts: 4546
166
• Number of slices to send:
Optional 'thank-you' note:
OMG!

I see only one quick solution:

Campbell, may we borrow that virtual WP of yours (including that calculator)?!?!?

But I'll give it a try. Just don't expect an answer in any finite time

Greenhorn
Posts: 2
• Number of slices to send:
Optional 'thank-you' note:
Well, I particulary use the Euler's problems to think in a solution then I like to study better ways to figure out the same response.
In that case I found out this solution:

I just took 0.001707374 seconds to find the answer... man I don't what happend here but I like it!

Piet Souris
Saloon Keeper
Posts: 4546
166
• Number of slices to send:
Optional 'thank-you' note:
hi Marco,

welcome in the club!

That certainly is a very fast way to find all the prime factors involved.
And in that 0.00001... second I couldn't even get my spreadsheet program to load...

Did you also solve Matthews problem 442?

Greetz,
Piet

Marco Correa
Greenhorn
Posts: 2
• Number of slices to send:
Optional 'thank-you' note:
Thanks Piet,

I didn't get to it yet, but if I solve it, I'll post here.

Campbell Ritchie
Marshal
Posts: 73263
332
• Number of slices to send:
Optional 'thank-you' note:
Have you worked out what Fred means about prime factors? That is how you can do it, and how I did it. My solution has vanished, as I said it would.

Piet Souris
Saloon Keeper
Posts: 4546
166
• Number of slices to send:
Optional 'thank-you' note:
I just solved it, at least, I think I did.

With a Java program, I determined E(1) - E(10), where E(x) = Matthews E(10^x).
I put these E numbers in LibreOffice calc, and found, after a couple of hours puzzling,
a recursive relation between the E's. I expected something like this, otherwise
they wouldn't have asked for E(18).

Then I put this formula back in my program, to calculate up to E(25).

So, my formula works for up to E(10), after that it is just Piets conjecture.

If anyone is interested, I can put up the list E(1) ... E(25).

I hope to be able to prove my formula. From the form, I have some ideas how to handle it.

Greetz,
Piet

Piet Souris
Saloon Keeper
Posts: 4546
166
• Number of slices to send:
Optional 'thank-you' note:

Campbell Ritchie wrote:Have you worked out what Fred means about prime factors? That is how you can do it, and how I did it. My solution has vanished, as I said it would.

hi Campbell,

to whom are you asking this?

Greetz,
Piet

PS: I saw your solution, and it was a very clear to follow method. Since it is very instructive, I suggest you put it back
here. I think many people could benefit.

Campbell Ritchie
Marshal
Posts: 73263
332
• Number of slices to send:
Optional 'thank-you' note:

Piet Souris wrote: . . . to whom are you asking this?

OP

. . . I suggest you put it back . . .

I am reluctant to leave the whole solution in case people simply copy it and solve Euler no 5 without understanding it.

I have however found some links: 1, 2, 3 = Wikipedia, 4, and there are lots more.

What you are doing it working out the LCM = Lowest (=least) Common Multiple of 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 and 20.
All you have to do is use prime factors, as on those links

Campbell Ritchie
Marshal
Posts: 73263
332
• Number of slices to send:
Optional 'thank-you' note:
Sorry, I had the same link twice in the previous post; I have edited it and I think corrected the problem. I was taught that technique for LCMs when I was about 11 or 12; I think some of the links are aimed at people significantly younger than that.

 I found some pretty shells, some sea glass and this lovely tiny ad: Thread Boost feature https://coderanch.com/t/674455/Thread-Boost-feature