CODEWITHSUNDEEP
pythonoptimization
Michael
Michael

Reputation: 81

Solution to Euler Project Task 5: Why does it work?

After some trial and error I have found a solution which works very quickly for the Project Euler Problem 5. (I have found another way which correctly solved the example case (numbers 1-10) but took an eternity to solve the actual Problem.) Here it goes:

def test(n):
    for x in range(2,21):
        if n % x != 0:
            return False
    return True

def thwart(n):
    for x in range(2,21):
        if test(n/x):
            n /= x
            return n
    raise TypeError

num = 1
for x in range(1,21):
    num *= x

while True:
    try:
        num = thwart(num)
    except TypeError:
        break


print(num)

My main problem is understanding why calling thwart(num) repeatedly is enough to result in the correct solution. (I.e. why is it able to find the SMALLEST number and doesnt just spit out any number divisible by the numbers 1-20?) I only had some vague thoughts when programming it and was surprised at how quickly it worked. But now I have trouble figuring out why exactly it even works... The optimized solutions of other people on SO Ive found so far were all talking about prime factors which I can't see how that would fit with my program...? Any help is appreciated! Thanks!

Upvotes: 0

Views: 462

Answers (1)

Isdj
Isdj

Reputation: 1856

Well this isn't really a coding issue but a mathematical issue. If you look at all the numbers from 1-20 as the prime sthat make them you'll get the following: 1, 2,3,2^2,5,2^3,7,2^3....2^2*5. the interesting part here is that once you multiply by the highest exponent of every single factor in these numbers you will get a number that can be divided by each of the numbers between one and twenty. Once you realize that the problem is a simple mathematical one and approach it as such you can use this basic code:

import math
primes = [2]
for n in range(3,21): #get primes between 1 and 20
    for i in primes:
        if n in primes:
            break
        if n%i == 0:
            break
        if i> math.sqrt(n):
            primes.append(n)
            break
s = 1
for i in primes:
    for j in range(10): # no reason for 10, could as well be 5 because 2^5 >20
        if i**j > 20:
            s = s*(i**(j-1))
            break

print s

Additionally, the hint that the number 2520 is the smallest number that can be divided by all numbers should make you understand how 2520 is chosen: I have taken a photo for you: enter image description here As you can caculate, when you take the biggest exponents and multiply them you get the number 2520.

What your solution does your solution basically takes the number which is 1*2*3*4..*20 and tries dividing it by every number between 2 to 20 in such a way that it will still remain relevant. By running it over and over you remove the un-needed numbers from it. early on it will remove all the unnecessary 2's by dividing by 2, returning the number and then being called again and divided by 2 again. Once all the two's have been eliminated it will eliminate all the threes, once all the unnecessary threes will be eliminated it will try dividing by 4 and it will se it wont work, continue to 5, 6, 7... and when it finishes the loop without being able to divide it will raise a TypeError and you will finish your program with the correct number. This is not an efficient way to solve this problem but it will work with small numbers.

Upvotes: 1

Related Questions