In the Josephus problem, people stand in a circle and every second person is eliminated until one is left. The Josephus problem calculator gives the position of the survivor, the position for another starting point, the largest power of two below the number of people and the people to add for person 1 to win.
How the calculation works
- Enter the number of people standing in a circle.
- Enter the position where the counting starts. Person 1 is the one at the start of the circle. If the counting starts at person 5, the survivor shifts by 4 places.
- The counting skips one person and eliminates the next, then continues around the circle, until one person is left. This is the case where every second person is eliminated.
- The calculator gives the position of the survivor J(n) = 2 × (n − 2ᵐ) + 1, where 2ᵐ is the largest power of two not above n, the survivor for your starting point and the number of people to add so that person 1 wins.
Example
41 people stand in a circle and every second person is eliminated. The largest power of two not above 41 is 32, so the survivor is at position 2 × (41 − 32) + 1 = 19. If the counting starts at person 5 instead of person 1, the survivor shifts by 4 places to position 23. To make person 1 the survivor, the circle should have 64 people, so you add 23. In total, 40 people are eliminated before the survivor.
Why it matters
The calculator helps students of mathematics and computer science, teachers and puzzle fans to see a classic recursion and its elegant closed form. It also helps to organize elimination games or to choose a starting point in a game for a group of children.
Good to know
The formula assumes that the counting starts at person 1, who is skipped, and that person 2 is eliminated first. If the first person counted is eliminated, the survivor changes, so check the rule of your game. The calculator handles every second person. For other counting steps, a program using the recursion is needed.
Related tools
The permutations calculator counts the orders of a group, the logarithm calculator finds the power of two, the combinations calculator counts the ways to choose people, and the tournament schedule calculator organizes matches between teams.