hydra(5)

Exact answer to the hydra game's 5th value. First 4 values are 1, 3, 11, 1114111

The Hydra Game

of course this is GenAI

The game is described in the introduction in the wikipedia page: Hydra Game

The Numberphile video (where I learned of the problem) does a great job describing the game (video starts when they describe the problem). If text is more convenient:

Start with a linear tree of length N. You may only chop leaves in this tree. When you chop a leaf of the tree that’s not a child of the root, you add new siblings to its parent. The number of new siblings is equal to the number of steps taken so far. So the first chop adds 1 sibling to the parent, the second chop adds 2 siblings, etc.

In this particular variant, you always choose the “right-most” leaf, which is equivalent to saying you always choose leaves closest to the root, and the leaves on a node are essentially indistinguishable. The drawing below demonstrates the hydra game sequence of 3.

from wikipedia: https://en.wikipedia.org/wiki/Hydra_game

Note hydra(4) = 983,038 is likely from wikipedia, and it’s incorrect.

tl;dr: the answer

Update: I’ve found the general answer here:

Here are the first four values

hydra(1) = 1
hydra(2) = 3
hydra(3) = 11
hydra(4) = 1,114,111

The exact answer to hydra(5) is:

\(Let\ F(x) = 2^x \cdot (x + 2) - 1\)

To denote the n-th nesting of the function F:

\(F^n(x) = \underbrace{F(F(\cdots F}_{n\, \text{times}}(x)\cdots)) \)

For convenience, let’s define a constant C:

\(C = F^2(2 + 1) + 1 = F^2(3) + 1 = 22539988369408\)

The exact value of hydra(5) is given by:

\(hydra(5) = 2 \cdot F^{F^2(3) + 1}(F^2(3) + 1) + 1= 2 \cdot F^C(C) + 1\)

The Proof

(Skip to Stage 4 for the math proof part!)

To discuss the evolution of the hydra throughout the hydra game, let’s define a state ([a, b, c, d, e], S), where the array represents the physical state of the hydra, and S is the step count. If e > 0, then after 1 step, the state evolves to become ([a, b, c, d + S, e - 1], S + 1).

Stage 1: Brute Force Coding

For hydra game 1 - 4, I ran the following python code:

def selectLevel(hydra: list) -> int:
    for i in range(len(hydra)):
        # end of list, return the last level
        if (i + 1 == len(hydra)):
            if hydra[i] > 0:
                return i
        # reached a node greater than 1, return
        if hydra[i] > 1:
            return i
        # reached a level which is a leaf
        if hydra[i] == 1:
            if hydra[i + 1] == 0:
                return i
    raise Exception('bad selectLevel')

def simulate(hydra: list) -> int:
    step = 0
    print(hydra)
    while hydra[0] > 0:
        step += 1
        print(hydra, step)
        # find where to chop
        level = selectLevel(hydra)
        hydra[level] -= 1
        if level > 0:
            hydra[level - 1] += step

def main():
    hydra_size = 4
    hydra = [1 for _ in range(hydra_size)]
    simulate(hydra)

main()

Instead of explicitly modeling the tree, it’s equivalent to modeling a list where we ensure that we cannot decrement an array value to 0 unless its children (indicies to the right) are also 0.

For this, we comfortably simulated to demonstrate the sequence of 1, 3, 11, 1114111. For n=5, it started to take too long to run and it doesn’t seem like it’ll end anytime soon.

Stage 2: Fast Chop

The most expensive step is in pruning the large number of leaves of the root node. The numbers got ridiculously large and it spent a lot of time decrementing the root node, so I implemented Fast Chop:

Instead of decrementing one by one, I just decremented all but one of the root (since we can’t chop until all the other indicies have been cut to 0) and added the difference to the step count. Here’s the updated simulate function:

