experimental-projects/oeis-research/Lekraj Beedassy/Smallest number m with n ones in sqrt cfrac expansion/prog.sf

#!/usr/bin/ruby

# a(n) is the least m such that a period of the continued fraction expansion of sqrt(m) is [1,1,1,...,1,1,1,Z] and there are n ones in the period (Z is 2*floor(sqrt(m))).

# Formula due to Lekraj Beedassy, Jun 11 2002:
#   Let F(n) = n-th Fibonacci number (A000045).
#   If n == 2 mod 3 then F(n+1) is even and there's no such m.
#   Otherwise, let x = (F(n+1) + 1) / 2. Then a(n) = x^2 + (F(n-1) + 2*x*F(n))/F(n+1).

# Simplified formula:
#   a(n) = (F(n+1)+1)^2/4 + F(n) + 1

# See also:
#   https://oeis.org/A071296

func F(n) is cached {
    fibonacci(n)
}

func a(n) is cached {
    (F(n+1)**3 + 2*F(n+1)**2 + 4*F(n)*F(n+1) + F(n+1) + 4*F(n-1) + 4*F(n)) / (4*F(n+1))
}

func b(n) is cached {
    ((F(n+1)+1)**2 / 4) + F(n) + 1
}

for k in (1..6004) {

    if (a(k).is_prob_prime) {
        say ("a(#{k}) = ", a(k))
        #print(k, ", ")
    }

    assert_eq(a(k), b(k))
}

# Indices in A071296 where primes occur.
#   1, 3, 4, 10, 94, 142, 388, 694, 1048, 1162, 2674, 6004, 28990

# The corresponding primes p = F((k+1)+1)^2/4 + F(k) + 1 have the square root continued fraction period of the form [1,1,..,1,1,2x], with x = floor(sqrt(p)), where the period has length k+1 and it contains exactly k ones.
# A071296(n) is the least m such that a period of the continued fraction expansion of sqrt(m) is 1,1,1,...,1,1,1,Z and there are n ones in the period (Z is 2*floor(sqrt(m))). If no such m exists, a(n) = 0.

# Limit_{n->infinity} (sqrt(a(n)) - floor(sqrt(a(n)))) = A094214.

# Next term is >= 30070.

# Also interesting may be the following primes:
#   3, 7, 13, 5273, 2081, 25106293, 51661853

__END__
Prime numbers in this sequence (subsequence of A307453, A309666, A071296):

