Thursday, September 9, 2010

A "phi-bonacci" sequence and its consecutive quotients

A most interesting sequence:
"phi-bonacci" ?...

X(0)=0, X(1)=1
X(n)=phi (X(n-1)+X(n-2)+1
if n is at least 2, where phi is the Euler's totient function.

This ensures that X(n) is never greater than the 'regular' Fibonacci number F(n)
 
Plotted - the sequence of quotients X(n+1)/X(n) for n = 1,2,...,324

The raw list of the first 325 non-zero terms follows:

1, 1, 2, 2, 4, 6, 10, 16, 18, 24, 42, 66, 108, 120, 228, 348, 576, 720, 1296, 2016, 3312, 5256, 7200, 12456, 17860, 25200, 40256, 37368, 39600, 72900, 112500, 185400, 282204, 364800, 517600, 805392, 1133988, 1939380, 2788176, 4727556, 6819120, 11539840, 18324852, 28220080, 46471680, 70297856, 77663160, 98640672, 173595168, 256221952, 408844800, 613907760, 1020322800, 1598868000, 2614401972, 3650502240, 6204873360, 9219832128, 14163287040, 23375208496, 37533203556, 59869153008, 77921885248, 136242824256, 171331767600, 280988047872, 412648088320, 492483317760, 759235553856, 1248565926960, 1825274073460,
3073836307872, 3978113132448, 6636847261248, 9414599018400, 14592172745040, 21479047741008, 30917830052736, 38408764197888, 54378496536000, 87270536994816, 141621640558420, 204978069450000, 346599710008420, 546415414612848, 824321653496544, 1273505666913792, 1870492091981184, 2867895918363648, 4373894096409600, 6668851027668480, 10968365961000000, 17636075809822080, 27843753154417200, 45387202021338100, 73230947973152172, 118409153326352640, 180367154164239808, 254678263217828352, 435045412842323412, 548124775676941200, 842636741843358000, 1390722744163952304, 1708934349714426432, 2817870085343980660, 4417003071671688960, 6704422010436648960, 11017446803061533760, 17721852339852796500, 28739299142914330260, 45464030613091983360, 67228835231231593200, 112692865844323576560, 179665019423334152400, 269868817170145595952, 449533836593479748352, 492232503262215905280, 940874939171119339200, 1432038650263363098768, 2366552259677947257600, 3798361623352915258596, 6164837034286314140400, 9716455148226400949760, 15881292182512715090160, 25498110275560635245568, 38945318100310511963136, 46167747423734483712000, 80197384452172822340352, 126365131875907306052352, 164857495216710031209600, 259665895706983607584512, 391867246267885017206784, 638282796608028042465280, 760726185508366567142400, 1398827572787379613919040, 1851033951744453775745280, 2780629528802265111834880, 4631663480546718887580160, 4870296952441164810639360, 9501949474279200560286288, 13578576406563154264768512, 23080525880830668684247104, 36636512525083302046924800, 45696467585332738772357760, 77999665367762564986688724, 95544599246167986511168320, 138835411691144441198285632, 198906947786839890550305600, 308548134907722402993160704, 307205703445151052367752960, 452716483320177963134976000, 759375650694251273643417600, 1210895279677466906879283840, 1687408961754930747342831360, 2897966167917708234222780592, 4198988427157076689437753600, 6674949322264815247934427600, 10873921847521312696476126720, 17531484476082762052247321920, 28405406323604074748723448640, 30318621103326437407966003200, 58716260725692622820577495840, 80715336249593419766328120000, 138867853989425882577034363200, 204615914976825579405376601040, 340019625335692223951918949456, 516978972882111157518043566480, 856005552333425857273589441476, 1150945835032145575321156177920, 1564734196797810877102235811840, 2715678666026624208798710093524, 3420097296720760025649658982400, 4894780911965323171900566835200, 7057388546486539688682413415936, 10233652872746911014578085874560, 14216989801267359971991112896000, 17733019776859291442208659251200, 31950009578126651414199772147200, 46480495226644489350142280391424, 62158007546211147073048654711600, 56847317174037843272516890252800, 119005248647835946972173239176704, 139608113315150339787228313958400, 206890689570389029407521242508080, 296998960115461158837906278692608, 490271010505151534509064615220960, 787269804774130766824393094140176, 1209445020345217455682692563052288, 1590334965444748023312407678515840, 2799779985789965478995100241568128, 2925844696771851526432974478546688, 5687706580774932246626117404684800, 5601346018677162601796023996809600, 10402154765774686112550747590057232, 15944447276022137095474643278427940, 20469848828115267195892605630720000, 36291684868106092034995258917120000, 49050392783540227073970581097676800, 85342077651646319108965840014796800, 133433861903842871817574602552000000, 217739086754585953283424594553648320, 341451766197802375848510779337523200, 479222518501859172925935060397482720, 815639468563147563858965121980150400, 1109881703197205446710862977849289248, 1916385546721076028451318739781220560, 2579883232775451120332008679128666176, 4473357831553303913459364585432383488, 5397262559078939045808035177913014016, 7762657391954305192139161720007524800, 12403983274747394628369631545637344000, 20136987799922970619263033148447340800, 32535762018951673016922302493877525572, 45148070341702224610491318811082233344, 77483885804232986944365087240345392640, 98105564916748169243885124841142100784, 140217884153584952417604045790742376000, 190658756689169353393927827853664719360, 330876640842754305149821211269571703492, 481417290029307926790763345171052849664, 795011081279039631260997650984441051980, 989838489710912740668751040798834949120, 1617403075991952074079228487422682344000, 2462313918955724028879876298289589120000, 4078769289419861931924117472655981185632, 6540901849116066103962571924140585396576, 10253453946166860827809888535101302893760, 16727918345245641478969945251292484355840, 26978739191700408241700282090638264383648, 43706657536929567377924108330131487496324, 57751354865819091193685661047796654333120, 69569737126474259129042565815977485739008, 119932276313116081339642368313047671418880, 188009871601483329857449902190196463823200, 285857339981724325757248289555910134759424, 376381514015789396140560325250211180736000, 518113067750072681075469426372976544256000, 879830736163143026769865329465430549172400, 1378793888791116849088571558445299604353952, 2037621046121669623464721223176719430432000, 2866921623703037599345420516046449539678960, 4458661411300660098513166832853742523989200, 7026525424932704626497783936102833406312960, 9294496654453114075443963261565068232281600, 15462020917312880875523760503053801552352724, 19804776923767720965829451393909506511776560, 28212245957201234674350738313653940457141568, 48017022880938949121610321557576873547309684, 68502643711931218566798802222620216214176000, 87732354993951625545310898053526432955059200, 143851481037889174345169383327210930200115200, 198500430884434971334697384040632025561578052, 342351901015198442045769632388519683039234784, 426104336732823914577407093527191019192320000, 613473553532852683531843223569048378024320000, 1039512511508814647208035339627758726485982800, 1652986065041667330739878563196807104510302800, 2688942685321612848154522276274674782925971648, 4331097439387373572423359899827044952257408000, 6596745631255153423262429506539749762418816000, 10927843070630788901244512268430836629871992404, 14018529015515310122544558383299935413914713792, 21382603257512951554193747403213202434698085072, 28256927147040671379494108680473583295694962688, 48622221292740944068439345084028824219562104400, 75952828048281392454886133753255280614959574400, 123175129608109054267752935811352182208627464192, 199126482298333290236988678164687038759586080320, 321696011891821379455505757347593721586066585600, 440768403763096537817346584092890833054757424080, 762385388686802432203817381849374218717427200000, 1145588168870817230587496893082337804331437103104, 1477424221847411945855803909409755681831222272000, 2098374838188828264714204047177748903393365368320, 3517078762310592019459695252915202575529821143040, 5615453558523613862220350021332346525827209643584, 7295169949005151468500577274207006292162932006400, 8667150864796501932470223011247300394808932884480, 15411895958153320516056127121281250511408904722768, 23928151222846763745934104482173048817842528915200, 39279243370263925844682070220965373742406427460960, 63207394593110684423602001863931183761410529605424, 81244525416024931500591076069602189991440729496576, 95817353975909051768811488880534700177770684428280, 170955088343438788394062195357563057903173612034960, 265575886780846007974779207294829628168739757758720, 436530975124284796368841402652392686071913369793680, 702106861560601016838290943328470250171888726308592, 1132056115085551213130322286907204156671858721254288, 1222775317764056320008385893873417139025439181977600, 2354798473196973177722397879566318154933594861768960, 3064242232824320614382419692694147850894432318500608, 5403049720021065139458079278961803821444103126260736, 6644593974278601883244354913693533005216456956294912, 11496553847261466966122321093021349119203685440197888, 18137337897007537761396709129568733399503631337459200, 25603698951338601309397487490882361543892721928396800, 43741036848346139070794196620451094943396353265856000, 69344669445086214085853084245407563662209163944723012, 96757752327508587582821145498967645376582178999859200, 165881942216214714771217503447109738999123689630537600, 258937668207148912574264693253899431781032287798508800, 423242635644017653778128217807513910870381763205817600, 584725523194283502487907023200390406014110226582051264, 619736338186295818547485819769314591558940458407183360, 825499364501330518443025833607416345518462684884800000, 1238773459441313639419410810873379565481378889130385408, 2019667683799614896197644656580937761746170003333987200, 3258369616912955940494646997818163857611476504299852240, 5135147380352942584544849231739174257846320791779082240, 8337123162180357633448852736294834704469304069682880512, 13458395869351074948818630470516071498042338481179738400, 21737086004637246435934326415371734872210002758501056560, 30157249244947970629641413006425219807513792903696301352, 51881524996499661593577325267409939879753486159441936100, 81736048137235648340476233704559015186576255893163557340, 133498613105652055023137257801951467487086371339638272000, 188644760423599405753515703263664751744852020200692509440, 319230017170279402584182075246645645073628778859255588288, 477672298882869442716236187809708104727004133636790630400, 796902315332379982445067962407815667158759107507259721536, 1158704194741135841055731045652294338077966582858227592660, 1948648256905222774940312158509637046788202727042555248640, 3048723159725442925738129031593370868705794168864739414480, 4693289107318797377544177017638486568478348256314035128320