def simulate(hydra: list, fast_chop: bool = False) -> int:
    step = 0
    print(hydra)
    while hydra[0] > 0:
        step += 1
        print(hydra, step)
        level = selectLevel(hydra)
        # chop
        if level == 0 and hydra[level] > 1 and fast_chop:
            node_size = hydra[level]
            hydra[level] -= node_size - 1
            step += node_size - 2  # already incremented step, so - 2
        else:
            hydra[level] -= 1
            if level > 0:
                hydra[level-1] += step
    return step - 1

Still produced the right answers for 1 - 4.

For hydra(5), I quickly ran into this issue:

ValueError: Exceeds the limit (4300 digits) for integer string conversion; use sys.set_int_max_str_digits() to increase the limit

And not a lot of progress was made. It doesn’t seem like I can easily increase the limit to solve this problem… for reference this was the last thing I saw before this error:

[5236751274087763604827335113503164542980300196051027772799054866553408315208749862621910699058066359304382851927240123690001657028076624243874905856369638573015266767173518533760881090665168657501466502575438814695379244920821816879398416379568995975331885966655627889373456252504294450808872324956279954441791424138238566544945055910878598449444356820527690288461439219089884273119672110780915086500181367389487847591622178596698590638598964162079073208267381018870683102042412374855218599064900594222409161345188381482756218697949512315491167618692787301782162184736991124223971701054644009826862190494573709271105283016638965612688564267675573446663137503920856946163800030385661836794421151038323102174273831660161943282774795456286219012025514744725129058365776715796186849330378082323946782828045123848071459942902828368123838185297691350796927183438726836331775328725893998022308339046666450649110098923213655788584420338021683310567449135992452580240598240949210098906606443034323449167094382342009720751240219585329918940963407988745009765182769239210185976272595207525201689610903562379503969853336779270227985605752034151825586837471803169417902911531690946991797181645549811951087317790371686134226956300584751700773029835508380819594560654781826332316405519852105346260214716258678990870714024313498644277768937813561794857945887410977910789497996279246650157863972578078236381769628727247654317441033159274592748068797421129624639669953783640862170282664397133282652299904463029437171264502226794590544077875216641287293069454710386248370680308708731029273018895879272852822220795151026965660328066845816623590817493823966958437300195250223341446166956531120990984133649788709888107516868282329681941441585518552792104733272698240012054637287259405459124930443017708422939350172006240588687592998904050506102490343772465687991422441448882011725609651783944361752435362062781589195510865475207181455225108775250001093738956361680441649527335822572336120455001762442505113797312189116632250263437321506263410518359810945829064312927586684675494831276823669068201460495423176123108409901698778301964724718957681497200352702701076000294559530265746359546619433943942940871442069738465827748357498595512514379055022004878344501765037265621885163003749999113603007286707281304209094602827386096346850598719467184159366295111010437092778471932435847585622290087202463029581238304221091731411342646010878158782598277736273725880547301418065127418837768153356358086680399888437754185935791653522527588641743823343406228041369298656125612209809308156697742068095146882731538744628536417045031881562234222022692975563640511286215378042016535361816522961162022289632861025679328602115231852923527050327616803340359251971379527588194183977451694394758300505712301729804885473523514141584822246161706088650448135123489998734583034450677447388385822893681353155622711404295181378827305822128040202984330793416842344269948350278999196273924686089626702081385958689896939223943945135658293948365266613362606866388013839023918573096791461760640816126897351506173851590079283933367950519316399171284435994198773170236082931563829489173596388230979952429868071244767722905954955193957444015662323635942083440563413775925250402785571597958667107947168757358479075225026526563032099728035575668109715823667685449996736046781140951726763715400819999867141471120936774055169955092818136292880667820574649938464671084088300302239619483984392792645074476910620078394019525809139132887110714887841277090342270471936907855105576556697910955352727191007370383437491260272759688502081997665341246371514518105005094429840370279355270165350942684119889898897785725295983426197612720256499277786884561502840067942542274821075820210267162117466922348246664073310562018052544726571554607306963521728197407669815297252788249623858769527282474860722408331998136164324865180469060271551771130264764731673686149466242204929133585865007342493911099519307953277164206639037770488051522091117052597342947125013900324244562835664605462604987945798805427063224160805807118493892312279199291896920341710392490804290716924090542886711173948988426531863920448490530479550509676455670400571503643438719913975901170479794011688362240795768686834708272261861187939120954315182187550884695934209489824329799121196304728207142986794926080, 22539988355169, 22539988369407, 0, 0] 5236751274087763604827335113503164542980300196051027772799054866553408315208749862621910699058066359304382851927240123690001657028076624243874905856369638573015266767173518533760881090665168657501466502575438814695379244920821816879398416379568995975331885966655627889373456252504294450808872324956279954441791424138238566544945055910878598449444356820527690288461439219089884273119672110780915086500181367389487847591622178596698590638598964162079073208267381018870683102042412374855218599064900594222409161345188381482756218697949512315491167618692787301782162184736991124223971701054644009826862190494573709271105283016638965612688564267675573446663137503920856946163800030385661836794421151038323102174273831660161943282774795456286219012025514744725129058365776715796186849330378082323946782828045123848071459942902828368123838185297691350796927183438726836331775328725893998022308339046666450649110098923213655788584420338021683310567449135992452580240598240949210098906606443034323449167094382342009720751240219585329918940963407988745009765182769239210185976272595207525201689610903562379503969853336779270227985605752034151825586837471803169417902911531690946991797181645549811951087317790371686134226956300584751700773029835508380819594560654781826332316405519852105346260214716258678990870714024313498644277768937813561794857945887410977910789497996279246650157863972578078236381769628727247654317441033159274592748068797421129624639669953783640862170282664397133282652299904463029437171264502226794590544077875216641287293069454710386248370680308708731029273018895879272852822220795151026965660328066845816623590817493823966958437300195250223341446166956531120990984133649788709888107516868282329681941441585518552792104733272698240012054637287259405459124930443017708422939350172006240588687592998904050506102490343772465687991422441448882011725609651783944361752435362062781589195510865475207181455225108775250001093738956361680441649527335822572336120455001762442505113797312189116632250263437321506263410518359810945829064312927586684675494831276823669068201460495423176123108409901698778301964724718957681497200352702701076000294559530265746359546619433943942940871442069738465827748357498595512514379055022004878344501765037265621885163003749999113603007286707281304209094602827386096346850598719467184159366295111010437092778471932435847585622290087202463029581238304221091731411342646010878158782598277736273725880547301418065127418837768153356358086680399888437754185935791653522527588641743823343406228041369298656125612209809308156697742068095146882731538744628536417045031881562234222022692975563640511286215378042016535361816522961162022289632861025679328602115231852923527050327616803340359251971379527588194183977451694394758300505712301729804885473523514141584822246161706088650448135123489998734583034450677447388385822893681353155622711404295181378827305822128040202984330793416842344269948350278999196273924686089626702081385958689896939223943945135658293948365266613362606866388013839023918573096791461760640816126897351506173851590079283933367950519316399171284435994198773170236082931563829489173596388230979952429868071244767722905954955193957444015662323635942083440563413775925250402785571597958667107947168757358479075225026526563032099728035575668109715823667685449996736046781140951726763715400819999867141471120936774055169955092818136292880667820574649938464671084088300302239619483984392792645074476910620078394019525809139132887110714887841277090342270471936907855105576556697910955352727191007370383437491260272759688502081997665341246371514518105005094429840370279355270165350942684119889898897785725295983426197612720256499277786884561502840067942542274821075820210267162117466922348246664073310562018052544726571554607306963521728197407669815297252788249623858769527282474860722408331998136164324865180469060271551771130264764731673686149466242204929133585865007342493911099519307953277164206639037770488051522091117052597342947125013900324244562835664605462604987945798805427063224160805807118493892312279199291896920341710392490804290716924090542886711173948988426531863920448490530479550509676455670400571503643438719913975901170479794011688362240795768686834708272261861187939120954315182187550884695934209489824329799121196304728207142986794926080