a(1)     = 3
a(3)     = 7
a(4)     = 13
a(10)    = 2081
a(94)    = 255047841168018789173346620877833525377
a(142)   = 29473731022709410162052905511145448845668953376836066564033
a(388)   = 195593365196912313716524147019225451522324366282451849920559958333100535573278778578654532863303339448133509588848108826972694691981365023678441930419852836972557
a(694)   = 15552132648108049482693507803715379194510097701340889749400617558045366894317549608277047372881266836650083208497709104068747637698951141080164302867204934003480763077698345316458718559286355664683913241677488087709603522324743179283839100897378964892978700917072125934196394213514095601377
a(1048)  = 142902309875467404691614503841940291665956434333124298723222541026088891219151208556455626984708510220041186516587367171232549167949246139701864651145796674351390310809601587057107452298509663153270694766083889896617535263557227242023328861805342606274852530768068047684332911946314195038856947376218037174202086945281873751629727761791416655024910407170414039232524842826822042463635543722073680948723124895174193193515405377505138376477
a(1162)  = 63711998157307337014753370400017459883154167053721944327218557262564804388934168251980184195177874917134346451419522401812477754484812759558207026202093553443600248771793455701601665648540909260098545270779710946759709446107835575319778239739930472645118474531336503707360451381763605256430905810967210924450569450578402378381300062916886711326137183236137763873713575730375630342766524510161115154947545733358330670252844881381842863113117918278314274041200520503643934224921539770913
a(2674)  = 6065203008490500320588202802464856612313469903518658311078974579123533674215754159161693940977061969990492263455521098912043807576557910065778957347026511805329812584739685439690452946026734155047693347177576530499238998265689716015943293585947707681075646437988164775680112826231739507597546863528741923720816076747489239931452753422373013850796283920512192128899329483628592351348141074635724409232440380872462915264131455067552617356564155172735181839764226833434062585190553881051959550314844607998190222222620318080662812898536635268788407144295601408597539456202581262889747417934050993623839049755329364361920837733279552764302703589888367578234291430782300224887501091548368615811164105021791139744386171205306779723110521639911321007906155961138440325941440668397432208544058713860982535838593581975516242999927340832327887685495596914280053797160107247047072536999409827735528950210463213879964336191747940975262270949999334802352498039412910165905373120492590011801783564119841128263699001222076497872422955586838029331914738385778276780148559413506938782171183101236612578972527855440502023975573485323777
a(6004)  = 4370482711116034540359575761922172244727063781962247087949929267343319212877052316497392718553195158315943502730938718470659655404687569532551038572806384905892358608853947457521265953689034876039150967913841817413861769004816926204754567690748919346404918156527869782875866664252783736042301150490240161234508736945351317659561223660014889667919958976163499037023224884165554650715467339103936550365189744161087036699258021262607318946286929045208765647638205543350490262587664628870029655307199177624026022919610234169987597657934026584659305906960124343314847893381559396081256018478266608279779928283770782444804906240871978893493203607695593387695905346908712028080123701820328809123344143655064862662210674279531600593333334599750715575335690234408892454374531274060118218083158223234602005762149012309520119532967225352994724869689400985624421723280207277099451498831818378655592027650786573814639921988713863566766526613780457642646484071621344495884928616467747003308410501034289527517463666115296785187449835151325179666761365819839165551502509093582698095990554945355285932969760698091034174318763785185994858564866192737204380390963511572155063761011125722740372091927721849924209257670926749643585618655871854988594187599993773374889285563377507451088542796147492324722719008400136110862528567731019363895084567051565376033650209330352786686282066812825786076491611773606380269744433747613943771713692543851228336710145127208527416946333483713739326034895054797663638316763011195991672881797581939570100176955485627568310861874937547020376795463091429552563752000177833044942670956424894138651364185647161616194246057175833449321291603201594864610490139836666953895561822372576894052350250678758611612903525482509244279153276093064968550696764670695468774623909605309147841677941317154732477103363708204450476875122296176929165379157935760482442182904472425731406001556088452518779595485254528398139628577108814939444952503431335616563488057700189266846433094916506404755216825220168288164478687495342536167768678380429126209934346895420033533220068958076423034247175720277469879840249168743124645021262686226952408854646209054983861147873793048927954024055122505233732582867381818126494155185821495195146774569702488225868727398528217753161740532464690058849411225136860578005199888834159786497744156557771387041260537869787421685263160520483459801897387078842808879295450637215757044895500219284334716845196660076064531657595450804045057337901689405859428210148660082713130343049737979995840013
a(28990) = 166083687436480004434914131552351117809927510262249019153635386057605770411649158594272923787871307779237284600495434509192174501108993738730636882631421159974291424865255009508552953967377067012164866656644265993077085893577050590588017905315309439930192532979679731769872336046543794540742472330259415298877578138866330710847211650866554400460289191201041208076362380635340843884775434252362721430100507208395166141143586457335835753912867801522073963622138368854618205870544988537527552408732617032608406009590457757490707995829044123822562532306609666731532983317485148139826000814110280885973591393696753887694565928587328504261236913840494188273388325622233217185184454968390238978197368433211720595515197313783723003348474726994471025400374657745103481435925426436109866404870844759238550456698918741333557626470075067207328412097762337642717289598602527958680698875441506057729408648412995782719244337377084913147200647159246950096510040963236321245368612470652429320767443422875504922413153155228390375146377722493362543628335346617957063605635568564443966866537591112497633567400726521692040620658538493222558413119934512159401250346013248979228010817650470249702462061646625298560380184454568804452684590902120022637076430219590633721184122026222390806821993490526548713887509149372796750699473408856506191979442036748978856157954505041287478110976256008337791213874963135702077138157805626674320624620894017702114888967575306607888636470467284348825320564623616003292067589150802750794994181504965953008768842013513280185217522285183049125974217121709053889956659232788014469909012110119550259936395204068605509670605907418682835150022224436196680733478194955700003816798630091128059543073630493089856540267660326800148998314243370781458815533138155782649563740793064865187631078134064749901108743091551374528350137457503662129308602745281125178110611790482682363941782500266118171357823452666938681919062113637092665132837368643233480491473914044147335867226196464354465668344860514715713767658242005106663123751117865793824311684014618437139834949524128935777917619542837485804918039284017233773124628909811752660756307135118612000529253355403181688459785762345146651630022217912772604267918228549737177160408444880802999822953856845144242606193007895944216516722665490712105441616355927256442192013905681806141993191549427343565770883807368798953962319853077357969266520300194689999105211516431957136226380970714328016549911574662129402355854066524994188433013032066273583570026395515470705777637648875423354085492084306016914317490652273859692293437910862157202361867047522539891247946323259543226720428922848933134241827010195534556896901689426876655050724883548497668960969739039176511128391555969802945537212953212112198932119641045402817865668284212028957110917517681748673581064975409036718729122729193597091599823746834523986317263882792922460880074440757341579712283179619384010401151283648198535119138806927572179885712058246757947362286400775866275522816044755562553202738588096692822020911845939840921405813843485249967375158344349310915052854477678058229119698247989199055509060935501628769898495808075326883872865781606305043696769013187315711794988010566533107022248411330837931583031857322953322228599454548312556810756814508115244018939511514398591473559639778072959141083755502445124765220564450074147766474580026368505315739176309520121131363612281249616231824708889329432764786987037259914399276394641995758377750271539451369187162261992590563165779270007548595363522214992017234734947212997079016246827793179266448031120941332913795718600018943833504574109361658328337237358339057700018718737471369484021178548579411843067196983019768753985818748980023027703381616084135889867278484890602714008856814599693764965230749455155749645149466662483582935760839587850047307529474764647282600032197707073798187370463518100085397647763336114418002446078199287830248623432510628574596839522816713791587362055820674655696362513823814033852707328129598453627348393172223610093649494271696506610045861105571134215584450949867416434149245537868297485004925176250229314713408845092740686292776772709637991561327283698869016958895874922389787838616478317013521113717471147942089833226514623270043582038186554674881006971043560800550063170904292506774757293031142132270656578524908526493503144958943197069971250356143180397933517724253250644135293486390939450746334641019623380771200466920887025709034812702778879242231628005116136985274743420292903071639013729730038562429830360421725140936985399170145404509768425091731699536025837887949985036813666432346796680553023579588349181042590251128090453433630086680827522119912378642314818110193939114868026117808632043952152655304626157628437429017332769939145770622065379317512566113543919726496763162394483188531441250897645282375396617587351516353138601759163877147059199372154965490680322529123277226744184018832096287255574262777130007482055192972156969650993469018629846949038444694783050729362942507824280462201748143474569387977032196796582042609802230747950968543312485984288088401463958513496555879499047415747480098869447680372421955616518270130845593819169620384051677639717866780711572018831410801444071168862297895905797188304225189476050231698754323906849145168621316814421380977404846662113149881719640213103724446318543521358977246413835539135379103019401244049163984932147429933114490913499845231974706110463560170245860997237739149786653642506051132155852212451216586930936829427615791582546821521578490667975626390674756784535329352717112091354565223034639351326016970459517662625041196178722601762252716641691093152508631691876887162870023489645412507297294509968476492534145984438224920835221494764415577732588875921779891023001792840505834435538791366118718674518266948435791622868237591553344756383961195123497250166915440195578742793363933767923347572989910586255084922270195234383325387614340137954602396426110356104017806796012700596678981597754355358092019762489717343668006491784354852498534600555871168426747765357952276107457598355096449318581009965640790109909915527369592872872016404932410719886956789883892155656767992840451659179081978957378865010085614623410376042590304448234765140763443395863005387193262831942610060816912053991705725114236540655130192368913936123101117822551855462315197647920944632759687780032561325797016291765814945225296963859180525075590008201322413808172303687287145792494191178579261022696239676695385162358064229076847362310428618218206172475738245506365269188980758383825313610938592502711565009502449294216031166582726761265967596754261299615186473762541771780351914527895335494752628350285223147033286680953773399506151585998761780949364648226573862900942626680812571835136667689185356861009144595914789992426924108114980462362617896652640394628040150714868708587204940827409522520649277859173423907178401118861191338455026675746726769561895820415114109816402135349579724880256721477532761548808479285948822728061284142497171910526442358784023151380886616731024582916565160265578739974449282005382687467738126369934088295284257177125250162340540124867285400094462736603529721121628613488805493655487511232108381783747643742849807133076099976031304152435833669832730640122118645473570683146364332224058417022783862291944951065894327575437535058173137709827033660908763913417519290616186616554794086872059850510754487472528804324059250834352765990633767893078481135574598621913896232452131780803124230092536315807780814912298562443156352049215187128873796149435523046289182454817348835666533799946404105111407117730667709011246459389979925212287856211719090406398620405774493771411031344019918337958423254604338398984652204946695688514475957493843419589781907355372251069526100061688726029647067956387218132814559610917784141747486305393169615518180624038918171368695857600918621686880664924232714534544070686529047641818733581588606222489100496435901411648897974292406155103787881562793048957308950214719423769315410655009233814353521601999439436131057168958560156855280198296805736051367331767576398151791051651434566957528198599666167360132715560603628037896478383020605316031842087586614054873254157444189745349718380262973031577038487456860432179351249460273810502865616567281791926910325737344922350171685754977063009628428355265101944895818258860452623018001316993925655886126158044811354143320468660371412362263601007247540578947709054156665549134312123625006623064133863316943163888438676508535441307069236514805667986905353558830472905704263033200485737014316485869802405544388617302722915881446703584294685387035839232338729042008052571212372186850281864094135333769540719970793894915995551438059612739633739626221337231835782516622572775321743799798275961008283311775298952311757810586335940270272284296079359939652668711956690583402222351011900270573672029611031413584762980768883808546522032837541989686338488604320600571235226320752452667107211208716216950072761174742292221885369575578149142497678999469850388302213953242597624654295896828247466568074996503673612586960132400057982245265630798749525697538600569049244088224543330768595379888867676969643294373473505961445537924277063476282447224528949502141635811349776088122746478132304930709380176776993858513309015493589859520499528064270533247742626964501957601261810846475649798833777479939453751497685820203185393581367530892733696277760001092818674687780797033927274339616197298140397585915790828695362539926467556203230172309662311744743586486710232691873747227981175564420267620966925653925555318069608252040643219953019393079491828888551452830774889873220955936317790784446143784739008578975448618106152370319719041269156364343551420114176546885604754060852407450140750548210885055208734171823285163933939005370975738311004021858378439659947178352112101115451374829586235582297458759672667323899793949532030769037327965516146643181611655871010412966311966446379996082517480208962414907597347181983466993354962601407614296116355561764171304081215807491075839601751099865343343845876517206430692814179684203057808701939310947872987195760859344217550028122912290496330590679348199388525744307992981220609307649973263730025106345486735991008685965024065486064181303707535499780782242659108544279795002427579532468369028316941956367159758832999855625510462040841872124919500491699999700854357341613039806064266477937206003928968708669526452894386136684004514378747853393612980084057303597626748865167656380304109936372585353138016973954228876844525682612954756309970944677888491496730238941787794795288513183429693236938909565055225996150087813591004198202547110195076183974517441644057031695745220259694094704494185788252735409833723325075850529946238616873840963766852789324498814020519747482246741236214415116611756381381747320220619082512275876786258171987727616510864204330079591816592691441437167608279655383743054898251604915292686774901622288019990245927772492834307565792965259228713445040595887888000914183388033185982018914522292359354131307838396170656177896118263325384354055408076664471803338836549470259132712828925535922189739823345948560196978190030117598018995098262781173633564199405603588392729557533486950449145891401249842351610173842517311013054837738595924105832058309347418194618146802920221412010720328020979402663176155441895828270553681908147185555140333769359699737358759373031663784906279354061838177595536175419595238122740348837663836754388523348885914759070486606879705905235544452144453710911312584765139694497445134646847314705455253127413640616024265046374533753522108290784013846377430583272371683297362671257416824539833594425541719907559556748814268559822003360492479222929177050951241671325535199029394436423981026102425313449217178916086407363514369652308167023241548487773851041148907344549331132976164433324340533530887226195834653847831604591087693434713687816269204750396885664911408243585679981581538778786437423346757428572096850263887033115889570694338055069741796280018328591040266889267288661874244694333950260783562374390090411175273450835372091282810237032008606029534127454750611967107221062002944912955143226138005946878379567700421968144327295555967543251582721