CODEWITHSUNDEEP
pythonalgorithmsearch
jalxp
jalxp

Reputation: 447

Understanding a solution to the Euler Project in Python

I'm currently going through the Euler Project. I've started using JavaScript and I've switched to Python yesterday, as I got stuck in a problem that seemed to complex to solve with Javascript but easily solved in Python, and so I've decided to start from the first problem again in python.

I'm at problem 5 which asks me to find the smallest positive number that is evenly divisible by all of the numbers from 1 to 20.

I know how to solve it with paper and pencil and I've already solved using programming, but in a search for optimising it I crossed this solution in the forum of the Euler Project.

It seems elegant and it is fairly fast, ridiculous fast compared to mine, as it takes about 2 seconds to solve the same problem for numbers 1 to 1000, where mine takes several minutes.

I've tried to understand it, but I'm still having difficulty to grasp what it really is doing. Here it is:

i = 1
for k in (range(1, 21)):
    if i % k > 0:
        for j in range(1, 21):
            if (i*j) % k == 0:
                i *= j
                break
print i

It was originally posted by an user named lassevk

Upvotes: 4

Views: 472

Answers (2)

PM 2Ring
PM 2Ring

Reputation: 55489

Bakuriu has answered your question by explaining lassevk's "factorial" algorithm. However, there's a simpler way to do this which is much faster for larger inputs.

Let num be the highest number in the sequence. So for your example num = 20.

Simply multiply all the numbers from 2 to num together and at each step divide by the GCD (Greatest Common Denominator) of the current multiplier and the current product.

In this code, I initialize the product to num, just to make the loop look a bit nicer.

num = 20

p = num
for i in range(2, num):
    # Compute GCD(p, i) using Euclid's algorithm
    # When the loop ends, a is the GCD
    a, b = p, i
    while b:
        a, b = b, a % b
    p *= i // a

print(p)

output

232792560

For small values of num this algorithm takes about the same time as lassevk's algorithm. But when num = 1000 it's about 4 times faster, and when num = 2000 it's about 14 times faster.

As Bakuriu mentions in the comments, the fractions module provides a gcd function. This makes the code somewhat shorter, but it doesn't provide a speedup in my tests.

from fractions import gcd

num = 20

p = num
for i in range(2, num):
    p *= i // gcd(p, i)

print(p)

Here's some Python 2 / Python 3 code that does actual timeit tests comparing the 2 variations of my algorithm. On Python 2.6.6, the version using fractions.gcd is about 10% slower, but on Python 3.6 it can be 5 to 10 times slower! Both tests were conducted on an old 2GHz machine running a Debian-derived Linux.

''' Test the speed of calculating the Least Common Multiple 
    via an inline implementation of Euclid's GCD algorithm
    vs the gcd function from the fractions module

    See http://stackoverflow.com/q/38074440/4014959

    Written by PM 2Ring 2016.06.28
'''

from timeit import Timer
from fractions import gcd

def lcm0(num):
    p = num
    for i in range(2, num):
        a, b = p, i
        while b:
            a, b = b, a % b
        p *= i // a
    return p

def lcm1(num, gcd=gcd):
    p = num
    for i in range(2, num):
        p *= i // gcd(p, i)
    return p

funcs = (lcm0, lcm1)

def time_test(loops, reps):
    ''' Print timing stats for all the functions '''
    for func in funcs:
        fname = func.__name__
        setup = 'from __main__ import num,' + fname
        cmd = fname + '(num)'
        t = Timer(cmd, setup)
        r = t.repeat(reps, loops)
        r.sort()
        print('{0}: {1}'.format(fname, r))

num = 5
loops = 8192
reps = 5
for _ in range(10):
    print('\nnum={0}, loops={1}'.format(num, loops))
    time_test(loops, reps)
    num *= 2
    loops //= 2

Python 2.6 output

num=5, loops=8192
lcm0: [0.055649995803833008, 0.057304859161376953, 0.057752132415771484, 0.060063838958740234, 0.064462900161743164]
lcm1: [0.067559003829956055, 0.068048954010009766, 0.068253040313720703, 0.069074153900146484, 0.084647893905639648]