Where the array is keeping track of the hydra state, and the last number is the step we were on.

Stage 3: Figure out what we need to solve

So I modified the simulate function again to figure out what is a tractable point to create a formula for the answer. I used stop_at to stop at a hydra of 3 levels deep (because that is empirically the point that the simulation was able to get to before it ran out of digits).

def simulate(hydra: list, stop_at: int = 0, fast_chop: bool = False) -> int:
    step = 0
    print(hydra)
    while hydra[0] > 0:
        step += 1
        print(hydra, step) # , getSteps(hydra, step))
        if hydra[stop_at] == 0:
            return step
        level = selectLevel(hydra)
        # chop
        if level == 0 and hydra[level] > 1 and fast_chop:
            node_size = hydra[level]
            hydra[level] -= node_size - 1
            step += node_size - 2
        else:
            hydra[level] -= 1
            if level > 0:
                hydra[level-1] += step
    return step - 1

For stop_at = 3, we get to the following state:

([1, 1, 22539988369408, 0, 0], 22539988369408)

So this hydra has 3 levels, with the third level having 22539988369408 heads at step 22539988369408. The fact that these two numbers are not really special, because when you make the first cut off of a linear tree [1, 1, 1, 1, …, 1, 1, 1] for step size S, the next step size is S + 1, and you add S siblings to the parent, so that level becomes S + 1. (by the way, when the simulation ran out of digits, the third level never made it past 1 minus that number 😱)

