2
\$\begingroup\$

Problem description:

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?

Least Common Multiple(LCM):

In arithmetic and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integers a and b, usually denoted by lcm, is the smallest positive integer that is divisible by both a and b.

Example:

LCM(6,7,21)

Multiples of 6: 6, 12, 18, 24, 30, 36, 42, 48, 54, 60

Multiples of 7: 7, 14, 21, 28, 35, 42, 56, 63

Multiples of 21: 21, 42, 63

Find the smallest number that is on all of the lists. We have it in bold above.

So LCM(6, 7, 21) is 42

The best solution with Euclid GCD algorithm

Euclid’s GCD algorithm:

1- The smallest positive number that is evenly divided (divided without remainder) by a > set of numbers is called the Least Common Multiple (LCM).

2- All we have to do to solve this problem is find the LCM for the integers {1, 2, 3, 4, > …, 20} using Euclid’s GCD algorithm.

3- After some reflection you might correctly realize that every integer is divisible by > > 1, so 1 can be removed from the list and use 2 through 20 instead.

4- we can eliminate other factors as well.

5- We leave 20 in the calculation but then remove its factors {2, 4, 5, 10}. Any number > > evenly divisible by 20 is also evenly divisible by these factors.

6- 19 is prime and has no factors— it stays.

7- 18 has factors {2, 3, 6, 9} and we already removed 2 but we can remove 3, 6, and 9. 17 > is prime — it stays.

8- We continue this numeric carnage until our original list of {1…20} becomes the much > > smaller {11…20}.

9- In general, all smaller factors of a bigger number in the list can be safely removed > > without changing the LCM.

My Solution

This is my solution for problem 5 of Project Euler using Python:

 def LCM(a, b):  
    '''Return the least common multiple of
       the specified integer arguments
    '''
    return a // gcd(a, b) * b  
N = int(input("The LCM for numbers 1 through "))
N_reduce = reduce(LCM, range(N//2+1, N+1))
print ("The LCM for numbers 1 through" ,N, "is:", N_reduce)
\$\endgroup\$
5
  • \$\begingroup\$ realize this is an algorithm suggestion and not a code review: to find such a number that is the smallest number divisible by all numbers up to N: you could probably generate all the primes up to N and consider their largest power <= N, and then take that product. \$\endgroup\$ May 26 at 18:51
  • \$\begingroup\$ An implementation of this would look like: numpy.prod([exponentiate_as_much_as_possible(x,n) for x in list_of_primes_up_to(n)] ) where you you need to define the methods list_of_primes_up_to and exponentiate_as_much_as_possible. \$\endgroup\$ May 26 at 18:54
  • 3
    \$\begingroup\$ Python 3.9 has an lcm function that takes arbitrarily many arguments. \$\endgroup\$
    – J.G.
    May 26 at 18:58
  • 1
    \$\begingroup\$ @SidharthGhoshal Just take 20**sum(math.floor(1/math.log(p,20))*math.log(p,20) for p in range(2,21) if is_prime(p)). \$\endgroup\$ May 26 at 21:25
  • \$\begingroup\$ ah yea your right the log lets you save a lot of time :) \$\endgroup\$ May 26 at 21:28

1 Answer 1

5
\$\begingroup\$

Straight.

If you
- defined "the range-LCM" in a function with a docsting
- presented imports
 and test cases or usage examples,
- added boundary checks (try N = 0),
I'd call it great.

You might get a reviewer's extra eye-roll throwing in

def largest_power_of_two_not_exceeding(n):
    """ Return the largest power of 2 not exceeding n taken as an integer. """
    n = int(n)
    if n <= 0:
        raise ValueError
    while 0 != n & n-1:
        n &= n-1
    return n

def LCMup2(n):
    """ return the LCM for numbers 1 through n. """
    n = int(n)
    if n <= 1:
        return 1
    return reduce(LCM, range((n//6)*2+1, n+1, 2)
                  ) * largest_power_of_two_not_exceeding(n)
\$\endgroup\$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.