Accelerating Sequences  

This page collects together a large number of integer sequences that interest me because of their accelerating growth. There are several other sequence pages, here is the index.

The Inspiration

When I was in about the 3rd or 4th year of school, I had just learned multiplication tables, and was already quite excited by the idea of large numbers. I therefore began learning my "exponent tables" (see the table I memorized at 7776).

Linear, then Polynomial, then Exponential, then Faster

The kind of sequence I am most passionate about is one that starts out growing at an apparently linear rate, like the integers and then at a polynomial rate like the squares and cubes; and then faster and faster, so as to eventually outpace even the various "hyperfactorials".

a + b*c form

0, 0, 1, 1, 1, 2, 3, 5, 11, 26, 81, 367, 2473, 32200, 939791, 80570391, 30341840591, 75749670168872, 2444729709746709953, 2298386861814452020993305, 185187471463742319884263934176321, 5618934645754484318302453706799174724040986, 425632451384909715242581951982860838627778260930154571891, 1040556299367291626141472184594831289773562749596746466784696205046709264397, ...

A6888 : a(n) = a(n-1) + a(n-2) a(n-3).

a + b*c + de form

These all use the same (recurrence relation) formula, but differ in the initial terms. In all cases there are 5 initial terms, consisting of a set 0's followed by a set of 1's.

0, 0, 1, 1, 1, 3, 5, 9, 25, 73, 423, 61297, 3814697357801, 38288777744833624093154249190851262684887027625, 528258894752342086654853145215440802971528579790334308951113813225299979018691671799930531702081852951550104737544671925312435106846550064476545745313218493305704456568674526765589945812620905, ...

A171877 : a(n) = a(n-1) + a(n-2) a(n-3) + a(n-4)a(n-5).

0, 0, 0, 1, 1, 2, 4, 7, 16, 46, 174, 3311, 268446771, 401906756202069927727330981, 11621586552644411467907986009695414159753052040180077344164072712841756067592413485931632195594453622338, ...

A171874 : a(n) = a(n-1) + a(n-2) a(n-3) + a(n-4)a(n-5).

0, 0, 0, 0, 1, 2, 3, 6, 13, 33, 120, 765, 4831534, 55040353993453427047, 410186270246002225336426103593500672000000000000055040353997149550557, ...

A171878 : a(n) = a(n-1) + a(n-2) a(n-3) + a(n-4)a(n-5).

a + b*c + d*ef form

These all use the same (recurrence relation) formula, but differ in the initial terms. In all cases there are 6 initial terms, consisting of a set 0's followed by a set of 1's.

0, 0, 1, 1, 1, 1, 3, 5, 9, 25, 73, 313, 3263, 1502337, 278472902914281, 11984387434132924341157279996736444304839056033321, ...

A171879 : a(n) = a(n-1) + a(n-2) a(n-3) + a(n-4) a(n-5)a(n-6).

0, 0, 0, 1, 1, 1, 2, 4, 7, 16, 46, 166, 1014, 47066, 12348246366, 66716521529543607970475115226, 1352103711242068192353912370110085456093703250694657783109527048738815728419903440987268632273515079282406, ...

A171880 : a(n) = a(n-1) + a(n-2) a(n-3) + a(n-4) a(n-5)a(n-6).

a + b*c + d*ef + g*hij form

These whimsical sequences use the "lower hyper4" operator defined here.

They all use the same (recurrence relation) formula, but differ in the initial terms. In all cases there are 10 initial terms, consisting of a set 0's followed by a set of 1's.

0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 4, 7, 13, 43, 139, 727, 37918, 2698325206, 238838713275241145040397, 102605542701267320250694866189529822540586803657649162661916219733794839361269512586419661588931, ...

0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 3, 6, 11, 31, 101, 461, 5969, 54970924, 2566256166594610582, 62757193346815419996912506199334550962862239663434039815556137875, ...

0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 3, 5, 10, 27, 81, 367, 3805, 2733535, 16677181703796554, 1240970832262840567855391280367952509479536766933320366, ...

0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 3, 5, 9, 26, 75, 325, 3401, 1563053, 407212778591593, 1834324679277188341330884213675744831969260330864096, ...

0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 4, 7, 16, 47, 168, 1033, 47347, 12616687331, 95252198578077627625561945222, 35417526400736770487203017847599134994600272804161169118661862248395279584127839949568054941407046092524711284598456436265387426699986794824089962702715356926186333956219724874248953788371081451206630341011483424206351, ...

Eventually Oscillating Recurrence Formulas

In 2004 I began developing the recurrence relation idea into an automatic search for all sequences meeting certain criteria, such as simplicity of the formula or including certain desired terms. This eventually led to the MCS webpage. During this time I found countless sequences that behave like this:

2, 3, 4, 8, 10, 14, 19, 21, 28, 31, 35, 43, 43, 52, 56, 57, 70, 66, 76, 84, 77, 99, 90, 97, 117, 93, 129, 118, 110, 159, 104, 156, 158, 106, 215, 113, 168, 227, 71, 287, 135, 136, 356, -11, 362, 214, 0, 592, -143, 383, 454, -347, 985, -271, 189, 1066, -1062, 1531, -180, -592, 2418, -2298, 2011, 717, -2700, 5031, -3989, 1619, 3747, -7396, 9360, -5263, -1778, 11498, -16396, 14988, -3115, -12901, 28274, -30999, 18493, 10181, -40775, 59678, -49082, 8727, 51376, -100028, 109190, -57374, -42209, 151849, -208768, 167019, -14705, -193593, 361087, -375312, 182204, 179373, -554190, 736894, -557016, 3336, 734073, -1290569, 1294430, -559827, -730207, 2025177, -2584459, 1854802, 170930, -2754829, 4610196, -4438696, 1684442, 2926334, -7364445, 9049477, -6122548, -1241297, 10291379, -16413317, 15172635, -4880636, -11532056, 26705321, -31585322, 20053906, 6652060, -38236732, 58291293, ...

MCS52150530 : A0 = 2; A1 = 3; A2 = 4; AN+1 = - AN + AN-2 + 5 N

Source Code

The following MAXIMA code computes and prints three of the sequences above, the ones that use the recurrence formula "AN = AN-1 + AN-2AN-3 + AN-4AN-5 :

/* When MACSYMA was young, its designers and/or users apparently had some uncertainly about how to handle 0^0. But for most integer applications using a general formula (like binomial expansion) to be consistent, 0^0 has to be 1. For details, see: http://en.wikipedia.org/wiki/Exponentiation#Zero_to_the_zero_power */   p(b,e) := block([], if ((b=0) and (e=0)) then return(1), return(b^e) )$   rec2b(n, z) := block([i,l,t], l:append(makelist(0,i,1,z),makelist(1,i,z+1,5)), for i:6 thru n step 1 do ( t:l[i-1] + l[i-2]*l[i-3] + p(l[i-4],l[i-5]), l:append(l,[t]) ), return(l) )$ print("a + b*c + d^e :")$ print(rec2b(15,2)); print(rec2b(15,3)); print(rec2b(15,4));



Robert Munafo's home pages on HostMDS   © 1996-2017 Robert P. Munafo.
aboutcontact    mrob    mrob27    @mrob_27    mrob27
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. Details here.

This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2017 Feb 02. s.11