Nov
21
Project Euler: Least Common Multiple
Filed Under hisabati, project euler by Mucheru
This is the second of a series of problems form Project Euler that I’ve worked on as part of my “Learn Python” project. In Problem 5, the question is:
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 number that is evenly divisible by all of the numbers from 1 to 20?
In mathematical terms, this is asking for the Least Common Multiple of the numbers in the range from 1 to 20. The algorithm here is an implementation of the “LCM by table” method described in the linked Wikipedia article.
1: def find_lcm_of_range(n): 2: assert (0 < n) 3: residues = range(1, n+1) 4: divisor = 2 5: lcm_factors = [] 6: found_factor = False 7: while True: 8: #print residues 9: found_factor = False 10: highest_power = 0 11: for index, item in enumerate(residues): 12: if(item < 2): 13: continue 14: elif((item % divisor) == 0): 15: found_factor = True 16: # extract all powers of the divisor 17: curr_power = 0 18: while ((residues[index] % divisor) == 0): 19: residues[index] = residues[index] / divisor 20: curr_power += 1 21: if(curr_power > highest_power): 22: highest_power = curr_power 23: if(found_factor): 24: highest_value = pow(divisor, highest_power) 25: lcm_factors.append(highest_value) 26: # remove 1s from the list 27: residues[:] = [x for x in residues if (x != 1)] 28: if(divisor < n): 29: if(divisor == 2): 30: divisor += 1 31: else: 32: divisor += 2 33: else: 34: break 35: print "LCM factors: ", lcm_factors 36: # multiply out all factors 37: lcm = 1 38: for f in lcm_factors: 39: lcm *= f 40: 41: return lcm
The algorithm finds the lcm of the numbers in range (1,n) by accumulating factors in a list. This is similar to the Prime Factors code from a previous post – we try all numbers starting at 2 and check if we have a factor for any number in the list. Once we find a factor, we figure out the highest exponent of the divisor that divides a number on the list (lines 18 – 21). The value of the divisor to its maximal power is taken as a factor and added to our list. We also reduce the values of numbers in the range as we find factors, keeping computation costs low. At the end of an iteration involving a particular divisor, we remove all numbers in the residues list whose values are now 1 (i.e. we’ve found all their factors so they no longer need to be considered in future iterations) [line 27]. At the end, when we have the list of factors, we multiply them out to give the lcm.
To get a better idea of how this works, you can uncomment line 8 and observe the list of residues at each iteration. The algorithm is exponential but runs surprisingly fast – the lcm for numbers between 1 and 20 is determined in 1 millisecond whereas the lcm for the range 1-10,000 is found in 2.749 seconds. The latter number is pretty big:
5793339670287642968692270879166240098634860297998518825393
1383511489793001457731823088325981761829221665744176794023
4070565594914024678915773283267630212994668431184746378526
5683193852154947234797107306816167930170547268523692646338
7338495220571064420250677315000599457941340849496227227628
9264937710182648218422303703496401025734928814243173061895
6946710149583460199127003991878092450649540579792376220536
0790652073159333382795670426041033566699342449050309786673
6816704833691556895675542398988790397441473339719882580610
4209097047672929348451307244361479576687872632579585485539
4491290821167148355514749149683707585283381546153703014210
4424703181805119066911083251464942193434988993829180182465
8660982766747032916601211087498110480041574152758628002673
7848182673635645872230905234515169611121042867043956727839
3141987286262740666554678461833435991947615903686084725783
9816974011148592404698687071488389428584139496462740809416
1019230662749101230783008668676907211199488107523306410531
7720454528539577068732384668299886498221575571035032835633
9828177546491190478915951590098740157467888594249390760474
0891878907698622679570965569483682456042918236444719794534
4111719076063360905340293493513002761418925297954487518263
9439915321618327038573779574877050861209637476533357823797
3395907265484337502903901947799663388329849198045756207969
5900556866076781952063672736006329094170242247547504287112
3691791366341921592583094403553984874916317848961422754665
6090790164108195741048033614368495827231281392190063051315
2480701922634008013150956085121395107314697323113138989957
4604056343312142777607148265590434653828101066847673113241
5829844984600414136781404774213539507859790229205890271721
6003091699268061218717500081637387739116100095086091496653
3257963276739707887799692658133741935183475437041100868613
6818501030862345505385357198060894463821342298717851567836
5629843448064696137680247649673729796551790660743981982468
0510457613447482301648884281807704166167609839937880971389
4284994865370648616800689225595431967181072865363430005250
8407678909121645307057049368379155848566069606873473723913
3925443211908593217554139295434368471669516262927122978928
9404752104218596977036941910521266321726821940533986384237
9944037806183013790993479752601227241944542750888255870444
8820896569037370690405692650932469630881097433179011945643
8147168585552011926921912167450509941646104076818762060881
9039696164316463849858959442312185056205470938742411697592
0545014547874611279689862671196632096505721221995856733885
1356631739947125096250452942497473309299907612330435197454
3927886373592531163086850070142496054926595244291345133441
3751710187227942820228595165285635482723076593150280534169
6470148698002737700823078904634554776750169178259216255903
9688655887498277898889501724524554482488337123098356575613
6923315797740557936529367194313141203410990194489281924500
1657496671822581274180596255340507054499934060282320458240
7224542099335697359400328591099346868782741108643949244635
7385201533842888196184329208356603466981461961260663828361
5766521897504566616272305253931938372830446073384019299355
3208643427340195176336623467904229159519548226451370914941
2610039010451098737336632861536305604213744080822597360080
9566845718073791616927784260557845021823094999326904373592
3194075166608967643880922625103691821535592854460749909418
6351624722653265314219855184006363198942877679953328621546
4660644129411503287306838551341184739976807097763115368031
7486460437805490551434282972306780537384530102349490082537
6935520720816799920335315752466601702980367961213182474079
4652592875662818479980117505768541194835524231818203552256
4267527304551157522808370997632376063481928679364579939708
6644626401581281917999413864229510887238170918193709229039
2544335464025324661284746003660247161196698209062164637264
1149307664444734710834082003296620590642018967211650156874
8772830085450178081015584483748979814430994299909177446640
6270065305461848242329380636274754660519867343112275861821
2935011121014348682253780418138368087454176062891599042941
6594140869292225060112780497196234280792774339003039504826
3275616935165347620718001157478088456439083590834464409622
7816937908832895970240439825842200692241702358634587453443
6568408211443036286744619360107556980365077301802670000381
2298460527976219100308016537538008597751565631582745643139
434508332515569645426771932483266712323523039014220800000L