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