Skip to content
Omnikalc

Josephus problem calculator: find the safe position in a circle

Enter the number of people in the circle and the starting position to find the position of the survivor when every second person is eliminated.

Updated on
Your inputs

Value out of range

Value out of range

Results

Position of the survivor (counting from person 1)

19

Position of the survivor with your starting point
23
Largest power of two not above the number of people
32
People to add so that person 1 survives
23
People eliminated before the survivor
40

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.

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.

Frequently asked questions

What is the Josephus problem?

The Josephus problem is a counting-out game. People stand in a circle, and every k-th person is eliminated until one is left. The question is where to stand to be the last one. It is named after the historian Flavius Josephus, who according to a legend survived a mass suicide of Jewish rebels in the year 67 by standing in the right place.

What is the formula for every second person?

When every second person is eliminated, the survivor is at position J(n) = 2 × (n − 2ᵐ) + 1, where 2ᵐ is the largest power of two that is not greater than n. If n is a power of two, the survivor is always person 1. If you write n in binary, J(n) is found by moving the first digit to the end.

Why do powers of two matter?

In the first pass around the circle, half of the people are eliminated, and when n is a power of two, the next pass starts from person 1 again with half the people. The problem repeats at a smaller size until one person is left, so person 1 survives. For other values of n, the first elimination steps bring the circle down to a power of two.

What if the counting skips more than one person?

For every third person or more, there is no simple closed formula, and the survivor is found by a recursion J(n, k) = (J(n − 1, k) + k) mod n. The calculator handles the case k = 2. For a larger k, follow the recursion step by step or use a program.

Was this calculator helpful?

Thanks for your feedback!

Results are estimates provided for information purposes. They do not replace professional advice.