#load "nums.cma";;
open Big_int;;
open List;;

let p l = match l with [] -> (0,[]) | x::xs -> (x,xs);;

(* Shift to the left *)
let g (l,m,r,s) = let (mn,ln) = p l in (ln,mn,m::r,s);;

(* Shift to the right *)
let d (l,m,r,s) = let (mn,rn) = p r in (m::l,mn,rn,s);;

(* Simulates a turing machine, which is currently the best known contender for a 6-state busy beaver according to Wikipedia *)
let rec f (l,m,r,s) = match (m,s) with
	(0,0) -> f (d (l,1,r,1)) |
	(0,1) -> f (d (l,1,r,2)) |
	(0,2) -> f (g (l,1,r,3)) |
	(0,3) -> f (d (l,1,r,4)) |
	(0,4) -> f (g (l,1,r,0)) |
	(1,0) -> f (g (l,1,r,4)) |
	(1,1) -> f (d (l,1,r,5)) |
	(1,2) -> f (d (l,0,r,1)) |
	(1,3) -> f (g (l,0,r,2)) |
	(1,4) -> f (d (l,0,r,3)) |
	(1,5) -> f (d (l,1,r,2)) |
	(_,_) -> (l,1,r);;

let u = fold_right add_int_big_int;;

(* Tabulate the number of ones in on the tape when the machine halts *)
(* The answer is: *)
(* 35147495252376463148555467711143647557672746259263 *)
(* 25736213218928820741221261252342696134490334047942 *)
(* 74158874085574161758640871026007689508568015893948 *)
(* 16617369051829709188616922820871763189464304029884 *)
(* 20114923841803314050578696912682707858206715741041 *)
(* 41760679252097596589256002393988435049030042962996 *)
(* 08328598584452491584942601826776980912203689596636 *)
(* 68603954175797097689265127461159832047501137152726 *)
(* 13296633418762591378797771268817989821473557446658 *)
(* 05546721277221528334928463320190554329437603309735 *)
(* 62614275563256082439609073071574542354046698495209 *)
(* 34716483696669851785572123129056141768445375226730 *)
(* 35204667004412551516735431150856993332429593771190 *)
(* 07518198828449361850684163180012165557935250830102 *)
(* 15561234974651474560806259406226923263313256435088 *)
(* 98474423857877708415465946677059198863088610910178 *)
(* 53759613456348210423340980584719251582866309840147 *)
(* 53328692543115455493415265297154616890813289571689 *)
(* 38845868903568468862228115551133122969375073285693 *)
(* 41516410688605240766787559744961818407414799983992 *)
(* 06655928556739364784151982149547061790442340349908 *)
(* 10152327460923777219392550972439012518241178142787 *)
(* 37859266659793419090062712148265949236095156172946 *)
(* 74095915824946318655414289920094329655410673596753 *)
(* 14416714070134049471684028519880794560876408344279 *)
(* 59552753930808773657643706467206098028110178109513 *)
(* 33916950068275233151858227368120461617753295768256 *)
(* 57741341656690859975493983107106349717771993363536 *)
(* 36662325243215113614540536886962877004611359666216 *)
(* 85455091860896716154909171711212346127093341065369 *)
(* 26011067838557740941276914805488536996942877425668 *)
(* 91909858885289059825119110077344384977588561623933 *)
(* 72047605744168688545911088487783416648091844864349 *)
(* 72527386940862493450496442786556709093405951437639 *)
(* 01219622320519072044427795692044757765238440648408 *)
(* 14586318238395711816795072862863662631642302281615 *)
(* 50050586964391104324521274467255652923174305654241 *)
(* 97122730094400198823220956985927543987437041948715 *)
(* 29069648123396837292758446973249496961025069426030 *)
(* 10562846113746903293868547020420655605910313215681 *)
(* 03564818322881780346206742136440107968150032548169 *)
(* 65949243676158757290031691031511939180938773925396 *)
(* 45024109412057280883082439612349272923902625449109 *)
(* 03195950051893841591744871613800278221791627890716 *)
(* 03150762471218432561035432177361059266702967012706 *)
(* 05581239349011082901514397909980291836701088776924 *)
(* 92393333169629552334980056251493696832383243356120 *)
(* 31880648259766568303700008082785775864478196930449 *)
(* 32693396484210262943457573044630102794310191951171 *)
(* 28321626851907866809136460866199256977426755389555 *)
(* 12925496347125583727342791035263666970908176693111 *)
(* 80009118920431059202320351642463432198489665735305 *)
(* 58311307854178870410038846575807822363697474924422 *)
(* 17649693387868576551467375538983345191342276348916 *)
(* 91036645200057195432754186375001446472689596158251 *)
(* 71661607487314458436918886725879482798921538491245 *)
(* 56651974708617623186702391763238528613218007692730 *)
(* 05361070700955882588708574346376091908012916904082 *)
(* 30182981956289264001517830293213549981813878674382 *)
(* 30595412031274199259647621541012985275707557930876 *)
(* 20227523509194562481352015540282042793333007787213 *)
(* 78491803946496203326949318849134086197900438081214 *)
(* 87534178034900867613658226842231884904437026351208 *)
(* 50991261938752174459077434858163083076458388010487 *)
(* 92297882650936236415118797613257809414464770307883 *)
(* 24183187260344148652133477311186819605163236773986 *)
(* 87174336827117152408571808770665204970171492988407 *)
(* 93122238628773301800047538500631687123056517590555 *)
(* 61276272625137807260303719284405560500505306793940 *)
(* 24414155319827820694641194676385413205326741236557 *)
(* 15949470351267526763698572384443123155601462022205 *)
(* 59392532476240079641840593445374340712017412419806 *)
(* 56047049657323343815884440757991039726348899411164 *)
(* 15585139509865834289491362051018053650005533811244 *)
(* 81813415974662711917191863569666459484664568222845 *)
(* 31371274999184986854565586713623861142691280469778 *)
(* 40285593647042470015346867811240853179097558465227 *)
(* 25771821644781656580248445684333319375911570881571 *)
(* 52721752427708116355657223277489228450926505510352 *)
(* 10236817998451758552136738660439006685527887130124 *)
(* 60947711221466416770446347560399991289294824698210 *)
(* 22122770957200605571966694649977097317455025937591 *)
(* 12534776537159853819706528420132103220446214361272 *)
(* 64873528655806262162325769114344451465885285439810 *)
(* 67531764631978042239417245498236628368824184442060 *)
(* 25781947795791252947167658698363076817262385131035 *)
(* 41750835313144556362254095204817174680670395003994 *)
(* 73944226689506713369468820755858358220322118323715 *)
(* 02574287198095762942333717547287166227428244340113 *)
(* 63028864648703097884380797925670975116935636065548 *)
(* 30046622330140782953992157808309928479736060659329 *)
(* 50421410268194466585727334449480070342319050687163 *)
(* 63736056924687836509948398956474927730253682677487 *)
(* 81025756639544417527950729067981320377938838477218 *)
(* 66959065508666082662609713491204998218858462738609 *)
(* 02551931309525209315984412679456529637180778026738 *)
(* 78704273820375935844701731541769240912956678288642 *)
(* 85930621754819628558116924035143213978939649161524 *)
(* 37268226815775744260575797014694636324876492559294 *)
(* 04366749564071643382673109805704020209999879927604 *)
(* 77479860584172687101902869610598946587131690764743 *)
(* 74557759336851803155862811842098854836241157580464 *)
(* 43223323593001754210091024085625697786955297847808 *)
(* 41262422288416660925739928708983654937681733201979 *)
(* 83366708467815723318887796068453700816978918479464 *)
(* 79557303577784482006782571769492217100947839486275 *)
(* 53968457609578862786080082273204665830926868867182 *)
(* 12345530170853739132863334581485662939066010047592 *)
(* 42391660633598183431003010942898973069628388149938 *)
(* 68464215376127380358154518813936733565993726641743 *)
(* 54116346106429856660634148563501547830958423138226 *)
(* 58157781076279416118853067547640143129761130373718 *)
(* 18189152018817383826551010392760178031817245725640 *)
(* 61638862150100379907951485621099598262716211367556 *)
(* 03474220311134995828498877404859696694275642352185 *)
(* 90806494292853620285725522315768212192095393065513 *)
(* 11454133755099605029325728660511637119656660345089 *)
(* 42145078051015576446561372138558063601517390992930 *)
(* 03378180003371811957214241931521001549089914921638 *)
(* 93962406484980599216026367686470159883079038890246 *)
(* 47057288698920890610188972713970037050025663060241 *)
(* 39286956904626942664363292584857913842343586082086 *)
(* 52454858531241986113758427451892846972458444375060 *)
(* 86951470766582851819998465656954195141899546428136 *)
(* 91991792592529920386333178721200158673826585297830 *)
(* 44685925255371318697454097034082073016611133766586 *)
(* 52084725129291365888009974959255829204819286020109 *)
(* 11911711564135173995932009083770796006529351162859 *)
(* 83826673039860330476954404884603575022443494792975 *)
(* 97969125611849441004920217882401505102595221546431 *)
(* 55583438399065561139305227772734183561730963425915 *)
(* 03186891583128959961285536170298908751197758111647 *)
(* 89531632531727565292621796731642080895787782534888 *)
(* 26050156494798549759468076064174742837802336519245 *)
(* 59632271946102211069523861982859591065099371932738 *)
(* 26471129473613179469141601134884061669366050012084 *)
(* 90839239500131373838749801807116182690857599363232 *)
(* 63554471059880787165336614469845113041439326669151 *)
(* 74461636929106391449338784774163967710281989755797 *)
(* 05599479457719250849499017216945835485855074398828 *)
(* 46967997004490730391519132129206053992221195027942 *)
(* 25137652590012113367809150416413639796108096731300 *)
(* 13196328201770316586576722064880331648722745260815 *)
(* 93599200303218103208166078647894747037651906064010 *)
(* 85039509743334929927966128748391502978155660116276 *)
(* 37709716352619707091843404310596464802177490060279 *)
(* 54510408738645751922153841755459516183616220017516 *)
(* 88797911268677843669997700722106029149056891999601 *)
(* 80159800286367125687477552066863524551468900631854 *)
(* 38337838509131578445181562760563986288171954611929 *)
(* 55171135963808032130313269169343330503947021700395 *)
(* 36163417445554693524928608812130408969631600401541 *)
(* 11314551082566175135446352016548185474326525974507 *)
(* 73950677832032489378946711485227827080199638113192 *)
(* 87582612604267157536635088862141276913090531055323 *)
(* 17279393276505890950976584290146770690667002600569 *)
(* 41680256363975523525421601447558840633052722606780 *)
(* 23509837585551183143469724628086534756193070658091 *)
(* 69884087154644446269948988913218279402527329702977 *)
(* 94487477474293699472291955865546794662158978381425 *)
(* 82113382428326438379994348211948623866177140995460 *)
(* 91728986194634458368896797056234536144198636457265 *)
(* 68364579223550514503806440795277032483435526007916 *)
(* 48389653929910708341445710397556903077090254763164 *)
(* 03422848149680788219223637001569392929996765450994 *)
(* 26630642802104502261907969461825534476670996779898 *)
(* 19685079194024616602332186914344637215688205807904 *)
(* 42847595373249110159911620687658830124602498627156 *)
(* 61134976574300181621149701476789675169337080414400 *)
(* 75498334764864369737447588990044120962752250043946 *)
(* 56637079776120596927133681561327035784806512010896 *)
(* 75562380632922351348217996537823190778202665734360 *)
(* 25438429495741392474837169658421880178254731396898 *)
(* 22503437763046984207587163315356259399838081709603 *)
(* 88596992586991128529929410272644158684441051325004 *)
(* 57390646457285237656842720271098878277361851275151 *)
(* 68065119867475347746567368840091797167101316466987 *)
(* 21372069968230691140438455276856223032176392232602 *)
(* 68203090873253625004573187410652131460728308875028 *)
(* 27646966691578238255072861071238401450144608242871 *)
(* 00776733502343552602573968493417923360088453207076 *)
(* 16447412830281952675472996651866262981821313105972 *)
(* 71759265336481819840281063772767710127671568907733 *)
(* 03812114066367115459934779491476318770830261939969 *)
(* 08744645297171887060637783167435341377497160154407 *)
(* 93473106616811562889813087733604562784517921429278 *)
(* 53847287597200144002915599866616990362752938059996 *)
(* 93388405948133061574365530520730494660190902878375 *)
(* 94767873796231666218024517580692044948925442205625 *)
(* 83076463167937749271269624001931063525635826515418 *)
(* 33392769379263829405452149348111687782129822204931 *)
(* 90273906851474058112511133707246318470289529887260 *)
(* 15263361133093359662471390109518067145771871587300 *)
(* 68193256589880226155466416058993998370537500018787 *)
(* 94505942981225184394387655681623530308684811868730 *)
(* 65540117541472318298122375805368730304523817442543 *)
(* 33401424292832326813948787858920473027839543535128 *)
(* 30691493165510030517078446996345935837252958913336 *)
(* 89702184854184485372639593078433702962150418942599 *)
(* 44615671056152125137938681085948333812735103693315 *)
(* 81926283087896770390656800312042855380523602212871 *)
(* 06524200054148436753921943215848345197989000944786 *)
(* 41413163852711305567849526137314180657351962773927 *)
(* 20880127897194673742695914379859967715298469406539 *)
(* 58326242113445724218715123667795963730905363089470 *)
(* 29082698134519967699122283319354687001061079663770 *)
(* 39339190158231861339782337891839076411340659445258 *)
(* 04390238345756221358658203589644793527772213785573 *)
(* 73261813657532635015530413498844405132311353861246 *)
(* 18112646186926329676147485468504227757025963053741 *)
(* 37938230948764266980146485321363902307692466056116 *)
(* 79030189671453824800744759911390505839279850384404 *)
(* 95658569897233488693493966326036083076458726988876 *)
(* 59604386015024452612711271278622113894910487477205 *)
(* 05832291493749779276324357165963691605968420924881 *)
(* 50847436130693933726213621488551554201472406983954 *)
(* 96801141044121161828943081891445275209045617469427 *)
(* 87863538786483571803073782409939219549222466535846 *)
(* 63539081260004903908679351094675650382205854791170 *)
(* 55353535639266458691879845305860875739150944029911 *)
(* 54413006098447900202591951116635775884647242969831 *)
(* 70743830915187124632232906696643798888400730907449 *)
(* 75253850698523909042244806026726153337410775044107 *)
(* 69281903983567511752284498818314575554294850446581 *)
(* 11147102307566282962933447516339523849753827875655 *)
(* 26671018021592014990276803333746163268133264748087 *)
(* 32750612907661650686081045331815098167409896755475 *)
(* 88097120459175858210872229578034582896638590735043 *)
(* 71812183886666731772051789743301165081206580053347 *)
(* 78217129751969378368497231415044702111142646113475 *)
(* 49378923694563060590681294820766228370297737162883 *)
(* 54482790186942121771428302249270396665341645846243 *)
(* 73883993719753333487688710911485326550343970990177 *)
(* 34761584092290317221908889396092103891486913944142 *)
(* 93150192774084087749894829244826754070945728933308 *)
(* 51924027701223159193334869919594993806226556250372 *)
(* 98665982158121038523619855311998456266385809984282 *)
(* 57705876681815534485907281517964171319007372745748 *)
(* 01183758867147218984105182020457654271154010872791 *)
(* 74671622357425393178212038689270542552214466202310 *)
(* 81172552875496733909388255432969790155831757028185 *)
(* 36438231517918724799404912746332205903799340346061 *)
(* 61657227176489551394535567629180319898306398673214 *)
(* 35311162645975223792069439280159092119781014892224 *)
(* 44378788374586552025749516091251126772975809663812 *)
(* 69919133025584351051318803535874334825495927658013 *)
(* 38379788454059857552063270523216617937234767602628 *)
(* 08514399311810195196301150594243192523184855353501 *)
(* 08824140032147513564438366689606782778269965801585 *)
(* 71277303942024370109571035261167171056177704479990 *)
(* 76774555663497541152845335887709148405405510300773 *)
(* 51645486873735916928707516170255625722699914135807 *)
(* 11143577787543862162375900625893770507698923995878 *)
(* 11215476336464877280721010587375779137401342839975 *)
(* 21230163072330567086814465244515578934133235004804 *)
(* 52081933066500966129772746495475617850732219971204 *)
(* 33237227113007623135283421640765283029718742436808 *)
(* 66490047057795152192731863747987169920882938599484 *)
(* 12523818252587755253997880672557427253662342397009 *)
(* 40334429515756252439632949645492807767260159282194 *)
(* 04143069574881290906968238170095139035367036094829 *)
(* 33773331831631715927229182210771698723750602060546 *)
(* 43704617123132819232828854927883974128370285210584 *)
(* 51280826123365564537767036648751676338482770796887 *)
(* 66964371898140207464428765276532603012525108378277 *)
(* 15769931520304328005023389439587778752196371059384 *)
(* 35548926992589492077731936934813187495887910106992 *)
(* 23089117920775266422662819969153318645498786587961 *)
(* 56808093979261595983199036894822112674496886635632 *)
(* 66590047951129278743323137788097851929371708260402 *)
(* 91292133786758019547721350376875027773282505414273 *)
(* 37666779806838362483164031074227068621473196479757 *)
(* 81437764124032148137522358986447763512074336592754 *)
(* 81659736417685056563674289502211067979849383465749 *)
(* 22398253343535258276119946645375973976227944066033 *)
(* 44134141893488885232615556879693945985895150563221 *)
(* 17306536895906818661163465163332919312055146919477 *)
(* 92927260993151293384508596783475145958021968598814 *)
(* 86957684903748844761805134041318946462490043442729 *)
(* 01984185403037693172966774439191971317458388376012 *)
(* 84870643857380495571112311998628564110204467537114 *)
(* 90213817844621083797926722170285692426492936821615 *)
(* 55601529722275774820708884020186107361771610907621 *)
(* 55352244698241838719127533739018714976099555322562 *)
(* 40052570889006035281960098831416204526173907582432 *)
(* 84109024462697267191726256916171574656705338156658 *)
(* 40080417809423704341162688614551734014510009170861 *)
(* 73463937886992437260553501361729173212760259094569 *)
(* 53354275932195469754743553854359960626449978029326 *)
(* 97663051639826024508249828573123161283693755340657 *)
(* 38177671599919877492600310824202962093668857029729 *)
(* 55566145057111027817980824799132410121344206139856 *)
(* 77545547599930974836668138582991825367237973210870 *)
(* 07442489622469295179098592531261391157609515799961 *)
(* 97650383250010781736831093547037726781966031274203 *)
(* 40400660754341236476006418349594912140895336612828 *)
(* 70523578420282584430939907967529573719938846459467 *)
(* 81180520354290463493787818828850378636917431338037 *)
(* 33206993733414184456021752830562641848312016547323 *)
(* 32022633919292702272407442521511979911892716044876 *)
(* 86052731144352652359117418058974491933541688549963 *)
(* 61799590900699726039810123970798719605024055188880 *)
(* 03962164594431042037778390829383004366307039086431 *)
(* 43716217049150290058314520375756475519631618755447 *)
(* 90637282774708379441643521925443264042372679361553 *)
(* 30060344051658914445867938589316341676195585539370 *)
(* 23092275081691123221500335023012389939585487504476 *)
(* 83942993671236450889925673847862535678453724474297 *)
(* 51307624447605431942334058274207135732784147228200 *)
(* 80350449950042151967046389291273697342959378463996 *)
(* 96813268631293100681063285947377099333482568040272 *)
(* 94534441591962737649466091616192889143821073759066 *)
(* 50767190007897926364460708124967096005469813772216 *)
(* 07154254743414468370698147275709564847938982559199 *)
(* 84208683019060784646968518568214989970285664783250 *)
(* 18746036431621838868357220208416795376643356002569 *)
(* 33524648421690335058415148658044729543166284798725 *)
(* 76496564555024280808577467198848913760632683889266 *)
(* 03946242993196845796643059352238081685987278461213 *)
(* 69264252619574076371539008583371120019023967835017 *)
(* 86716752191846856011850457129838896870176329617586 *)
(* 07931193123766606571733398043952888773807250865946 *)
(* 16303136433530273892086829658890838044297770641694 *)
(* 60433180653911958771529749097101459765235092905282 *)
(* 31822988596243641608369450490569042290395675273382 *)
(* 09009257944012278833172546137834598401723691921544 *)
(* 53201365988939284616645696455850090165264194711681 *)
(* 93337406710120784610192471047820013115096329516373 *)
(* 06746732306947404805606839880431351573553693735959 *)
(* 25311119900592196097443546172032526378666216257833 *)
(* 59337477289970451320798508411880461339083036914178 *)
(* 19201747857600262141730125048436354112103057689765 *)
(* 54556674445973479148077262161356514573017704149318 *)
(* 35981996351489600209242050250930066270428663697162 *)
(* 13679894579494229477179188180343901781309432085685 *)
(* 42675963684681173668196756741274805271101846637421 *)
(* 09458131791899829223308177514072757665147019956217 *)
(* 55869662888138104932648678789974266433285142401804 *)
(* 41204357828247633362820610640385381570419692177197 *)
(* 77838388603880868595161770249784566663591886967840 *)
(* 22371301651037192157757159007783603753362408287258 *)
(* 74644296570599404223741582221103907315896753977084 *)
(* 81954193526299431504836576998792116226379674221110 *)
(* 70594722314284916344079567226700478649779927885215 *)
(* 13206929798699270353679585014140152971796169795288 *)
(* 74644598622643262608270255196211998504817496769955 *)
(* 44993771447644731324820891353424389050552418370566 *)
(* 75827834886958159988448387551899747924275744772448 *)
(* 03440324063595336128069728883960473329181780852044 *)
(* 84318989859562173202090671022918960971809631512588 *)
(* 74927285893737305275365197886045704607821499321571 *)
(* 71136344306748125214822992554294598207380902584239 *)
(* 16274369626633846542380407223122555050200275836767 *)
(* 51099443668097158762336430159715630381370925372823 *)
(* 42667738618478633158169046285615666791051423408230 *)
(* 69533024507976929433752283557502822412804543793364 *)
(* 19417994600552152500137286623685611990835073946663 *)
(* 95447337900238932868218427969606999996412809594006 *)
(* 97853605858215807556989340554084967411692144714789 *)
(* 72382534010622603921998447394381860874948059030432 *)
(* 77765045155369551669235705175893482547610512484076 *)
(* 17163971078677927834885789038401547826079894648475 *)
(* 40975224010031425581926978888090321338071493278257 *)
(* 03073817576212284748288587081781044731711884821426 *)
(* 45769036539219284441099253321835034076348326562788 *)
(* 284314395618690847 *)
(* Source: http://www.drb.insel.de/~heiner/BB/bb-xlist.txt *)
let a = let (l,m,r) = f ([],0,[],0) in u r (u l (big_int_of_int m));;

print_endline (string_of_big_int a);;