Tribonacci Numbers

Thursday, July 24, 2025

Tribonacci numbers are a 3 argument version of the Fibonacci sequence. Specifically, they are defined by the first 3 numbers in the sequence and then a recursive formula:

T(0) = 0
T(1) = 1
T(2) = 1
T(n) = T(n-1) + T(n-2) + T(n-3)

Note: Some other tribonacci sequences have different starting values, and in general are defined by their first 3 values: a, b, and c — in this case: a=0, b=1, c=1.

Let’s go ahead and build this in Factor, making sure to use memoization to improve performance!

MEMO: tribonacci ( n -- r )
    {
        { 0 [ 0 ] }
        { 1 [ 1 ] }
        { 2 [ 1 ] }
        [ 3 2 1 [ - tribonacci ] tri-curry@ tri + + ]
    } case ;

And write some tests to make sure it works:

{ 0 } [ 0 tribonacci ] unit-test
{ 1 } [ 1 tribonacci ] unit-test
{ 1 } [ 2 tribonacci ] unit-test
{ 2 } [ 3 tribonacci ] unit-test

{ 98079530178586034536500564 } [ 100 tribonacci ] unit-test

And just for fun, we can easily print the 10,000th tribonacci number:

IN: scratchpad 10,000 tribonacci .
104970887945512179720156402562881884282669908701507376396226849
507715880964253502566653834053217081868282654421270875998847083
354963158781389172213221498323513985337426272701217011859592971
352141098891805206420900134582429646587046427436005495255798883
246073618031475000139396853427893513436406142049154715999765086
094048789520150380301629928195007762620367936007950031281567424
852796946143324764098612546824050145564601448681311727789904337
617216196640219842106590802021786745819241462665059249132141577
894579630772922197404756269452287431128951784520600882264401580
836789430310052922795100107599314150699335030135447534365101972
212856424810302264081751728175450009246816642287808303756431642
190229866618955021220164854376449799003570929253752356712382127
291554067625436999262482815025295032640196317590693733687242877
497883233594054067312780455244938306491277888412407808533948897
005235795246966581196760639279751925372382092157588570477362227
283625689293926489206546461529591280578644740130681436616270947
399935554399753037011040986396134560464682737227548122835065232
761643277488106437767837022869773684192764695319605886553868567
702494744004565987231502563031894899087422143067624588247239246
209236949388263940118095456771744163270015460183378322484380736
904832346845106349873481841268013335459411318711113804921252701
685818949515305915278859806703369590630798205066890114557299609
200541159049091178364828975083353240663240973018961078785884623
754180387714833134965646472067988582492257260500195932241449015
697681978518891318647464646160278703772005509287994250063276822
738895989306087163591588324360743585286169954643632915363025595
643953167630122098912124456056268912098768342566371268760363924
442889888379550780367698680933768551834171582391185682035582704
931276111575092809048515510639048207408965825151544995661087361
202117757159833101907264820660711114748638250941161679012607717
553825173370181059141538350424453457744455331742600716423279982
267989192083554417406081238679478603607583176975551563763168876
520982495090528860247780663854311039370938787207531507059750255
331836155899138120278616825251002413907470627146790383955760350
784999437437547112858192681843997153570155437021076042591359601
550872111063258125973939212682654169479750147837067955643100320
187644616709502788318461621953487535087913200131635597400731137
771945144547828956806094091586378911072748574105653223033633806
849090649589109247111615640029564835225683410527907839461600211
731583707928939187244387112961247901688359209735935698701057372
453283021738155105525668197910700091097683706470201003266177476
093728339123616912247097871463717510180588398935948725584082432
8

And that, of course, shows off our bignum integers holding almost 8,800 bits.

But, if we want to calculate the 100,000th tribonacci number, we get a retain stack overflow. This error depends on how many recursions have to be performed before a previously memoized answer is found:

IN: scratchpad 100,000 tribonacci
Retain stack overflow

Type :help for debugging help.

Instead, we would need to approach it by calculating interim values:

IN: scratchpad 10 [1..b] [
                   10,000 * dup tribonacci log2
                   "%s = %s\n" printf
               ] each
10000 = 8789
20000 = 17581
30000 = 26372
40000 = 35164
50000 = 43955
60000 = 52747
70000 = 61538
80000 = 70330
90000 = 79121
100000 = 87913

An iterative implementation might do more computation when called repeatedly, due to lacking memoization, but gets us directly to the answer we want:

: tribonacci ( n -- r )
    {
        { 0 [ 0 ] }
        { 1 [ 1 ] }
        { 2 [ 1 ] }
        [ [ 0 1 1 ] dip 2 - [ [ + + ] 2keep rot ] times 2nip ]
    } case ;

We can see that the millionth tribonacci number has almost 880,000 bits!

IN: scratchpad 10,000 tribonacci log2 .
8789

IN: scratchpad 100,000 tribonacci log2 .
87913

IN: scratchpad 1,000,000 tribonacci log2 .
879144

We could combine memoization and iterative computation by implementing an inline cache:

:: tribonacci ( n -- r )
    V{ 0 1 1 } :> seq
    n seq ?nth [
        n 1 + next-power-of-2 dup
        seq capacity > [ seq expand ] [ drop ] if
        seq 3 tail-slice* first3 n seq length 1 - -
        [ [ + + ] 2keep rot dup seq push ] times 2nip
    ] unless* ;

Now subsequent calls are fast, at the expense of a possibly large cache!

! First computation is slow
IN: scratchpad [ 100,000 tribonacci ] time .
Running time: 0.211418458 seconds

! Second computation is fast (cached)
IN: scratchpad [ 100,000 tribonacci ] time .
Running time: 0.000272875 seconds

! Other requests in range are fast (cached)
IN: scratchpad [ 99,999 tribonacci ] time .
Running time: 0.000344792 seconds

In this case, the cache now holds 100,000 integers in about 550 MB of memory.

IN: scratchpad 100,000 <iota> [ tribonacci size ] map-sum megs
543.9405975341797 MB

Nifty!