Problem 5 - Smallest Multiples

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?

The most obvious number which would be divisible by 1-20 would be n-factorial (n!).  Obviously this would not be the smallest possible number or the question would be too simple.  What can be eliminated?  If you have 2 x 5 then the number will be divisible by 10 without having to multiply by 10.  This leads to the idea that only the prime factors are necessary.  But what about 12?  The prime factors are 2 and 3, but a number which includes 2 x 3 only will not necessarily be divisible by 12.  Thus you need all the repeated prime factors as well.  So we need to multiply all the prime factors of each number, including repeated factors for the composite to be divisible by each number.

Solution

#!/usr/bin/python

import sys
from primes import factor

def union(a,b):
for each in a:
if a.count(each)>0 and b.count(each)>0:
b.remove(each)
return a + b

if __name__ == '__main__':
#Determines the smallest number divisible by each of a range of numbers
#smaller than just n!
val = int(sys.argv[1])#Bad practice, assumes input is an int
factors = []
for each in range (2,val+1):
factors = union(factors,factor(each))
composite = 1
for each in factors:
composite = composite * each
print (composite)

Prime factors with repeats are [2, 3, 2, 5, 7, 2, 3, 11, 13, 2, 17, 19].

The answer is 232792560.  (n! is 2432902008176640000) 

Approach

I start by defining a "union" function.  In set theory, the union adds two sets together but doesn't repeat the common members of the set.  My approach was to compare the two sets and remove the repeats from one of the sets as I went along.  Then I can simply concatenate the remaining sets without overlap.

Benchmarks

The surprising result here was the poor performance of pypy.  In this case, pypy was slower than either Python 2 or 3.  I even repeated the tests to see if the computer happened to be busy when pypy was running.  With this program, pypy performed almost as slowly as Jython.

Problem #5 Benchmarks

time python primes20.py 2000


151117794877444315...


real 0m0.902s

user 0m0.896s

sys 0m0.004s

time python -O primes20.py 2000


151117794877444315...


real 0m0.945s

user 0m0.928s

sys 0m0.016s

time python3 primes20.py 2000


151117794877444315...


real 0m1.253s

user 0m1.252s

sys 0m0.000s

time python3 -O primes20.py 2000


151117794877444315...


real 0m1.276s

user 0m1.264s

sys 0m0.008s

time pypy primes20.py 2000


151117794877444315...


real 0m2.520s

user 0m2.508s

sys 0m0.004s

time pypy -O primes20.py 2000


151117794877444315...


real 0m2.511s

user 0m2.504s

sys 0m0.004s

time jython primes20.py 2000


151117794877444315...


real 0m3.102s

user 0m5.984s

sys 0m0.104s

Conclusion

This was an interesting twist on the prime factoring problem from earlier.  I had to modify the factoring code I had written not to throw away repeated prime factors.  Pypy had a surprisingly poor performance in this program and the "count" function used in my union subroutine may be implemented poorly in pypy.