Binary, Hanoi and Sierpinski, part 1 

How is this the first time I hear that _bit_ is short for _binary digit_... Mind blown.

I simply love your videos! I'm a mathematics student, so I'm used to the joy of understanding, but that doesn't make it any less exciting! And your animations are a wonderful, powerful and beautiful help in this delightful process! I may be repeating myself but nonetheless: Thank you! Keep up the great work! :)

I am software developer (who also has a love for math) and it never once occurred to me that counting was a recursive action. I am continuously amazed at how elegant and simple your videos are and how effective they are at showing complex ideas in an approachable way. Thanks for all your hard work!

Binary digits? I'd have called them bidgits.

There's something you overlooked at least in this video and that is quite beautiful. The even-numbered disks either move one space to the right or two spaces to the left, and the odd-numbered ones do the opposite: move one space to the left or two spaces to the right. It's determined by the binary number that each disk adds but modulo 3.

You missed the fact that odd numbers are always moved left and even numbers are always moved right.

Wouldn't it make more sense for the binary numbers at 6:05 and 11:20 to be coloured exactly the opposite way they are, i.e. leftmost digit bright blue and rightmost digit dark blue? That way the colour of the digit that flips corresponds to the same colour of disk that's actually moved.

I've used Desmos for a little over a year now, and I'm sad that my math classes never use it. I mainly just use it for my game development and for math-fun. It's the best math-function graphing tool I've ever used.

Fun trivia: According to legend, when the full 64 disc puzzle is solved, the world will end. Assuming 1 move per second, it would take 2^64-1 = 1.84*10^19 seconds or 585 billion years, which is incidentally the time it takes until the last star in the universe burns out.

Man, I really appreciate your videos. I must say that I a computer scientist of sorts (Information Systems actually) so binarry is no problem for me and that I loved Tower of Hanoi since I first saw it. So normally to solve the puzzle, I just look if the the ammount of disks, check if it's odd or even to tell the direction of cycle I'll do with the smaller disk, left or right repectvly. Then I just know that I must start moving the smaller according to the cycle, after that, do an obrigatory move, moving smaller, obrigatory move, and so on. Even though I know exactly the logic of how to do it in the most efficient way, I never saw any connection of the puzzle and the rhythm of bynary counting as you showed. I was simply amazed. Thank you, keep doing this amazing work for us.

Oh man, I know desmos was a sponsor of this video, but I gotta say, I'm a computer engineering university student, and I use the graphing app from them all the time. I do some very complicated mathematics most of the time, and it's really helpful to be able to put a complicated function in and add some parameters as sliders to see how it affects the shape of the graph. I actually just used it the other day and noticed they added integrals, and I was super excited to see that. On a more related note, this video was excellent. I took an algorithms class in which we studied towers of hanoi solving methods. However, my professor didn't really show the connection between the recursive algorithm and counting in binary. Really insightful stuff.

Your channel is absolutely gold dude. Keep up the good work. It's so refreshing to see university level mathematics displayed so entertainingly and so clearly. Thank you.

tower of hanoi puzzle is pretty neat. i had to write a recursive method in java that would "solve" the puzzle recursively for any amount of discs. the craziest thing was how much time it took for the compiler when you added a crazy amount of disks like 20 or 50.

Great video you explained everything so well I could feel why counting in binary works in a way others haven’t been able to do.

This one was incredible! the math was really cool and the animations were insane! and you're supported by the best graphing calculator ever!!!

Interesting video! I tried a little experiment. In the unrestricted case If there are 3 stones stacked on top of each other labeled 0, 1, and 2, then the next column position of the rock represented by a trit change can be calculated by 3^label modulo columns. I tried this with 4 columns and it works out, but for 3 or 5 columns, the direction of the move toggles left and right.

