The Hydra Game - Numberphile
Vložit
- čas přidán 16. 05. 2024
- Tom Crawford discusses Hercules and The Hydra Game. See brilliant.org/numberphile for Brilliant and 20% off their premium service & 30-day trial (episode sponsor). More links & stuff in full description below ↓↓↓
Tom Crawford's website, with links to his work and other outreach: tomrocksmaths.com
More Tom videos on Numberphile: bit.ly/Crawford_Videos
Tom on the Numberphile Podcast: • The Naked Mathematicia...
Tom Crawford is based at University of Oxford as Early Career Teaching and Outreach Fellow at St Edmund Hall and Public Engagement Lead at the Oxford University Department for Continuing Education.
Watch The Josephus Problem - • The Josephus Problem -...
POST-PUBLICATION NOTE: Have seen a number of people saying the 4 case should be 1,114,111 rather than 983,038 - I'm not qualified to comment but you can read some discussion and coding here: redd.it/1c6z1t4
Patreon: / numberphile
Numberphile is supported by Jane Street. Learn more about them (and exciting career opportunities) at: bit.ly/numberphile-janestreet
We're also supported by the Simons Laufer Mathematical Sciences Institute (formerly MSRI): bit.ly/MSRINumberphile
Our thanks also to the Simons Foundation: www.simonsfoundation.org
NUMBERPHILE
Website: www.numberphile.com/
Numberphile on Facebook: / numberphile
Numberphile tweets: / numberphile
Subscribe: bit.ly/Numberphile_Sub
Videos by Brady Haran. Animation by Pete McPartlan
Numberphile T-Shirts and Merch: teespring.com/stores/numberphile
Brady's videos subreddit: / bradyharan
Brady's latest videos across all channels: www.bradyharanblog.com/
Sign up for (occasional) emails: eepurl.com/YdjL9 - Věda a technologie
Flash forward 11 months: ‘Hi, I’m Matt Parker, this is standupmaths, and today we’re calculating pi with the Hydra game.’
Bonus: we get to see some extremely inefficient Python code
Calculating pi by killing a hydra
*Fast forward 3 month 14 days and 15 hours later
"I've calculated the answer for y=5 to within an error margin of about ten orders of magnitude, and that's close enough for me." The introduction of the Parker Hydra.
@@IceMetalPunk, to be honest, the y=5 number has got to be so huge that being of by ten orders is not that bad.
Long computation required? Better get Matt Parker to knock up some inefficient Python!
Get Matt Parker to *WHAT* some inefficient Python!?
@@11Natrium Do not the python!
nah a spreadsheet will do
Python, Hydra, what's the difference....?
@@jeremylakeman- ...the number of feet. 🤔😁
"obvious" and "trivial" are the words that haunted me throughout university
ikr. I think it's some kind of inside joke amongst university lecturers.
ok bro
Flashbacks to “this proof is trivial and is left as an exercise”
The "look at how smart I am you are inferior to me" stuff in university- all the posing in math- became quite clear to me off of those words. "The proof of this result is trivial." Then you look it up. It's complicated. Not only that but mathematicians had been trying to figure it out for YEARS before somebody came up with it and it was celebrated at the time as this great advance. And if there's an easy proof it sure doesn't use any of the machinery that existed at the time or any machinery someone in that class would have.
@@logstargo627 Damn, that sounds awful. At my uni "trivial" was only ever used for things that you could essentially demonstrate at a glance with a simple diagram. Also, anyone else here familiar with the The Proof Is Trivial website?
Hercules should simply have dammed the water source. The monster would then eventually become dehydrated. Job done.
then you'll have what is known as an anhydrous hydra..
I applaud this joke. The best of mythical/mathematical dad jokes. I salute you, stranger on CZcams. You are the champion.
De-hydra-ted. Yes.
Well done, very well done. Great joke.
I was never big on Greek mythology, but didn't he redirect a river to clean out the stables?
There's a version of this game where, instead of adding individual leaves, you add copies of the whole subtree. In this case, the length of the game grows so fast that proving it ends is independent of Peano arithmetic.
What does 'independent of peano arithmetic' mean please?
@@abigailcooling6604 I believe it means that you can proof it true or false in different models of Peano arithmetic, by adding axioms. Solely using Peano arithmetic is not enough to proof it either true or false. Like how the axiom of choice is independent of Zermelo-Fraenkel set theory.
by "subtree" you mean...? everything from the root to the level of the parent of the head you just shopped off?
Actually, you can choose any computable function f(n) and at each step you add f(n) copies of the subtree. It still ends. The proof is not very difficult, but you need ordinals for it. Proving that Peano arithmetics is not enough to conclude is difficult.
@@abigailcooling6604 I am not sure that 'independent of Peano arithmetic' is the accurate way to tell it, but what I think he means is that, in the case where you add to the grand-parent N copies of the subtree above the grand-parent, it has been proved that 1) the game always finishes, but 2) you CANNOT prove that the game always finishes using ONLY peano arithmetic. You need a more extensive theory to prove it, like ordinal numbers.
That's an adorable hydra design.
I would certainly not say no to a plushie of one of those heads.
I felt a tinge of sadness when the hydra died
Something about seeing all the heads blink in unison tickles my brain.
I liked the sound it made
too little horrifying to be "accurate", but adequate to an educational maths video
The Comic "The Order Of The Stick" solved the problem on page 325 / 326. They just chopped of heads until the hydra has too many heads for its blood supply and passes out. You don't actually need to chop off all heads.
I knew someone would reference this!
There are weedkillers which consist of plant hormones that encourage growth of top part of plants. In the end roots can't support the metabolic demand of such, and plant dies.
mmmm hydra steak
A Hydra that follows physics and biology?😂
This is a mathematical hydra, nincompoop.
the whole time I was watching this all I could think of was Danny DeVito shouting "Will you quit with the head-slicing thing?!?!"
GET UP ON THE HYDRA'S BACK!
It's nice to know that I'm not actually alone.
@@phiefer3My first thought
It's interesting looking at how the myth of the Lernaean Hydra changed with time. At first, it just had six heads, and they didn't regrow. Later, it had nine heads, or just an unspecified multitude. The heads would grow back, either a single head replacing the old, or two, or sometimes three in the one's place. The way Heracles eventually defeated the Hydra changed as well. According to Apollodorus, his squire Iolaus cauterized each neck wound after Heracles severed the head, preventing it from regrowing. But according to later authors, he used the venom from the first neck wound to irreparably destroy the other heads.
I think the squire with the fire is the most well known but I could be wrong
It is fascinating how mythology changes over time though
Hercules was lucky that Tom Crawford didn't define his labours or he would have spent forever sharpening his sword.
He probably has a magical sword
This reminds me of the TREE sequence that goes TREE[1] = 1, TREE[2] = 3, TREE[3] = Is a number so absurdly large one of the only things we know about it is that it far exceeds the size of Grahams number.
(and I believe numberphile has some videos on the TREE sequence already.)
yes, great video by Tony Padilla.
I need to know how it compares to those numbers.
We actually know a lot more about it than that but it's only in relation to other absurdly large numbers/fast growing series.
@@miniropyeah isn't it funny how the Smosh guy is a genius mathematician
the hydra game grows alot slower than the TREE sequence
Send your drawings of the y=4 case to Dr Tom Crawford, St Edmund Hall, Oxford, UK.
The postage costs would be astronomical!
@@codahighland Won't the Postmaster Generals split the difference, or is that too soon?
@@codahighland The Hydra will pay for you
The interesting thing is that if you just chopped off the furthest layer each time, instead of the rightmost head, then it would be a significantly smaller number.
@@michaelmurray6197Yeah, 48.
A variation of this was explained on PBS Infinite Series a few years ago, there’s a relation to infinite ordinals!
Ah, i thought this was a remaster! I miss that channel
Yeah, I saw this is my recommendations like 2 or 3 times and thought it was a suggestion for that video so I didn't click it because I thought I had already seen it. Then I checked and lo and behold, actually a new one!
missed opportunity to say w_d = 40
this is why I'm in the comments
@@TomRocksMaths woah.. your profile picture needs a haircut dude!
Okay, some things I've figured out:
-The correct number of steps for n=4 is 1114111, not 983038. This number appears on an old blog and in wikipedia, so it probably was copied by some editor without checking and then by numberphile on this video.
-You can also calculate "equivalents". For example, for a [0,0,0] hydra, the equivalent would be a [0,1] hydra starting on step 2. So, n=5 would be the same as a [0,0,0,1] hydra starting on step 2. I can't calculate that yet, but I've calculated a [0,0,0,0] hydra starting on step 2, and it is on the order of 10^6785212601122 steps. That number is still way, WAY smaller than the number of steps for n=5, which continues to grow a lot.
Maybe someone with more time or a mathematical background can make a formula to calculate these; I know it's possible for n
I also got 1114111 when calculating n=4 with a method I had that might be quite similar to yours, Where did you find the correct answer? Wikipedia had 1,3,37,>graham's number which was not the same function. I'd be keen to correspond more on that. I haven't looked at 5 yet but I don't think it's quite as big as you say, although it would be ridiculous (intuitively, I'm not actually certain)
I take it back, your size for n=5 makes more sense on some experimentation, but I'd be curious to hear how you got that value exactly
@@evanfrench3040 can anyone share a code example or link on the head determination algorithm?
I have a working code that got n=1,2,3 the same and after logging the operations n=4 seems logically consistent but produces 327,677 steps,
and n=5 is bigger then 10^(10^( ...million more times.. .^(10^10)))) which I would write as 10 ^^ 1,000,000,
after my code reached the max supported number I made an estimation using the growth pattern and would place n=5 around 10 ^^ 1,441,792.
( and n=6 would be around 10 ^^^ (10 ^^ 6,291,453) and yes that's 10 ^^ (10 ^^ (10 ^^ ... 10^^6,291,453 times)) )
I got 1114111 too
after some research it seems that:
1114111 is what you get if you cut at the lowest height with 2+ nodes or the highest if all 1.
327677 if you cut the highest with most nodes total.
720891 if you cut the lowest with most nodes total or highest if all 1.
I love the animation. I've never seen such a cute hydra!
No one cares about "cuteness" in math.
@@Gordy-io8sb or battle!
Just chopping off all heads generated by chopping the highest level head in the 5-level Hydra (following the rule of always chopping off the most recently generated lowest head) is removing a total of 21,990,232,555,519 heads (i think). Therefore Chopping the one remaining new highest level head (original 4th level head) generates 21,990,232,555,520 heads at level 3. Chopping one of these will generate 21,990,232,555,521 heads at level 2. All told, removing these lvl 2 heads (in the correct sequence) will generate (21,990,232,555,522 + 1)*(2^(21,990,232,555,521)-1) - 21,990,232,555,521 heads at level 1 (directly connected to root, generates no more heads) to be removed before the next of the 2E13 remaining level 3 heads is removed (i think).
Yeah it would have been nice to see him make a crack at it and see how far he can get...
I have discovered a truly marvellous proof for a lower bound for arbitrary d, which this comment is too small to contain.
I calculated that chopping the 2nd head of level 4 would been done at the step 22,539,988,369,407 but maybe I did something wrong. But it still pretty close to your number (for that magnitude).
Thank you for this, I started programming a Hydra game and the rules for cutting heads wasn't clear -- I ended up slaying the hydra much too quickly.
That Hydra would need to use a lot of toothpaste.
i just love the animations, it's SO CUTE
I need to use this when I'm teaching induction and inductive variables. It's such a nice bridge from "inducting purely over the naturals" to "inducting over sets"
The sequence {1,3,11,983038,…} for the simple linear starting graph _very roughly_ (in order of magnitude) grows like power towers of increasing height: {1, 2, 3^2, 4^(3^2), …}. If this holds, there could well be on order of 5^(4^(3^2)) steps for _n_ = 5, or _roughly_ 10^(183,000) steps, give or take a factor of _n_ ( _in the exponent_ ). No wonder this number isn't known exactly!
I wrote a super quick python script to see what would happen. It crashed around step 10^4300
That's wrong estimate. I have written a script and it estimates value to be above: 2^2^2^2^...^22539988369409, with height of this tower 22539988369407. Just one step of this tower is going to produce a number with 6.7*10^12 digits.
That only vaguely matches the numbers in the sequence, and we don't have enough information to verify that based on the sequence alone.
Also, looking into it some more I've concluded that it actually seems to grow in hyperoperators - i.e. moving through exponentiation, tetration, pentation etc as d increases.
Heads on each layer create loops at lower layers. These loops are n long - n being the number of heads cut off so far. This leads to loops of loops of loops of... etc... of successorship (cutting off a head from the root node) - which is how hyperoperators are defined, each as a repeated form of the previous.
@@newkobra Yeah, that seems right. A few people in the comments have got very similar answers.
What does your script do btw? No way it's brute force.
@@alansmithee419 it possible to prove that if level_1 has only 1 node and on level_2 there are x nodes and you currently on step S, then you will get to the state with level_1 and level_2 having 1 node at step 2^(x-1)*(S+1) - 1. Using this equation it's very easy to write a script that will quickly decrease first two levels. In less than 10 iterations I got to the point where I had next number of nodes on each level 1, ~22*10^12, ~22*10^12, 0, 0. But using an equation after this point is impossible as I need to evaluate 2^(22*10^12) and this number has 6.7*10^12 number of digits. And this will just reset first two levels to one, after that we need to remove one head from level 3, and repeat but with this huge number instead.
I really love the animations you provide! They are whimsical, sounds are hillarious but at the same time delivers the content of the explanations. Thank you for making me happy
"You enter a 20' by 80' room. A long oak table runs down the center surrounded by chairs. Sunlight filters in through windows on the west wall. The north and east wall are lined with bookshelves laden with old tomes. Some are kept imprisoned behind brass grills, as though yearning for escape."
The old library in St Edmund Hall, Oxford.
A bit scary at night.....
*examine table*
@@serversurfer6169 Nononono no, you're not drawing me into DMing a game in the comments section :)
@@marasmusine Fine... I cast Magic Missile!
I…
cast…
extremely…
slow…
Internet…
on you all!
the answer for y=4 being 983038 doesn't make sense. lets assume we're close to finishing the game where we have reached a tree with 2 parts left: the root plus 1 more head after having made c cuts. if we cut the top head, we'll grow c+1 heads. to get down to the root, we'll need 2c+2 cuts in total (c that we started with, +1 to cut the top + c+1 to cut all the heads that got attached to the root). after that, we need to cut the last head giving us 2c+3 cuts. 983038 being even, is not of the form 2c+3 so can't be the correct answer. when i went through it, i got 1114111.
It looks like they just copied from Wikipedia
I also got this result
this is related to A180368 in OEIS, but there the process is not like described in the video. Instead of growing N on step N, a new copy of the parent is spawned from the grandparent.
it goes like this: 0, 1, 3, 8, 38, 161915
Next term is not known, but it feels like should be computable just like in the sequence described in the video.
The sequence described in the video (1, 3, 11, 983038) doesn't seem to be on OEIS.
"Computable" is actually a rigorously defined mathematical term and yes, all of these numbers are computable in that sense. Doesn't necessarily mean they are computable in the sense that there is an actual computer that can spit them out ;)
I've thought about it some and I might've been wrong. This grows more like a power towers sequence. 1, 2^2, 3^3^3, 4^4^4^4, ...
So it's not going to be just few thousand decimal digits, more like few trillions decimal digits. And the next one will have its amount of decimal digits being represented by a number with millions of digits.
@@DukeBG That doesn't really match the numbers in the sequence.
Also, looking into it some more I've concluded that it actually seems to grow in hyperoperators - i.e. moving through exponentiation, tetration, pentation etc as d increases.
Heads on each layer create loops at lower layers. These loops are n long - n being the number of heads cut off so far. This leads to loops of loops of loops of... etc... of successorship (cutting off a head from the root node) - which is how hyperoperators are defined, each as a repeated form of the previous.
@@alansmithee419 I'm not sure what you mean by matching, I'm using a subjective description of "this grows like". I would say hydra(5) might be between 3^3^3 and 4^4^4^4
@@DukeBG
Well, they just don't line up at all so I don't know where you got this from.
1, 3, 11, 983038
1, 4, 7.6e12, 4^(1.4e154)
These sequences are nothing alike?
Always cutting off one of the longest heads on the single line hydra should result in the fewest cuts. With the regrowth from 16:27 a recursive function can be formulated:
f(x)=x+(f(x-1)^2+f(x-1))/2
f(3)=9
f(4)=49
f(5)=1230
f(6)=757071
True, but they have a very different view of what "right-most" means. You should at least get the 11 they get for 3, in your formula, before you try and change the rules.
I got the same (numerically, I didn't think about a function). As @kindlin points out, it's not the approach they took but I also noticed that they chose a clearly not optimized approach. But maybe it's because cutting off the rightmost head is less efficient that makes it blow up in a less predictable way and therefore makes it more interesting, I guess.
@@kindlin my hydra grows the heads to the left
@@uzqap to the left, to the left
There's actually a game called Hydra Slayer that's all about chopping off these pesky hydra heads! And it also offers a nice mathematical puzzle, but not the same as the one described here - there's no "tree" of hydra heads, but instead you have a choice of weapons that chop off different amount of heads and cause different amounts to regrow, and you need to get the count to 0 exactly.
negative infinitely amplyfying hydra heads, where you have to supply it with a hydra head to counterbalance a negative hydra head, but still having more negative hydra heads appear somewhere else on the negative hydra.
Spooky.
TLDR; for n=5 the number of steps is 2 * f^N (N) + 1 where f^N is f applied N times and f(x) = (x+2) * 2^x - 1 and N = 41 * 2^39.
We can think of the hydra problem as a process applied to an array of whole numbers, such as [1, 2, 3, 2, 2, …] for example, where there is also a step counter x. Each step removes the last number n and (if n > 1) appends x copies of n-1 to the list. I will denote f_L(x) as the value of the counter when the process has finished clearing a list L, if the process started at time x. First useful property: f_[a, b] (x) = f_[a] (f_[b] (x)). So we can decompose lists into a composition of functions. When k>1, f_[k] (x) = f_[k-1]^x (x+1) which is f_[k-1] applied x times at time x+1. Since any 1 will be removed in a single step, f_[1] (x) = x+1. We can now use the recursive formula to inductively prove that f_[2] (x) = 2x+1 and f_[3] (x) = (x+2) * 2^x - 1. We can check that this is correct by finding the known answers for n=1,2,3,4.
n(1) = f_[1] (1) - 1 = 1
n(2) = f_[1, 2] (1) - 1 = 3
n(3) = f_[1, 2, 3] (1) - 1 = 11
n(4) = f_[1, 2, 3, 4] (1) - 1 = f_[1, 2, 3, 3] (2) - 1 = 17 * 2^16 - 1 = 1114111
Let’s find n(5) = f_[1, 2, 3, 4, 5] (1) - 1. We can simplify it to n(5) = 2 * f_[3, 4, 5] (1) + 1 since f_[1, 2] (x) - 1 = 2x+1. Setting N = 41 * 2^39, we can directly compute f_[5] (1) = f_[3, 3] (3) = N-1. Now, putting this together and using the recursive formula, we get n(5) = 2 * f_[3, 4] (N-1) + 1 = 2 * f_[3] (f_[3]^(N-1) ((N-1) + 1) + 1 = 2 * f_[3]^N (N) + 1 which is the simplest form I could get it down to. If we make the approximation f_[3] (x) = 2^x, we get a lower bound of 2 * 2^2^…^2^2^N + 1 where the power tower has height N. It’s really big. Please let me know if you find any mistakes I’ve made!
slay
The true solution to the Hydra game is to join Hydra. Hail Hydra.
Why take the rightmost leaf in the algorithm? The topmost leaf would have a smaller path right? I'm curious to see how much by?
Because the goal is to get the biggest number, not minimize the length of the game.
Isn't it much more interesting to see how fast the minimum length of the game grows, though? If I want to move 10 centimetres West and go East around the entire world to do so nobody's going to be impressed by how long it took me to move the 10 centimetres. Sure it's a big number but it's horribly inefficient, why would you ever want to do that?
when Wd is 40, does the hydra stop squeaking?
The extremely circular hydra looks like 3blue1brown
4green
y=3 is too small to demonstrate what counts as rightmost. Are we assuming the heads are positioned from left to right in such a way that the most populous level also contains the rightmost head? And in that case, if two levels have the same number of heads, do we start with the one highest up?
Yeah I didn’t get this either. In the y=3 when they were chopping off heads from the root node, those nodes were not the rightmost in the way the hydra was drawn. So “rightmost” must be defined some other way.
Yeah I was also very confused by the definition of right-most.
I'm assuming, since it's the simplest, that the rightmost is simply the most recently created node, and the root is the first node created, and that satisfies the video, but you're right that the y=3 example doesn't have enough heads in the early steps to make a determination between these interpretations of the rules.
@@patrickrobertshaw7020 I was thinking the same at first, but in that case it's not too hard to compute the numbers. Also, if my math is correct, y=4 will be about 500 steps, nowhere near what Tom said. Which made me think it's as described in my comment, as that pattern is way less predictable and should lead to bigger numbers too.
@@LeviATallaksen Hmm. Not so sure. I haven't done the numbers here, but intuitively you'll get the smallest numbers if you chop the higher depth heads as early as possible, that's because chopping a higher head with a higher n will scale the number of future heads needed to be chopped quicker. So you want to get that out of the way.
This strategy, fully resolves a head and its creations before moving onto the next one, which should have incremented n as much as possible before moving to the next head at the same depth.
The other interpretation allows for chopping higher heads sooner in the cycle
@@patrickrobertshaw7020 yeah I think that's correct. And to clarify, it sounds like you must chop a head that is at the lowest level. So if there are heads at levels 2, 3, and 4, then you must chop the heads at level 2. Once you chop the head at level 2, you'll have heads at level 1, which then you must chop the heads at level 1 before moving back up to level 2
"A geometric series is where to go from one term to the next, you multiply by the same thing."
I've tried and failed to find a ready, layperson-comprehensible way to explain what a geometric progression was, and you summed it up in one neat sentence all but flawlessly.
Question. Why is it not 31? Because if onely R remains shouldn't that point then be converted into a head?
7:02 I think they specified that in this minute
You can think of it as the body of the hydra. Without any heads, the body dies.
no more edges to cut
I'm also confused why stumps become heads. It's kinda like 1 chop - 3 heads, which is against the rules
cause you can't chop off the root so even if it did turn into a head, it coudn't be chopped
There was an episode of Infinite series about this! My favorite pbs channel.
PBS Infinite, alongside Numberphile and 3Blue1Brown, were probably the biggest influences on me trying to get into learning maths more, so it's always nice when Numberphile makes me think "I'll go back and rewatch those!". Is a shame Infinite didn't hang around for two long, but there are so many great maths channels out there right now :D
You can prove just by pure logic, that it will always end: You only ever reduce complexity (number of parents) or keep it the same - you never add to it. No matter how many steps it takes to reduce the complexity, it *will* always happen. And once the complexity is down to one level (only on parent - the root), you have basically already won.
That's basically what he did with the induction, but his method being a bit more mathematical subsequently gave him an algorithm which he used to derive the formula for the number of steps required.
@@NikozBGI don't think that's true. The induction doesn't care about the structure. That's why it only gives an answer in the first case.
If your proof is not based on "pure logic", I don't think it counts as a proof ;) I don't think your intuition counts as "pure logic" though, especially since you state that the number of parents never increases, which is not actually true. And you didn't define "complexity" rigorously.
@@unvergebeneid Where exactly do I use "intuition"? And what about "number of parents" isn't rigorous? Your comment makes no sense.
@@NikozBG My point was, that you DON'T need math to prove it.
This is giving me TREE(3) vibes.
What about TREE(3+3i)?
@@Gordy-io8sb I doubt it's defined for non-natural numbers.
@@alansmithee419 TREE(a)+TREE(b)i is a possibility, dimwit.
like tree sequence, this is also a graph theory problem
@@DarkestValar Category theory*
When N is variable total number of steps becomes dependant on the order of chopping. As Hercules we want to minimize that number. In the last example if we go by levels from highest to lowest, instead of right to left, we can lessen number of steps dramatically because biggest steps will happen on the level where nothing can grow.
I agree with Brady on this one - this is obvious. In my opinion the fact that you can clear a level without any new heads growing on that level is the full proof. As long as your n's are finite, there's no way you won't finish. I don't see that any other steps are necessary.
When you say the "rightmost" head is the target for each decapitation, what is the definition of the "rightmost" head? I am under the assumption that the rightmost head would be head(s) on the lowest depth that is not on the original branch, right? Because any new head on a lower branch would be, by default, to the right of the original branch, and all of those at higher depths would be have to be off of the original branch since the tree will never grow upwards.
I'm wondering because I coded this up in a python script with that logic for the head target selection for decapitation and I get the correct outputs for y = 1, y = 2, and y = 3. That is 1, 3, and 11, respectively. But for y = 4, I get 1,114,111, not 983,038. I think I'm missing some understanding in the rules. Also, either way, y = 5 makes my PC angry. Haha!
EDIT: I've also retried this algorithm where the target head is the one on the depth with the maximum number of heads, prioritizing those on lower depths first, and then prioritizing those on the higher depths. In both cases, y values 1 through 3, again, came out correctly. But the resulting values for y = 4 for either of these rightmost selection algorithms were 720,891 and 327,677, respectively. None of these methods for choosing the "rightmost" head align with the expected outcome. I can see no other way to define what the "rightmost" head is. Help me, please!
EDIT(2): Also, side note, using original selection algorithm (where lowest branch not on original branch is selected for decapitation unless completely pruned, then highest head on original branch chosen) I've tried to optimize the process somewhat by bulk decapitating when the target is on the lowest branch. I've been letting it run for just over 5 minutes so far and the number of decapitations is already greater than 10e62500 and it's nowhere near done (still over 22 trillion heads on the 2nd and 3rd nodes each). This definitely wouldn't finish in my lifetime. I'm not sure that it would finish before the heat death of the universe.
Yeah I got your values of 720891 and 327677. There is too much ambiguity
I also got 1114111, 327677, and 720891, depending on how "rightmost" is defined, and where new heads are growing (be it immediately right of the existing heads on that level, or further right than any currently existing leaf on any level). Poorly defined procedure indeed.
No real Hydras were harmed during the making of this video.
Steps for killing a level 1 hydra is constant: 1.
Calculating steps for killing a level 2 hydra needs addition: 1+1+1 = 3
Calculating steps for killing a level 3 hydra needs multiplication: ((1+1)*2+1)*2+1 = 11
Calculating steps for killing a level 4 hydra needs power: (1+1+4*(2^2-1)+1+17*(2^15-1)+1)*2+1 = 1,114,111
So i believe killing level 5 hydra will require tetration, and i expect it to be astronomical.
How did you come up with those formula? If the tetration is relatively small, a computer could handle it.
by my calculations (really inaccurate), if you were to develop a software for it and allocate the graph to RAM (where the node is defined as a set of memory adresses to its children) it'd take roughly 10 petabytes(10*1024TB) of ram (which still fits 64-bit architectures on a single computer)
@@kindlin I just followed my back-of-the-envelope model to count the steps. No formula for level 5 because there are too many terms to write it down.
@@peguera_eu You only need to store the step counter and the number of heads on each level to run the calculation. But i think even the step counter alone would be too big to store in a computer.
@@suan22 maybe it fits on an unsigned long/bigint
btw I'm aware that you don't need a graph structure to make the calculation, I just wanted to state how big one'd be
I'll note that when you get to that last game the order of operations matters quite a bit. For example for the y=3 case if you focus on not the 'right-most head' (which honestly seems a tad ill defined since where do you add heads?) but rather the available head at the greatest depth the number of steps reduces from 11 to 8, and I anticipate that for y=4 the effect is even more dramatic.
I tried it for y = 4, and if I did the math right it is 48 total cuts if you always chop off the highest most head. Y = 5 is 1179, assuming I didn't make a mistake here either. Thank you friend.
@@bebe8090 nice! I also got 48 for 4. It was so low I was worried I did something wrong, but seems not. It's amazing how much of a difference the order of things matters here.
For those who are confused by the video counting 30 heads @4:58, but then later calculating the result as 33 @15:36 (or "total=3+30" [but the graphic display erroneously shows 30. pause and look at the brown paper]), the calculation is accurate, but the counting has omitted the three extra heads that grow, as mentioned @3:47. Counting these 3 extra heads makes the count match the calculation.
I absolutely love the silly animated hydras!
When n is fixed, the formula is a generating function which can have recurrent relations between the coefficients.
It is not clear what they mean by the left-most head. If I replace that with the last added head, I get 1114111 steps for a path of length 4.
I did the lowest available head in the tree and got the same result as you (which thinking about it it does seem we did the same thing by thinking about it in different ways). So I'm not sure. Maybe if they gave a source for the ~950,000 number.
Ah, okay. So I'm not the only one then.
I also think 1114111 is a way more interesting result, simply due to the shape of the number itself. xP
It appears that "right-most" is very under specified here. How do you compare the "rightness" across depths? The ones that grow back, are they always right-most? Does it depend on how many are left in the depth above it?
Rightmost here just depends entirely on how you draw it which is surely not mathematically deterministic
I am impressed, how slow it grows. Roughly like a factorial. Noware near to Graham sequence (not to mention tree sequence aka tree(3)).
Had an impression that in a hydra game it grows faster.
I estimate the second version of the Hydra game described in this video is somewhere between f_w on the fast growing hierarchy and grahams's g series (of which graham's number is g64), both it and graham's function would then be between f_w and f_(w+1).
This is because as depth of the initial tree increases, the hyperoperator that would represent its growth increases (d=4 is described by an exponential, d=5 can be described with tetration etc), and all of the finite order FGH functions are fixed in place in the hierarchy of hyperoperators (f_2 is exponential, f_3 is tetrational etc).
It is possible (by which I mean I haven't personally proven otherwise) that it is instead the case that the hydra series is faster-growing than all finite order FGH functions (f_a where a is any integer), but slower than any transfinite order FGH function (where f_w is the first such function). But in any case it should be on a similar order as f_w (increasing hyperoperators with function input).
Working it out on paper, the reason the jump from 3 to 4 is so large is because the leaves at the base grow exponentially over the course of the game. Or in other words, steps where you cut off level 2 leaves grow exponentially far apart. If you start from a level 5 hydra, I'm pretty sure cutting off level 3 leaves will be exponentially far apart, and solving the whole game will require tetration.
Surely it depends where you draw the new heads? For the y=3 example. Because if you draw the s2 heads to the left you'll get a different final number. This only works because you've drawn them as the right most heads?
Yes, that was the result for that specific rule set. If you draw the heads a different way, that’s a different rule set.
I think "right most" actually was intended to mean "the right-most *lowest available* head."
E.g. if you can cut off a head at the base of the hydra you must.
In this case though the specifier "right-most" doesn't actually matter, so I'm not sure what they were doing.
I watched it again and they never mentioned a rule where the heads have to grow back to the right. Was that an actual rule that they accidentally omitted from the video?
@@SethLavender that's the only way I can see it working so I assume so.
@@karmachameleon326 but the drawing of the heads isn't specifically mentioned in the rules right? Just their starting node, not which side to draw them on?
Assuming that the mythical hydra doesn't follow the rules of your hydra game, and there is a never ending supply of 2 heads that grow for each head chopped off, my answer would be to fight the hydra in a cave with the cave opening being smaller than the cave itself. Eventually, the hydra would grow so many heads that it would be trapped inside the cave, unable to squeeze its way out. Even if it gnaws off one of its heads, two grow back, right? Alternatively, if conservation of mass is considered, and heads grow back smaller and smaller (like Jake stretching too far in that one Adventure Time episode, even if the Hydra escapes the cave, each head would eventually be so small that the bite would be ineffective, and the beast with thousands of tiny heads would be easily defeated before it could escape the cave and grow larger.
@Numberphile: I tried to reproduce your number for y = 4 by Matt Parker method (inefficient Python script), but I don't reach the same values.
What head do you consider the "rightmost"?
For example: after step 14 I again have a hydra of length 3 [1, 1, 1, 1]. Cutting of the outmost head, yields [1, 1, 16] in step 15, [1, 17, 15] in step 16, ..., [1, 15, 15] in step 18. Which one is now the rightmost head?
I tried it and got 1114111 cuts. My logic is:
Whichever leaf you cut, following it up with cutting "the rightmost leaf" will always work through all of the new leafs that have been produced by that cut, until you are left with your original tree minus the first leaf you cut.
Let f(n,s) be the cost of cutting off a leaf at level n where s is the number of the cut. Then f(n,s) = 1 + f(n-1,s+1) + f(n-1,s+1+f(n-1,s+1)) + ... repeated s times
Then you cut down the original tree by cutting an end leaf at level n (taking f(n,s) cuts), incrementing s by the number of cuts needed, and repeating with the next end leaf at level n-1
@@Matthew-eu4ps Mhm, I tried going with the following rule for "rightmost head":
If one level has more heads than all the other levels, than the overall rightmost head is the rightmost head in this level.
If there is a tie between levels, I go with the highest level. (Following the example in the original comment, step 19 would be [1, 34, 14])
So I've done some coding, and the value of n=5 is so so so far out of the realm of computability. Using various shortcuts to reducing the computational load, after reducing the head of the Hydra by height 2, It gets in the shape (lowest height first) [0 22539988369408, 22539988369407, 0, 0], at round: 22539988369409. To reduce all nodes on the second height? That's 2^22539988369408 * 22539988369409 more moves. That is approximately 10^6,785,212,601,122. Once you;'ve done that, you make that amount more heads which takes (2^(10^6785212601122))*10^6785212601122 more moves, then again for 2^((2^(10^6785212601122))*10^6785212601122) * ((2^(10^6785212601122))*10^6785212601122) until you've done it 22539988369403 more times.
It's a big big number.
I implemented it in javascript with "rightmost" defined as at the highest step with most nodes total:
it overflowed to infinity after reaching step 1.23e308 with [1.23e308, 4324378, 1441789] remaining,
but after doing some abstract math estimations from there,
and defining a notation for repeated exponent-first power called ^^ here
and for example 3^^4 = 3^(3^(3^3))
I estimated n=5 to 2 ^^ 1441794.04 within 0.01 digit accuracy on the "super" exponent.
you can also define ^ as ^1, ^^ as ^2, and x ^n y = x ^n-1 ( y times total (x ^n-1 x))
these are repeated exponent-first powers of the previous order
with these high operations and "highest step with most nodes total" logic,
chopping all x hydra heads on any height n and below once equal can be estimated at once !
and have the rounded effect of increasing the step total from (2 ^n-1 y) to (2 ^n-1 y+x)
its not perfectly accurate but would not deviate beyond less then a digit of the relevant exponent :)
you can estimate until overflow in code and describe the remaining estimate steps as
a nesting of the appropriate power functions for the remaining higher head heights and the value before overflow.
Hang on, there was a big assumption in the straight chains example at the end, in that new heads grew to the right of existing steps. If new heads grew to the left of old heads for y=3, it would only take 9 steps. "Right most" needs a more robust definition if we're gonna follow that rule.
Any estimates or lower bounds for y=5?
with the logic of cut at the highest with most nodes total as "rightmost" I actually estimated y=5 pretty well !
but to describe it you need repeated power
so I defined x ^^ y as x^(x^( ..y times total .. (x^x)))
and with this I can write it down as 2 ^^ 1,441,794.04 and its accurate up to 0.01 of the "super" exponent.
16:09 Because of how quickly the heads compound, it is much faster to stick with the initial strategy of clearing the highest level first before moving down. But even then, the number of moves explodes quickly. I found the following recursive formula for it:
H(1) = 1
H(2) = 3
Let p = H(n-1) and q = H(n-2)
H(n>2) = 1/2 * [(p+1)(p+2)-q(q-1)]
The series goes: 1, 3, 9, 49, 1230, 757071, 2.86E+11, 4.10E+22, 8.43E+44, 3.55E+89, 6.31E+178
Excel couldn’t calculate anything past n=11. In the limit, the value is squared each time
Does the root become a leaf at the end? Would that make the length of the game one step longer?
The bit at the end really reminds me of TREE(3), except that Linear-Hydra(n) becomes incomputable at 5 instead of where TREE(n) does at 3. So now I have a new monster of TREE(Linear-Hydra(G(63))).
It's always mind boggling to see us stumble into these mathematical beasts where we can likely never compute them, and even if we could, they're just so absurdly large that knowing the specifics of how many digits long the number is contains enough information to turn your head into a black hole.
for y = 4 I counted 1114111 heads. After 15 steps we arrive at a position, where when chopping one head of we add the current number of step to the bottom node. I.e. after step 16 we added 16 heads to the bottom. This requires another 16 steps. Then we can chop of one of the next "parents" heads. This happens at step 33. Therefore, after step 33 we have 15 heads on the parent node and 33 heads on the grandparent node. eliminating those 33 Grandparents, we delete the next parent head at step 67, adding now 67 heads to the grandparents node. We eliminate those 67 heads and chop of the next parents head at step (67*2)+1 adding 67*2+1 heads to the bottom. We can keep on playing this game until all parents heads are chopped of. Therefore, I found: let k be the number of initial steps and n be the number of parents head in this position. The function is defined as \( f(x) = (x+1) \cdot 2 \). Applying this function recursively \( n \) times from \( x = k \) gives the following transformations:
\[
x_0 = k
\]
\[
x_1 = (k+1) \cdot 2
\]
\[
x_n = (k+1) \cdot 2^n + \sum_{i=0}^{n-1} 2^i
\]
Where the sum of the series \( \sum_{i=0}^{n-1} 2^i \) is the sum of a geometric series:
\[
\text{Sum} = 2^0 + 2^1 + \ldots + 2^{n-1} = \frac{2^n - 1}{2-1} = 2^n - 1
\]
Simplifying the formula, we get:
\[
x_n = (k+1) \cdot 2^n + 2^n - 1 = 2^n \cdot (k+2) - 1
\]
For example, with \( k = 15 \) and \( n = 16 \):
\[
x_{16} = 2^{16} \cdot (15+2) - 1 = 1114111
\]
Interestingly the answer presented can be expressed as 2^(16)*15 -2, so maybe I made some errors.
Given my rule of thumb (the formula can be applied for all of those combinations). I can predict that one has to chop of approximately 45079976738815 heads for y=5.
You, I, and at least on other I've seen in the comments all got that result too for d=4.
As for d=5, that seems incredibly small. I'm having a hard time articulating why but the number should be vastly larger than that.
Remember each head on the grandchild of the root node (the one that gets 15 heads which leads into this exponential mess for d=4) will trigger an entire similar exponential back and forth between heads attached to the root node and heads attached to the root node's child. Only once that's over you will have to return to the root node's grandchild, cut off another head there, and then launch into another one of these exponential loops with >1000000 steps in it. Rinse repeat I guess a few dozen times (it will be bigger than the 15 that happened for d=4) and you get ridiculously big numbers.
Edit: just have a look at it by hand by doing some of the initial steps, you'll soon see that not only are you going to get huge numbers but you're going to get them long before your tree even reduces to being smaller in depth than the d=4 case. Meaning you will eventually have something similar to the d=4 case, but starting with an n that is vastly larger than 1 (which is what we started with in the d=4 case).
@@alansmithee419 Exactly the problem can be solved recursively. Now it turns out actually that the formula applies always, when we have n hydra heads emerging from a parents node above the grandparents node, where when cut off the heads do not respawn. That being said one can apply the formula in between calculation steps, and predict at which step this entire set of hydra heads are cut of entirely, while leaving the main strain untouched. (you have to subtract 1 to actually end up at that step, where only the main strand is left, because otherwise you would have deleted another head an spawn a new one at respective positions.) Using this information one ends up with a configuration where one has 40 parents heads at step 39. plugging into the formula yields:
2^40*(39+2) -1.
@@alansmithee419 I also have it written down by hand, but maybe you might be able to cook up with the same solution. At least that would be great.
@@TobiliGames My point is that after you've done this (minus one step because you've skipped to the end) you will be left with a tree that is the same as the d=4 one, only you now have n=~2.25e13 as your starting point. This will continue to explode.
@@TobiliGames I created a recursive solution similar to yours, but a bit different. I also get 1114111 for the d=4 case.
However, my estimate for d=5 is vastly larger.
Using a computer simulation, I determined, that it takes 22,539,988,369,406 (~2*10^13) steps until the d=5 case will turn into a d=4 graph.
Then, cutting the d=4 node creates 22539988369407 (call this number m-1) d=3 nodes.
The first d=3 node is removed in Step m, creating m d=2 nodes, we'll now look how many steps removing them takes.
Step m+1: Remove first d=2 node, leaving (m-1) and creating (m+1) d=1 nodes.
Step 2(m+1): All d=1 nodes removed.
Step 2(m+1)+1: Remove next d=2 node, leaving (m-2) and creating 2(m+1)+1 d=1 nodes.
Step 4(m+1)+2: All d=1 nodes removed again.
Step 4(m+1)+3: Remove next d=2 node, etc....
repeat until no d=2 and d=1 nodes are left.
We can see, that the steps where a d=2 node is removed follow the pattern: a(n) = 2^n*(m+2) - 1, when removing the nth node (starting at 0).
This operation has to be repeated m-times and after removing the last d=1 nodes, one d=3 node can be removed (fits well into the sequence).
So the step at which the next d=3 node is removed is a(m) = 2^m * (m+2) - 1.
Removing this d=3 node now creates a(m) d=2 nodes, so we can again remove all these node, finding a new sequence for their steps: a2(n) = 2^n * (a(m)+2) - 1.
Since we need to remove a node a(m) times, this results in removing the next d=3 node at step a2(a(m))
If we simply define a(n) to be 2^n*(n+2) - 1, this simplifies to a(a(m)).
We now define a new sequence for the steps at which the d=3 nodes are removed, call it b(n).
We know b(1) = m (by definition).
By the last two steps, we see a pattern, that b(n) = a(b(n-1)).
The last d=3 node will then be removed by step b(m-1).
Computing a direct formula for b(n) is not simple, but we can find a lower bound for it by disregarding some terms.
We can use the exponential ã(n) = 2^n as an approximation, as ã(n) < a(n) for n > 1.
Using the exponential, we can see, that this lower bound for b(n) is just repeated exponentiation (a power tower), which we can write using Knuths arrow notation as
b(n) > 2 ↑↑ n.
So our total number of steps until all d=3 nodes are removed is at least
2 ↑↑ 22,539,988,369,406
Which is really a gigantic number
As a programmer by trade... Making a program to brute force that would be simple.
You just need an array of size distance, each cell is the number of heads at each distance. Have a counter to keep track of step.
Then you go through the array, remove 1 from the top cell, add step count to the cell 2 lower, and add 1 to step count.
When you add, repeat the previous process for the cell added to - repeat until cell value = 1.
That iteration will mean it goes deeper down as it needs to before going back up.
The issue is that it would take quite a while to process. At 1 operation per ms, you'd need 1s just for d=4... If 5 is a result a million higher, that's a million seconds to process. 11 days. And it's probably bigger than that.
Idk if this would help anybody computing terms of this sequence, but the algortihm can be interpreted as adding 1 to the total if you remove a head not directly connected to the root and multiplying by 2 whenever you remove all of the heads connected directly to the root. So ((1+1)2+1)2+1 = 11 and ((((((((((((((((((1 + 1 + 1)×2 + 1)×2 + 1 + 1)×2 + 1)×2 + 1)×2 + 1)×2 + 1)×2 + 1)×2 + 1)×2 + 1)×2 + 1)×2 + 1)×2 + 1)×2 + 1)×2 + 1)×2 + 1)×2 + 1)×2 + 1)×2 + 1 = 1114111.
tried to do the d=4 tree myself and got the very weird result of 1114111.
Not sure what I did wrong but the result was fun.
Me too. I can't get 983038
Same here...
also get 1114111.
Yeah some others got 1114111 as well. Seems unlikely none of us would get it right.
d=5 is interesting though. It is *very very big.*
I also got 1114111.
Also I'm pretty sure 983038 cannot be correct, as the correct solution must be an odd number, I would be happy if someone could check my reasoning.
Since we always chop of the newly generated heads next, the d=4 hydra will eventually become a d=2 hydra. Call the number of steps it took to get here m-1, then cutting the d=2 head is step m.
Then this action spawns m new heads at d=1.
There are now m+1 heads (m generated + 1 original) at d=1, which take m+1 steps to cut, after which we are finished.
In total, this means, cutting all the heads took 2*m + 1 steps, which must be an odd number, regardless of m.
I love how mathematicians say things with such confidence, like the hydra game always has an end, but quickly skip past the 'if we assume' part :p
From what I know, the hydra had one “main” head that was indistinguishable from the others, except that when cut off the hydra dies, and that would be a whole different interesting mathematical situation
Was looking for this genzlemans nametag, till I saw the description.
Great video through and through
Bro out here looking like Machine Gun Kelly while talking about "killshot" and thought we wouldn't notice
you got me
So, I just calculated the 5 step rapidly growing hydra except with the strategy of cutting the farthest head first, and I got 9,472 steps. The same strategy defeated the rank-6 rapidly growing hydra in 132,985,715 steps.
I calculated this with a hand calculator through reducing the steps to "super-steps" per layer and creating a simple formula the next layer's heads based on the previous layers and the number of heads of all previous. (I could probably make a formula for the entire hydra this way...)
I tried implementing it in code and while it works fine for trees of size 1,2 and 3, for size 4 I am not getting 983 038 but rather 1 114 111. Is there any chance that number was incorrect? I tried looking it up in the encyclopedia of sequences but apparently it doesn't exist with either number.
Same! I think wikipedia got it from a blog, and the blog is wrong :)
Holy cow, I got the same too! I am thinking maybe there's something wrong with how we define the "rightmost" leaf. The way I implement this is just by adding new leaves at the top of the queue. But apparently this is incorrect because the answer is not the same with the video
Many people in the comments have been reaching the same result, and no one seems to have any idea where the 983038 figure came from. Definitely seems to be wrong.
I think *Tom's mind* has the strength of Hercules. Excellent explanation.
At 5:00 shouldn‘t there grow a new head at the root if you chop of all leaves adding one more head, so its‘s 31 heads to chop?
i think because the root doesn't have a parent, a leaf node (head) should always have parent
19:30
The thing is if it's larger than a few quadrillion/quintillion (exact boundary not known to me) you need more than brute force to compute that.
Loving the animation on this.
Thanks to Pete McPartlan
@@numberphile You should make another video on the Buchholz Hydras, a more powerful version of the Kirby-Paris Hydras. It creates bigger numbers than even TREE(3)!
Okay, I tried writing this up and I think there's something ill-defined about "right-most" or whatever. My slaying of the 4-node hydra was much more efficient than that almost-one-million step result claimed here.
Does anyone know the rules for cutting heads in order? Is the newest head always the most "right"?
Someone proposed that the intention was to maximize the number of required cuts, which I believe would have been better defined by "Always cut the lowest available leafs" rather than "Always cut the rightmost available leaf". But if we assume new leafs are always growing further right than any existing leaf at any level, then the two directives are effectively equivalent (although the former is clearer and would have avoided some of the long discussions in the comments).
The reason you can just throw a supercomputer at this is that supercomputers are massively _parallel_ devices. This isn't a parallel problem. Each step requires the output of the previous step to be executed because you might need to remove a leaf added by that step. So you can't split it up and run it in parallel. We could if you modified the rules to allow selecting any leaf. That means each step only cares about two nodes, instead of the entire tree.
Even the modified version still isn't super trivial to implement. If your unit of work was a single step, you're going to have massive contention keeping the step count synchronized. So you'd need to divvy up the tree into subtrees or something like that. But that doesn't seem to be an option because our starting graph is so small, simple and degenerate. Instead you might need some kind of rules for selecting a leaf to guarantee you can merge the output of all workers. If there are N workers, pruning at most 1/N of the leaves from any node, for instance.
Can I ask if there is a video for the "Large Number Garden Number" in the works? There are very limited resources on this subject...at least for the layman!
This is peak animation.
Math enjoyer here: why not attempt to plot it using an exponential regression in something like Excel? With the first four points and the number of cuts, a spreadsheet program should be able to calculate the function representing the hydra game with these rules.
So that's crazy i haven't learned like this, thank you
I am getting 1, 3, 11, 1114111 instead of 983038
Same here
Same.
I found a solution for the order of growth if we assume that taking the rightmost always results in removing the lowest head.
An endpoint head on layer a of the hydra has an assocaited reduction function, fa(n) which is the number of cuts it takes on step n to return to an identical hydra without that head.
For y = 1, f1(n) = n+1
For y = 2 f2(n) = 2n+2
For y = 3 f3(n) = 2^(n+2) + n*2^(n+1) + 2^(n+1) - 2, and so forth.
Now, define a function Ga(n) , with G1(n) = n+1 and Ga(n) = n iterations of Ga-1(n). These will follow the form
G1(n) = n+1
G2(n) = 2n
G3(n) = n*2^n, which behaves like 2^n for large n, and so on.
As n gets very large, only the behavior of fastest growing part of each function fa(n) matters. To see why only the fastest growing portion matters, consider reducing a height 3 head on step 1000. This will result in a value of approximately 1000*2^1001. Increasing n at this point only marginally increases the multiplying term, while massively increasing the exponetiated term. This same logic applies to fa(n) for greater y, so the rate of growth roughly follows Ga(n).
Due to the magnitude of growth by higher Ga(n) absolutely dwarfing the growth of lower Ga(n), one only needs to consider the heads generated by the initial cutting down of the hydra to find what order of n needs to be plugged into the largest Ga(n). This generates a number of end heads on layer i following
1 for i = a-1
a-1-i for 1 < i < a-1
a-1 for i = 1
As this occurs on step a-1, it is equivalent to starting with a hydra containing 2(a-1) layer one heads and the rest of the hydra as it appears on step a-1. Taking the associated Ga(n) functions, one obtains the form of H(a).
The lower bound for the growth of straight hydras of height a follows H(a) = Ga-1(Ga-2(Ga-3(Ga-3(...(0)...)))), with the number of compositions of Gi equal to
1 for i = a-1
a-1-i for 1 < i < a-1
2(a-1) for i = 1.
There are various ways to improve this lower bound, such as replacing Ga(n) functions by their assocaited fa(n), but this doesn't effect the growth rate of H(a).
Also for those curious, the size of y = 5 is a power tower of roughly 2.25 trillion 2s. So not at all computable
My guess as a demonstration after 5 mins video:
some definitions and immediate yet important properties:
a.let's T be a rooted graph (tree). let's define the depth of a node (possibly leaf) as its distance to the root.
b.Let's define the depth of the tree as the maximum depth among its nodes.
c.We note # the cardinal ie the number of elements in a set.
d.Also we note a node can be cut if and only if it's a leaf (no child).
e.Finally, a leaf will remain a leaf after we cut another leaf since the grow occurs on the grandparent of a leaf, which is not a leaf by definition.
f. head and leaves are the same thing here. Hydra and tree too
i. Assuming depth(Tree) = d >=2; We will demonstrate we can reduce by one the depth of the graph with a finite amont of steps.
let's define Si ={x in T / depth(x) = i} the set of nodes of the Tree with the distance i to the node.
cutting a leave of depth i will decrease #Si of 1 and increase #Si-1 of 2 (increment ignored if i =1).
All elements of Sd are leaves since Sd is the set of maximal depth nodes. If they had any, the child depth would be greater than the depth of the graph which is a contradiction. Thus Sd only contains leaves, they can be cut. (and they will remain cuttable after every step using the property (e))
We now can count #Sd (cardinal of S ie the number of elements of Sd), it's an integer, we'll assume #S = n.
, Cutting those n leaves will have the effect of decreasing #Sd to 0 and increase #Sd-1 of 2n.
At this step, we have no leaf in Sd and some leaves in Sd-1, the depth of the tree is now d-1.
Conclusion of i: if the depth of the Tree is d>=2, we can reduce it's depth by 1.
Repeating this process d-1 times will lead to a Tree of depth 1 with possibly an enormous number of heads, but all of depth 1.
So in any case, an hydra can be reduced to a tree of depth 1 after some steps. (case 1, initial depth >=1; case 2, well it's already depth = 1)
Now we have to show we can kill a hydra of depth 1. All heads are now in S1, we note #S1 = m . Cutting all of them won't make any head regrow since they have no grandparent. We cut all the m heads.
We now killed the hydra, no matter how she looked initialy.
Bonus. I tried to make it formal and define everything to allow anyone with no math background to follow this. A simpler explaination would be easy, just cut all the most distances heads => reduce the max depth, and repeat until death.
Bonus2: the order of the cuts don't matter, just cut any of them in the order you want will and up killing the hydra
(to demonstrate it, you could show result of bonus3 to define a non variating number z: the sum defined in bonus 3 for current (just plugging the value) + the number of cuts already done, this number should not variate after a cut). So the current sum value = z - number of cuts done , so the current sum value will reach 0 after z which doesn't depends of the order of cuts).
Bonus 3: a head with depth k will generate 2 heads with heads k-1, then 4 with heads k-2... until 0 so we ll have to do
sum(j from 1 to depth(head)) 2^(j-1) to kill a leaf and all the ones that will grow after we kill it and the new ones reccursively.
This sum is equal to 2^(depth(head)+1) - 1, a head of depth 1 will need only one cut, a head of depth 2 will need 3 and so on.
Thus we can kill any hydra with an easily calculated number of cuts in any order, and this number will be the sum over each node of 2^(depth(node)+1) - 1.
I know it's unreadable but I enjoyed it. If you did follow (or just read), here is a potato:
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣠⠤⠴⠒⠋⠉⠉⠉⠉⠙⠒⠲⠤⢴⣤⣄⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⣀⡴⠋⠁⠀⠀⠳⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠉⠳⡄⠀
⠀⠀⠀⢀⠴⠊⠁⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠆⠘⡄
⠀⢀⠜⠁⠀⠀⠀⠀⠑⠀⠀⠀⠀⠀⢸⠓⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡤⠀⢱
⢀⠎⠀⠀⠀⠀⠀⡤⣤⡀⠀⠀⠀⠀⠀⠉⠀⠀⠀⠀⠀⢀⠀⠀⠀⠀⠀⠀⠀⢸
⡎⠀⠀⠀⠀⠀⠀⠈⠒⠣⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⠄⢀⣀⣠⠏
⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⠀⠀⠀⠀⠀⠀⣨⠁⠀
⡟⠄⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠀⠀⠀⠀⠀⠀⠀⠈⠛⠃⠀⠀⠀⣠⡾⠃⠀⠀
⢱⡈⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠑⠠⡄⠀⠀⠀⠀⠀⢀⣠⠀⣀⡴⠋⠀⠀⠀⠀
⠀⠑⢤⣀⠀⠀⣖⡆⠀⠀⠀⢄⡀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣠⠏⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠈⠙⠒⠢⠤⠤⣄⣀⣠⣤⣬⠶⠶⠦⠤⠶⠖⠚⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
edits: spelling, and might come back to demonstrate bonus2 (done on paper)⠀
edit2: I watched the viedo, this demonstration is done for 2 heads growing back (didn't pay much attention), but it remains very similar for any other number of regrowth
edit3: with the variate number of regrowth in the end of the video, the formula isn't so easily derivable and the order matters. But the demonstration before bonuses hold since you can cut maximum depth heads at each steps and the number of regrowth in lower depth won't affect this step. I believe it's also the fastest way to kill it.
not cutting of the right most head but just one of the highest ones: can we just write the number of heads connected to a joint to an array?
like [0 0 1] would be one head.
Each step we remove the topmost number by one and add n at index -2.
But about the "cut right head": why would the heads grow right of the stem we are currently working on? why not on the left so we can focus on the highest heads?
This vaguely reminds me of the Ackermann function, with how each step decrements a value from one variable (W_d) while perhaps dramatically increasing the value for another variable (W_d-1). Is there a known connection between the two? Can one design a graph and rule for the n's such that the number of steps exactly equals the Ackermann function for some chosen values?
Is there a version where instead of the right most head you always do those with the highest D value 1st - would that not be the most efficient way?
(Massive assumption, i aint able to do the calculations)
Are the total algorithm steps smaller if the new leaves are added on the left instead of the right?
Hercules should have just cut of all the heads at once from the base root, steps always = 1 that way! 🤣 Great video Numberphile love the content, as always it makes me want to go program something lol
One question I have. How do you know where to draw the new heads. because for the last problem, where you draw the heads changes what the answer is. If you draw every new head to the left of the higher branches, you chop off from top to bottom. but if you don't, you can end up increasing n on smaller layers before chopping the higher ones.
Smells a bit like the Collatz Conjecture...
Yes, the nodes and values can grow like "Ladders" (in surprising ways),
there's always a "Snake" that eventually takes the value back down toward the ground floor...
I guess i can see a slight resemblance, but they're actually very different in terms of which areas of math they are relevant to. The hydra game is about combinatorics and the proof that they will always eventually count down to 0 is not difficult. However, we have no idea whether the Collatz conjecture is true or not. Only that if there are counterexamples, they are so large that we can't find them on supercomputers. The d=5 hydra has too many steps to calculate (at least with brute force) on any supercomputer, but we still know it's finite.
Yeah, taking a crack at the level 5 one it quickly becomes very obvious that this is going to blow up dramatically.
You end up more than doubling the total head count for each excess one at the second level and end up throwing well more than 2^21 new heads onto the 3rd level when you finally get back around to cutting off the level 4 head. From there it gets hard to even think through how to keep track of the rest of the calculation through to the end.
Please explain!
I feel like this could be done much more efficient, if you don't go to the right most branch and instead go to the top most, or one of the top most branches, I could get the sequence down to HYDRA(1)=1, HYDRA(2)=3, HYDRA(3)=9, HYDRA(4)=49 which is significantly less than 1, 3, 11, 983038, I feel like I've miss understood something, because it feels like it's inefficient to cut of the bottom branches before any other branches, since cutting them off will result in the 'S' growing without actually adding more branches, this means that once you've cut them all of at the bottom and you get back to the top, your 'S' is very big and will cause the next round of branches at the bottom to be even bigger, causing exponential growth. I'm sorry if this is a silly question, I understand that this is way out of my league since I haven't even started high school yet, but if some kindhearted soul in the comment field below could please explain to me the reason behind this method, I would be very great full.
The goal with this way of fighting the hydra is basically to showcase, just how absurdly different it CAN get, simply by having the worst possible strategy.
I guess having the direct comparisons would be interesting as well.
Also, the actual result to the highest amount of steps on the fourth one is 1114111, not 983038. Somehow they got a wrong value in the video.
Cool idea but it needs a different name.
I mean.. unless the heads grow from where you just cut, it's not a hydra is it?
P.s. Proposed alternative name: The Bush Pruning Game.
I disagree. There are countless mathematical analogies to objects that does not exhibit a fundamental property of that object. It's not the Herculean hydra but that doesn't mean it can't be a hydra in some sense.
What name would you suggest for when you cut something off and more of it comes back? Is an excellent choice if yoi ask me, they simply arent interested in the trivial case where it blows up to infinity.
@@fatsquirrel75They could just go with the analogy of pruning a bramble bush. Snip one branch and 2 new ones pop up at the grandfather node a few days later. It's also a closer analogy to something that exists.
@@Marlosian , mathematicians like Greek mythology more than gardening, apparently. I like your idea, though. It sounds like a more fitting name.
@@SgtSupaman Instead of hydra....kudzu?
I did some messing about and started to notice a patern. Not awake enough to translate this further into proper formula's... but here's my 2 cents.
d = distance from the root (my logic goes from that side, so it's easier for me to redefine d here)
s = steps
we have 2 kinds of interactions:
Chopping = chop 1 head, s amounts of heads grow below
Pruning = we are at d = 1, any heads chopped are gone and don't create new ones.
take 1 head at d = 2. We need to: Chop, followed by pruning of how many heads it spawned.
take 1 head at d = 3. We need to: Chop, (s heads spawn at d = 2), chop (one less head at d = 2) prune at d = 1, chop at d = 2, prune at d = 1 (repeat until heads at d = 2 are 1. So basically the s (at moment of chop) amounts of time)
A chop is a single step, a prune is always equal to the amount s was when that bunch of heads was created.
y = 4, starts with 1,1,1,1 ==(chop)=> 0,2,1,1 ==(chop)=> 0,1,3,1 ==(chop)=> 0,1,2,4 ==(prune)=> 0,1,2,1
chop, chop, chop, prune = (+1+1+1)*2
0,1,2,1 ==(chop)=> 0,1,1,13 ==(prune)=> 0,1,1,1
The next set will be "chop chop prune" followed by a large amount of "chop prune" (so +1,+1,*2, (+1,*2)repeated s times (this s is what the step count was when we started this line)
Anyhow, long story short, I looked at the set for Y = 5.
By the time you get down to 0,1,1,39,1 you are at step 80.
We need to repeat "chop, prune" 38 times to get back to a linear graph.
So 80 plus one, then times 2 repeated 38 times
You end up at roughly 2.254*10^13.
And that just reduced your length from 5 to 4. (and now every head chopped adds 22.5 quadrillion new heads)
And those new heads aren't at pruning level, they are at chop chop prune level, meaning so many many many +1+1*2 and +1*2's are needed.
At this point I think I fully feel the size of this number coming and no longer feel the desire to look any deeper 😛
this game is also called the central finite curve game of convergence.
Edit: I'd missed that tge number of heads regrowing is based on the number of steps taken
I presumably missed part of the explanation, but I don't understand why the order you cut heads will affect the number of chops?
Im going to rewatch and update this if I figure it out, but if I haven't, would anyone be able to explain it?
correction: the number of steps for a path of 4 nodes is 1048575, not 983038
edit: nevermind, for some reason i thought 15+2=16. but 15+2=17, which means it's actually 1114111. the affected parts of this comment have been fixed
anyway, it's not actually that hard to calculate. i mean, it's obviously just a slightly modified version of the fast-growing hierarchy, so it can't be difficult to get pretty much as close as we can.
normally, the FGH works like this:
f_0(n) = n+1
f_α+1(n) = f^n_α(n) (or less formally, f_α(f_α(...(f_α(n))...)) with n f_α's)
there's also a limit case because α can be an ordinal, but that doesn't matter for the hydra game. the FGH is kind of the standard way of measuring sizes of large numbers.
and what's the hydra game? well, let's modify the FGH slightly:
F_0(n) = n+1
F_α+1(n) = F^n_α(n+1)
now go through all the nodes (not just heads) from left to right, and consider their distance from the root. subtract 1 from the distance, put it in the subscript of F, and then put brackets around everything you'll write after this. at the end, write a 1 inside the innermost brackets. and subtract 1 from the whole thing afterwards, since at the first step we already had n=1 instead of n=0.
it's easy to see by induction that this works:
at every step in the calculation, the number in the innermost bracket is the number of heads that will be added the next time you cut one off. so it increases by 1 at each step, which accounts perfectly for the n+1's in both lines of the definition of F
and every time you cut off a head at a distance of d>=2, it gets replaced by n heads at distance d-1, which accounts for F_d-1(n) changing into n copies of F_d-2 (applied to n+1).
and finally if you cut off a head at distance 1, you just get rid of it (and of the F_0 at the end) and increase n by 1, which is why F_0(n) is simply n+1.
the base case is easy, so the induction is done.
for example, for a path of length 3, we start with nodes at distances 1, 2 and 3 respectively. subtract 1 from them to get 0,1,2, put them in the subscripts of F's to get F_0,F_1,F_2, and then write the brackets and the 1 inside to get F_0(F_1(F_2(1)))
so the number of steps is F_0(F_1(F_2(1)))-1=
F_0(F_1(F_1(2)))-1=
F_0(F_1(F_0(F_0(3))))-1=
F_0(F_1(F_0(4)))-1=
F_0(F_1(5))-1=
F_0(F_0(F_0(F_0(F_0(F_0(6))))))-1=
6+1+1+1+1+1+1-1=11
notice how the individual steps perfectly correspond to the steps of the hydra game. if you watch the video, the sequence of distances of heads evolves like this:
1,2,3
1,2,2
1,2,1,1
1,2,1
1,2
1,1,1,1,1,1
and then you just cut off those 6 heads and you're done
a quick analysis shows F_1(n)=2n+1 since it's just adding 1 n times to n+1.
and F_2(n)=2^n*(n+2)-1 because it's 2(2(...(2(n+1)+1)...)+1)+1, where the n+1 is multiplied by n 2's and the 1's are multiplied by n-1,n-2,...,1,0 2's respectively, meaning they become 2^(n-1)+2^(n-2)+...+2+1=2^n-1 after expanding the brackets, while the (n+1) turns into 2^n*(n+1), and of course 2^n*(n+1)+2^n-1=2^n*(n+2)-1.
which allows us to quickly calculate the number of steps for a path of length 4:
F_0(F_1(F_2(F_3(1))))-1=
F_0(F_1(F_2(F_2(2))))-1=
F_0(F_1(F_2(2^2*4-1)))-1=
F_0(F_1(F_2(15)))-1=
F_0(F_1(2^15*17-1))-1=
F_0(F_1(557055))-1=
F_0(1114111)-1=
1114111+1-1=1114111
so yeah it's not 983038
anyway, for a path of length 5, we get this:
F_0(F_1(F_2(F_3(F_4(1)))))-1=
F_0(F_1(F_2(F_3(F_3(2)))))-1=
F_0(F_1(F_2(F_3(F_2(F_2(3))))))-1=
F_0(F_1(F_2(F_3(F_2(39)))))-1=
F_0(F_1(F_2(F_3(2^39*41-1))))-1=
F_0(F_1(F_2(F_2(...(F_2(2^39*41))...))))-1 with 2^39*41 F_2's
2^39*41 = 22539988369408, and since the exponential part of F_2 is by far the most significant, the answer is approximately 2^2^2^...^2^2^22539988369452 with 22539988369408 2's
the F_0 around the whole thing actually cancels out with the -1 after it (as you may have noticed in the other examples), and the F_1 barely does anything compared to the little unavoidable errors that pile up from trying to calculate the power tower. while you could get a better approximation by calculating 2^22539988369408*22539988369410-1 and adding the base 2 logarithm of that+2 to it, and then putting that on top of a power tower of 22539988369407 2's, and maybe you could improve it a little bit beyond that, there literally isn't enough space in the entire observable universe for the information needed to shave off 5 2's from the power tower and know even the first digit of what's on top.
so in a sense, you could say we don't know the answer. but it's not very difficult to know almost as much as the universe allows us to.
unless someone pulls out a number theoretic tool for calculating the first digits of massive numbers obtained through exponentiation, but i don't think that will happen in this century, if ever.
That’s the nicest hand writing I’ve ever seen
I'd love to see a video on the Buchholz Hydra. The one covered in the above video is neat but the Buchholz Hydra just breaks my brain.
Phil: _"Will you forget the head slicing thing!"_