"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.
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?
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.
@@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.
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.
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.
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.
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.
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)
@@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)) )
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.
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.
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).
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).
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!
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.
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!
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.
@@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
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.)
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"
"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."
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.
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!
"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.
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.
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.
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?
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?
@@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?
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?
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
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.
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
@@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)!
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
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?
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.
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 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.
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.
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.
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)
@@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
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.
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.
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.
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.
Yeah, a video about it would be great, i agree. If I remember correctly, the BH function grows much, much faster than the TREE function right? Something on the level of the TFB Ordinal
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.
If you always chop the furthest head then you cet a fibonacci-like sequence: chop 1, 1 grows, there are 2 on the furthest. Chop 2, 2 and 3 grow, 5 total, there are 6 below now. Chop the 6 and you add 4,5,6,7,8,9, and so on. Take the sum of the next n integers plus one to decide how many integers you take on the next layer, on and on, a fixed process. 1 step -> 2 steps -> 6 steps -> 28 steps -> 10+...+37+1 steps; add these to get the shortest time you can solve a 5 chain in. 10+...37+1 = 659. I guess it was blind coincidence that 2,6,28 (very important sequence) appeared. So yeah, i can solve a 5 chain in 1000 steps, using the furthest chop rule.
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.
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.
The explanations in the comments remind me of the hydra problem. "I don't understand this phrase or concept. Can you explain it?" "Yes! And in doing so, I'll always add 2 new additional phrases or concepts that you don't understand, but at a deeper level." "Great! So will the explanations ever end so I can understand what you are saying?" "Well..."
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.
This is easy, because D always decreases. I'd be curious if there is a variant of this game that has situations that can add new heads at D, or even at D+N, but is still finite. The maths involved there would be very interesting
If you add heads at D it will never end because you are adding complexity, your next hydra is always more complex than the previous one and it is very simple to show. As long as you add heads to d-1 you can copy however you want to, my favourite is that after chopping off one head you add a whole copy of the remaining branch above, so in the 3x3 case you would add two Y shaped bits to the grandparent. Still decreases, but VERY VERY slowly.
You could examine the case where the heads regrow with a random parent. If you include the leafs in that selection then the tree can also grow higher. This also needs a new rule that stops the heads from regrowing at some point and the selection needs to be skewed towards the root, so this has any chance of terminating e.g. pick a leaf then pick a random node on the path towards the root or pick two random leaves and then select a random node that appears on both paths to the root.
There’s a variant where it does grow heads at D. At 18:09 where he chops off the head at step 2, instead of just growing two leaf nodes directly out of the root, it would grow 2 new entire trees of length 2. This still terminates but to prove it you need to use ordinal arithmetic.
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).
@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])
@@michael.huepkes I tried going with a rule like this at first as well, but I think I realized it didn't always work - somehow the tree structure would matter, not just the number of heads on each level. But I think it is consistent that any new heads are always "to the right" of any existing heads on any given level, so they will be cut before any of the original heads on the tree get cut.
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.
The linear hydra feels something similar to the towers of Hanoi, where the next answer should be related to the previous one. But it also somehow doesn’t.
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.
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.
Please do not edit these videos to start with a trailer for the video. We are already here and ready for 20 minutes of numbers, we don't need a 5-second dramatic clip to get us interested.
This just a more complicated version of the "beetle crawling on the elastic" puzzle. It doesn't matter how quickly the elastic is expanding, the beetle is still moving forward expressed as a percentage of the band, so the time it takes to complete the distance is still finite.
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.
Just a pedantic note: if a head grows at the node after heads have been chopped off i think 1 should be added. For the original Hercules example the root node would grow a head making it 31. All equations just get a 1+ at the beginning
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
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.
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.
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
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...)
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. 🤔😁
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 TH-cam. 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?
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.
"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?
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.
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.
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
Or the Hydra was immortal so he threw it under a mountain 😅
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
@@phiefer3GET UP HAN THE HYDRA'S BACK
Might I join the same boat as you? Also I remember it being "Will you forget the head-slicing thing?!"
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
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.
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
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.
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.
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
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.
@@MajkaSrajkathat sounds like "i wanna lockpick", but now with hydra heada.
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.
missed opportunity to say w_d = 40
this is why I'm in the comments
@@TomRocksMaths woah.. your profile picture needs a haircut dude!
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
I love the animation. I've never seen such a cute hydra!
No one cares about "cuteness" in math.
@@Gordy-io8sb or battle!
i just love the animations, it's SO CUTE
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
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"
"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!
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.
Or just. Y'know. Go for it's body.
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!
"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.
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
The true solution to the Hydra game is to join Hydra. Hail Hydra.
The extremely circular hydra looks like 3blue1brown
4green
18:35 OK. We have a sequence that has to do with trees, or graphs, that starts with 1 and 3, and features insane super-growth. Flashbacks, anyone? 😅
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
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?
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?
A clever man once told me, I would never see Herkules with a flamethrover.
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
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
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.
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
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)!
🙂
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
I absolutely love the silly animated hydras!
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?
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.
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
dont most renditions of the hydra have the heads regrow directly from the wound?
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
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.
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
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.
Yeah! Another Numberphile video!
Same reaction here
Reaction same here
Here reaction same
Here same reaction
Bro out here looking like Machine Gun Kelly while talking about "killshot" and thought we wouldn't notice
you got me
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.
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.
Why isn't the root node considered a leaf when it's the only one left?
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.
Yeah, a video about it would be great, i agree. If I remember correctly, the BH function grows much, much faster than the TREE function right?
Something on the level of the TFB Ordinal
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.
If you always chop the furthest head then you cet a fibonacci-like sequence: chop 1, 1 grows, there are 2 on the furthest. Chop 2, 2 and 3 grow, 5 total, there are 6 below now. Chop the 6 and you add 4,5,6,7,8,9, and so on. Take the sum of the next n integers plus one to decide how many integers you take on the next layer, on and on, a fixed process. 1 step -> 2 steps -> 6 steps -> 28 steps -> 10+...+37+1 steps; add these to get the shortest time you can solve a 5 chain in. 10+...37+1 = 659. I guess it was blind coincidence that 2,6,28 (very important sequence) appeared. So yeah, i can solve a 5 chain in 1000 steps, using the furthest chop rule.
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*
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.
I think *Tom's mind* has the strength of Hercules. Excellent explanation.
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.
The explanations in the comments remind me of the hydra problem.
"I don't understand this phrase or concept. Can you explain it?"
"Yes! And in doing so, I'll always add 2 new additional phrases or concepts that you don't understand, but at a deeper level."
"Great! So will the explanations ever end so I can understand what you are saying?"
"Well..."
you are keeping the rolls of brown paper industry alive.
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
This is peak animation.
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 note that you kinda end with an immortal head, since you put one on the stumps, and there was an immortal head in the myth.
This is easy, because D always decreases. I'd be curious if there is a variant of this game that has situations that can add new heads at D, or even at D+N, but is still finite. The maths involved there would be very interesting
If you add heads at D it will never end because you are adding complexity, your next hydra is always more complex than the previous one and it is very simple to show. As long as you add heads to d-1 you can copy however you want to, my favourite is that after chopping off one head you add a whole copy of the remaining branch above, so in the 3x3 case you would add two Y shaped bits to the grandparent. Still decreases, but VERY VERY slowly.
You could examine the case where the heads regrow with a random parent. If you include the leafs in that selection then the tree can also grow higher. This also needs a new rule that stops the heads from regrowing at some point and the selection needs to be skewed towards the root, so this has any chance of terminating e.g. pick a leaf then pick a random node on the path towards the root or pick two random leaves and then select a random node that appears on both paths to the root.
There’s a variant where it does grow heads at D.
At 18:09 where he chops off the head at step 2, instead of just growing two leaf nodes directly out of the root, it would grow 2 new entire trees of length 2.
This still terminates but to prove it you need to use ordinal arithmetic.
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
@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])
@@michael.huepkes I tried going with a rule like this at first as well, but I think I realized it didn't always work - somehow the tree structure would matter, not just the number of heads on each level. But I think it is consistent that any new heads are always "to the right" of any existing heads on any given level, so they will be cut before any of the original heads on the tree get cut.
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.
The linear hydra feels something similar to the towers of Hanoi, where the next answer should be related to the previous one. But it also somehow doesn’t.
I love the sound effects, they are nice
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?
So that's crazy i haven't learned like this, thank you
this is cheating 😂 surely the new heads grow out where you shopped one off
*chopped
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.
Please do not edit these videos to start with a trailer for the video. We are already here and ready for 20 minutes of numbers, we don't need a 5-second dramatic clip to get us interested.
You underestimate how many viewers get bored and click off otherwise
TL;DR: the hydra never gets taller, and thus inevitably perishes.
This man has a pokeball tattoo and it only makes me respect him more
He has two actually ^^
It's nice to be passionate about things I guess, but I always find it weird that people pay to become walking advertisements
I always immagine the hydra have a "main" head and the other are in couple for me is 29 cut to end
TREE(HYDRA(g64))
TREE(gHYDRA(64))
TREE(TREE(3)) is still much bigger.
@@iankrasnow5383 What about TREE(TREE(3+3i+3j+3k))?
This just a more complicated version of the "beetle crawling on the elastic" puzzle. It doesn't matter how quickly the elastic is expanding, the beetle is still moving forward expressed as a percentage of the band, so the time it takes to complete the distance is still finite.
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.
When n is fixed, the formula is a generating function which can have recurrent relations between the coefficients.
Heracles. If you're going to say Greek mythology its Heracles
Just a pedantic note: if a head grows at the node after heads have been chopped off i think 1 should be added. For the original Hercules example the root node would grow a head making it 31. All equations just get a 1+ at the beginning
Is it just me or is this kinda boring and obvious? There's no neat trick or anything, the heads just move closer to the root
It is but mathematics gotta prove everything
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
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.
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.
Hercules showing up with a modern lawnmower: *_SAY GOODBYE TO YOUR HEADS, HYDRA_*
I love Tom videos. He explains things so well.
❤
This problem has more structure than it needs
If you cut the furthest leaf instead of the rightmost, it should be doable in fewer steps.
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
love your script / writing
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...)