Project Euler #5 using python

Question

The problem statement goes like this:

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?

Here is my solution:

x=2520.0
list=[]
true_list=[11.0, 12.0, 13.0, 14.0, 16.0, 17.0, 18.0, 19.0, 20.0]
b=1
def test():
    for n in true_list:
        z=x/n
        if z%2==0:
            list.append(n)
while b==1:
    test()
    if list==true_list:
        b=2
        print x
    else:
        x=x+20
        list=[]

-> Basically, I have defined an empty list which gets filled up by the function test(). What test() does is it checks if the given number (x in this case) is evenly divisible by values from 11-20. If it is, it places that value(between 11-20) in the empty list.

When test() has run it's course, the program checks whether the list is equal to a predefined true_list which contains all numbers from 11-20. If it is, x is printed. Else, the program continues after incrementing the value of x.

This means that if list is equal to true_list, all the numbers from 11-20 are evenly dividing our number (x), which is what's asked in the problem.

It gives the answer: 465585120.0 after running for a minute or so. This happens to be incorrect. I do not know why that is. I've been trying to solve this for 8+ hours now and am at my wit's end. What is the error?

You do not need to read ahead, but in case you have queries about why I've used certain things in my solution, then I've addressed some of them here:

->I have not used all 20 numbers in true_list to speed up the program as any number evenly divisible by 11-20 is also evenly divisible by 1-20 as well.

->I have used x=x+20 to speed up the program because it is just as valid as x=x+1 or x+2;only, it is faster.

->I have used float values because I am using z=x/n in the function 'test()', and i do not want to chop off the decimal part because doing that would make even float values eligible for the subsequent operation i.e. z%2.

example:

1) with int values:

x=17
n=2
z=x/n=8

Here, z%2==0 is valid which should not be the case since it is not actually valid in mathematics.

2) with float values:

x=17.0
n=2.0
z=x/n=8.5

Here, z%n != 0 which is how it should be.

Answer 1

Like other people have mentioned just find the lcm, but here is a simple way to do it. Just remember lcm(a, b, c) = lcm(a, lcm(b, c)). That's all this is:

from fractions import gcd

print(reduce(lambda a, b: a * b / gcd(a, b), range(1, 21)))

If you want to write your own gcd function, it works like this (https://en.wikipedia.org/wiki/Euclidean_algorithm):

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

Answer 2

First of all as I stated in the comment, why are you trying to do it the brute force way? You could much easier calculate the LCM of the numbers 1 through to 20 in a couple of seconds.

Second of all, your line of code,

if z%2==0:
        list.append(n)

That essentially gives you double the answer you want, as this statement causes you to calculate the LCM*2, as it must divide into an extra factor of 2.

The correct answer is 232792560, which I calculated using a piece of paper and a calculator in <20 seconds. As you can see, the answer you are getting is double that

<-- Edit my previous code was wrong. this one works----->

You can correct this by doing:

x=2520.0
list=[]
true_list=[11.0, 12.0, 13.0, 14.0, 16.0, 17.0, 18.0, 19.0, 20.0]
b=1
def test():
     for n in true_list:
        if x%n==0:
            list.append(n)
while b==1:
    test()
    if list==true_list:
        b=2
        print(x)
    else:
        x=x+20
        list=[]

This is how you can do it by working out the LCM:

allFactors={}
#for each divisor (ignore 1 as it can divide into everything)
for n in range(2,21,1):
    factors={}
    i=2
    while i<=n:
        while n%i==0:
            try:
                factors[i]+=1
            except KeyError:
                factors[i]=1
            n=n/i
        i+=1

    for pf,v in factors.iteritems():
        try:
            if allFactors[pf] < v:
                allFactors[pf]=v
        except KeyError:
            allFactors[pf]=v
lcm=1
for pf,v in allFactors.iteritems():
    lcm=lcm*(int(pf)**v)

print(lcm)

Answer 3

Tht % operator is called the "modulus" operator. In english: a % b is read "a mod b" and means "the remainder of a/b". So 100%3=1 and 12%5=2.

A common way to check divisibility is to check "Does my number modulo my divisor equal 0?". Or in code:

if a%b == 0:
    print("b divides a!")

In your code you want to check if n divides x. You checked:

z=x/n
if z%2==0:
    print("n divides x?") #No not really

z is the quotient of x and n. if z%2==0 can be interpreted as "If z is divisible by 2". So you are asking "Is the quotient of x and n divisible by 2?" Which of course is nowhere close to what you want. Instead simply do

if x%n==0:
    print("n divides x?") # YES!

I suggest you do a couple python tutorials so that you can get the basics down before attempting problems. :)

