The Josephus Problem - Numberphile
Вставка
- Опубліковано 27 жов 2016
- The Josephus Problem, featuring Daniel Erman from University of Wisconsin-Madison.
Winning at Dots and Boxes: • How to always win at D...
More links & stuff in full description below ↓↓↓
Correction: Around 9:40 that should be L less than 2^a NOT 2a --- Sorry, typo in editing! But you got the point hopefully.
Support us on Patreon: / numberphile
NUMBERPHILE
Website: www.numberphile.com/
Numberphile on Facebook: / numberphile
Numberphile tweets: / numberphile
Subscribe: bit.ly/Numberphile_Sub
Numberphile is supported by the Mathematical Sciences Research Institute (MSRI): bit.ly/MSRINumberphile
Videos by Brady Haran
Brady's videos subreddit: / bradyharan
Brady's latest videos across all channels: www.bradyharanblog.com/
Sign up for (occasional) emails: eepurl.com/YdjL9
Numberphile T-Shirts: teespring.com/stores/numberphile
Other merchandise: store.dftba.com/collections/n... - Наука та технологія
Imagine doing all of these calculations, and then one dude decides to go counterclockwise.
You just number anticlockwise 🤷🏽♀️
@@pranalijoshi4623 but you already sat to where it goes clockwise and you can't switch seats because the killing already started :/
I don't think you got it but ok
@@pranalijoshi4623 imagine not having basic reading comprehension skills
lol 🥲
@@keontedennis7872 That's not entirely fair, while their comment does purposefully ignore the joke of the original comment, the original comment didn't say you were already seated, and so you could reasonably reverse the circle mentally, sitting in the correct seat.
The real problem is Josephus’ loyalty
Touché
I don't know why I can't stop laughing 😂
Is that a jojo reference ?
@@cloroxman7194 Don't make me remember of jojo, Jojo was my fav character in SC
xD
Plot twist. Josephus after working feverishly on the problem but found that seat 19 was already occupied…by his math professor.
Lol
SumENazViruleCowO&ootRojaz!
He just gonna pick 35 and he is gonna be safe with his math professor after a truce
spoiler alert bro 😭
@@Shinrakaichu i
Students: Where will we use math in real life?
Real Life:
Qui?poobLikaz?
@@steveclem7873 indeed my friend
lol
Ok now after spending 30 mins here I know the solution for this problem and now all I need to do is wait till a army of roman soldiers catch me with 41 others
But before you can decide where to sit, you have to know which seat will be “1”. What if you’re not in on that decision? That’s life.
This is the most violent math problem I've ever seen.
you are not familiar with the mathematicians employed by the RAF to determine the most efficient way of killing the most people by dropping bombs on them back in the forties..
@@Valchrist1313 SHAD no!
Ever sense how many bombs would bin laden have if 3 terrorists blew themselves up with 4 bombs each and bin laden had 420 bombs in the beginning
After E=MC²
@@Valchrist1313 how 'bout we agree that our original poster meant "math puzzle", in a strictly academic and/or pedagogical (rather than applied maths) context.
The story of josephus also goes to show the lengths mathematicians will go to to not have a difficult conversation.
Damn bro 😂😂😂
Im 1k like noice
Math to solve pointless problems.
Einstein’s Theory of Relativity was pointless math in the early 1900s. Few people even had the ability to see the need. The problem is you have no crystal ball to have any idea on the applications that may come up in the next 100 or 200 years.
X-D
I'm taking a class with this guy right now and I can't believe that I've watched this video before and I never realized until today that this is him. He's easily the best prof I've had tho.
cool!
It's probably too late, but you should ask him about this problem and see what his response is. Maybe "Hey, I actually helped make a video on that very topic"
I can imagine so. I enjoyed this.
... should learn to iron his shirts though.
@@allasar nobody’s perfect. I’ll accept brilliant in place of pressed laundry. 🧐 😺
01:40
"Phil Hanlen: what we should do is gather data. You and your classmates please form a circle while I go get a sword..."
Daniel Erman forgot to mention that's the reason why he's here today to tell us the solution to the problem.
Phil Hanlen sure played a big role to leading him to maths with very convincing incentives
It cracked me up so hard xD
Jews: we’re gonna commit suicide to avoid being captured
Josephus: hang on lemme do some algebra
Boolean algebra X-D
And if he does it wrong he'll have a alge-bruh moment
He's stoopid
@@jwm6314 He didn't fight to the death. He surrendered and became the right hand man to the general who later became Roman Caesar.
XD
A lot of people died in the making of this video.
How many?
Shouldn't it be a lot of "hypothetical" soldiers from long ago "hypothetically" died? In real terms, I'm much more concerned about the cost of butcher block paper this guy is going through on a daily basis. Ha! Have a great day everyone.
@@johnburke3693 you're fun at parties aren't you
@@ministerc9513 (2^n)-1 of course
@@johnburke3693 I wonder if there are videos which contained topics about infinity soldiers killing each others, and at least one people watch each day...
Why am i feeling that someday a lunatic genius killer gonna play this game with their victims
NumBerzDoopkeTaxMainz?
his name is John
that is squid games if u know what i mean
This is my favourite Numberphile video. Interesting problem, history, and visualisation. Most importantly, it explores how to solve *ANY* math problem. Absolutely wonderful.
The sound effect when a soldier gets killed deserves an award.
What about the unpleasant scratching of his marker on the paper? What does that deserve?
ive watched this vid so many times JUST to hear that sound effect
Man scream have to admit i laugh on movies with man screams
It's like an Android button click sound effect
Satisfying
The real question is: Why do they fear the Romans if they have *_BOOMERANG SWORDS?_*
The Australians had actual boomerangs. Didn't work out too well for them.
Jb Jaguar Well, Josephus wasn’t caught by an army of emus
@@DavidSavinainen The emus would win anyway
And the boomerang swords...
For the sake of argument I guess.
6:33 That's some pretty damn cool animation ngl
*-blob-*
Someone has to mention the satisfying sound the killing swords make, and I guess that someone is me
Amogus
I like how he doesn't just gives the answer, but discusses whole process of getting the right answer step by step
If only schools were this interesting.
@@DraconicDuelist idk, back when I was still in school it was pretty much exactly like this. Sometimes a bit faster though, if there wasn't a ton of time
@@Mixu. Then I congratulate you on having a well trained/enthusiastic teacher.
I had one who said there are no numbers less than 0 (no, not even negatives), another who spent all of class time on e-bay while flipping through PPT slides, my geometry teacher left only 2 educational memories: proofs and Numb3rs (the tv show)...
@@DraconicDuelist owh. Yeah, guess I got lucky. Had a pretty motivated math teacher who also taught us about how math is applied in every aspect of our daily lives
BECAUSE SIZE MATTERS ,,, ON UA-cam ,,,, VIDEO LENGTH
This is the most f*cked up game of duck duck goose I’ve ever seen.
I laughed so hard at that
Laughed out loud at this too
😂🦆🗡
or the most ducked up
wow why is there even 1 like on your comment
playtonz, because at least *2.6K people that read it have a sense of humor. It’s clear that you don’t. And that is just fine. Also, I gave your comment a like. 👍
*Edit: 2.6K (I’m looking at you, playtonz)
This is one of my favorite videos. Solid explanation, positive reinforcement of guessing without being completely right. And very approachable maths. The animation compliments it nicely. Plus, an example of an intelligent guy being less than perfect at drawing a circle.
For those curious, the reason the binary solution works at the end (and I've watched this vid like ten times over the last few years and it finally clicked) is because when you move a number to the left in binary, you multiply that value by 2. In decimal, 40 becoming 400, that's ten times bigger, in binary, 10 (2) becoming 100 (4) is doubling.
Remember in the solution, it was 2L +1 is the correct seat. L = the whole binary number except the first digit, because that is the power of 2a, since all binary digits are powers of two and we ignore the largest one. By removing that first digit, and shifting everything left, we have doubled L. Then we need to add one, so we place the one from the front at the end, which increases the value by one, giving us 2L+1
Small note that confused me at first, while in computers you will often see binary numbers start with 0, here that won't happen because computers work by having a fixed length, the most famous being the 8bit of 00000000 or the like, and they show the full register all the time. Normally we write decimal numbers, like 41, but we could also write it as 00000041 if we wanted to force an eight length number. That's computers, not binary itself, so you can expect every binary number to start with 1 in this case, the amount removed by taking it away is the largest power of 2 in the number, and adding it to the end always will increase the total by one since it has to be a digit of 1.
Love this video, and boomerang swords are best swords.
I will never sit in an even seat again.
what if you sit in an odd seat and someone slides a chair up xD
others will notice that you are odd
well odd and even is relative to how everyone starts counting.If you sit in a circle table practically every sit is even and odd.
Thank you Josephus
odd that you would say that
What if Josephus calculated the position he should sit and the first person was a left hander and started in a counterclockwise direction? 😭
-7- man they are all, already, left handed actually 🤷♂️
Back then, weaponry training was standardized so everyone could use the same weaponry. It was guaranteed to go to the left.
They'd need to be right handed for a counter clockwise rotation.
or he didnt know what is right and left LULW
The one who takes the napkin first....
3:24 In your last moments, where you don’t know that you can just surrender instead, just getting sniped by a tomahawk chad with a boomerang sword that you gifted them.
I keep coming back to this because I keep forgetting the solution and I also find the animations quite satisfying.
Kid's math: How many apples does jessica have after giving 4 apples to matt?
*_M a n ' s_* math: What position would you take in order to live another day as a war prisoner?
Noble prize please
What is the answer to the first one? D:
You've purposely left out data on the first you fatlord
Bent
Bent
The real question is how the army got captured in the first place since they can just nonchalantly throw their swords like boomerangs
Idk.maybe aliens
They were besieged in a place without any source of water
They were probably few hours from capture before doing this or sth
Mmmmm
Smortboi ask smortquestion
Well, basically all I could do was nodding knowingly while thinking about my taco. He lost my in at about 4:03 in the video. I already knew I wasn't smart enough to understand this but I really love the enthusiasm in these videos. These are the guys that make progress for the rest of us.
That’s really awesome of you to call yourself out like that, I believe by the ways of the universe, that technically makes you the smartest person in this comment section! 🙃
I really appreciate your comment !
The last trick works because you are sliding everything a position over, which doubles the value of each since each binary spot to the left is just an additional power of two. And you will always be adding 1 because the binary representation of N will never start with 0 (since you always start with whatever the highest 2^a is). Very cool trick.
This is advanced eeny meeny miny moe.
Brandon Lemon 🍋 😂
but its in reverse
Negan should try this
Brandon Lemon eeny meeny miny moe, stab a tiger in his toe
I thought about playing tag, put our feet in. Bubble gum bubble gum in A dish how many pieces do you wish? This was cool.
"If you were writing your numbers in binary..." as one typically does
ah yes, computerspeak
*waits in replies to find the dingus who says “I aCtUaLlY wRiTe My NuMbErS iN bInArY”*
*I aCtUaLlY wRiTe My NuMbErS iN bInArY* (nt rly)
@@haroonq2456 I'm gonna call bs on that one big man
@@majikss yeah it's jokes
Forget the problem
Forget the animation
Forget the conjecture
Forget the math
.
.
.
This guys explanation skills were flawless!
In case anyone's wondering, the binary "trick" works because:
1. To find the solution, you first subtract the highest power of 2 from the number, which is the first 1 from the left in binary
2. Then you multiply L by 2, and 2 is 10 in binary, so you just add 0 to the right of the number
3. You add 1 to get 2L+1 as the solution, so that means that 0 from step 2 becomes 1
I love the way 1 boomerangs his sword
You'd think that with boomerang words such as that, they could defeat the Roman army.
Soham Kanerkar he did a darth vader
Dsennack - If I would stay alive until the end along with Darth Vader, I would immediately move to the Dark Side and ask Darth Vader for a job interview!
6:33
try 11:25
The detail of having the little animated guy flop his hand as he dies is ...
...gnarly
Attention to detail!
finish your sentence
Hilarious!
@@screamsinrussian5773 you had to do it yourself
This video is my earliest memory of doing math for fun. I just wanna say thank you
LOVE this video, fantastic content, love hearing the lesson on how to explore math!
My thoughs during the whole process...
If Josephus managed to figure this out just after the rush, and the adrenalin of a battle, and found the correct seat he had to pick in the little he had to think...
The dude deserved to live...
Nah he got lucky 😂
He became the advisor to the caesar. He was a genius
Well he doesn't have variable n. When n is fixed it's easy actually
He went on to provide the mythical basis for Christianity.
Why was the 6 afraid of 7?
Because 7 killed 1.
because 7-8-9
@@trevormiles5852 You ruined it.
@@trevormiles5852 XDDDD
Trevor Miles r/whoosh
no no no it is why was 6 afraid of 7? because 7 8 9. why so cruel...
Saw this video and decided to make a python program to tell you at an instant the number position you would need to stand in, fun project for someone learning programming!! I’m proud and thanks for the inspiration!
When they showed the pattern up to 16, one thought popped into my mind: maybe I can use logarithms to write this. 10 minutes of shuffling later, I made:
W(n)=2(n-2^(floor(log2(n))))+1
This is the first time that I did such a thing - I've heard of logs and know what they do, but I've never attempted to use one in an equation before. Thank you for inspiring me to try new methods!
The hard part is getting everyone to agree to let you be the one to choose who starts.
You wait until the person to start is chosen, then you take your place in the circle. If the group is a power of two, you volunteer to go first.
+Lugh Summerson And then they decide to go counterclockwise...
Tetraedri_
"Hang on, guys, I think I hear God talking to me. Excuse me while I go and pray."
Then elbow your way into the correct position when you return.
Even if its counterclockwise in power of 2 situation the winning one will be 1.
Majoofi But if everyone were supposed to die willingly anyway then there shouldn't be any fuss in picking someone to start.
Well, that's possibly the happiest explanation of a pretty morbid problem I've ever seen.
nothing remains morbid when put in front of a mathematician . . . or on a platter~
Nick Hadfield
To be fair, people were pretty enthusiastic when the math for the atomic and nuclear bombs were created
For some reason
hm when you say that I asume you Like seeing people get killed^^
Nick Hadfield ha ha yep
Welcome to the history of my people, basically.
my first video of yours and i'm already sold on your channel and i'm not really even into math but you make it interesting to me
Everytime i find something new about Math...I fall in love again & again❤❤❤
That boomerang sword throw at 3:25 was priceless.
I'm not the only one who noticed it!
SputnikSkull7 I was not expecting it and burst out laughing when I saw it
Yeah.. if I had a +3 sword of boomeranging then I think I might be better off sitting this whole thing out, you know?
If only he applied his skills to fighting the Romans.
Clearly his heart bar was full.
The title of this video should be called "How to betray your very last friends in life"
blood oath
"how to weasel out of your suicide pact"
well, i sort of doubt 40 people would care for the sole man's wish to live.
For the first time I can really recommend this; do not do this at home....its just to messy and too much to explain.
😂😂😂😂😂
What an amazing trick at the end! Thanks for presenting this in such an entertaining way!
I just love your numberphile videos,there a lot of fun and i think it helped me to get a interest in math.
If they could throw swords like that why surrender?
Luke Beef Exactly what I was thinking. Was going to type it myself but I found your comment.
Because the enemy could throw two
they didn't surrender didn't you watch the video
whoooooosh
whooosh
i love the sound of the sword hitting the people idk why xD
Max Moore
Me too. Thwunk!
I like the throwing sword method
I thought your dp was a hair on my phone screen
It reminds me of a sound effect you'd hear in an NES game.
your profile picture is genius
I’m happy people like you exist. Keep inspiring
It’s so satisfying watching them fight in fast motion :) lol
"Joseph, are you doing death math again!?"
*looks up from sheet* "Uhh no?"
Underrated comment
Hahaha Golden
3:25 That boomerang blade animation tho. The production team is on point for this episode.
op boomerang sword
3:23 is no one going to talk about how he just boomeranged his damn sword like that
In school, I was horrible at algebra (failed it 3x between HS and freshman year at college) because I always needed to know WHAT real-life problem I was trying to solve! Requiring me to memorize seemingly purposeless processes and procedures simply frustrated me to no end!
Had my teachers used real life examples such as this, I believe I would have been successful at learning algebra!
and then they start the circle at the wrong person.
That feeling of knowing you will die... rip.
can we start again? Or can I go to the bathroom and sit somewhere else then?
dont you know you will die? lol
gave me a chukle
1 will always equal the first person to go lol
This is how math should be taught in schools, being able to solve hard problems without knowing much information beforehand, rather than relying only on a formula for everything
And knowing it has practical implications in Roman life! :)
but there is a formula to this problem
And a liberal amount of death and gore
@@kidskers6771 but it is not known at the beginning. They are using only the information given and finding the formula themselves
The way math is taught encourages lazy thinking
Moving the first bit to be at the end is exactly 2n+1.
It's effectively a single bit shift to the left (which is multiplying by two) and then making the last bit a 1 (which is adding 1)
if the high school professors had explained math to me like this I would not have hated it
thank you
The sword swinging is so satisfying.
***** I am reporting you for having different tastes than me. Leave your hate speech off the internet.
Eliot _ He should've ended them rightly with a pommel
Especially the throw 😂😂😂
finally a problem i can relate to
you've been in this situation before? q:
We've all been there.
Username checks out
***** I see what you did there
User Name Lol
I think another thing that should have been pointed out (which isn't too hard to see if you do a bunch of these in sequence) is that the pattern which seems to reset back to 1 at powers of 2 when written in a table appears to be continuous when drawn out, since the highest seat number wrapping around to zero, so the correct spot will rotate around the circle continuously, completing a cycle every time it reaches a power of 2.
I really like this video. It made my curiosity fly so far. Thanks for that!
The killing animation is oddly satisfying
Will T
Oh thank God...I thought I was the only one
Will T oddly so, with great shame and enthusiasm
Asolutely, and the second best thing is the thud in the animation.
It's the sound
@@CultofThings its so satisfying
The animation and sound effects are so satisfying
I also had to stop and laugh for minutes. Just so curius...
Ikr
666th liker.
So you add 2 to w(n) on each step until w(n)>n, in which case you subtract n and continue from there. But since you're adding 2 to odd numbers and powers of 2 are even, it will always exceed the power of 2 by 1
Man, I really hope I remember this when the time comes.
What if josephus had a friend Jimmy who also wanted to live? And they want
wanted to coordinate them being the last 2 survivors? How can one represent this as a function?
I liked your comment so much I tried to figure this out myself. Turns out, it's almost the same as the original but slightly different.
The second last person's position gets changed to 1 every time N (number of people) is 3(2^a) rather than just 2^a like before (so the second last person will be 1 when N = 3, 6, 12, 24, 48, 96 etc.). Using this we can use the same strategy of making an equation N = 3(2^a) + M much like N = 2^a + L. From there the equations for the last person and the second last person are 2L + 1 and 2M + 1 respectively. I bet one can generalize this even further and make a formula for the nth last person.
See, now you're asking the real questions
+
Probably (this is just a guess) n = (2^a + l) -1
Turdy Tootsan I make an estimate of n = (2^a + l) -1
I really liked this video.
I have to say, videos with silly and irrelevant math curiosities are my favourite ones.
👍
I tried the problem and got the pattern, but man was it useless. Still fun though.
that is far from irrelevant.
villanelo1987 : Il like your avatar ! baldur's gate \o/ and this char was my favorite because of bouh ^^
Luiz Henrique elaborate
*"One must fight till the end and not commit suicide so as to prove his blood!"*
*-Dmitri Petrenko*
1:24 YOU BETTER NOT HAVE BEEN IN HIGH SCHOOL WHEN I’M STILL NOT!!!!
In the real story Josephus convinced the last remaining solider to get captured with him.
True. Funniest guy in ancient history. What about the "dream" that Traiano would be emperor? LOL Got him his "Flavius". Excellent stories.
Don't you love replaying movies its like we learn how people feel when we have to walk in thier shoes and experiance life through there shoes
His name was Jimmy.
@@ricardocima what
@@commenturthegreat2915 he prophesized to the romans that Tito would become emperor. Trajan died soon after and he became Tito's favorite, hence his name Flavius (Tito's family) Josephus. If i recall it well, I mean...
If anyone wants the binary explanation:
The leading digit is always 1 (since we don’t bother to put zeros in front of it) and represents the largest power of 2 smaller than n. Therefore, the remaining digits are L. Shifting L to the left is equivalent to multiplying by 2 (since each digit in powers of 2 is upped by 1 power), and putting the leading digit at the end means you get 1 x 2^0, or 1. In other words, it’s equivalent to just doing 2L + 1, which was the answer the video derived
Thanks a lot. I was searching for this explanation. But I don't understand how it's multiplied by 2. What do you mean by 'shifting to left'?
@@senthamizhan2422 Ah so in binary, each digit is a power of 2. The rightmost is 2^0, then 2^1, 2^2, etc until the leftmost digit. So the number 101 would be 1*2^2 + 0*2^1 + 1*2^0 = 5. Now "shifting to the left" means the number above would be come 1010, or 1*2^3 + 0*2^2 + 1*2^1 + 0*2^0 = 10. This is the same as multiplying by 2 because each digit is now multiplying a power of 2 that is one greater. The same reasoning means that a right shift is the same as dividing by 2 in binary.
@@marcantonios1066 Thank you so much. Now I understand it.
Yeah, as soon as he wrote out the binary and said he wouldn't go through the justification for it, my computer science education kicked in and said "Why not? It's literally the same math you just did expressed in binary; drop the highest power of 2, bitshift 1 spot left (multiply the remainder by 2), and add 1".
A simpler explanation of why shifting the digits one spot to the left in binary is the same as multiplying by 2 is to compare it to base 10. If you want to multiply a number by 10 in base 10, just move all the numbers one spot to the left and slap a 0 on the end (e.g. 5120 = 512 times 10). Moving digits one spot to the left is always equal to multiplying the number by whatever base you're working in, so shifting the digits one spot to the left in binary (base 2) and putting a 0 on the end is the same as multiplying by 2. 10 = 1 x (base) whatever base you're working in.
If you were to write this using ARM, you would just use the ROL function.
The way he framed that solution at the end in binary was CLEAN… i though of it as “first take off that front digit since that’s the 2^a part, then shift every digit leftwards one place to multiply the number by 2, then make the trailing digit 1 for the +1
The binary part totally makes sense. The lead digit is always going to be a one. By moving it to then end, you're essentially turning that 2^a bit to 0 and therefor, subtracting 2^a from n. Now you are left with L. By shifting all the bits over to the left one, you essentially increase the power of the binary components of L. 2^0 becomes 2^1, 2^1 becomes 2^2 and so on. This is the same as multiplying each binary component by 2 (When you multiply 2^1 by 2 it becomes 2^2), which is essentially 2L. (I hope you can follow how 2a+2b=2(a+b) where a and b are binary components of L) Now, since 2^a will always be a one, by putting it in the 2^0 position, you are adding one. The result is 2L+1
Late at night absolutely exhausted but UA-cam randomly suggested this video and I am reminded why I loved Maths as a student. Brilliant dude
I really enjoyed this video. Liked Daniel, liked the problem but particularly liked the trick at the end.
Glad you enjoyed it
Thomas Whelan the animations were very swish too
I know Daniel Erman said he wouldn't explain the binary trick, but can anyone else? I mean that's as close to mathematical black magic as anything I've ever seen and I would love to know more.
+Dan Brown If you move the highest digit of the binary to the end, you effectively do: 2×l+1. First you subtract the highest digit, our 2^a, then you move all remainig digits one up, which is multiplication by 2 in binary, then you add 1 on the 2^1 spot, which is one.
i didn't like the trick because tricks are deceitful and of the devil.
last "justify" question
basically, the winning number is 2(l) + 1. so the first digit that shows is always 1, so putting it in the last digit means +1. moving the other digits to the front all means ×2 to the powers of 2, which represents 2(l)
this is one of the most exiting video i have ever watched
Great job.
PG-13 for Mathematical Violence
Ha, you should have seen the X-rated one I originally submitted to Brady...
Can't you release a director's cut? ;)
No, he was uncut
*snort*
I needed a moment to get that one, Boredness.
Boredness Have we reached our limit yet?
That is one weird battle royale
The original battle royal
where we dropping Josephus?
Epic
Ruined that 555 'cause 1) Your comment is funny. 2) Haha.
Turn based battle royale
One of best professor I have ever seen in my life ❤️
So cool explanation..and the man who has animated is appreciated
4:20 *waiting for the 177 "sha-thunks" of the swords*
4:21 my disappointment is immeasurable and my day has been ruined.
@@NotAlshami I paused the video to figure it out cuz I had to know.
11:25 makes up for it. Kind of
Winning seat is 101 btw
178=10110010->1100101=101
@@masterspark9880 ye
I'm pretty sure they had a chance to fight back with the spin-throw sword technique, just saying...
But they wanted to die
aidan bowman but it's not suicide mate
Ben Lehner but it is when you are the last person
The binary trick at the end comes from the following:
-ℓ is the remainder of the subtraction of the largest power of 2 from the number, which is like saying dropping the leftmost non-zero digit of the binary number and keeping whatever's on the right.
-Multiplying a binary number by 2 can be done by adding a 0 to its right, or shifting all of its digits one spot to the left and adding a 0 on the new vacant digit on the right. It's like multiplying a decimal number by 10, you just add a 0 on the right.
-Adding a 1 to the previous number would just flip the new rightmost 0 to a 1. Performing 2ℓ+1, is like taking a number and adding a 1 to its right.
Since you drop the leftmost 1 and add a 1 to the right, it can be portrayed as moving the digit from there to here. It's an artistic depiction... except for the circular shift left operator which does exactly that.
I would like to have a screensaver on my computer with these animations of dudes killing each other in a circle with random starting numbers.
First digit in binary is always 1, so if you put it at the end, you remove biggest power of 2 smaller than n, the move every other digit to the left, so you multiply it by 2 and then you add 1. So it's 2l+1.
Exactly, the justification he didn't give is merely what happens when you shift by one digit an entire number in a given base, then add a single unit.
Thanks!
Here sir, take my upvote. I came here for this
So obviously, if n = 2^a - 1 then W(n) = n, and is the only case where W(n) = n.
Eg. 3, 7, 15, 31, 63, etc.
I was also wondering why they did not point this trivial bit out, but then I am a programmer so maybe manipulation of binary numbers seem more obvious to me and my kind.
December 2019: UA-cam taught me a very important lesson - don't sit at EVEN number. 😰
Always sit in an odd
@@jovianguyen3135 you always have to be the odd one.
don't sit at 2l+1 number
The final thing works because you bump everything up by one power of 2 so it's the same as multiplying by 2 and then you just add the 1 to the end. So it's the same as 2l+1
exactly. because every number can be expressed in binary as sums of powers of 2, so by adding a 0 you double each of those powers (definition of binary power), and doubling its parts must equal doubling the whole (associative property), which happens by bumping it by that first 1, removed to the end, which is the +1 in 2L+1
That was awesome.
Math is one of the most amazing things. Just unbelievable how it is in absolutely everything you can experience
"Alright everyone, we've lost. Get in the circle."
"Wait!! How many of us are there?? Does anyone mind if I do some quick math...?"
*2+2 is 4, - 1 that"s 3*
*quick maths*
@@stormizalive4380 I get it.
eyyyy
got emmm
Huh, the binary trick actually makes a lot of sense.
Based off of how a and l are defined, we know that the leftmost digit corresponds to 2^a, and the rest of the sequence is l. Then we shift each digit in l one place to the left, essentially doubling their values and giving us 2l. Then we place that 1 we took off on the right end, in the 1s place. So the result is 2l+1, the solution to the problem.
Nifty!
indeed makes a lot of sense, beautiful!
Really cool, thanks for explaining :) Little correction: The digits are shifted left :)
+TheAwesomeDudeGuy D'oh, you're right. Fixed.
Was just going to say this. I was right to search the comments for some1 who already did :p
an i felt so smart as i came on that solutuin xD
Thank you; Numberphile!
By far the most violent Numberphile video ever
but if they can throw their swords the way they do no Roman army can capture them.
🤣🤣🤣🤣🤣😁
Unless the romans have... you know, shields? ;-)
优秀
Unless the Romans can throw their swords too...
@@irrelevant_noob stfu Irrelevant noob
You gotta remember this for when you accidentally time travel to the roman empire and formed an alliance with the Jews
as one does
wow...amazing problem & approach!!
Josephus: "Wait, if nobody wants to be captured, why don't we just turn and fight? We don't *have* to surr-"
*everyone has already started killing each other*