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 3^rd or 4^th 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 exponential growth, the lower and higher forms of "tetration", and so on.

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 + d^e 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).

In the last of these is a string of 0's that is due to the term a(n-4)^a(n-5) taking on the value 120³³, which itself ends in 33 zeros, and the remaining part a(n-1)+a(n-2)×a(n-3) is small enough to leave a bunch of zeros visible in the total.

a + bc + de^f 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 + bc + de^f + g*h^{i^④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 of 0's followed by a set of 1's. The 18^th term (i.e. the 8^th term after the ten 0's and 1's) is shown in bold.

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, ...

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

(These last two are the same except for one extra zero at the beginning.)

Continuing this game

I would want to continue, surpassing the various "hyperfactorials", the higher hyper Operators, and so on, with no end. Before I got around to it, I decided to switch my focus over to the busy beaver function, which is guaranteed to grow faster than anything we can compute directly (e.g. with functions and operators recursively defined in terms of addition). It's a bit unsatisfying in that only a few initial terms will ever be known and the next term (i.e. the first unknown term) is guaranteed to be at least 13pt1.26720185×10¹⁰⁵⁶⁵, which is way to big to print here in actual digits.

1, 6, 21, 107, 47176870, ...

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 : A₀ = 2; A₁ = 3; A₂ = 4; A_N+1 = - A_N + A_N-2 + 5 N

Source Code

The following MAXIMA code computes and prints three of the sequences above, the ones that use the recurrence formula "A_N = A_N-1 + A_N-2A_N-3 + A_N-4^A_N-5. Most of the others above can be generated with similar code :

/* 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 2025 Apr 30.

s.27