Here is a nice argument about towers of Hanoi, that I think it's pretty trivial but i never see people talking about it: At any valid position in towers of hanoi you have at most 3 valid moves: moving disk 0 on any of the other two pegs and (if at least one of the two other pegs are populated) moving the smallest disk in other pegs. In the ideal solution you never move the same disk twice in a row (because you could just move it once in the right position in the first place), so for odd numbered moves you move disk 0, for even numbered moves you move whatever else is available, in the only available place. The disk you have to move is always forced by this simple argument of "not doing useless moving around": counting in binary, or thinking about recursion does not give useful information to solve the problem (but helps to figure out the total number of moves, see below), because the only choice we have to make is "where do I have to put disk 0 now?" The only "solution" part of the video is thus "always move disk 0 to the right". Or always to the left, depending on where you want to end up in: the total number of moves you have to do is 2^number of disks - 1 (which can easily be deduced from both binary and recursive description above), and the first and last moves are thus moves of disk 0. With a simple modulus 3 operation you realize which peg you end up in: with an odd number of disks your last move will be toward the same peg as your first move, with an even number of disk you will end on the other peg instead. Indeed all disk will move in a rotating fashion in the final solution, in alternating directions: if you move disk 0 to the right disk 1 will move to the left, disk 2 again to the right and so on. This will give you a hint on where the biggest disk, which is moved only once, will end up accordingly to the direction you choose for disk 0. If your goal is to print the sequence of moves without having the actual puzzle then counting in binary will indeed help. But then you need an argument to figure out in which disk the peg is from the binary number: I'll add one here. Since the direction disk moves is easily predictable, you only have to count how many time each disk has been moved: in the binary representation this happens every time you flip its digit to 1, that is you can toss away the least significant digit and divide the number you obtain by two, approximating by excess. Example: if your count is 010011001 and you want to know how many time disk 4 has been moved, you can throw away 4 least significant digits (you don't care where disks smaller than it are) and get 01001, which is 9. This mean up until now you moved disk 4 and bigger 9 times, of which the odd moves disk 4 was moved, even moves you moved a bigger disk (you don't care which one now). Disk 4 has thus been moved 5 times, and thus it did almost one full rotation. As disk 4 is even it moves in the same direction of disk 0, hence if you move disk 0 to the right disk 4 is currently in the C peg, if you move it to the left it is in the B peg.

I just realized that 2048 was just making us count in binary

So nice ! I taught the Hanoi towers when I was teaching algorithmics, because it was the simplest example I could think of with exponential complexity, but I never knew this trick with binary counting ! There is an error in the transcript at 7:55 : the number of steps required is 2^n - 1, not 2^(n-1).

Your channel is lovely. a fantastic corner of RU-vid.

I think you could have highlighted the fact that you are moving the piece one right, and if you can't move it one right, two right. Moving straight left in the animation, in the case of skipping over from the middle position or the rightmost position, had me confused for a while. This mechanic also neatly explains why the piece moving can never move back onto the piece that was "trying to get rid of it", which was what I didn't originally understand. Great video though! Thanks!

Wow, just solved a programming task for the Towers of Hanoi, and remembered that this video existed. Thanks for saving the day _and_ blowing my mind.

I really like your use of the Computer Modern typeface!

Your videos captured my attention so well in your calculus lectures, that I finally dispelled the notion that I was not a math person, and simply needed to try harder. Finally going back to school, and no longer avoiding math intensive fields! Seriously though, this video is so cool, my girlfriend generally isn’t interested in this kind of stuff, but she loved this as well. Thank you, for working hard to put this stuff out.

I have been struggling with finding the best strategy for this game and you revealed it!!! :O

There are 10 types of people in the world: Those who understand binary. Those who don't, And those who were'nt expecting a ternary joke.

A simpler rule (only needing to count in base ten (or not at all when you got into the rythm) I noticed when trying this out: - On an odd numbered move: Move the 0-piece once to the right (or left, works both ways as long as you dont switch direction) - On an even numbered move: Move the largest piece you can move (which is never the 0-piece) to the only legal place Which is, of course the same as counting in binary, but a little simpler to put to use imo :)

another great perspective that I just realized...count up how many times each disc /has/ to move, starting from the bottom. disc n has to move just once, disc n-1 has to move twice (once to get off of disc n and once to get back on again), disc n-2 has to move four times, etc

