dc, 34 bytes
0sg[[d1-*1+Lgx]Sg1-d0<f]dsfx2Lgx++
This pops the argument from top of stack, and pushes the result to stack, as normal for dc.
Annotated full program
#!/usr/bin/dc
# accept input
?
# initialise the bottom of the g-stack
0sg
# Add n iterations of recurrence formula
[[d1-*1+Lgx]Sg1-d0<f]dsfx
# Prime the 0th value
2
# Execute all of the g-stack
Lgx
# Last instruction left a zero on the stack
+
# Special case: if input is 0, f left a -1 behind. This is a correction
# for wrongly doing 2->3 in that case
+
# print output
p
It works by using the recurrence relation described in OEIS: a[n+1] = a[n]² - a[n] + 1
, starting with a[0]==2
. Equivalently, a[n+1] = a[n](a[n]-1) + 1
, written in dc as d1-*1+
.
We push n copies of the program d1-*1+
to the stack g
, prime the main stack with the initial value 2
, and set off. There's a correction for n=0, because we always push at least one instance of the recurrence. Handily, we can fix that, because function f
leaves -1 on the stack in that case, and 0 otherwise.
Test output:
0: 2
1: 3
2: 7
3: 43
4: 1807
5: 3263443
6: 10650056950807
7: 113423713055421844361000443
8: 12864938683278671740537145998360961546653259485195807
9: 165506647324519964198468195444439180017513152706377497841851388766535868639572406808911988131737645185443
10: 27392450308603031423410234291674686281194364367580914627947367941608692026226993634332118404582438634929548737283992369758487974306317730580753883429460344956410077034761330476016739454649828385541500213920807
11: 750346333909286311464218348364293017384724140073732363176684391768374238237200233203724274839819736227493060107386942069521875902258281351952761393460726027774387698896086030486687796275661950199835484418384103096899499524666007073298797852932127876923983340497448231960048833094195425231846478785035602339261149953564729371337917773386670133413581537490788020231265093210310224397095644371148893261284201611453610443
12: 563019620811106188735345793029131127645126456201508328395934709948713369875017428398616526515350801978901280848429236023780360625686785326318172135941491985234945009397938528773976977887356630327917721419666751591559883455828027643329740930320548089836575156581070880066847294722353255119648341271402723167206816552066010592134725124376810874159292118224274440907862996344067325025151751506647339684959479438354192989470470488621172745980086435801519575581664038703641801974453354864238123148678312993828328158261237284571445163949954735321181426755485563860804935755099928085508785637606452207007984638610604113718738727804169240213041488645142155664706600019329809186121988322464207409749450811638629159492106903853533242008723387118397794980575878357156285111258733862431522178328441469980110808406224908967784943255608168545045807
13: 316991093418281796980738587324498503465985663563441351614965595710659626509023026378810664917769979749230375616949095839488230630774365784766585678394020150307543448990686716629735821013846949520218610883960194258122308878890968113466913053158083723070515602776324450012006168592325685889943262781933132780014500164781142497008320197365141855119010118077705678576368755229432787283587491897170937657553086679827144799087397199129432233281774986701578182361474362882421927116451702868297347253630717771757957438615228337552613006602138504913204731416596016919892552584014059657038635241014722034375088903021315484876024289828564177721518967548558336213757430766087730295001595138792039193609746512786881659903942227205537012891959828532940594409566163694454653037016800027294499421291400492041597627904670868358757293568071192353450861046220903121264904877170553117406388566305811088048722332066039563082830094354238880920553702156022717609505663704069061610519598560624334935881397512984533454362321248854729174814176943381209734396537109715522733592519084452225492188715705481658124794599731527140827530319488791822858978924780015280035310521766457660381662363459675166288099343838361130665940967928850877954452552005403436587169730515877297387774041696625714088910160966686976352250237188765370786055553236020704945964404004577531357576565107610684603955726197582253686411381871520005412537060114403951740688011605681233186481569161991920354077827812176666950510226500521720520469387009627382085749910481677989034236154462513159644551504513525508614268492165297534777956118363272320828495465015734808069866823697938666550506233479919235237378935603448169915183235443
14: 100483353306517857188816511171973264968130481955993490961776578914384855009465596512878627978186320098524674810822809215084298821790532480217571435837318997038501027166944291436298311859998927368878478765662052261013905379683606908563327049366289350227874801320137528476359434996625155321924896471487253609774383161294073700386567438895729619959183688827019175395384990049660760826706275656247200320644562229907983316938796200727194177710641698165578469600709422183645673081099011178658794923207340118316226811044120124994280172667435132674250477913878334229469634774955766654959747171269329356217729819952093850230832136940392143299736102334976183356619572749168857678782222255344301700168226608019630704240193738779198063738629831841413772846575231497629810592678428725195220732911880790353530776313807267315574488856933933931968726196972550157616749777588888821303729634383570842953721086839502335017753789603211887639264756326943906234925564059713122739441052488376985825209930025027331642643833862623818612641648534007690784009230583997364206027891426162271405399576520661523570494921380174573570295575834537952976231451138917903119690734728050868143651943079046629073247009723903287946523072583428647088990713577505274669321894108556505593299658881909461644436220683735665670039545950199079805499092674406353548516096407916275052371510047476698658893306349068133879014809524920709542592832744670134019181012820484031829100985336532444887396195766078330294774788615792775829183741076029977456631131003360810557200089618493958319779112283680033864350359591347851857639767660909655544622503481811302270128415655545885368248621757558781407774929247336942808205264958129961178967782261436710020914320953492879039247990865098954170193648898076402861312803632817456574773061811978648089614340109760702469211985641224691799075765885167117855362986656144090527289697873066081524676142089795828969028242126025160985084779781007974719610529121366009147473928798323429514961662955075830495059188425232901129844306717176754536658533793214326255403412914373598713551532524170357661947859352181097102731800860434424406585016086605044703266455861041380556886689319004123095655013285849524741495205262970148746426581276319938997140587845485798731493239638046736464142096404810367841352036464369335995230683471276720095626585363049720580305501778636182605592068492151793190258602236893550140479021220581841241476297575889705144565984983772835663470728331437295945770147420128139970898197153180098987682528952187399111614545313650329728193759220800741639763444502297436225484681500013482802572032911312979385547883726365017125898034265710900263014307543995711388447583272341504352098242603013317289071851486202200363353430637400418445403028209289752937101610106546407815385279051077386957963745649023423516876644029840971378691516442745761797057396994687382618710236478541855961623090443801434726418529440871490091117324165342131670988126442133481305788646667033011070351616554711007362680081909808994105138595194669575127185645557552945017168697977343707144183186705714691228418618276386168995938283316172058534438295911377445943568762495111242585896098376432273844229629284777619272064792008892485171141118486114024760197688360378085790695965894817048250719620713759873671293320363983916413298621510321025850259140267373664767105414000002388170807
15: 10096904291722493183368071064267380357661660106693410869782248738635339952029780296539828646172395134010176258872559248732741423552501907091337488535022650906084259275771532963008605081632727310004012388176378536060181935481315268687099524445976260304963174491384169963045142817764845502919067852341670367757214257530633293876394038000350905620840512848346819593805771248299327648920495911888951338828154665350353011028755722053225038368211236471204894130005662338828040087277653058053926026954188748978276428965217873579228638399408512216051253190389034963502534563472810420786777664075947493242192178950439356302457015948704092615392563507116646622139031277627186004366940766141012052387764963550498137526380034475497296039349645231313666622023168074000757905961415842342549436827136456191636706102191216058665157997484620186504093031595354885464177047583044817527035079867175693262594053326482246251372100971181835929117940968577571250416834584873665407254954117674557725158296520696253051564213291342016830516195717769009307399800985739314707922476435511042184118717157710123856432818413241079127700236873849278099459856806348919726613157276845134234932007694512914360885347631604498444654808443385936829467322014251107608292907841706266154583649605962409356906673289214039345980157983585238598611007015744123201308500000501171750479205303582207819895099792053754750437003972197944606653029649026511175714325665022972458270451004669272442201984239750747468526034925512545591753011926422349450964423576514073138580199215901274311120011401651594856947935270421689304827295107046206967840957322813332397883867061874677422607993141403436835194178479678002082797785957214499969042437649907039865138475341601851262738461348829498716689032746766421448268807692569878289178989757874505465513706845654082199878640106345757795320020739808531463815126727793408754933994363877756899864984281822553007221098602810615408658488405255740618942035792348576150930466937442754907072240355711448059483670791970963065005273062169924072707136909529672907160105055146511078451274809649030962702634933950427417208754579558886670435513091693673392184012357060290800383391444894054478864880104489516105493654428700350038712306497215399390236421973359744231122582759112860245414994943705887755550168313104764831522917085274446816071187952611343217412489624486276718615486137440593087587611396073446784461983318011057978917824445958877834279858529200202638788438701918355676112013825796803683126156843171950302720509023656389038392904612771500795961428815515700691617938343841438201393483006625614378303192786900137915585090133838299336587186981703609917848314020827402418570324364874947405687083727868993183779937556273574979260142267138459345033733513139351742945236547818177589597395538573007069591004145636009266460791802852586248255385289853281955169539287181071240815317693402096387634696936821000809631189985664604670044343502290633727054957569135476042643752035180934112239281974650350606386279562906729624417142767675201654289420896239230816419019207223473210929276206272092462056393663617978292734035101190436048576301803958886273461936172885771511862036063913756041537697347875482651037641523871879511678343487920223572132145739383709173152270680681310792907045630147132642987006838913096888964072928407230377138093587963274543641998748031680910300484752483355961271051871764670801481617005498624008434455328965073448480620868102535798012683148073884828324180309706818271859159551486830624586719405678169003856743183359837325497215633938263574447227327183271417291639794183966954289906892687109652179007215463563426176830359892183207233285822949660507077627537452834236906264132679889387996620400887660540962057531356190936101639054478093742499726068975793037082183383865686389498095746349939423534144214424590382440964976484867660771427325735849308944235845015356241354445696546089110157687163547154187467782703339375797651594636517829331851603968540007770827383674978837195667966783942598590005707606899598870358218737372718556947211584091628920829232578301363561094654677362755304340099041557393126374570806664174774672252295969797311898222174146620044760522846344262741406020752321947103535566408000012063814621832503287764621196638959476702017397368768611288471914511970208911319812356033065360580161537672606063147955100825583445007228467438964318530588833314227952807420669509481593752391013652385527265940130738577518623923144732574439124910418367782835256447209415920224852739207102376107549910900016609384699171269913834437302619696395967407403281737973927596729463096846440722701084830141077051693427101822933034765921597611642383174592217106235280063364807994845967928868775308917858901963126456181289228987259157357205165107173015949882380826616387118049560139377785643404568749158677579677208043068040426770373946180960339686720961911527699043135729279627875429387003955052493364045280876757418765025033413409695324102028154397073950951401567130147958372561569250050115315916847340453713208876117379301986667758145971227712872147895344905202887742406317502743062970210845212570078375900706888423049419555978420360921631722072989494341411138773004386281045887595369408041990902949518621346831502701670122393407384031882407604009301423213075983205272951905634691701992363763765888174623813887930919348488342067724581729853334984081939086632732434453956218768468183725430125421255133039599918534162062203667355213720786895392466152263818029440258554305624849880544213626390640948333905744463929627653854612119535445334027593407956380447236951547078528959161595578692429043586756439280569634716651582120200055321411830495982390826367621607002210296561627357116758704330413920956492877559588940623076249085869711793382001280098156479042244980992199856870800160054773199711318857550253043892154687359419493836459018178858912353349265010015483995639971814634269831053349107064945281072025876791515512079928334870219925857377191409571925519964876967440971512831998547786258887266563455459842692713648700908802193837365344293863475229662378317646816581703457458087022086456107898532154008695237892810276905079816989491080554325994079331146736778976547365594121259003534473921615596015201516355517406353725481606002913150708780327087476617568081058821630455774175060733600369172506996856463081328450537659429232435723045704083403070244189764018093741052294003432036465533377161762848539600279097402470862336866023549397815233762584023941563793660829256982551259589645533178920322179582797164662459946595598265241525713404577113113372646314182883627343354869741769162896070344018435127261845682850523004349904479262461514591088185144460723000848892643437542445798485359801018860443
16: (13341 digits)
17: (26681 digits)
18: (53361 digits)
19: (106721 digits)
20: (213441 digits)
21: (426881 digits)
22: (853761 digits)
23: (1707522 digits)
24: (3415043 digits)
25: (6830085 digits)
26: (13660169 digits)
27: (27320338 digits)
28: (54640675 digits)
29: (109281349 digits)
As you can see, these numbers grow quite rapidly; the computation time also increases in the same proportion as the result length. It took me half a minute to compute a(23)
, and several hours for a(29)
.
What inputs are expected to be handled? The output grows quite rapidly. – Geobits – 2016-08-26T01:44:19.040
1@Geobits you are expected to handle as much as your language can – Post Rock Garf Hunter – 2016-08-26T01:46:33.067
Is an array which when indexed with
n
returns thenth
number of the sequence accepted? – user6245072 – 2016-08-26T07:05:30.230@user6245072 No you must index your own arrays – Post Rock Garf Hunter – 2016-08-26T12:55:28.847