Win a copy of GANs in ActionE this week in the AI forum
or WebAssembly in Action in the JavaScript forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
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 all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Bear Bibeault
  • Paul Clapham
  • Jeanne Boyarsky
  • Knute Snortum
Sheriffs:
  • Liutauras Vilda
  • Tim Cooke
  • Junilu Lacar
Saloon Keepers:
  • Ron McLeod
  • Stephan van Hulst
  • Tim Moores
  • Tim Holloway
  • Carey Brown
Bartenders:
  • Joe Ess
  • salvin francis
  • fred rosenberger

Problem 5 in Project Euler

 
Ranch Hand
Posts: 78
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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).
 
Gihan Madushanka
Ranch Hand
Posts: 78
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Gihan Madushanka
Ranch Hand
Posts: 78
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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: 12792
51
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 12792
51
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 67435
257
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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.
 
Gihan Madushanka
Ranch Hand
Posts: 78
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
 
Bartender
Posts: 3674
151
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
that you googled is correct?

Greetz,
Piet
 
Piet Souris
Bartender
Posts: 3674
151
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 12792
51
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Bartender
Posts: 3674
151
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 12792
51
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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: 67435
257
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
Bartender
Posts: 3674
151
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Since it is obvious to all readers now, I might as well confess: never did any of this Euler project
 
Campbell Ritchie
Marshal
Posts: 67435
257
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I never signed up for Project Euler, either. Only, that question looked easy.
 
Matthew Brown
Bartender
Posts: 4568
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
Bartender
Posts: 3674
151
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Hibernate MySQL Database Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Bartender
Posts: 3674
151
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Hibernate MySQL Database Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Piet,

Feeling welcome already ^^

I didn't get to it yet, but if I solve it, I'll post here.
 
Campbell Ritchie
Marshal
Posts: 67435
257
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Bartender
Posts: 3674
151
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Bartender
Posts: 3674
151
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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: 67435
257
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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: 67435
257
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Replace the word "snake" with "danger noodle" in all tiny ads.
Java file APIs (DOC, XLS, PDF, and many more)
https://products.aspose.com/total/java
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!