I saw this puzzle 50 years ago in high school. My classmates were struggling with it. I just sat down and did it without hesitation. It has always been obvious to me. I earned a Masters Degree in Computer Science. It seemed to me trivially obvious that this puzzle was binary counting. 3Blue1Brown explains this beautifully.

I always felt like counting in binary when solving towers of Hanoi! That's amazing now that I understand why.

If I were to put counting in binary into a memory based way, rather than a function, I would tell you this; For every iteration the 1's place digit changes, for every two iterations the 2's digit changes, for every four iterations the 4's digit changes, and so on. I have always been amazed by the infinite number of distinct patters in binary. 1 001 2 010 3 011 4 100 5 101 6 110 7 111

Once in year 7 or 8 I was in maths and at the end of the class the teacher asked the class how we could improve our understanding of the content covered in class that day. Some students suggested things like calculating the cost and change (if paid in cash) of grocery expenditure. Another said "counting" and the teacher laughed, and said "counting what?", the student said "anything", the teacher laughed again but louder and with the rest of the class before saying "No [name], I don't think counting is going to help". Looks like counting is pretty useful right about now.

I never thought about it, I just found it so simple once I found the pattern, but I never could've imagined it'd be hiding something more complex and so beautiful

Your visuals keep getting better! Nice!

"Counting is self-similar" -- fantastic and thought provoking!

i believe the recursive subroutine at 9:52 could use a return statement at the end (although it may be inferred by the compiler ?) with disks 3 2 1 and 0 pre-stacked on PEG A - this subroutine generates the following sequence of directives (d = decimal notation / b = binary notation) A 3210 B C STATE 00d = 0000b MOVE DISK 0 (from PEG A to PEG B inferred) A 321 B 0 C STATE 01d = 0001b MOVE DISK 1 (from PEG A to PEG C inferred) A 32 B 0 C 1 STATE 02d = 0010b MOVE DISK 0 (from PEG B to PEG C inferred) A 32 B C 10 STATE 03d = 0011b MOVE DISK 2 (from PEG A to PEG B inferred) A 3 B 2 C 10 STATE 04d = 0100b MOVE DISK 0 (from PEG C to PEG A inferred) A 30 B 2 C 1 STATE 05d = 0101b MOVE DISK 1 (from PEG C to PEG B inferred) A 30 B 21 C STATE 06d = 0110b MOVE DISK 0 (from PEG A to PEG B inferred) A 3 B 210 C STATE 07d = 0111b ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- axis of symmetry MOVE DISK 3 (from PEG A to PEG C inferred) A B 210 C 3 STATE 08d = 1000b MOVE DISK 0 (from PEG B to PEG C inferred) A B 21 C 30 STATE 09d = 1001b MOVE DISK 1 (from PEG B to PEG A inferred) A 1 B 2 C 30 STATE 10d = 1010b MOVE DISK 0 (from PEG C to PEG A inferred) A 10 B 2 C 3 STATE 11d = 1011b MOVE DISK 2 (from PEG B to PEG C inferred) A 10 B C 32 STATE 12d = 1100b MOVE DISK 0 (from PEG A to PEG B inferred) A 1 B 0 C 32 STATE 13d = 1101b MOVE DISK 1 (from PEG A to PEG C inferred) A B 0 C 321 STATE 14d = 1110b MOVE DISK 0 (from PEG B to PEG C inferred) A B C 3210 STATE 15d = 1111b notice the sweet symmetries around the axis indicated. PEG A mirrors PEG C. PEG A in STATE 00d is identical to PEG C in STATE 15d. PEG C in STATE 00d is identical to PEG A in STATE 15d. PEG A in STATE 01d is identical to PEG C in STATE 14d. PEG C in STATE 01d is identical to PEG A in STATE 14d. etc PEG B mirrors itself. PEG B in STATE 00d is identical to PEG B in STATE 15d. PEG B in STATE 01d is identical to PEG B in STATE 14d. etc

you forgot to link to your patreon. I'm the new guy there btw [double handed- mid jump freeze frame high five]

Okay so I actually have a handheld binary counter and I just used it to solve tower of hanoi and it's even easier than you think. Because the toggles on my counter click, I listen for the clicks to tell me which disc to move. As long as I remember that disc 1 always moves to the right, it's impossible to mess up.