num=10, loops=4096
lcm0: [0.058645963668823242, 0.059965133666992188, 0.060016870498657227, 0.060331821441650391, 0.067235946655273438]
lcm1: [0.072937965393066406, 0.074002981185913086, 0.074270963668823242, 0.074965953826904297, 0.080986976623535156]

num=20, loops=2048
lcm0: [0.063373088836669922, 0.063961029052734375, 0.064354896545410156, 0.071543216705322266, 0.10234284400939941]
lcm1: [0.079973936080932617, 0.080717802047729492, 0.082272052764892578, 0.086506843566894531, 0.11265397071838379]

num=40, loops=1024
lcm0: [0.077324151992797852, 0.077867984771728516, 0.07857513427734375, 0.087296962738037109, 0.10289192199707031]
lcm1: [0.095077037811279297, 0.095172882080078125, 0.095523834228515625, 0.095964193344116211, 0.10543298721313477]

num=80, loops=512
lcm0: [0.09699702262878418, 0.097161054611206055, 0.09722590446472168, 0.099267005920410156, 0.10546517372131348]
lcm1: [0.1151740550994873, 0.11548399925231934, 0.11627888679504395, 0.11672496795654297, 0.12607502937316895]

num=160, loops=256
lcm0: [0.10686612129211426, 0.10825586318969727, 0.10832309722900391, 0.11523914337158203, 0.11636996269226074]
lcm1: [0.12528896331787109, 0.12630200386047363, 0.12688708305358887, 0.12690496444702148, 0.13400888442993164]

num=320, loops=128
lcm0: [0.12498903274536133, 0.12538790702819824, 0.12554287910461426, 0.12600493431091309, 0.13396120071411133]
lcm1: [0.14431190490722656, 0.14435195922851562, 0.15340209007263184, 0.15408897399902344, 0.159912109375]

num=640, loops=64
lcm0: [0.15442395210266113, 0.15479183197021484, 0.15657520294189453, 0.16451501846313477, 0.16749906539916992]
lcm1: [0.17400288581848145, 0.17454099655151367, 0.18450593948364258, 0.18503093719482422, 0.19588208198547363]

num=1280, loops=32
lcm0: [0.21137905120849609, 0.21206808090209961, 0.21211409568786621, 0.21935296058654785, 0.22051215171813965]
lcm1: [0.23439598083496094, 0.23578977584838867, 0.23717594146728516, 0.24761080741882324, 0.2488548755645752]

num=2560, loops=16
lcm0: [0.34246706962585449, 0.34283804893493652, 0.35072207450866699, 0.35794901847839355, 0.38117814064025879]
lcm1: [0.3587038516998291, 0.36004209518432617, 0.36267900466918945, 0.36284589767456055, 0.37285304069519043]

Python 3.6 output

num=5, loops=8192
lcm0: [0.0527388129994506, 0.05321520800134749, 0.05394392299785977, 0.0540059859995381, 0.06133090399816865]
lcm1: [0.45663526299904333, 0.4585357750002004, 0.45960231899880455, 0.4768777699973725, 0.48710195899911923]

num=10, loops=4096
lcm0: [0.05494695199740818, 0.057305197002278874, 0.058495635999861406, 0.07243769099659403, 0.07494244600093225]
lcm1: [0.5807856120009092, 0.5809524680007598, 0.5971023489983054, 0.6006399979996786, 0.6021203519994742]

num=20, loops=2048
lcm0: [0.06225249999988591, 0.06330173400056083, 0.06348088900267612, 0.0639248730003601, 0.07240132099832408]
lcm1: [0.6462642230035271, 0.6486189150018618, 0.6605903060008131, 0.6669839690002846, 0.7464891349991376]

num=40, loops=1024
lcm0: [0.06812337999872398, 0.06989315700047882, 0.07142737200047122, 0.07237963000079617, 0.07640906400047243]
lcm1: [0.6938937240011, 0.7021358079982747, 0.7238045579979371, 0.7265497620028327, 0.7266306150013406]