If you need anymore help let me know. :)

Answer 4

There are many ways to solve this problem. Since you're doing an early exercise from Project Euler, I suppose you'd like to develop an approach that helps you understand the basic Python constructs (as opposed to the "batteries included" approach with gcd and so on).

Here's a basic approach, not efficient in run time or developer time :) but a decent exercise:

found = None
n = 0

while not found:
    n += 1
    for d in xrange(2,21):
        if n % d:
            break
    else:
        found = n

print found

Which goes like this:

• Examine a numerator n starting at 0. (You could actually start at 2520 since we know the answer must be no smaller than the answer to the 1-10 case, but that's a tiny optimization.)

• Loop forever until a solution is found. (In a real-world program, you would probably put in some kind of safety check so this can't run forever, but this is fine for what we're doing.)

• If we haven't found a solution yet, bump the numerator up by one for the next round.

• Divide the numerator by a denominator d in the 2-20 range. If any value of d results in a non-zero remainder, break out of the loop - no point in testing the remaining denominators. (If we wanted to be more efficient, we could use xrange(2,n) since there is no point in dividing by a value greater than the numerator. If efficiency was an extreme concern, like if the range was vastly larger (2-1000 instead of 2-20), we could actually use xrange(2,floor(sqrt(n)) since there is no possibility of no remainder for a divisor great than the square root).

• If we make it all the way through the for loop without breaking out early, the else clause operates, and we record the curent value of the numerator - this is the solution.

This approach is clearly brute force. It's fine as a learning exercise. For larger versions of the same problem, you'd be much better off using Euclid's algorithm and hardware-aware optimizations.

Answer 5

import time
start_time = time.time()

for i in range(2520,10000000000):
    if i % 11 == 0 and\
    i % 12 == 0 and\
    i % 13 == 0 and\
    i % 14 == 0 and\
    i % 15 == 0 and\
    i % 16 == 0 and\
    i % 17 == 0 and\
    i % 18 == 0 and\
    i % 19 == 0 and\
    i % 20 == 0:
        print(i)
        break

print(time.time() - start_time," seconds")

Answer 6

You can find the LCM of the Prime Numbers and the Composite Numbers separately, and then find the LCM of their LCMs. Gets the job done in almost a second! Here's my code:

import time

start_time = time.time()
nums = []
primeNums = []
allNums = []

def findFactors(num):
    factors = []
    for i in range(1, num + 1):
        if num % i == 0:
            if i not in factors:
                factors.append(i)
                x = int(num / i)
                factors.append(x)
            else:
                break
    return factors
 

def isDivisibleByAll(number, numbers):
    isDivisbleBy = []
    for num in numbers:
        if number % num == 0:
            isDivisbleBy.append(num)
    return isDivisbleBy == numbers



for i in range(11, 21):
    nums.append(i)

for num in nums:
    if findFactors(num) == [1, num]:
        primeNums.append(num)
        nums.remove(num)

currentNum = nums[-1]
currentPrimeNum = primeNums[-1]
while isDivisibleByAll(currentNum, nums) == False:
    currentNum = currentNum + nums[-1]
    print(currentNum)

while isDivisibleByAll(currentPrimeNum, primeNums) == False:
    currentPrimeNum = currentPrimeNum + primeNums[-1]
    print(currentPrimeNum)

allNums.append(currentNum)
allNums.append(currentPrimeNum)
currentAllNum = allNums[-1]

while isDivisibleByAll(currentAllNum, nums) == False:
    currentAllNum = currentAllNum + allNums[-1]
    print(currentAllNum)

print(currentNum, currentPrimeNum, currentAllNum)
end_time = time.time()

print("Time taken: ", end_time - start_time)

Answer 7

A more efficient and shorter way of solving this problem will be the code mentioned below. So, as we know from the question that number that is divisible from all numbers between 1 to 10 is 2520. And we know that the factors of x are also the factors of yx. So, we can create a function that checks whether the number is divisible from all the numbers from 11 to 20. And we can make a while loop in which will increment the value of x by 2520 until the value of x is the answer. This method takes less than a second(on my i5 machine and 0.6083979606628418 seconds exactly).

def isdivisiblebyall(n):
    for i in range(11, 21):
        if n % i != 0:
            return False
    return True

no = 2520
while not isdivisiblebyall(no):
    ## if number is not divisible by range of 11 to 20 the value of 'no' will be incremented by 2520       
    no+=2520
print(no)