Hi @3Blue1Brown I want to share a slightly different interpretation. The process of solving the Tower of Hanoi reminds me classical beginner's programming problem of swapping two variables content. You perfectly know that we need a third variable to swap the content of two of them, this is because we have the constrain that we can't send the information from one place to the other at the same time and without loosing one of the two (I call it quantum swapping :). That's exactly the analogous case in the Hanoi game "you can't put a bigger square on top of a smaller one" this constrain recast the game in a "swapping game", where the sticks works as variables. You are forced to use another stick and therefore follow the binary pattern. Can we apply the XOR trick by achieving a quantum swapping also in the Hanoi game? :) Thanks for your amazing work, a MS CS student.

Wow this is really cool. So technically you could solve the tower with n pieces just by following what the binary tells you. Given the time anyone could solve any! And eventually get quicker. Had a competition in my class before where we had to solve the 7 bit one as fast as possible, my record was 12(!) seconds! Using an app though, so 2 quick taps was enough to make 1 move. Then though I just got a feel for the moves requiered and memorized the pattern.

I've never even taken a CS class but this is so fascinating! I love seeing videos appreciating the thrilling cohesiveness which seems to appear in every area of mathematics. Absolutely adore these videos, thanks for putting them out there!

For all the people who are confused of the trick explained in the video, This is what it means... say i have 2 disks lets count in binary 01 -> move disk 0 to the nearest peg to the right. 10 -> move disk 1 to the nearest peg to the right. 11 -> move disk 0 to the nearest peg to the right. ok you get it now? heres the pattern remember to ignore when a digit turns to 0, but to not ignore when a digit turns to 1 so when i have 1s place, (disk 0) goes to the nearest peg to the right. dont worry about the size for this disk since its the smallest disk. when i have 2s place, (disk 1) goes to the nearest peg to the right UNLESS there is no smaller disk occupying the peg of choice. when i have 4s place, (disk 2) goes to the nearest peg to the right UNLESS, again, there is no smaller disk occupying the peg of choice. if you have a disk and its on the rightmost peg and you transfer it to the right just go to the leftmost peg and check if the peg is being occupied by a smaller disk. how about 4 disks. 01 - 11 -> use disk 2 formation 100 -> disk 2 goes to the nearest peg to the right. 101 - 111 -> repeat instructions i told you earlier :) 1000 -> disk 3 goes to the nearest peg to the right. 1000 - 1111 -> repeat instructions i told you earlier :) again order another smiley again :) so yeah if you master that you can become an absolute OP and solve a 20 ring tower of hanoi : ) ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))

0:25 nah, you win in the category of "best educator" :)

Very insightful.

Maybe the tower of Hanoi problem has 3 pegs to represent 0 bit, 1 bit and the carry bit P. S : this is just a random thought of mine. I haven't read or heard of it anywhere so it's most likely wrong 😅

Please do check your volume levels to make sure they are between 50% and 100% of the possible range, if your video is so quiet people will have trouble hearing you on mobile phones, tablets, some laptops etc.

Has anyone else noticed how the 3 of "Disk 3" looks an awful lot like a cartoonish mouth, especially when the eyes are shown

The problem with "move it over once" is that the way I learned the rules of the puzzle is that you had to go from _leftmost_ peg to _rightmost_. So if you started with an odd number of rings, you would need to move it over twice (or once the opposite way). The way I always solved it was: odd numbered tower/subtower -> move next disc to destination you want the whole tower/subtower to be at even number -> move next disc to non-destination This pattern works throughout the whole puzzle, and I assume it's basically the same as the binary thing, but harder to keep track of. I used to obsessively do this puzzle with playing cards (i didnt have pegs and rings), and i went up to 13 one time (took 2-3 hours I think?). Every new card would take about twice as long, I guess because 2^n (oh hey, binary!!)

If I didn't grow up with so called western world numbers, I'd find this video severely informative ;D I love this planet ;D