The goal is to create a closed form formula for the form: ([1, 1, c], S). Note it’s best not to constrain the problem where c == S because it’s easier to come up with the more general form and then plug in the situation where c == S.

Stage 4: Inductive proof

(note, I don’t know how to make writing LateX proofs in SubS NOT painful…)

Proof Strategy: Write formulas for simpler states, and then show how more complex states evolve into simpler states with solved formulas.

Base Case ([1], S) → ([1 + A, 1], S)

\((a)\ ([1], S) \rightarrow S;\ \text{on the S-th step, the last head is chopped}\)

\((b)\ ([1 + A], S) \rightarrow ([1], S + A) \rightarrow S + A,\ \text{per (a)}\)

\((c)\ ([1, 1], S) \to ([1 + S], S + 1]) \to 2 \cdot (S + 1) - 1,\ \text{per (b)}\)

writing 2*S + 1 as 2*(S + 1) - 1 for convenience as it will soon become clear.

\((d)\ ([1 + A, 1], S) \to ([1, 1], S + A]) \to 2 \cdot (S + A + 1) - 1,\ \text{per (c)}\)

Solving for ([1 + A, 1 + B], S) and ([1, 1, 1], S)

\((e)\ ([1 + A, 1 + 1], S) \to ([1 + S + A], 1], S + 1) \to ([1, 1], 2 \cdot S + A + 1) \to 4 \cdot (S + A + 1) - 1, \text{per (d)}\)

\((f)\ ([1 + A, 1 + 2], S) \to ([1 + S + A], 1 + 1], S + 1) \to ([1, 1 + 1], 2 \cdot S + A + 1) \to 8 \cdot (S + A + 1) - 1, \text{per (e)}\)

\((g)\ ([1 + A, 1 + 3], S) \to ([1 + S + A], 1 + 2], S + 1) \to ([1, 1 + 2], 2 \cdot S + A + 1) \to 16 \cdot (S + A + 1) - 1, \text{per (f)}\)

Since the pattern is the same, therefore:

\((h)\ ([1 + A, 1 + B], S) \to 2^{1 + B} \cdot (S + A + 1) - 1, \text{per (e), (f), & (g)}\)

\((i)\ ([1, 1, 1], S) \to ([1, 1 + S], S + 1) \to 2^{S+1} \cdot (S + 2) - 1 \to 2 \cdot (2^S \cdot (S + 2) - 1) + 1, \text{per (h)}\)

