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.
0, 0, 1, 1, 1, 2, 3, 5, 11, 26, 81, 367, 2473, 32200, 939791, 80570391, 30341840591, 75749670168872, 2444729709746709953, 2298386861814452020993305, 185187471463742319884263934176321, 5618934645754484318302453706799174724040986, 425632451384909715242581951982860838627778260930154571891, 1040556299367291626141472184594831289773562749596746466784696205046709264397, ...
a + b*c + d^e forms :
0, 0, 1, 1, 1, 3, 5, 9, 25, 73, 423, 61297, 3814697357801, 38288777744833624093154249190851262684887027625, 528258894752342086654853145215440802971528579790334308951113813225299979018691671799930531702081852951550104737544671925312435106846550064476545745313218493305704456568674526765589945812620905, ...
0, 0, 0, 1, 1, 2, 4, 7, 16, 46, 174, 3311, 268446771, 401906756202069927727330981, 11621586552644411467907986009695414159753052040180077344164072712841756067592413485931632195594453622338, ...
0, 0, 0, 0, 1, 2, 3, 6, 13, 33, 120, 765, 4831534, 55040353993453427047, 410186270246002225336426103593500672000000000000055040353997149550557, ...
a + b*c + d*e^f :
0, 0, 1, 1, 1, 1, 3, 5, 9, 25, 73, 313, 3263, 1502337, 278472902914281, 11984387434132924341157279996736444304839056033321, ...
0, 0, 0, 1, 1, 1, 2, 4, 7, 16, 46, 166, 1014, 47066, 12348246366, 66716521529543607970475115226, 1352103711242068192353912370110085456093703250694657783109527048738815728419903440987268632273515079282406, ...
a + b*c + d*e^f + g*h^i(*)j :
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 Linear 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. */
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 (c) 1996-2010 Robert P. Munafo. about contact
This work is licensed under a Creative Commons Attribution 2.5
License. Details here
s.13