Tuesday, August 26, 2008

Problem #5: find smallest number evenly divisible by all numbers less than 21

# In order for a number to be evenly divisible by all numbers less than 21,
# the number must be evenly divisible by the product of all primes less than 21. Use brute force to # search for all multiples of this product until one which is evenly divisible
# by the non-primes is found.

# The range 11 to 21 contains within it numbers which are evenly divisible by all of the numbers 1 through 10.
# Therefore testing to make sure that a number is evenly divisible by 11 through 21 is sufficient.

>>> primeprod = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19
>>> def test():
... n = 21
... while (sum(map(lambda i: (n * primeprod) % i,range(11,21) )) > 0):
... n += 1
... return n * primeprod
...
>>> test()
232792560

No comments: