The Josephus Problem – Numberphile
Articles Blog

The Josephus Problem – Numberphile

October 8, 2019


So it’s called the Josephus Problem. It’s based on something from history. There was a group of Jewish soldiers who were surrounded by the Roman army and they didn’t want to get captured, so they decided to come up with a system- – to avoid getting captured or suicide. So they’d sit in a circle, and the first man would kill the guy to the left of him The next remaining living person would kill the next remaining living person with their sword. And they’d go around like this, till there’s only one person left, and the last person would have to commit suicide of course, rather than get captured. And the story – at least the story I was told, I’m not sure if this is historically accurate – Was that Josephus preferred captured than suicide, but he worried that if he said this, the other soldiers would turn on him. And so he wanted to figure out: WHERE should he sit within the circle- – in order to be the last man living. And then he would surrender, rather than kill himself. That was the problem It’s a little tricky, so let’s do a smaller example. Let’s say there are seven people. And so just to be clear, the way it works is:
person number one kills number two. Person number three kills four, Five kills six, But now things gets a little of harder to kind of see in advance Because seven, there is no eight, so seven kills one, Three kills five, Seven kills three. So seven’s the winner; seven is the last one left over. For Josephus, there were 41 people.
He needed to figure out where to sit. The mathematical problem is if there were n people. Where’s the winning seat? When I learned this problem I was in high school, And it was one of the first problems that got me to understand how you approach- – difficult and- and… Math problems where you don’t know the answer in advance, or someone hasn’t shown it to you in advance. And it was a professor of mine his name was Phil Hanlon who played a big role in, kind of, leading me to math. And he suggested: what we should do is we should gather data. Just… Take various values of n and just do it by hand and start looking for a pattern. I don’t know, maybe we should just do that? n is the number of seats,
and w of n will be the winning seat. And what we know so far is that:
n is seven, w of n it turns out is also seven. And so what I would do is I’d start doing some other values So, I don’t know, why don’t I do five? One kills two, three kills four, five kills one, three kills five. The winner is three. I guess there was no reason for me to skip six,
so why don’t we fill in six. One kills two, three kills four, five kills six… … one kills three and five kills one. The winner is five. So If you’re watching you might already start to notice some patterns. For instance, they’re always odd.
I mean, that’s maybe the first thing you notice And you can start asking “why are they always odd?”
And maybe you can already see that- – in the first loop around, all the even people get killed. So So you can – even with a tiny amount of experiment – start to see some patterns. – *Brady* So you DON’T want to sit in an even seat?
– Don’t sit in an even seat, no no no. And maybe we’re even getting some glimmers of other patterns But before I really try to phrase those,
I’d like to fill in the table a little bit more. So let’s do some. So if there’s only one person… well… That person’s the winner, so that one was easy. If there’s two people: one kills two. One is the winner If there’s three people: one kills two, three kills one. Three is the winner If there’s four people: one kills two, three kills four, one kills three. If there’s eight people: one kills two, three kills four, five kills six, seven kills eight, one kills three, five kills seven, one kills five. The winner is one. Alright so it was one, one, three, one, three, five, seven. One, three, five, seven, nine. And you could keep going,
but maybe you can see the pattern now? – *Brady* Is thirteen a one?
– NO! Good guess actually! But it is not a one. So let’s do thirteen. *Brady* This is good, I don’t know then, I can’t see the pattern. So as you see it’s jumping by two each time,
but then it resets at some point and And I want to go back to this, so we’ll see what thirteen is quickly So we didn’t reset that,
and I claim we won’t reset it the next one either. Fourteen will be thirteen and here, by the way, we’re be starting to make predictions. It’s worth noting we’ve- Even though we maybe can’t say
exactly what like 178 would be- – we’re starting to see well enough so we can make a prediction. So… so you could guess. Is it really true that fourteen is going to give you thirteen? We could do it out, and you’ll see in fact that’s what you’ll get So we’re getting some understanding… But I want to go back to this point you had, you asked if it’s going to reset and go back to one there And the answer was no, and it’s worth looking. Because this is the next thing I was going to do. Where do we get the ones? So if you look for a sec, there’s something very special about the numbers that give you ones. It’s the powers of two. And so maybe you can now guess that if i put in a sixteen, I would get a one back. And that’ll be right, and that’s actually going to be a real key in unlocking this. The professor I was learning this from made a really big point out of this. And I thought, you know, well I don’t know what the general answer is yet! And he made a big point: If you know something… Prove it, and make sure you really understand that one thing, and that often unlocks the rest. So So he really pushed us when I was first doing this, to try to state a conjecture and then prove a theorem- based on what we just saw here. And so that’s what I want to do, so here’s the conjecture: If n is a pure power of two, then the winning seat is one. I want to think about this for a second and maybe see why this might be true. So let’s do the next biggest power of two,
maybe the biggest one I can bother writing down. So let’s do sixteen So I want to do one pass through the circle. – *Brady* Take out all the evens.
– Take out all the evens. And now, fifteen has just killed sixteen. So I’ll put a little dot here so we’ll remember it’s number one’s turn again. And it’s number one’s turn again, and we’ve removed all the evens. And what’s left is therefore exactly half as many. So if i relabel at this point You can see that there’s a power of two to start with. I pass through the circle once, I get rid of all the evens, I have half as many. And I’m back at number one’s turn. So now if I do this again,
the same thing ought to happen. Right? I should kill all the evens on the new labeling And now there are four people left, and it’s STILL number one’s turn So you go through again… Kill those guys, there’s two people left,
it’s still number one’s turn- – and that one kills that, and it’s still number one’s turn and that chair wins. So let’s say we believe that.
We know what happens to two to the n. So how do we explain what happens between the pure powers of two? If you see the pattern, you know- we know what happens at eight, and we know what happens at four… … but between them it goes up by twos until at this point, if I added two to seven, I’d have a nine Which would be too big anyway, so that’s our reset But we knew it was going to reset because it’s a pure power of two. So how do we explain this jumping by two phenomena inbetween? So what I’m going to do- I’m gonna just mention that: For any number- – you can write it as
a big power of two plus something else Take the biggest power of two you can subtract from a number- And then what’s left should be smaller than that. When you express a number in binary notation- – ou choose zeroes or ones, and that gives it out as a sum of a bunch of powers of two… … and you just choose the biggest one. So 77. The biggest power of two I can get is 64. And then, what is it, it’s 64 + 13. So then for 13, the biggest power of two is
8 + 4 + 1. Did I do this right? 72… 77, there you go. And these are all powers of two! And this is unique. This is the unique way to write 77 as a sum of powers of two. Where no powers repeated, that’s a key point. So if you wanted to take a general number, take the biggest power of two – 64 – and then the remaining part. *Mumble* Twelve… Thirteen. I’m going to call this part two to the a,
and the remaining part I’m going to call l And I claim that this l is going to tell us which of those odd number between are going to show up. So let’s see how. How about we do thirteen. n is thirteen. This is the binary expansion, but using our new method the eight will be the two to the a- – and the five (which is the four plus one) that’ll be the l. And here’s the thing that’s going to happen with the l: I’m going to do five steps. So 1 kills 2, 3 kills 4, 5 kills 6, 7 kills 8, 9 kills 10. So now I’ve dropped… l people. And it’s number eleven’s turn. Now watch what happens, how many people are left?
Well what’s left is a power of two. And we know who wins in a power of two,
it’s whoever starts! *Brady* The first killer. The first killer! So now, if we go from here I claim that eleven is going to win. And just watch, it’s going to be. 11 kills 12, 13 kills 1, 3 kills 5, 7 kills 9 Back to eleven, and now there’s only four people left. 11 kills 13, 3 kills 7… Back to eleven, two people… Eleven wins. And so this is really the key to the final answer. Which is If you’ve written your number as two to the a plus l- – after l steps, whosever turn it is is going to win. Because it’s going to be their turn and there’ll be a power of two left. And so the winning seat will be two l plus one. If you write it in this way, because that’s whose turn it is after l steps. The theorem or the claim, is that if you’ve written n in this way… So if n is two to the a plus l, where l is less than two to the a. It has to be strictly smaller So in other words: two to the a is the biggest power that sat inside of n. Then the winning seat is going to be 2 l plus one. So we’ve already seen it was true here, right? l was five and the winning seat was eleven, which is two times five plus one. And if you start going back through you’ll see it’s the same thing for all the answers. We’ve already illustrated the mechanisms, which is after l steps- It’s the turn of person 2 l plus one, and after l steps, there are a power of two number of people left. and… Everyone knows that the power of two people, the first person who kills, that’s who’s going to be the winner *Brady* Let’s see if Brady has learned! *chuckle* Yeah! Alright! Let’s do it *Brady* – I think I follow. Now in the Josephus problem… – Yep! – … There was Josephus and 40 soldiers. – That’s right. Oh yeah! We got to go back and do that! – Alright so we got 41 people… – So n is 41 – Alright, now I think – expressing that in the way you told me to – it’s going to be 32 + 9? – There you go, 32 + 9 – So… Two lots of nine… plus one… – Mhm – … is nineteen – There we go – So we want to sit in position nineteen. – There you go. You want to sit in the nineteenth chair. So here we go we’re going to do n=41 – Alright. Put them in, in the cave, waiting their fate. – Not a very good circle but… – It’s getting smaller now… – I know. *Brady and Daniel chuckles* *Daniel chuckles* Should I redo this? – Nah you’re okay. *Daniel mumbles* 40… 41… – Okay there we are.
So we got a little tight at the end – Look at that, this is a lession about
planning ahead, people. Okay so let’s do it. So one kills two… – We’re losing our even numbers. – Yep. Okay now… 41 kills 1. *Daniel mumbles* three kills five… And 19 kills 35 and there we go! – Alright. I was right! – There we go, nineteen! Oh and one other thing in this
problem which is kind of fun… So this formula I wrote can be interpreted in binary notation. When we wrote a number as a sum of powers of two… This can be re-expressed in binary notation. So what was this… 32 + 8 + 1 So that’s… 2⁵ + 2³ + 2⁰ And binary notation… The digits correspond to the various powers of two, and all the digits are either zero or one. So 41 in binary notation would be
one copy of 2⁵, zero of 2⁴, one of 2³, zero 2², zero 2¹ and one 2⁰ Here’s the trick for the Josephus problem. Which I won’t justify but it’s super cool,
and you can try it own your own. The way to find the winning solution if this is n- – the winning solution in binary is you take the leading digit- – and you put it at the end. So in other words I claim that if I write *Mumbles* Zero… One… So I take this part and then I add the first digit to the end. That number in binary code is… Well let’s see… It’s 2⁰ + 2¹ + (I skipped 2² and I skipped 2³) and I add 2⁴ So it’s 2⁴ + 2¹ + 2⁰ Which is 16 + 2 + 1 Which is nineteen, which is exactly what the winning seat was. and… And so there’s this super efficient way in binary code to jump straight from the number n- – to the winning number w of n. So if you’re writing you numbers in binary code, the pattern would’ve been even more quickly apparent Isn’t that cool?! *Brady agrees and chuckles* Isn’t that cool? – Yeah This video was filmed at the
Mathematical Sciences Research Institute (MSRI) That’s the building behind me. If you’d like to find out more about them, link’s in the video description. They do some really important serious mathematics here, and they’re also a big supporter of math outrage. As evidenced by this video.

Only registered users can comment.

  1. But what if they all wanted to be captured. But they didn't want to say it because they could be turned on. By their other friends who also didn't want to die. But hey, that's just a theory

  2. This is a classic example of making a problem much harder than it needs to be. You assume the the direction of action is clockwise. When really he would just sit with the first person to be killed on his right. Then let the action go CCW where the person who last killed someone is the next to die…..I highly doubt if the scenario ever happened and if it did there is little to no chance they wondered how to execute it. K.I.S.S.

  3. Binary swapping the first 1 to last is simply subtracting the biggest 2^a from number and adding 1 at the end of the binary number is multiplying with 2 +1. You could have just explained it.

  4. If the winning seat is 2L+1, what that binary trick does is remove the top power of 2 entirely, the left shift in binary is exactly the same as multiply by 2, and adding a 1 at the far right is the "+1" part of the formula. So you haven't really moved the 1 from the left to the right; you DROP the 1 on the left, shift everyone left one column, and insert a 1 at the least significant digit place.

  5. So instead of being nicknamed the Serial Killer, you might label the "winner" here the MSB-to-LSB Binary-Digit-Transfer Killer . . . – j q t –

  6. I'd have been real suspicious if Josephus was the guy who came up with this contrived system and also took like half an hour to decide on where he wanted to be seated.

  7. The last binary trick is simple. By putting the first number in the back, you are removing the 2^a, and you end up bumping each other number up one space in the binary chart, which in essence is just doubling that value. Then the first number is moved into the last slot, which always equals one. So right there all you did was double the number and add one.

  8. It's 1 in the morning but I have to justify that last bit, because the feeling of suddenly understanding it is making me really happy.

    When you take any binary number out of the blue, it's going to start with 1. You don't need to know there's no 256 or 512 in your number if it's 85, i.e. way smaller, so your binary number will always do away with all the 0s and start with the biggest power of 2 you have as a 1. Separate that 1 from the rest, and you have the 1 representing the biggest power of 2 in your number, and the rest representing the "L" of your number…or 2^a + L.

    When you switch their positions, by moving up each digit in L, you're changing it from 2^4 to 2^5 let's say…which is just multiplying by 2. Each piece of L gets multiplied by 2, then added…or you could just add them, then multiply them. Your 1 from the beginning then gets tacked onto the end, in the 2^0 place every time, making it represent 1…so you've literally created 2(L) + 1 in binary.

    It's part binary rules and part one of those math tricks that will always give you the same number, and it's fantastic.

  9. starting to try figuring out this problem during a battle might end the war itself.

    "aye, mate, do you know Josephus Problem? Gather around let me teach you guys eyy?"

  10. Nicely explained, I love the way you teach. Sometimes I wonder if my teacher taught like that I would have been a better student.

  11. With "binary trick" he missed tiny important part of it. Its not about putting first didit to the end, but first "1" digit to the end.
    So for example for 117 winning number is 107. In this case 117 to binary would be = 01110101. So if you try to put zero at the end
    it will be 234 which is not correct already ( its even bigger than amount of N ), but if you put first 1 to the end it will give you the answer
    which is 107. Please correct me if Im wrong.

  12. If sy is interested in the last bit: if you take away the first digit, the rest of the number is the l from the formula 2^a + l, and similarly to base 10, multiplying a number by 2 is just putting a 0 in the back, so, by putting that 1 in the back, we essentially just double l and give it +1, which yields 2*l + 1, which was shown as the winning seat.

  13. What if a couple of soldiers wanted to survive? Can someone figure out the pattern for the 2nd last survivor please?

  14. Where P=X and P is prime, X = P -1y where y is also prime. This pattern always lands on the lowest reducible prime from a given starting number = Z

  15. I remember that my teacher gave us this assignment on our first day of college. It is a programming class and some of us couldn't even write Hello World program yet.

  16. Is this the mathematical problem they had to solve before the mass suicides at Masada ? There's no way any rational person (even Josephus) would chose capture by the Romans over suicide !

  17. The bit shift trick at the end is not as surprising when you're a programmer:
    Shift to the left doubles a value, shifting to the right divides by two.
    Now we're also taking away the leading 1, so we're subtracting our highest power of two, and we're putting it in in the back, therefore adding one. So that's really just the same formula by bit manipulation.

  18. The real question is, why didn't you first lean how to say his name? It's joe-see-fuss. His whole story is fascinating! He wrote the oldest non Bible history of Israel.

  19. Josephus calculates the perfect place one of them messes up and kills the wrong person and they just continue as usually
    Josephus: wait that’s illegal

Leave a Reply

Your email address will not be published. Required fields are marked *