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

Postby Seanharrs » Mon Dec 01, 2014 3:24 am

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

Postby Mekire » Mon Dec 01, 2014 3:35 am

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]
New Users, Read This
  • Use code tags when posting code.
  • Include any errors with your post (in code tags).
  • Describe your problem; not your chosen solution.
  • Make examples the minimum length to demonstrate your issue.
User avatar
Mekire
 
Posts: 1711
Joined: Thu Feb 07, 2013 11:33 pm
Location: Tucson, Arizona

Re: Smallest multiple problem

Postby Seanharrs » Mon Dec 01, 2014 10:14 am

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

Postby Mekire » Mon Dec 01, 2014 10:50 pm

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,5
9: 3,3
8: 2,2,2
7: 7
6: 2,3
5: 5
4: 2,2
3: 3
2: 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
New Users, Read This
  • Use code tags when posting code.
  • Include any errors with your post (in code tags).
  • Describe your problem; not your chosen solution.
  • Make examples the minimum length to demonstrate your issue.
User avatar
Mekire
 
Posts: 1711
Joined: Thu Feb 07, 2013 11:33 pm
Location: Tucson, Arizona

Re: Smallest multiple problem

Postby Seanharrs » Tue Dec 02, 2014 1:05 am

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

Postby Mekire » Tue Dec 02, 2014 1:46 am

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
New Users, Read This
  • Use code tags when posting code.
  • Include any errors with your post (in code tags).
  • Describe your problem; not your chosen solution.
  • Make examples the minimum length to demonstrate your issue.
User avatar
Mekire
 
Posts: 1711
Joined: Thu Feb 07, 2013 11:33 pm
Location: Tucson, Arizona

Re: Smallest multiple problem

Postby Seanharrs » Thu Dec 11, 2014 12:05 am

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 math

total_factor_list = []

def IsPrime(value):
    for number in range(2,int(math.sqrt(value)+1)):
        if value % number == 0:
            return False
            break
    else: return True

def 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_list

for 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

Postby Mekire » Thu Dec 11, 2014 5:47 am

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

Answer removed for posterity.
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
New Users, Read This
  • Use code tags when posting code.
  • Include any errors with your post (in code tags).
  • Describe your problem; not your chosen solution.
  • Make examples the minimum length to demonstrate your issue.
User avatar
Mekire
 
Posts: 1711
Joined: Thu Feb 07, 2013 11:33 pm
Location: Tucson, Arizona

Re: Smallest multiple problem

Postby Seanharrs » Thu Dec 11, 2014 12:13 pm

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

Postby Mekire » Thu Dec 11, 2014 12:26 pm

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
New Users, Read This
  • Use code tags when posting code.
  • Include any errors with your post (in code tags).
  • Describe your problem; not your chosen solution.
  • Make examples the minimum length to demonstrate your issue.
User avatar
Mekire
 
Posts: 1711
Joined: Thu Feb 07, 2013 11:33 pm
Location: Tucson, Arizona

Re: Smallest multiple problem

Postby micseydel » Thu Dec 11, 2014 7:46 pm

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.
User avatar
micseydel
 
Posts: 3000
Joined: Tue Feb 12, 2013 2:18 am
Location: Mountain View, CA

Re: Smallest multiple problem

Postby Mekire » Thu Dec 11, 2014 7:55 pm

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
New Users, Read This
  • Use code tags when posting code.
  • Include any errors with your post (in code tags).
  • Describe your problem; not your chosen solution.
  • Make examples the minimum length to demonstrate your issue.
User avatar
Mekire
 
Posts: 1711
Joined: Thu Feb 07, 2013 11:33 pm
Location: Tucson, Arizona

Re: Smallest multiple problem

Postby micseydel » Thu Dec 11, 2014 8:25 pm

(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.
User avatar
micseydel
 
Posts: 3000
Joined: Tue Feb 12, 2013 2:18 am
Location: Mountain View, CA

Re: Smallest multiple problem

Postby Mekire » Thu Dec 11, 2014 8:35 pm

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
New Users, Read This
  • Use code tags when posting code.
  • Include any errors with your post (in code tags).
  • Describe your problem; not your chosen solution.
  • Make examples the minimum length to demonstrate your issue.
User avatar
Mekire
 
Posts: 1711
Joined: Thu Feb 07, 2013 11:33 pm
Location: Tucson, Arizona

Re: Smallest multiple problem

Postby micseydel » Thu Dec 11, 2014 11:15 pm

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.
User avatar
micseydel
 
Posts: 3000
Joined: Tue Feb 12, 2013 2:18 am
Location: Mountain View, CA

Re: Smallest multiple problem

Postby Mekire » Fri Dec 12, 2014 8:22 am

Full solutions and explicit answer removed.

Seanharrs, if you are still working on this feel free to continue the discussion.
-Mek
New Users, Read This
  • Use code tags when posting code.
  • Include any errors with your post (in code tags).
  • Describe your problem; not your chosen solution.
  • Make examples the minimum length to demonstrate your issue.
User avatar
Mekire
 
Posts: 1711
Joined: Thu Feb 07, 2013 11:33 pm
Location: Tucson, Arizona


Return to Project Euler

Who is online

Users browsing this forum: No registered users and 1 guest

cron