Euler 3 Just Got Lisped Up

“What is the largest prime factor of the number 600851475143?”

One thing I’ve learned so far from the euler stuff is that if seems too hard, I’m doin’ it rong. What I initially did is go from 2, tried to find any prime number that is a factor 60085…3, and keep updating the highest found. This was silly. In reality, I needed to start from 60085…3, find the largest factor of it, and keep going if it’s not a prime number. After all, the highest possible factor can’t be higher than 60095..3/2, prime or not. If that fails, then increase the divisor by one, and check if the other number is a prime.

600851475143 / n = x where n 2 -> ?
600851475143 / 2 = x
600851475143 / 3 = x
600851475143 / 4 = x

This meant I needed two parts, one to roll through all possible values of n until x was a prime.

(defun lowest-prime-divisor (start &optional (current 2))
  (if (and (= 0 (mod start current)) (is-prime-number (/ start current)))
    (/ start current)
    (lowest-prime-divisor start (+ current 1))))

As I wrote before, this is taking the original number (6800??adf…3), and start with dividing it by 2. What ever the remainder is, take it and check if it’s a prime. If so, return that. If not, divide by 3. I have no clue why I named it lowest-prime-number. Probably a case where my limitless intellect is proving that I am not nearly smart enough to understand it.

Here is the brute force prime number check. Essentially start a 2, use mod, and increase the iteration. This is done until either something mod iteration is 0, or the iteration is the same as the number being checked. It has a special kind of ugliness, and inefficiency.

(defun is-prime-number (start &optional (currentDivisor 2))
  (if (= start currentDivisor)
      T
      (if (= 0 (mod start currentDivisor))
          nil
          (is-prime-number start (+ currentDivisor 1)))))

And I don’t have a macro this time. Mostly because I’m on 8 currently, and this is only the third post.

Common Lisp and How It Conquered the Euler Problem 2

So yesterday I took down Euler problem 1. Yeah, I’m just that good. In fact, only something like 250k of the entire world population (7 billion or so) got it right. That’s not even including people like Santa Clause. Elite level, here I am.

I would tell you what the second question asks, but that would mean I read it correctly the first time around. What I read was something like “Add up all even Fibonacci numbers up to the four millionth Fibonacci number.” Cake! Right off the bat I was going to do this tail recursive style, ’cause that’s the way an elite programmer like me does it. Now, I know I’d seen the cannon version of how to get the Nth Fibonacci number, but I chose to blaze some trails. (And I forgot what the cannon version was) The idea was instead of doing that whole (n – 1) and (n – 2) nonsense.

So to start there is 0 and 1. Then 1 and 1. Then 1 and 2. Then 2 and 3. Every iteration has a sort of shift where the right parameter becomes the left, and the new right was the old left + right. Sounds like a really easy recursion problem. Only thing missing is an iteration used to find the Nth Fibonacci. That will just be reduced by one every iteration until it hits 0.  Once that happens, the last number is returned.

  (defun fib (left right iteration) 
    (if (= 0 iteration) 
      left 
      (fib right (+ right left) (- iteration 1))))

And it would be called by:

  (fib 1 0 37)

Which, by the way, is 24157817.

So now I have a way to get the Nth, it’s time to add up all evens up to the 4 millionth Fibonacci number. Oh yeah.

 ;;This is needed to add the current Fibonacci number to the sum if it's even
  (defun adjust-sum(sum currentNumber)
    (if (evenp currentNumber) (+ sum currentNumber) sum))

 ;;And this is an update that keeps adding up the even Fibonacci numbers and stuff.
 (defun fibo (left right iteration sum)
   (if (= 0  iteration)
     sum
     (fibo right (+ right left)  (- iteration 1) (adjust-sum sum left))))

Now the site gave me the first 10 numbers: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89. So adding up the even numbers in that list gets… eh… Oh! 44. Well time to see if the above bit of lisp works.

(fibo 0 1 10 0) ;;44

Yay. Well that’s easy. Next 4 million.

(fibo 0 1 10 4000000)





15 minutes later