I assume base-2 counting works for the Hanoi puzzle, because... of the THREE spindles, 2 of them are 'in play'. Is it true that FOUR spindle game would correlate to base-3 counting; and that an ELEVEN spindle game would correlate to base-10?

This is one of your best videos! It really appeals to my sense of pattern :) One small note: I think the plurals of "two", "four" and "eight" are "twos", "fours" and "eights". No apostrophes are needed. Maybe this confusion arises because apostrophes are often used with digits to reduce ambiguity, e.g. "10's", "100's"; this isn't the case for numbers spelt as words.

I didn’t find the Hanoi puzzle very challenging because most of the time there is only 1 possible move that isn’t retracing your steps. In some situations where there are two moves that don’t retrace steps (the most their can be) it is still easy to see which move will get you toward your goal, as long as you ask yourself the question “ will this accomplish my goal?”.

you should make your "intro eye" blink ... after it has done the (beautiful) "pupil shrinking" animation... ;)

When you realize this result in 8th grade, only to find out the exact same thing on youtube, years later ;-;

Hey 3Blue1Brown, what do you use for the music in your videos? It's really calming and focusing and would be great for listening to while studying

I discovered Towers of Hanoi early on, as a side/minigame in Escape from Paradise. I was pretty young so it was a bit difficult. At the least I could get to level 2 (only 4 discs haha)

Who's here again after Mathologer's video!

Holy! This is absolutely amazing. I solved this puzzle for/with a student of mine and came to these conclusions, but the binary counting perspective is simply mesmerizing. Thank you for this video!

This would help 2 months ago when I solved a 9 disk tower of Hanoi... Man that shit was hard i kept forgetting what i was doing

In a Numberphile video about this, I learned that disks with like parity are never consecutive on the same peg.

well done. I like to think of periodic boundaries where even number disks go one way and odds go the other.

Isn't it very obvious that solution to time complexity of Towers of Hanoi, that is it's recurrence relation, is 2^n -1 , the maximum number you can make by n binary digits. And you can reach this maximum number, by adding 1 to this number starting from 0. I don't understand why is this an astonishing discovery.

11:10 - that's wrong! All the disks end up on the central peg, when they should end up on the right peg. Why?

Once you see disk 3 sending you a kiss, you cannot unsee it

7:53 where did it come from why does it work where did it come from binary code joe

Woooaaahhh fine structure constant easter egg

Keith Schwarz! Did you study CS at stanford?

This is overly complicated if the aim is to solve Hanoi. The shortest algorithm is as follows 1. First move: only legal moves involve moving the smallest. If there's an odd number of disks move the smallest to the destination; if even move smallest to the other peg. Note which direction it moved. 2. On even numbered moves make the only move available move that leaves the smallest where it was 3. On odd moves move the smallest in the same direction as step 1. That's it! You do not need the rest of the binary number, just the last digit. In effect you only need odd-even so a simple toggle is enough, adding in modulo 2. And when adding mod 2, the numbers look the same in any base: 1 0 1 0 ... Binary is a distraction: it's mod 2 that matters

you've done a little error at 5:59 11111111 in binary equals to 256 not 255 (which is 11111110 in binary) cause 2**8 = 256 otherwise realy nice video keep going like this (sorry for grammar error )

The binary method shown in this video work great for odd numbers of discs, as the result ends up on C. But for even number of discs, it will end up on B. I thought the goal was to end up on C. But fear not, all you have to do is to move the first (0) disc to the left and not right, when you have an even number. That's all.

I really loved math when i was studying it at school and you give me so much unsuspected insight into topics i thought i knew very well. Thank you so much. After each of your videos i feel that i learned something new.

Every number system, when represented in its own base, is "base 10"

This HAS to be related somehow to the Chinese Rings Puzzle somehow... Please get your friend to tackle it and make a video about it, I'm scared to think about it on my own! :P (Seriously, I wouldn't know where to begin at)

Marvelous again. When I was younger, my grandpa taught me a slightly different version: A larger disk not only cannot stop over a smaller one, but it cannot pass over it at all. This essentially makes the game longer, which I suspect was the goal of my grandpa. I kind of remember talking about it with a friend a couple years ago, and I think we came to the conclusion it was very much like classic Hanoi, but with base 3 instead of base 2. Maybe I should take out a pencil and check that again.. EDIT: Shame on me, I should have binged the series like a true 3Blue1Brown fan before posting this.. Keep up the good work!

