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

Solution 1:

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.

Solution 2:

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]