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*hi④j 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));
This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2022 Mar 28.
s.30