Recall that:

\(Let\ F(x) = 2^x \cdot (x + 2) - 1\)

So:

\((i)\ ([1, 1, 1], S) \to 2 \cdot F(S) + 1\)

Final Stretch: transform ([1, 1, X], S) → ([1, 1, 1], ???)

Final stage of the proof is to find how to transform ([1, 1, X], S) into ([1, 1, 1], ???), then input ([1, 1, 22539988369408, 0, 0], 22539988369408) and (i) to get the exact solution to hydra(5). First, we will solve ([1, 1 + B, X], S) into ([1, 1, X], S).

\(\text{Goal:}\ ([1, 1+B, X], S) \to ([1, 1, X], ????)\)

Inductively:

\((j)\ ([1, 1 + 1, X], S) \to ([1 + S, 1, X], S + 1) \to ([1, 1, X], 2 \cdot (S + 1) - 1)\)

\((k)\ ([1, 1 + 2, X], S) \to ([1 + S, 1 + 1, X], S + 1) \to ([1, 1 + 1, X], 2 \cdot (S + 1) - 1) \to ([1, 1, 1], 2^2 \cdot (S + 1) - 1, \text{per (j)}\)

\((l)\ ([1, 1 + B, X], S) \to ([1, 1, X], 2^B \cdot (S + 1) - 1), \text{from (j) & (k)}\)

\((m)\ ([1, 1, X], S) \to ([1, 1 + S, X - 1], S + 1) \to ([1, 1, X-1], 2^S \cdot (S + 2) - 1), \text{per (l)}\)

\((m)\ ([1, 1, X], S) \to ([1, 1, X-1], 2^S \cdot (S + 2) - 1) \to ([1, 1, X-1], F(S))\)

\((n)([1, 1, X], S) \to ([1, 1, 1], F^{x-1}(S)), \text{per (m)}\)

\((o)([1, 1, X], S) \to ([1, 1, 1], F^{x-1}(S)) \to 2 \cdot F^x(S), \text{per (i) & (n)}\)

For the case ([1, 1, S, 0, …], S), which will always be the case for the first instance of the height of any level as we discussed before (including 3):

\((p)([1, 1, S], S) \to 2 \cdot F^S(S) + 1, \text{per (o)}\)

Plugging in hydra(5) to the formula

The answer is:

\(([1, 1, 1, 1, 1], 1] \to ([1, 1, C, 0, 0], C) \to 2 \cdot F^{C}(C))+ 1), \text{where C=22539988369408}\)

Validating with hydra(4)

We know the answer to hydra(4) so we can validate our new formula with it. First step after ([1, 1, 1, 1], 1) is ([1, 1, 2, 0], 2).

\(([1, 1, 2, 0], 2) \to ([1, 1, 1, 0], 2^2 \cdot (2 + 2) - 1) \to ([1, 1, 1, 0], 15)\)

\(([1, 1, 1, 0], 15) \to 2 \cdot (2^{15} \cdot (15 + 2) - 1) + 1 \to 1114111\)

So the math checks out!

Hinting of the larger pattern

This is hand-drawn by ChatGPT 4

I’m stopping here for now. I explored on a whim whether our magical function F(x) is related to the magical number 22539988369408 from hydra(5). In fact, through brute force:

\(F(39) + 1 = 2 ^ {39} * 41 - 1 + 1= 22539988369408\)

And even 39 is a function of F(x):

\(F(3) = 2^3 * 5 - 1 = 39\)

So:

\(22539988369408 = F^2(3) + 1\)

In fact, you can rewrite all the previous answers as functions of F:

\(hydra(1) = F(0) = 1\)

\(hydra(2) = 2 \cdot F(0) + 1 = 3\)

\(hydra(3) = 2 \cdot F^1(1) + 1 = 11\)

\(hydra(4) = 2 \cdot F^2(2) + 1 = 1114111\)

Probably worth further investigating F(x) to understand how hydra(n) grows!