num=80, loops=512
lcm0: [0.07672808099960093, 0.07784233300117194, 0.07959756200216361, 0.08742279999933089, 0.09116945599816972]
lcm1: [0.7249167879999732, 0.7272519250000187, 0.7329213439988962, 0.7570086350024212, 0.75942590500199]

num=160, loops=256
lcm0: [0.08417846500015003, 0.08528995099914027, 0.0856771619983192, 0.08571110499906354, 0.09348897000018042]
lcm1: [0.7382230039984279, 0.7425414600002114, 0.7439042109981528, 0.7505959240006632, 0.756812355000875]

num=320, loops=128
lcm0: [0.10246147399811889, 0.10322481399998651, 0.10324400399986189, 0.10347093499876792, 0.11325025699989055]
lcm1: [0.7649764790003246, 0.7903363080004056, 0.7931463940003596, 0.8012050910001562, 0.8284494129984523]

num=640, loops=64
lcm0: [0.13264304200129118, 0.13345745100014028, 0.13389246199949412, 0.14023518899921328, 0.15422578799916664]
lcm1: [0.8085992009982874, 0.8125102049998532, 0.8179558970005019, 0.8299506059993291, 0.9141929620018345]

num=1280, loops=32
lcm0: [0.19097876199884922, 0.19147844200051622, 0.19308012399778818, 0.19317538399991463, 0.20103917100277613]
lcm1: [0.8671656119986437, 0.8713741569990816, 0.8904907689975516, 0.9020749549999891, 0.9131527989993629]

num=2560, loops=16
lcm0: [0.3099351109995041, 0.31015214799845126, 0.3101941059976525, 0.32628724800088094, 0.3492128660000162]
lcm1: [0.9883516860027157, 0.988955139000609, 0.9965159560015309, 1.0160803129983833, 1.0170008439999947]

Upvotes: 3

Bakuriu
Bakuriu

Reputation: 101999

That code is computing the least common multiple of the numbers from 1 to 20 (or whichever other range you use).

It starts from 1, then for each number k in that range it checks if k is a factor of i, and if not (i.e. when i % k > 0) it adds that number as a factor.

However doing i *= k does not produce the least common multiple, because for example when you have i = 2 and k = 6 it's enough to multiply i by 3 to have i % 6 == 0, so the inner loop finds the least number j such that i*j has k as a factor.

In the end every number k in the range is such that i % k == 0 and we always added the minimal factors in order to do so, thus we computed the least common multiple.

Maybe showing exactly how the values change can help understanding the process:

i = 1
k = 1
i % k == 0  -> next loop

i = 1
k = 2
i % k == 1 > 0
   j = 1
   if (i*j) % k == 1 -> next inner loop
   j = 2
   if (i*j) % k == 0
      i *= j
i = 2
k = 3
i % k == 2 > 0
    j = 1
    if (i*j) % k == 2 -> next inner loop
    j = 2
    if (i*j) % k == 4 % 3 == 1 -> next inner loop
    j = 3
    if (i*j) % k == 6 % 3 == 0
        i *= j
i = 6
k = 4
i % k == 2 > 0
    j = 1
    if (i*j) % k == 6 % k == 2 -> next inner loop
    j = 2
    if (i*j) % k == 12 % k == 0
        i *= j
i = 12
k = 5
i % k == 2 > 0
    j = 1
    if (i*j) % k == 12 % k == 2 -> next inner loop
    j = 2
    if (i*j) % k == 24 % k == 4 -> next inner loop
    j = 3
    if (i*j) % k == 36 % k == 1 -> next inner loop
    j = 4
    if (i*j) % k == 48 % k == 3 -> next inner loop
    j = 5
    if (i*j) % k == 60 %k == 0
       i *= j
i = 60
...

You can immediately notice a few things:

  • The range(1, 21) can be safely changed to range(2, 21) since the 1s never do anything
  • Everytime k is a prime number the inner loop ends when j=k and will end up in i *= k. That's expected since when k is a prime it has no factors and so there's no option for a smaller number j that would make i a multiple of k.
  • In other casesthe number i is multiplied by a number j < k so that all factors of k are now in i.

Upvotes: 6

Related Questions