You move the first disk 1 place. The second: 2 places. The third: 4 places, The forth: 8 places....

4:20 forget resisting the urge to see it as ten... i have to reiast the urge to tell a "there are 10 types of people in the world... so there are 11 types of people those that understand binary, those that dont, and those who realized this joke was originally in base 3.

Oh the memories! The very first program I wrote for my Assembly Language class project was the solution for the Hanoi puzzle on a Dec PDP11-45 back in 1975.

When I started doing python I made a script to solve the Hanoi towers, but I didn't know what recursion was so I analyzed different cases and found a really weird relationship between numbers and letters. I thought about recursivity as you mention it here, but I solved it completely different for n disks with the most efficient moves. I could show you the code, but it is very messy and I, to this day, still not understand how the math I did really works xDD

Love all your videos. Easy to follow the lectures and the graphics surely make an awesome impact on understanding. Thanks :)

As someone who's in the middle of a computer networking course, I really like the way you explained binary. While I already know how it works (thanks IPv4!), your explanation is really good, and if I have to ever explain binary to someone else I'll probably have to borrow from this.

I've learned the relationship between the ABACABA pattern and the Tower of Hanoi from Pocket83's channel.

Are there variations of the puzzle whose solutions relate to counting in other bases?

4:13 I read binary :'zero' , 'one', 'ten', 'eleven', ' one hundred', ... Call me a monster if you must but 10 is still 10 to me even if its not a base ten series. (And yes I keep track of it being in alternate bases)

Found the puzzle online: www.mathsisfun.com/games/towerofhanoi.html

I wrote my own algorithm to solve this without any resources and came up with a similar system, but instead of binary I just say "up" or "down". Basically if you have an even amount of disks, move the first disk only up, the second down, third up, etc. And if you have an odd number of disks only move the first down, second up, third down, etc etc. Then it's just as simple as remembering which disk moves up and which moves down. Here's the messy pseudocode I came up with, and while it's a mess I haven't seen anything else that does it quite this way // For 5 disks, a is the smallest, e is the largest, and the positions they move to in order a3 b2 a2 c3 a1 b3 a3 d2 a2 b1 a1 c2 a3 b2 a2 e3 a1 b3 a3 c1 a2 b1 a1 d3 a3 b2 a2 c3 a1 b3 a3 a_moves_when=1 3 5 7 9 11 15 17 19 21 23 25 27 29 31 b_moves_when=2 6 10 14 18 22 26 30 c_moves_when=4 12 20 28 d_moves_when=8 24 e_moves_when=16 ring_count=5 a_total_moves = 2^ring_count-1 b_total_moves = 2^ring_count-2 c_total_moves = 2^ring_count-3 d_total_moves = 2^ring_count-4 e_total_moves = 2^ring_count-5 a_pos=1 b_pos=2 c_pos=4 d_pos=8 e_pos=16 while(a_pos

When will you be uploading the essence of calculus series??

Towers of Hanoi is also related to the partial sum of 2^n...

I actually remember when I first noticed this. I didn't really understand it in such a formalized way, though.

Ohh, This reminded me of 2 years ago, there was a competition to see who could solve the tower the fastest in my uni. I didnt join, but I did end up making up a solution to the puzzle, which I can't remember well, but it goes along like this: Always mov the smalles number that wasnt moved in the previous round; Never place odd numbers on top of odd numbers, or even numbers on top of odd numbers; Well, thats all I can remember for now, I will see if I can find my papers that I drew on. Now back to the video.

Tháp Của Hà Nội

8:45 peg 3 looks like it is doing the duck face or sending a kiss

I figured out as a kid that if you have an ODD number of disks, the first step is to move disk 0 to the target peg, and if you have an EVEN number of disks, the first step is to move disk 0 to the non-target peg. So in some sense it was a parity solution. And then I pretty much solved it recursively. Interesting tie-in to binary counting, however.

