## Smallest multiple problem

For questions about problems on the Project Euler web site. No spoilers. Please include the question number in the subject line of your post.

### Smallest multiple problem

So I'm trying to solve problem 5 (Project Euler), and I'm not sure if I have implemented the code incorrectly somehow, or if the number is just so high that I cannot reach it before I close the program (I did wait a fair amount of time, going into the 10's of thousands), and so I am asking here. Of course, there is likely a much better way to do it, but this is what I came up with first:
Mekire: Removed to avoid spoiling for others.

I used an infinite loop on the outside because I think that is the only way to "restart" the for loop, i.e. have it set value to be 1 again, so that it tests from 1 upwards for a new number, not from 5 upwards (for example). It never prints a number, however, so I wanted to ask if it's because my program is faulty in some way or whether the number is just too high for it to be reached before I stop the shell from running.

Oh, the question is "what is the smallest positive number that is *evenly* divisible by all the numbers from 1-20.". I started with the number '2520' because that is the smallest number divisible by all numbers from 1-10 (therefore, no number smaller than it could possibly be correct for 1-20).

EDIT: I left the program running for 5 minutes or so and got the result: Answer removed (Project Euler says I'm correct). So I guess now I can just use this thread for help as to how to 'improve' the solution, such as making it faster or less resource intensive (for example)?
Seanharrs

Posts: 15
Joined: Mon Oct 06, 2014 3:41 am

### Re: Smallest multiple problem

It seems you are trying to just brute force the problem, which with a lot of project Euler will just not work (very much by design).

I haven't solved this problem in a long time, but I'm fairly sure your first step is to find the prime factors of the numbers 1-20.
The product of all the prime factors should be the number you are looking for (I think).

-Mek

Edit:
Code: Select all
`[2**4, 3**2, 5, 7, 11, 13, 17, 19]`
• Use code tags when posting code.
• Include any errors with your post (in code tags).
• Make examples the minimum length to demonstrate your issue.

Mekire

Posts: 1711
Joined: Thu Feb 07, 2013 11:33 pm
Location: Tucson, Arizona

### Re: Smallest multiple problem

I don't understand how you got the above list of numbers. The prime factors for 4 are 2 and 2, no? Then 18 is 3, 3, 2, and 14 is 7 and 2, and 10 is 5 and 2 but then we get more than 4 2's, so I get a different list to what you got...
Seanharrs

Posts: 15
Joined: Mon Oct 06, 2014 3:41 am

### Re: Smallest multiple problem

As I said, it had been a long time since I looked at the problem. It isn't simply prime factors, it is the product of the highest power of every prime factor.

So if you do the numbers, 1-10:
Code: Select all
`10: 2,59: 3,38: 2,2,27: 76: 2,35: 54: 2,23: 32: 2`
You can drop all twos except 2**3; and drop all 3s except 3**2; and drop a 5.
The result then being:
Code: Select all
`[2**3, 3**2, 5, 7]`
With a product of: 2520 (the least common multiple of 1-10).

Think about 16 (2**4). 16 (and any multiple of it) is divisible by all lower powers of 2 below it; so if you include 2**4, including 2**3, 2**2, and 2 is redundant.
If you do this programmatically with python the LCM of 1-20 can be calculated in a couple of micro-seconds.

-Mek
• Use code tags when posting code.
• Include any errors with your post (in code tags).
• Make examples the minimum length to demonstrate your issue.

Mekire

Posts: 1711
Joined: Thu Feb 07, 2013 11:33 pm
Location: Tucson, Arizona

### Re: Smallest multiple problem

Oh, okay, that makes sense now. Thank you. I never would have thought that you would be able to obtain an answer from such a method, seems like a pure luck method (even though it works for each case, so I know now it isn't) to me.
Seanharrs

Posts: 15
Joined: Mon Oct 06, 2014 3:41 am

### Re: Smallest multiple problem

Project Euler problems often have fundamental mathematical concepts at their core.
In this case, the program required knowledge of Least Common Multiples, and prime factorization.
As said, especially in more advanced problems, the initial brute force approach will often just take an enormous amount of time to crunch. Finding the underlying concept to an Euler problem is the key to solving it.

http://en.wikipedia.org/wiki/Least_common_multiple
http://en.wikipedia.org/wiki/Least_comm ... torization

-Mek
• Use code tags when posting code.
• Include any errors with your post (in code tags).
• Make examples the minimum length to demonstrate your issue.

Mekire

Posts: 1711
Joined: Thu Feb 07, 2013 11:33 pm
Location: Tucson, Arizona

### Re: Smallest multiple problem

Thanks for your previous help. I understand how this works now, but I am re-posting here because I am unsure how to delete "useless" items from the overall list now, because items are int and others are list. My current code, which gets the prime factors of each number from 1-20, is:

Code: Select all
`import mathtotal_factor_list = []def IsPrime(value):    for number in range(2,int(math.sqrt(value)+1)):        if value % number == 0:            return False            break    else: return Truedef GetFactors(integer):    number_factor_list = []    while not IsPrime(integer):        for value in range(2,int(math.sqrt(integer)+1)):            if integer % value == 0:                number_factor_list.append(value)                integer /= value                break    number_factor_list.append(integer)    total_factor_list.append(number_factor_list)    return total_factor_listfor number in range(1,21):    if IsPrime(number):        total_factor_list.append(number)    else:        GetFactors(number)print total_factor_list`

When total_factor_list is printed, I have:
Code: Select all
`[1, 2, 3, [2, 2], 5, [2, 3], 7, [2, 2, 2], [3, 3], [2, 5], 11, [2, 2, 3], 13, [2, 7], [3, 5], [2, 2, 2, 2], 17, [2, 3, 3], 19, [2, 2, 5]]`

Which is correct. But I am unsure how to delete the 2, 3, [2,2], [2,3], [2,2,2], etc. because some items are of type 'int', and others are type 'list'. I've tried multiple ways, but can only delete some, and sometimes I'm not even sure why it's deleting some of the things it does.

If you're against posting whole solutions that's fine, at least give me a start. I tried something like:

Code: Select all
`for factor in total_factor_list:    if factor in total_factor_list[total_factor_list.index(factor):]:        total_factor_list.remove(total_factor_list.index(factor))`

But this doesn't work properly because lists are involved. I could convert all lists into multiple integers (e.g. [2,2] becomes 2,2 (two separate items in the overall list), but then I am not sure how to ensure I have four 2's at the end, which I need. And I can't hardcode that, because then I cannot alter the program to go to higher/lower values.
Seanharrs

Posts: 15
Joined: Mon Oct 06, 2014 3:41 am

### Re: Smallest multiple problem

Instead of just appending to a list, make a dictionary that keeps track of how many times each factor has appeared.

Not the most elegant solution to this problem in the world, but it is surprisingly fast. Examine the second and third function and see if you can get the idea.
-Mek
• Use code tags when posting code.
• Include any errors with your post (in code tags).
• Make examples the minimum length to demonstrate your issue.

Mekire

Posts: 1711
Joined: Thu Feb 07, 2013 11:33 pm
Location: Tucson, Arizona

### Re: Smallest multiple problem

I don't entirely understand what's going on in the functions, but I'll run through the program using the Python Shell's Debugger so I can understand what happens at each step a bit better. I've not really used dictionaries before (all I have learnt came from university, and it was an overview course so we didn't look at dictionaries and tuples and generators, etc.), so I'll need to practice up on those a bit more to understand their methods and syntax I guess. I'll try and come up with an alternate method when I have a bit more knowledge, I guess. Thanks again Mekire for your patience in this thread.

P.S. I'm not even going to bother trying to understand what's written at the bottom Haha.
Seanharrs

Posts: 15
Joined: Mon Oct 06, 2014 3:41 am

### Re: Smallest multiple problem

The bottom is just running the code and timing it with a builtin module called timeit.

This line on the other hand:
Code: Select all
`if __name__ == '__main__':`
You better look up. It's important.

-Mek
• Use code tags when posting code.
• Include any errors with your post (in code tags).
• Make examples the minimum length to demonstrate your issue.

Mekire

Posts: 1711
Joined: Thu Feb 07, 2013 11:33 pm
Location: Tucson, Arizona

### Re: Smallest multiple problem

Mekire wrote:Spoiler below

Um? No spoilers?
Due to the reasons discussed here we will be moving to python-forum.io on October 1, 2016.

This forum will be locked down and no one will be able to post/edit/create threads, etc. here from thereafter. Please create an account at the new site to continue discussion.

micseydel

Posts: 3000
Joined: Tue Feb 12, 2013 2:18 am
Location: Mountain View, CA

### Re: Smallest multiple problem

Feel free to nuke it if you so desire.
In this case he had already solved the problem, albeit with an extremely suboptimal approach.
If you want to remove it so that others can't get a free solution in the future though, we can.

-Mek
• Use code tags when posting code.
• Include any errors with your post (in code tags).
• Make examples the minimum length to demonstrate your issue.

Mekire

Posts: 1711
Joined: Thu Feb 07, 2013 11:33 pm
Location: Tucson, Arizona

### Re: Smallest multiple problem

(Moved to PE forum.)

If he has a spoiler than that should be removed to. Or we should remove the rule if we're not going to enforce it.
Due to the reasons discussed here we will be moving to python-forum.io on October 1, 2016.

This forum will be locked down and no one will be able to post/edit/create threads, etc. here from thereafter. Please create an account at the new site to continue discussion.

micseydel

Posts: 3000
Joined: Tue Feb 12, 2013 2:18 am
Location: Mountain View, CA

### Re: Smallest multiple problem

Well this sub really doesn't get used at all.
It isn't like we get flooded with Euler problems these days, and solutions to the lower ones are all over the place.
I personally think we should discuss problems as we would normally; especially with something as simple as an LCM.

But either way it doesn't really matter to me.

-Mek
• Use code tags when posting code.
• Include any errors with your post (in code tags).
• Make examples the minimum length to demonstrate your issue.

Mekire

Posts: 1711
Joined: Thu Feb 07, 2013 11:33 pm
Location: Tucson, Arizona

### Re: Smallest multiple problem

The subforum not being used much doesn't seem to make a difference to me. All I want is consistency within our rules. Do we want to whitelist some problems as spoilers being ok?

KDoiron isn't around anymore but he didn't want us to become a repository of solutions even if there are others that exist elsewhere. I'd rather we help people find a solution themselves, and any spoilers can reside in the PE forum that isn't accessible to people who haven't solved the problem.

So my preference would be to delete the spoilers here, and if you really want to share a solution, you could do it safely in the PE forum for the question, and point the OP toward it if you wanted. If we had better forum software I'd be down for a hidden part of your post that is accessible only by previous solvers but that's not an option right now.
Due to the reasons discussed here we will be moving to python-forum.io on October 1, 2016.

This forum will be locked down and no one will be able to post/edit/create threads, etc. here from thereafter. Please create an account at the new site to continue discussion.

micseydel

Posts: 3000
Joined: Tue Feb 12, 2013 2:18 am
Location: Mountain View, CA

### Re: Smallest multiple problem

Full solutions and explicit answer removed.

Seanharrs, if you are still working on this feel free to continue the discussion.
-Mek
• Use code tags when posting code.
• Include any errors with your post (in code tags).
• Make examples the minimum length to demonstrate your issue.

Mekire

Posts: 1711
Joined: Thu Feb 07, 2013 11:33 pm
Location: Tucson, Arizona