Now the fun part about that solution is that I will never get a stack overflow. Bad part is that I have no idea how long it would take to add up 0 -> 4 millionth Fibonacci number. So at that point I was thinking I would have to somehow create a tree structure of parallel operations. Start with 4000000 / 2 and find the total in those two. To do that, I would halve those, and then halve again… ect, and sum up everything while traveling back up the tree. Or is it down? Whatever. I couldn’t believe how *(@#ing hard this second problem was. That was when I re-read the problem. Turns out I was supposed to add up every even up to 4 million. So the Fibonacci number closest to 4 million. Not the 4 millionth Fibonacci number. Then it seemed to be back to what I would expect for the second problem.

  (defun fibos (left right sum)
    (let ((adjustment (adjust-sum sum left)))
      (if (< right 4000000)
        (fibos right (+ right left) adjustment)
        adjustment)))

Basically every number found that is even, add it to the sum. That is until the right number is greater than 4 million. (Which would make the left number too high on the next iteration) At that point, add the left (If even), and return the sum. And guess what? It worked.

Now this wouldn’t be a lisp post if I didn’t add in some macro for over kill. After I failed to add up all even numbers up to the 4 millionth Fibonacci, I thought that maybe if I put them all in a list, and then added them up: magic would happen. Magic did happen, I killed the heap. I mean if adding two really big numbers was killing lisp, having a bunch of lists full of large numbers being added together should be fine, right? Make perfect sense. HOWEVER, one interesting thing did come from that: A macro. Here’s the original function for the array adding, pre massive tree idea. This just puts all into a list. I didn’t even get to the adding part.

  (defun fibl (left right iteration numbers)
    (if (= 0  iteration)
      numbers
      (fibl right (+ right left)  (- iteration 1) (if (evenp left) (append numbers (list left)) numbers))))

Well I figured instead of just having a method call fibl to add all the numbers, just make a macro that would call fibl to get the list, then run an eval to add them all together. Why settle for simple, when a macro can make it way more complex. Although in my defense, when using macroexpand-1, I get to see the whole list of numbers before they are added.

  (defmacro fibl-bibl (a b c)
    `(eval (+ ,@(fibl a b c '()))))

With expansion:

  (macroexpand-1 '(fibl-bibl 1 2 100))

I got:

(EVAL
 (+ 2 8 34 144 610 2584 10946 46368 196418 832040 3524578 14930352 63245986
    267914296 1134903170 4807526976 20365011074 86267571272 365435296162
    1548008755920 6557470319842 27777890035288 117669030460994 498454011879264
    2111485077978050 8944394323791464 37889062373143906 160500643816367088
    679891637638612258 2880067194370816120 12200160415121876738
    51680708854858323072 218922995834555169026))

A list of Fibblenibble numbers. That was a lot for just one problem. Oh and for fun, here is the original golden function when adding all evens up to the 100000th number.

210134635149757719315950255064695756588695785131611725165235804359916786572863811331696923863350683048126683085142916459332058114941110766686678707363430726110258898018010828814604839776532825126899915724751316525031035954444949232180979996323811805415925251187493235192974551234331062086534136805786177582386212877375117620623437303742552667696171935177393500985079313725745197179088900620541323223091163646241337468114147700211796183133392908337016188476611677040521713333083986943297965232600862288054724778303558352715084544785730244200683974569728324692232314945603947032229789125399896443936969649280509005067194130014191019906960046358175606148496241991973176681118479994029681227415747795999136572033230343019483738392331535711939926003061047418009792141434744705747844399720376659431081235302156392379430858982251915271749438857727345183251386080769599191998495894067199070972184404625055740909899201130583052303659016146177688301879324924998727010234689589652398161124306953007370681861516962672162830424285078239244552669896314483208891095985314333206792218890143817628106119467673305141311764463161724418159970207964328041486429941060257374678419608037203240907685335494485955430304182439776700248640864773279209804130107815203595074666252436894851980635269999972922994229316228817842523295140034108168011150940569150560436362656065740205309181537316695861739407779209971100218486739728373214686579514950816073845513802397657286856676531046668500663748143833301204618907223112395593062138681442360586312693005182921398053824358166567360026424432237244893361109213993070525649845617875919021011326149817574499600796480668479299614246073642029837591242910304168518758793534817372587124224044754480947765539973773666516619403727561494805255585195903740965473156483826329176162700309900774052207962720926430456721705920419295629157748986005586754127144175997102510354485314565966185296805934985438370260768324842285912332030181915108852664242572126624872731549974878879155226050609755790730339295164790392508584467954066309414696582480695424863249711810312524443221741471814759761642591927546176444474249387569051116004412758001682082295704641159441424272689037737589652445380001275607073531853320125093627397613857071252531071586306675618824599663218410951341233889913902500614833884066908233398699567328935275637267197347202298538859593997703697713802957906539642606370828416414147810799658734529479109231110665556187176418548476384868832963210485071523013131404475587489246037723764622677791224251854058483148068071872834278461455417690222393581989010116042011804685461127070238504845641024580288388683486518326824941746182412364178381937706647179795904877648631685848537286241780452140116126363436113503233969227750339200404403271385824016244124590198080724853578464251549859567798872700339233328199123293182072219835862411700901312198089085324168018585880297699588552274806528231438637456543897771694662159568469764070690619750679540394911382924413162540130926242538137809271974228796966756307877297146883981035775477003257465643278222185432771988583677109052727922684880948307777590208566505337135736871655930805583340006737117885774782210441102763126560381512377013745064883258066541654232929359000450636792943019366164523868429521535469074034946258620181476030719978796857587893526752267013243359357704275788464983521293250604674874972904203574191004579440328676946195685201217530982857554917402649304912755548774644266805777262869652122134839557928817095037660048000300983583156138998227663706230691350142110382572156360795370566704001744520381292459642329429020643458193257739821488816256213262167854518663999704530401445716210010813920156878484439665966358964075682592874240824755027657575343644672852034918243245446316952102752735068725543566246724899970431874885063985801405302823267128880668375592237892911980938256404473624342563948754159675405491888599705183505124206483194289438402679806151662578956199048579482571884905313726646964715915902481919126863415141459926644007647035716861604316055203082217917719133243245860921910514675871227687275287904537667794101260280122689215877177692659971254050108571563988273142096434551936972388013889468525869265313987202386124454335737401442779149708893730357123453230525472812601106412916497512782130114995296452342079789558396075642943016414842497563577672325443914816380590195336781663311206154684378687331712606758533984749064480897205038658440932747251187171925615932041948405830247876193685033702230130932424171267174008628519670296361919459610294515999453092599210519154108208264305103436934737238114113533578104044878364038805466064185038826829618126068508780524600524532396321751115668117851883641022819256371424253155374856570004090384898320933546043135375879145452469151210230166702462732829179222147648168544388272632793803303122346891630514391171335250309356292095466008088199378325674346357700504254182363476775695790837935514439560228061226354773830823231721171817925342307215071868982885889541475143724812654735837013547431202790870732505233531398825890187747794954413346873325089496704707900879389656488821344562140479083399346311640681278838002510254530994419956170461984422108213527538906614386259246674521029974783963230282955512888041250709653893598294048112482622910077840761873334973198377454635795213978371736970235694420172850166988573277784747359753551788762540593326628753294639877707665080404530665383601082885770093671822607628346295993226276841728411776535299081065042752452287473106250279305015609577612263706122258615273003824478437201890581856024447124072122869194061082349696061506541146882810975740599373902964150305958292734863572211538327420362893741030060918112493319686075487376326876983867697925992238478866107122304899040508647431253037732782392528717428733688046182831729132774784725040247331280034150165198489598636448927438644934585011667241905557181221099862417418669690895727041918337056896533627181530365929210694465523664873064732165456703307561043626687310115887431899952005701851752064305634513236819669863690896215787275155359301452323258424483249574247791813760513919904799453367672688587351772118267772287356372396160702030198472586422560132252593869683043910370213989746468578566913116289689458398973054296570754784174314808120093787794706506020368933585621886459424376006095645540516337457704802032437712446376726098103705121264595688347218451606605177546669112269977919387895237275587948254401392746864976823592328331881845950067569933987319425473420264227457037823974302822896032471480891487098097305485181465226545673335811922107441009472479075151488317678985169434996018295266202368656027482782167093131138853719482321158978983728897817066141539245801340677422731168147452795744266894019921848745903566804479001006155549580727806394856431476422910453397609716348844849887606352116821462340936742691737144466549028005167896114433828324010330732622222173088700586063219910281155121562420408416384427387652289708818083295152927629068305962450984958140124822704302666063753142031169908652700969937967560785599365331808920514154488957336620911995116533849705595812479209241064508087094244537228712955164255338447272814693237786944972817747162992695126655916021555696910288300621111158764772032998163892743242649237104158980565714542878020285536410647945320115296595370947305512788680378113862524317461361104377898340233653765440250113911194734180701435331951303967217221734314727819805156190906849061439718539268419425329956751349030666546704748089678154731359992660080659657693255422636089340707029328611600500872957698125089435060190254908205989007442684601204354306128681811653225112598061698749618332036772594552243139973109440779102119329001540055344504861934352772627605541498252958062267170758050417721581345853192205827455124849694038122424540952113490208003720269622508701810492374185547454640205838677373971255884836178808659477383029849240657152245346957236828601255626545670117515828979636355357010237289609065632163399008313810676989365934339225832320452186973067052917093306509725760336403569400860087523267258884178358312322554843735839611544507427486582585771335956735088950482325185692785684530748994744497094422864864143797723195179954757435410302928616925707931383712057489757701207799996919323616506079812268859145047501530863469235679989559672702217770826479903005058658549708092818077513289356168467776629816164319215465270457262582602493827064947268566585714868977533411971593664133914653747763343228160437188427004775818365599277926000143684854386339411112041507140914711404454127284070064271895340157513116501567771785420553078419525971929246516298920300129180663727392570824792779311312612668016083738349081021091366969260329686954844262639357270307133632913108878682752416413368429863460872892282596218097575256714738390692771125065632039823487232487934816134008137046656159997657704350599552440619655586356167648218951021071029187849742480638340944718834853662025553240185857312911444283841660542935130176492325518542248626959742553708412118992866903849589661592444892326674773575698043679715574196616158748568450383757530991595937631481647034939033650291447159318070426821677259125681086668323496716293016795080464641752217809778007597626795191933481646571059765954320801474588409330216905430892844682932638129957978823154452874202850621093728059168457837220013599499692971762130344115615325995269667250785121954660127785415291473924408415171614813511358905517066018649343142785307691809627637425698725735864130408323368656111884389482769754811960576769415909056295045296535188276050861691547829255173581117186073547261975619158894909018402883026854086197997246977225550369748004330315700368486340493017657401401781958962964775701777837545067311278282560025002019448234788264341968794716332067981937949097609548861654631809646464344213575300476910860746689637212371057494876111459257852148911385967048755465998441364146400022319073769030669486255997867547995222556113671998576983652014900141037588411791395604752605136783160867609748118109236373232248011307499087595417610165317101079602536029939751761961409793458257927122496473727405330252505881260348617548185100987630099263033869211094826230264992746499766937765664767047006915745373423356974983886028631806018605368717143402885871329102564704048497978176595564136999504898026980399221876155825386735988890478521694182263511982214715473315781195200662586608289146076691505127900696857629942816467387762785961640417229457596102193240304059314877424478667842289912208938780134312689210803665796315755850327333239648241364437120059014779223556434771264888962692080320296371365675443041834819783967762151313094344287600324088024886298056503696129538223922486941503288613783288870731822184804697687684051260150598523227085670596698786755189436919638468778275342260526833915914197270020098776736064622519166800190869283946064085690137489511277163716308622192219175958296397500085684126837927336173451686684923202975662385803826521428261798994900934113002497407521439855373833822964723019320494102332671987095211054238025332581283303947523503685018243913424390547185206189041043360160551399181866804529327190930148746439057774213307320757229157969585047879576209642937323116289964490410633199594898960154825688501502166627998287854790244025814015914565894614176980590304824038029416219941692596393563315421871832759822557040046812392613152131516662651071131811697677932327278397600019337002820692075165825022159844139593104475602024359541715915936040280694024136104975224838491512973122332169367004377967404039156085742436134266885110263040401912806482685606546407143416336601227367095920477163288537592301398535052907715237130177064760726499531799400005658598752165833477119918705900029310637497082895816444819618200059170161703470214369422592382641320506101680281216156081778448799318487482379825143559429289217755084375231231826966227624507701607028493277365212297731816558232776081859195320720765487935640845306071293298175978648896121109699931766693640815838766469144414269416881611661901832254474993736903002870444918037696406186096461094396767891407003453281738910144375394090662039131219749613014416244957286368701539109549586816734329366236746259041128698402728540623058249769198276372684574367047631508878368246825155252000604186666175384857635626157366171685799119057749145104626216349054268607435891936118142348404291584681919224938269484894447299275783313866238268605651170354567618500066640828464663845039073553932154895328922389658948027157160251222979894704360571691297862952533805704188878883347493951724921180841678272882101995530922680946787505085500886281017788478168947687933289789265967458335625338880010055835991224103398106910681873999803919447373848842718558974101069467493059087041449542369885578310978786508338476580819501430821887216699397523296232481211068079127848989527274911018295957930245601035781781552015776949331402066548318836070545702259101601202858355941021723239696437490190967646907252717163788218362609765047387412812296570896130256850884470118212380074491599062494090782968188381275032884690293738157030772407788960626763826311786521684459634262702726313120595550807817889783348003295426613850135163759356093858562640172806341511755083377256237743856688685833977571021335173367552139558669231461890051388052084168584309212686328101875686642176681678258161007255939143491156297571055310068227096515002086176644475958915947792826544980920701818638312130673149091618335925811380646453223742132133536011417584230713296025838111560391541436824783737657386591404783962547872759160432036001703664023848862521453258338793133106897041110831983625006829845247141544780274547562798449396105088732940897438717261579517926301609165483354955629169674272424362392449499327755308169464334499835011272786260059623448169962267096528431414363307727748879558583861743513655499714227653314531461547230325298066242977520913896933633425978231755203930891989970693601676641392159782285450394650447351396177405259220091086399878803399037284230150075406946172625105252246743707323586128249768358241061843301856995209716718881119943331925960878386314159192691633628371990365999473324033224660166283362406508472119313013046929763109273691491482783208361952804867618709155359763254784189783537132337034192486723758484296789460982120806248955719901979533349518748800253928816551805010361299912777533130155627166184669776817910914491556108545726579739015553397637872032024840343939020724989466155622700211781395397524802676616039939897330181240843168074214891914751916504821544411228786746871441634365565516782266448300241467948069931858061626078054431628234960332693691868914691195100883613120189661632186182481828827508722120099555633056092701975580830614548967717547124834107408844338075996676965118798713414760398527484510079855409467866187873865171641234435736694892493290285643393962280230933866378605205069640229730086747322559948835347701346316298854270595950784552299777610367564656909358070274954245477742270971746595867221526118823469613170169632325502587230182228537723192376736698335277895419921587983445396504232871929928095633156235885197769500331225291266518088953227966713707787164877369121792584377914564446736202678535672272911148596686537910294857223644454489067037707405536559306146842998665525356136573125169693694886923967734414247683916610832803230551830328329656615597750684742556921964560578078724927390800180947770481117230846398997474232831807416534958691477507232803171451867978795773477926362693036590124982640838421272171294486953694217648730529551119670790362378479165040057727884581718811537409504375754180213357329518840339658857659225472227753910940218573950862702436879531170719059054588899794722642555547715622550383094211836998109622803898475556138968220399520755975722033077348250428810898854659545479156649389371726108262751722270235138158485718438123481002162926100167821842434644145808964390957121673782737814361306217583217184598124487848407570736394438276748884900324043557738088347297955596146371472719244124866695710978580801114611245318214829898604977359790001251837337744732514003227801568532210870981711391593902347140202374989962533922017246308539050932634459280027964473921781011525328104539916639202720496687716273313449817119092654390857956906620484412000245041169243761472435023051769094170910850758938973425167314947084154044967895410170129849078550957606216129957114899698050874439894391514059609561936396117681164751704852351319228847525908033832852224331049094563435794419534196340813328302275203470566275886315079650273405931265702058827312707374247710482760916463127541794836090581772091569435534252008530734238443706779462426747561809295073772989948906690839206749462851068679596295946925255856047917667723409795120929223023568942635473417139817402379357828670784544822226269789762591879865710801484081920604407651804998349809431989752090348608514876630638518621108872119987893037612213788399531244956067024823744464295926421141662355934743056022382942013556145563955739612625216357651684218328907508641093930276516014993979403960868963166273417646322104257657318991066104656039851755604731303550365138945603628337154214247460120272519587532156053928853272059360997202235662983082664787151377470547835077166304969488757406500477091420132564946761388009999150205307085916054009789475189522966304063839406949736916211375628242467064326553552643434482432201764730991631960975879963107928392665409042731125871602886202088963271887832908611559265610937788384690085152310913834573388112507237937730757225715912796153347153130186632328418177766308016585771876766217468711212548383498610478459146019961088987462203396327400295530783739475027149900881772201888789353158601700677782184152573400851186942994078175811891797233717783138006757483715072021020758596443618732393369139098591351799194301830809367863135024667117464305862025311413756063774077713211423576086774857290123690738822518048520949175918815981438611077457489344566987152913956325533160483220764219027004363784496316622361504723876457646422206742143391453606184716462121044180218197530275337938606215705136430264193780692405120326312862385649988784732175002811670077610443264135934777412150018828223954244695050026842052876118164018541944874833774670555994814420671882408288137775812469290989993809529670529829438647687529606774014120319239986257497301032425187103725121654968658239135595585158593925124607814088125454604787206451352483254459291222047592454341812243065137310481737689661315940835763055390630366405531005767248882907865249389338691377250865829483136636108551155102223445510020797415176337695410000496618501795801013486367948364379840004621567554498797988586983536885277281766989388141535482632178393529591983320058577012810211414053003397205458982697084268250263636216226849867255775808792107079985095487774153671231747128545554886268144818502591552230433514295245774489272593082024298356091609395630161222343283728600145481504536639820969054368415028850424427493816321210061288780567589605603485304929240318765007165160314895042800565872673010844927496776724062145035309838535179167338585946480482502304095322690687232463519446532509780903023128865047531103223461741746558159843591973034411569970280749644844477684427221300798945879744261065241666018944132807794398191204384532714659652333888454053602445432009656690476219493586861862650276087376220797396105688332640294421919802707378374349366858367758305227152144956599671541049582507982382810422816218154089085630110850817388778205572090179609654423564462789769682143891222682702408297516161189408903014295279135004336934244187516885749045858222234653015419511298118997313635664488446496836226827661674123289710636701353528269425596810788132814943234221768541178592404212356919876288915506439277672285401338295086910304093675952549924981548295539671618340692698510141069747470306724497622695441545177289389783198167673153308821130110105288781096189097874731485821840767460542853635315821366422678874925699731857970947686041338357356660254628504966783647630558181400040291220487730085425878820572203969786010762422205821077797891437437271211300592243295335783205540143414525910530643020222737525571946127221957193409744066896412724685850198276695031732241655051863572337617886213017558284975788698382145678631876793675083523530665626372542375260667989689193097509441096459016277376089258829001608871316651176241624092467422390421989410935677121376456674284503881285948347811403148308417350334010647129893085265060932398947369906762515000254008951352275939889675264734960540139416482458019250609247002478434809985351376227426552083399686034233737113135721952938073954444792091208018687445435005640893031581207597214528639333548781765175930179702379384879976002408492565223093051749059256

Project Euler: Question One… And A Pointless Macro

So for the something of it I am going to see how far I can get in the Euler Project Problems (Not sure if I should have capitalized “problems”). Basically finding solutions to questions no one has ever asked. If nothing else, this is a way to further my Lisp knowledge… so yes, this is in Lisp. Hide the children.

First problem is simply to add up all the numbers that are multiples of 3 and 5. It’s like a more boring version of FizzBuzz. Apparently that is possible.

So it’s not exactly a difficult problem. Essentially I just went with tail recursion. Don’t know what that is? Well it’s magic. This is typical recursion:

 def someMethod(current, end)
    if current == end
      return end
    else
      return current + someMethod(current+1, end)

Basically the method calls will look like this:

(0 + (1 + (2 + (3 + (4..... end)...)

Because the preceding method depends on the current’s answer, that method call has to sit in memory. If end = 10000000… Stack overflow. Oh yeah.

Now some languages have something called “tail call optimization” which basically means all useful information is passed into the next method. IE the preceding method isn’t waiting for a return, because it supplied the next method with everything.

def someMethod(current, end, final)
  if current == end
    return final
  else
    return someMethod(current+1, end, final + current)

The big difference here is that every iteration sends all information forward… as in there is no return “x + someMethod(…)” call that leaves the previous iteration on the hook for the current function’s return. Yay. Why does that matter? ‘cuz. Fine. Some languages are smart enough to forget about the previous call, because it no longer has a use. Kind of like garbage collection.

So to attack the original problem at hand, I used a simple tail recursion strategy. Every iteration with push the next number to check, and the updated total to the next.

def euler-one(currentNumber, total)
  if currentNumber == 1000
    //At the end, so just return the final tally
    return total
  else
    if(currentNumber % 3 == 0 || currentNumber % 5 == 0) 
       //The currentNumber is divisible by 3 or 5 // so add it to the total, and increase the currentNumber
       return euler-one(currentNumber + 1, total + currentNumber)
    else
       //The currentNumber is not divisible by 3 or 5 // so just increase the currentNumber, and leave the total alone
       return euler-one(currentNumber + 1, total)

Or in a real language:

(defun euler-one (currentNumber total)
  (if (= currentNumber 1000)
    total
    (euler-one (+ currentNumber 1)
      (if (or (= 0 (mod currentNumber 3)) (= 0 (mod currentNumber 5)))
        (+ total currentNumber)
        total))))

Of course this wouldn’t be a post by me if I didn’t over complicate it… MACRO TIME!

You might have read my macros primer thing (Most likely not), so this shouldn’t be to hard to understand… right??

What I was shooting for is a macro that would not only do the above, but would allow for as many numbers to check as the divisorable thing… So instead of:

(euler-one 1 0)

Where “1” is the starting number, and “0” is the starting amount. Instead I want to do this:

(euler-go 3 5 7)

Where “3”, “5”, and “7” are the numbers to check if the current number is divisible by. Pretty sure that made sense… Ok, so!

(defmacro euler-go (&rest args)
  `(progn
     (defun euler-one-a (currentNumber total)
       (if (= currentNumber 1000)
         total
         (euler-one-a (+ currentNumber 1)
            (if (or ,@(mapcar (lambda (x) `(= 0 (mod currentNumber ,x))) args))
              (+ total currentNumber)
              total))))
     (eval (euler-one-a 1 0))))

And here’s what it looks like expanded.

(PROGN
 (DEFUN EULER-ONE-A (CURRENTNUMBER TOTAL)
   (IF (= CURRENTNUMBER 1000)
     TOTAL
     (EULER-ONE-A (+ CURRENTNUMBER 1)
       (IF (OR (= 0 (MOD CURRENTNUMBER 3)) (= 0 (MOD CURRENTNUMBER 5)))
         (+ TOTAL CURRENTNUMBER)
         TOTAL))))
 (EVAL (EULER-ONE-A 1 0)))

Looks pretty much the same right? ‘Cept for the PROGN thing. PROGN basically just runs everything in order, and returns the result of the last section. So this macro actually creates the euler-one-a method, and then calls it with the “(EVAL (EULER-ONE-A 1 0))”. The important part is the section that creates the divisor check:

(IF (OR (= 0 (MOD CURRENTNUMBER 3)) (= 0 (MOD CURRENTNUMBER 5)))

Which looks an awful lot like:

(if (or (= 0 (mod currentNumber 3)) (= 0 (mod currentNumber 5)))

From the original method. HOWEVER, the one thing the macro can do is make as many or checks as I want. Say I want to use 3,5,7,9:

(euler-go 3 5 7 9)

The expansion is:

(PROGN
 (DEFUN EULER-ONE-A (CURRENTNUMBER TOTAL)
   (IF (= CURRENTNUMBER 1000)
       TOTAL
       (EULER-ONE-A (+ CURRENTNUMBER 1)
        (IF (OR (= 0 (MOD CURRENTNUMBER 3)) (= 0 (MOD CURRENTNUMBER 5))
                (= 0 (MOD CURRENTNUMBER 7)) (= 0 (MOD CURRENTNUMBER 9)))
            (+ TOTAL CURRENTNUMBER)
            TOTAL))))
 (EVAL (EULER-ONE-A 1 0)))

And the macro creates all four. How is that possible? One line in the macro:

(if (or ,@(mapcar (lambda (x) `(= 0 (mod currentNumber ,x))) args))

Remember, with macros there’s a step where you can create more code BEFORE the final expansion. What that line says is to take all the values in args (3,5,7,9), and create a “(= 0 (MOD CURRENTNUMBER X)” where X is 3,5,7,9. For people more familiar with c#, pretend you are creating a string.

"(if (or (" + args.Select(x => "(= 0 (mod currentNumber " + x + ")) ".Aggregate(new StringBuilder(), (builder, current) => builder.append(current)).ToString() + ")";

Or something like that. The difference is lisp is creating actual code, not strings. Anyways, that’s it. Yeah. This is awkward.