Wow. This is already awesome ! And now : let's check part 2. :)

Looks a little bit weird how, around 7:25 for example, the piece for 0 is the darkest and the piece for 5 is the lightest, while in the number below the bit corresponding to 0 is the lightest and 5 is the darkest. Other than that, really cool video! We learned about the recursive solving of the Hanoi towers problem in class but I never made the connection to binary.

Binary works because the algorithm reduce to binary complexity for each actions. This is useful when you measure it's complexity. For each depth of recursion, we essentially do 1 + 2*(steps for that depths). To ilustrate, let f(N) be the number of steps needed to move the pegs efficiently. It is a recursive function. For f(N) the steps involves: 1. Moving the rest of the pegs (N-1) means f(N-1) steps 2. Moving the bottom peg count as a step 3. Moving the rest of the pegs again, means f(N-1) steps. algo 1 and 3 is the same, so it is the same steps. So: f(N)=2*f(N-1) + 1 The recursion ends when f(1) = 1 (one step to move one peg). One now can easily reduce the counts by finitely recurse until f(1), which is, if we write it as sum of power of two, is the same as writing binary in this form: f(N) = 2^N - 1 --> which is basically all 1 in binary until N digits. So, for 2 pegs, it is like: 11 in binary (2 digit). 3 pegs becomes: 111 in binary (3 digits). and so on. It's just because: 2^3+2^2+2^1+1 is equivalent to 1111 in binary for 4 pegs. Amazing.

*realizes I could solve tower of Hanoi when I was younger and realizes I might not be a genius*

5:46 this is when i got what 3b1b was saying: i made a cpde that prints out the stepbystep solving of hanoi that prints out A C A B C B ... where A C means move the top one in A to C. i used recalling?(재귀) functions for it: hanoi repeats itself. for blocks in A, move all but the last one to B, move the last one to C, move everything in B to C. how do i move everything except the alst from A to B and B to C? recall that function. all that the function does is move blocks from one place to another. why did i get hanoi=bi in 5:46 ? 1.move all-1 from A to B 2.move one to C 3.move all to C(which is the same as step 1) 1.increment all-1 so all digits are 1 2.add 1 3.increment again(which is the same as step 1) a programmer's explanation on why this work. 3b1b you and your friend is a genius!

4:22 there are ten sorts of ppl in the world. Those who can count in binary And those who can't

There are 111 types of people: those who understand binary, those who don't understand binary, and those who didn't expect a unary joke here

Hi. First of all, I love your videos, but I don't see how binary counting solves the towers of hanoi with the algorithm you have given simply because it does not guarantee that the tower moves from peg A to peg C. It seems to me that this will only happen when the tower is of even height, the resulting stack will otherwise end up in the middle, and you need to compensate for that somehow. Am I missing something? The thing is that if you have to take care of this then the binary counting solution is not as clean and elegant as we might originally think. It's still pretty though, and I hadn't seen it before. Personally, my favourite recursive algorithm for solving the towers of hanoi (which I am in no way taking credit for, but it is also optimal and moves any size tower to the right peg) is the following, where 'hanoi n to from via' will solve the towers of hanoi by moving 'n' discs from peg 'from' to peg 'to' via peg 'via'. The results is a list of pairs [(A, C), (C, B), (A, B), ...] where every pair (A, B) means move the top disk of A to B. hanoi n from to via = if n = 0 then [] else (hanoi (n - 1) from via to)@ (from, to):: (hanoi (n - 1) via to from) here [] is the empty list, @ is list join, and :: is list addition. If you call 'hanoi 3 A B C', for instance' you will get the result [(A, C), (A, B), (C, B), (A, C), (B, A), (B, C), (A, C)] moving a tower of size 3 from peg A to peg C whereas your algorithm, if I read it correct, would move the tower from peg A to peg B. As you noted, these algorithms get really tiny and are great for explaining recursion. We don't care how the smaller problem is solved, we just assume that it is and work from there ;). I just found your channel (thanks to Ask a Game Dev) and I'm looking forward to seeing your other work. I love seeing math made accessible.