here is Pari/GP code to compute and factor the terms of a generalized Fibonacci sequence a[n+19] = a[n] + a[n+1] . it is initialized with 1 one and 18 zeros as described in a previous post.
addprimes(...);
len=19; a=List([]); for(i=2, len, listput(a, 0)); listput(a, 1); gettime; for(i=1, 5959, x=a[len]+a[len-1]; listpop(a); listinsert(a, x, 1); y=factorint(x); print("output= ",i, " ", floor(log(max(x, 1))/log(2)), " ", x, " ", y, " ", gettime))
the full addprimes command is given below, providing selected second and third largest prime factors to keep factorization time below 20 seconds for any term. although the 540 primes seem like a lot of text, this demonstrates data compression, compressing all the factors, thousands of numbers. after addprimes, factoring takes about an hour.
not sure what this is useful for. are there algebraic factorizations that could have been exploited?
the last term we had the patience to factor, term 5959, is approximately 5.096*10^95 or 318 bits. the asymptotic growth rate of the sequence is RootOf[1+x-x^19] = 1.03818802 , but, as of term 5959, the ratio of consecutive terms is still fluctuating between 1.03 and 1.045.
the lag of 19 was chosen somewhat arbitrarily: we aimed for a sequence growing slow enough that there are a good number of terms before factoring becomes too difficult, but fast enough that oscillatory behavior has mostly died down. the last time the sequence decreases is term 3686, 5.0*10^58 or 195 bits.
for reference, here are terms 307 through 330, the first few terms after there stop being zeros.
307 1
308 17
309 136
310 680
311 2380
312 6188
313 12376
314 19448
315 24310
316 24310
317 19448
318 12376
319 6188
320 2380
321 680
322 136
323 17
324 1
325 1
326 18
327 153
328 816
329 3060
330 8568
addprimes([15573284902449268810943222803, 10413174605148708056451303311, 14615238098173461393253725840881, 472339427526480933772911495016927, 14275910086271654116507, 10862908518844548850421, 33708225281463224437261, 4062808454135288716284118213356701, 55193835546559292729, 52257033966732559771534801, 551588427458158296343, 9096258447932786378602967780533, 9490155319722510244963, 18637446533813399844882268305925643, 42642295350442551433, 3912307617282611157527836548478807, 158222972677373524937, 10993030230200853701356104127951, 68123247728081172526014212061599, 1147180538233638296823904291, 579708133051578303991275896370533, 175323338486423103173, 8637348264075326240969, 520611298062231830398319, 27079712185341662425157, 6266843665591071481253558393, 626754329854654320468776359, 1887176061070031579687611501, 20701837120790979879578148389, 2379224885017418758306775917, 39423993552958256495347117, 121196759664198690673198117, 4024789745373199082584094543, 137541029406701085803707, 113232587595197102251895177, 11384082965993266236417998531, 6822733929589424540911596062261483, 31120709930262015525189088132546813, 164863394011399419445146727, 2234285343626568201863, 23719987729866370751, 459689100695755393717478654459, 253819900707989165093, 9812622887014520907468366232087, 674283422453114557012660333, 2892771937851271243019362718371, 361948810464890952079210836740773, 556358243829623462843657650348109, 318701968179322245734891, 1823932392636874206259, 76116190777325065357073191, 972164249930469892447, 15713072519005080430531981, 1370562583374661889533, 119116878413074401127, 142994297586600239660533, 259834310996040487495403, 35228581948200841553, 30819947491257269970279023, 1053417704929839163982944512893161, 1472839170425709529631, 49059609367739916142383323, 1333310589650202058336018771783, 157506960347827580505373330518563, 513011124694361993921477, 7523755140726156571114749548717587, 81000209015925788802657466011901019, 495287087748272321567625719, 904680290722786469744107309157, 6485276629442576518339, 4056416281008186056268445693, 744431173779360928092313, 140113869309517565963, 6154860461430585659983, 4699130705070494022953859680459, 1281739122827492278978477, 86054096853154442740103, 5210631360100057510714111, 40031143898998908087253, 14235754355488765112859248939267, 108278739375486923024263542057911798021, 195245990167477343801143, 68345710783508311791254106415117501, 1040602165643709174431322923, 638808909059331990857758125836702954221, 4145051603065729084229, 24603221847006795437839431787, 1601538314808193346591785707641431, 11268321001066943623637, 3191099068430298559843670045807327, 11244037467258377486445410603, 60804664355541620111791, 169381501694356998494202817703117, 12217851294023882584669, 1450670492058102000699270847236469, 1468290403804451147030752894326258444697, 173425874475121403465725826596939, 134393312651488415084795394874961, 25185177627406031074523, 72455973295133357862169, 154318826605082317970937618827, 20454927994230000268400723, 3656835271907819646727026762241, 36324421960094775434528654371, 67518095590256102022800345603, 2287253539189785010242530812223, 31418630279938339703, 7311489684903893383638259, 311963596378055054942439665177, 75431720274848178409600667, 134731382929609958533, 358684700306895433744610287024416553, 3212873792957373852809779, 1595778007863910396938426510179, 135703215213317719619, 450005035905966435580871, 1969134065635642365621061224353341649, 219874487211753059349262604623, 51124812181674117165997199, 6460006885750843717217383957, 295937930622709838059, 4611829958874423003190061608097, 1866999539497248867170897, 319224334475166870109655562612966388211, 510938412961283708846058554995033997, 344089790127918858337098363694798883, 12130821188615809354783, 1018964463583305243597462629, 4248925230113393476335506267, 281113078682046739049086939, 31504520761203420738953773891, 1197369149730741050762309152127, 2911985188743536196667738098677, 3300105769038717485713995043, 114605774561558655337, 7625673097666658459439787, 58964419750808194026647, 5427378791300264780754597169839889127, 89361861780749808947, 52852007701595725145654665284083, 65176744787379022786245257327, 528404741502705131447545986632663, 397669649113653546730682767510277, 79670490904451407934664374851, 31606967386387966248155067767, 422215655538503617608079064541757669171, 8326641545018562594295827693535351, 68824667547307053636613, 152881217181853299855058843, 1017919059627196878407, 148147685398679583829, 5713195278032424569381374866246706615547, 273117191452761636529, 2186966000230875946992525191, 2614869060534088232996489, 282917562072246867508052040959, 42321992668630850873, 1655010736391563579728036317209, 1013119162006273980367, 2315153451636379894232017654887367547, 18615533028726722141, 10916172516055133508887, 186238286354512765511213539, 277115315480197604691422527, 5195516510667253921550468963, 120103698706244807093, 29600067644404016589148474246636297, 21701368218610915613577463590360749, 8845975500286702720541, 4713007749003164752730767119788309, 22916704977123276198784904506166462939, 7916446228423804180999, 1560805448363091752397020429323189, 31872771462711517051536421589, 81944523704186098793, 354093656867631443970833712869, 8252907169202325518717903537, 80988386182105467196241082540767, 1331229980572417308006571, 8204753182611383562214310481942331600007, 114056303747692927576587979262039, 617441505790951327224588190669, 23248738513983320688227, 1016314601064314154016792979, 112258770293296412789947, 77903394838838499806868739, 4837730852889800224605569, 1229134396327891145573235258028507, 12135934440902161179084406836121, 8243306463308406875789979301, 592795954387476198304713750061217, 5330695902346794152017571, 10776041958596187836693381, 29515154776812572517126586182708961, 20969269842382472547191, 69903406727084912958863, 25637551406809388859200295199660692277, 8892828987219553956423161, 1705670770149315973519, 15270215901160126962148823747067905709203, 4902550913723701126822877383259819, 4436472045123410257846706220931, 3245922630068362053408403851659089, 163442546229258387571, 752787503202927360610126967, 63780618273553517207, 52499657887760063305648180729, 120183576415411931389948118801446361, 41519931924256605802470294239, 708890340664056044270044323941675393, 7366023995748926083774438750621, 2579631937636906273267, 4605406182061593777527759, 173724097092938423868043416893, 103376456619686821783699, 10467337773274758931303229219, 684150311395671182198207, 11858125037327720517728042432888846533, 1882641361411532580404398101436357, 13711555994527463332572396671, 56284575843972236909, 134309765263576756836381880670707361, 136303373919038786382480712993, 213201547863655520539, 1708022167369578522363576467057, 1957100941407884264471610773, 75962394992148168197, 452467416406338590110158572353, 127572979727225982437595130366539833381, 3348995222159845327266183898375799263991, 1691780300518890100367, 122201045164980570888776129324353582649, 1541784827533862030199770077, 7405028499064986969269864871943, 8389850497302911611945213, 1115034799034927023318921, 1004881115157306231320753, 38564810413799572243594071875807, 58868477722872078449686479161, 106102363158829894521588899, 83564650502248964287, 1056860051058793709078015467145998349, 2310734102408179299182004757, 302666385880670409942667548677, 529822711285839715961749570453, 1356683826056621491783, 91394338414026734384626799803373080841141, 62109833439810603631073480821, 12934013674748001227920372024003, 1205151702822455494989433236377, 2093112174990804317169559, 150090546518434554757970386819, 168680701882881182828762083300511, 1355221465852026318739634087767, 920941959541625178533349129521, 31255415908715115199403, 17595148171070104416373447, 832119550950065512944305362086767, 16789744608759411625810853546565017023, 42022050996574224565985209, 21945041526772444477, 286632551027557449184014971, 98113361932076226751439087, 1734767444188074071111579837403577, 1650954271875071034138515428487, 394515072323099114557027441, 311724172653335034713, 95831810929332425970217130017, 82742156331480531964532122531, 208232253707374173119170457646349757, 1424128368733207215734570708809, 609001884565945089617723918741191, 95099006354626549372396619, 7314622319140181994905266613621113, 42913496335730145557126381213, 888746895903253553846201790701591, 10782969226508135319547623176467243, 10806657716724822562104497, 1283083837518181945571599373100367, 18927680977294936548329434661, 19673429865582362281, 569416538724813674463732503359, 26346685671083740158049109, 174125684469593828929, 468618263035386266860868809082327, 558733336725803173648657, 227653588885888687155746842871, 799678286199314239610129935129562623153, 372374882371619383365531981583, 1311276484580392290881993, 2373529026783612881474537, 22528668848401179242324347, 1869351582419831809921728077325907841, 2083116618568739843440746107383991622103, 221043466074559363208744549819, 4881466221603799563986405669, 19845324262341689454738245907421, 721937019703228336045657015243019, 605682061379981523360623203241119229, 95797416314495818361814654180221, 3411659612940113435038665739, 17044027698513779637536669, 42209352134754494719, 19923038892346251740532131338462041858221, 1112571228448112177571959962018734762307, 54961880471412009717213760061207, 536568497245219892351896971872333801237, 3232150653438433424737867035827, 3863541017999695449922259, 20801622009877172169793, 1240426727117069718438173855782922863, 1532534983937766829140321420509137, 752010276757310466627366361400769674840507, 2188234714851624107956602827, 742252699544167332329, 1304061984887993930989939619519, 412365894122267997917, 5151929274802989669206790071, 6223603175597931984291251094123931, 1633101535306230627052021829, 64401057821930005211933, 1010413603408116135096405360283667, 975122221520493224928733, 15056402010826611344842709049663073, 36015075141677010277009583, 357427641830570467719166361, 28142725035465231319, 74799176876656607716099735021, 3177584897390553756341489982493577953, 46211318228914792784398559632443465001, 50468065755423368029, 2268629828136004580219277894821879, 5662598309877470626961, 219809636993833129630411, 115145452467650572008241, 4672224596755119950731, 2801774897289652704321194398943, 285754304387462933367340660151, 4972379012782626787705264016443918721, 525739489699229054624929, 7159929549609182964701, 6108103965295164259733, 267270289300822080443799362668060530211, 159222199769422404470761462056001, 267092496584229751333866837386727732859, 406350612147780362865001, 1690545621048058107012457, 40154971039313715291935959, 8814763905298979238555173, 1396730146809430428739, 99069357388548025109, 9549716934329951771131343, 39178272237273701179188363579707701, 183616363151701179001, 260606549206483674665671, 167016091951914601935673078828937, 99102733917209474939, 32264265270053485567103684988890172610813, 34215201853364936105057, 11196725640061800327802421839, 2075896760960784740824837825824228877, 137291213400185610918970009378751, 32683379572704691, 277954371090770770291655717, 17835235743841681817, 3328226083648038051797769126733, 1677033631102045537, 218961181627921724699, 3018307931461341971075081891, 68913445784501125771, 27080727946080130780937409779, 12377720747227168687666479187, 2832444531814884557, 8255196919770852659934602387, 123457136362543044302173, 1038001422640221840738043, 16610368831602143642202825863579, 3454357856767475189362723, 152465401680678919263968983, 649413558647770086275994054797, 6461551633052820529328860287859, 23408316537126913852531, 7845645003340948233223857443, 96640574855827861531, 2712937571259446519672247247, 38432743772678243409439280071, 1150987610702549160213521622463, 277219684468236427225244050879837, 10389269374220923429, 37894328382438109606557979, 7553237917173419714857, 224848582215223887081215123, 2397570773087535074429, 128945213309641163350929341941, 1366978940481848142869087, 2393841685084446011810999, 119076523240346688250799, 301175878886525913521084887, 1594453633517102885829870109, 14996393323344924768301, 233402632660536344445371, 19403294770096754986098551, 39945025771705079821, 13650753298263391873, 874999557372547112834023637, 4571630908912168051, 7542427959102827251616297, 24662756782709464117741223, 2332307488154345965032706579, 3509508292813885871, 3097628646195111470435591833, 118192600023844974179, 1269600615937201907, 15472043257812712471, 29515019051123817793, 3902834818890119946157, 5284321093418117598435517181507, 5103173654026823756055242707, 682941083488994944477, 60151936339717921172881023677701, 1046193602275724360449780421, 25533311420082591454752191, 1099529792506351314138519731527, 661750441340559123541678382887, 260316706937682846497, 6171401361846117641, 4154613191827207051, 688328349680820160061, 20898218923918814589131, 1019583897647221633180169, 151301564462191999846411, 742219481836999417697, 1523877646696767997039, 18097324026933323, 112993552743211243, 2537465111395552117547, 2708600474532092579901503311, 7762303454457826781234871086857, 1010606036791544900266913, 16167980843043222897947653, 571378705662496173579239245170113, 101892926504600428793, 16044492718397501, 4635293839661848940031874226537, 1865778960805883672863730276051, 20303923644792486007203783247, 87906525082888331891225179, 7425611474161616870087, 31830777930303290568228257, 431738725828981211164961, 39744597592606701160913, 3096078186753339091, 92217265531871521882541, 60593778163877395427468047, 224437516093046041605554268097, 200799158260020564138137897, 740665477377978387074461, 32509131190057434683, 34731194334798292038971, 2069510436803002366163, 13957750879594578721609339, 265612663122736116917, 3141450844616600124091924037, 2125189248149275722649, 19874462531098864654789, 331300776025815220770053, 19075115270379596440276547, 431670751466458860839492131, 9597919372534570806731803, 58826430166074186083453, 8823809723843288583048142973, 53697585832629209529871, 45386809246168291497116971819, 382738307258157727, 108124405768303755382613, 24308918004732575644856717925397, 74700568231827412050976021, 17749619123669928309992921929, 6958650758032860924714506189, 368377976396593964669443, 774480134016017874081568691, 333079743839492203667634380399, 726475821023378241698419697, 489442158836393233, 40887605803603327277080201208591, 429824866224209322611063932163, 3786012862767888407, 2421124436075416566857, 162435233205514149473, 327747261312854552238484365563, 507705379970590121896035167, 25438558842935434047966907406869, 401236843080999714783889, 27564044046909750832301, 2158909529102418863, 3432264546369240247, 956924464648350425175737308033, 14170925434091129859788621871733, 73817181407519691905101903, 54817903226261101259650644329, 156593154911995255237439, 13320059912941399164419646437977, 110374475102719642718511759826027, 157406499205084756296617, 2182610308665842494947457063, 844470442796808612537531437, 1929552990851900142629311, 308410119101918035497481, 33198695688276885088660768861, 2580575881036959349856891, 76518173797929671841973652584733, 393080546191072767817230457, 171329109779207393485797284573, 114709310138173619898647, 67001065727290046465777, 2151863820021063264377831555299, 165322863065787590897, 2198107857101171136592374583, 5088234063653121776625221, 103514351309336306138422933, 281010990424988379773900077, 66057500726963481569, 47603692929912037, 70752850585258707668917, 801537827642431781555807, 717823036145065913500112639, 990528613348826863709866123, 1327749224973790260581, 112464516901932646313179, 90034993642508721427927, 53130343537354305734045066513, 1684920958089139745437, 164791605545639802840950077201, 71968710161697464884509561461, 7227658331219610769, 4595151463111347549043, 1189655014503064236728176983943, 960238354084378225186050329003, 222610818319582608367589, 1389432114469197661]);
No comments :
Post a Comment