Josephus problem¶

The recurrence problem of locating the survivor or elimination order when positions in a circle are removed at a fixed counting interval.

Version: v2 · 2026-09-19 · History
Domain-specific #: 5154
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomain: Discrete Mathematics → Mathematics
Aliases: Josephus permutation

Core Idea¶

Indexing may be zero- or one-based, counting convention determines whether the current or next position starts a round, and the classical step-two closed form does not extend unchanged to arbitrary step size. After each kth position is removed, the circle is relabeled relative to the next starting position; this self-similarity yields a recurrence mapping the survivor index for n minus one positions back into the n-position circle. The abstraction is therefore identified by a declared carrier, a transformation or constraint over that carrier, and an invariant that tells an analyst whether the named structure is genuinely present.

How would you explain it like I'm…

Last Kid Standing

Kids stand in a circle. You count around, and every second kid (or every third, or whatever number you pick) sits down. You keep going around until only one kid is left standing. The Josephus problem is figuring out ahead of time which spot will be the last one.

The Counting-Out Circle Puzzle

In the Josephus problem, n people stand in a circle and every kth person is removed as you count around, until one survivor remains. The puzzle is to figure out the survivor's position without acting it all out. A clever trick: after one person is removed, the remaining people form a smaller circle, which is the same puzzle with one fewer person. So you can solve the small puzzle and shift the answer back to the bigger circle. The rules must be clear, like where counting starts and whether you number seats from 0 or 1, because these change the answer.

Circular Elimination Recurrence

The Josephus problem places n positions in a circle and repeatedly removes every kth one until a single survivor is left, asking which position survives (and sometimes the full order of removal). Its key structure is self-similarity: after one removal, relabel the circle starting from the next position, and you have the same problem with n − 1 positions. This gives a recurrence that maps the survivor of the smaller circle back into the larger one. For step size 2 there's a neat closed formula, but that formula doesn't simply carry over to other step sizes. The answer depends on conventions: zero- or one-based numbering, direction, and whether counting begins at the current or the next position.

The Josephus problem concerns n positions in circular order with a fixed step size k: starting from a specified position and direction, every kth position is eliminated, and counting restarts from the next one until one remains. After each elimination the circle is relabeled relative to the new starting point, which reduces the problem to the (n − 1)-position case. This self-similarity yields a survivor recurrence; in zero-based indexing it is J(1) = 0 and J(n) = (J(n − 1) + k) mod n. The classical k = 2 case has a closed form, but it does not extend unchanged to arbitrary k. Correct statements must fix the conventions: indexing base, whether the current or next position starts a round, inclusion and restart rules, base case, and whether one wants only the survivor or the full elimination permutation. Changing a convention shifts the answer, so comparing results requires matching conventions.

Scope of Application¶

Josephus problem belongs to discrete mathematics and is useful where the analyst can specify the typed discrete mathematics carrier, including objects, relations, parameters, conventions, evidence, boundaries, and comparison targets, then evaluate the number of positions n, step size k, circular ordering and direction, initial counting position, inclusion convention, elimination and restart rule, zero- or one-based survivor recurrence, base case, closed form for special k and full elimination permutation are explicit.

Clarity¶

The abstraction clarifies a crowded vocabulary by making the number of positions n, step size k, circular ordering and direction, initial counting position, inclusion convention, elimination and restart rule, zero- or one-based survivor recurrence, base case, closed form for special k and full elimination permutation are explicit the center of the account. A claim should name the carrier, the governing operation or relation, the applicable assumptions, and the recognition test.

Manages Complexity¶

Without the abstraction, an analyst must reason directly over many local details: the carrier roles, admissibility assumptions, competing conventions, derived invariants, boundary cases, and proof or validation obligations specific to Josephus problem. Josephus problem compresses them into the roles in the structural signature. That compression permits comparison across instances without erasing the variables that determine validity. It also exposes which details may be varied safely and which are constitutive.

Abstract Reasoning¶

Identify the carrier. State what the elements, states, objects, or observations are: the typed discrete mathematics carrier, including objects, relations, parameters, conventions, evidence, boundaries, and comparison targets. Reject examples whose alleged carrier belongs to a different problem.
Lock the constitutive rule. Express the number of positions n, step size k, circular ordering and direction, initial counting position, inclusion convention, elimination and restart rule, zero- or one-based survivor recurrence, base case, closed form for special k and full elimination permutation are explicit independently of one notation or implementation.

Knowledge Transfer¶

Knowledge transfers strongly among subfields of discrete mathematics because they reuse the typed discrete mathematics carrier, including objects, relations, parameters, conventions, evidence, boundaries, and comparison targets, After each kth position is removed, the circle is relabeled relative to the next starting position; this self-similarity yields a recurrence mapping the survivor index for n minus one positions back into the n-position circle., and type the carrier, state every parameter and convention in the definition, test that the number of positions n, step size k, circular ordering and direction, initial counting position, inclusion convention, elimination and restart rule, zero- or one-based survivor recurrence, base case, closed form for special k and full elimination permutation are explicit, compare the nearest accepted identity, and report counterexamples, uncertainty, and limiting cases.

Relationships to Other Abstractions¶

Current abstraction Josephus problem Domain-specific

Parents (1) — outgoing typed relations

Josephus problem is a kind of Recursion Prime

It remains its own entry because its identity is fixed by the number of positions n, step size k, circular ordering and direction, initial counting position, inclusion convention, elimination and restart rule, zero- or one-based survivor recurrence, base case, closed form for special k and full elimination permutation.

Hierarchy path (1) — routes to 1 parentless root

Josephus problem → is a kind of Recursion

Neighborhood in Abstraction Space¶

Josephus problem sits in a crowded region of the domain-specific corpus (25^th percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Numeral Systems & Integer Sequences (22 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25