Fact-checked by Grok 2 weeks ago

Josephus problem

The Josephus problem is a classic puzzle in mathematics and computer science, describing a scenario where n people stand in a circle and are systematically eliminated by counting every k-th person (with k ≥ 2) until only one survivor remains; the goal is to determine the initial position of that survivor, denoted as J_k(n). This elimination process forms a permutation of the positions, and the problem has been generalized to various counting rules and moduli.^[1]^[2] The problem originates from a historical account by the first-century Jewish historian Flavius Josephus in his work The Jewish War (c. 75 AD), where he described 41 soldiers trapped in a cave during the Romano-Jewish War of 67 AD; to avoid capture, they agreed to form a circle and kill every third person until none remained, but Josephus calculated positions 16 and 31 to be the last survivors, allowing him and another to surrender.^[1] Although Josephus did not pose it as a general mathematical problem, his narrative inspired later formulations, with the earliest explicit puzzle version appearing in Claude Gaspard Bachet de Méziriac's Problèmes plaisants et délectables (1624) for n=41 and k=3.^[2] The problem gained rigorous mathematical treatment in the 18th century through Leonhard Euler's 1760s analysis of related circular permutations, leading to a recursive solution published in 1776.^[1]^[3] Mathematically, the classical Josephus function J_k(n) satisfies the recurrence J_k(1) = 1 and J_k(n) = (J_k(n-1) + k) mod n for n > 1, with adjustments to map results to positions 1 through n.^[1] For the common case k=2, a closed-form solution exists: J_2(n) = 2l + 1, where n = 2^m + l and l < 2^m, or equivalently J_2(n) = 2n - 2^{\lfloor \log_2 n \rfloor + 1} + 1, allowing efficient computation in O(\log n) time.^[2]^[1] No general closed form is known for arbitrary k, but algorithmic solutions, such as those by Donald Knuth using binary representations or dynamic programming, achieve O(n) or better complexity, with applications in algorithm design, queue simulations, and analyzing elimination games.^[1] The problem's variants, including non-constant k or modular arithmetic, extend its relevance to number theory and combinatorics, with fixed points (where J_k(n) = n) and periodic behaviors studied in modern analyses.^[2]

Problem Formulation

Classic Setup

The Josephus problem originates from an account by the first-century historian Flavius Josephus, but its classic mathematical formulation abstracts the scenario into a combinatorial puzzle.^[4] In the standard setup, there are n people standing in a circle, numbered consecutively from 1 to n.^[1] Counting begins at position 1 and proceeds clockwise around the circle.^[1] Every k-th person (where k is a fixed positive integer, typically k \geq 2) is eliminated from the circle, and the counting resumes from the next remaining person, continuing this process sequentially until only one person remains.^[5] The objective is to determine the original position of this last survivor.^[6] The survivor's position is denoted J_k(n), using 1-based indexing.^[1] For illustration, consider n = 5 and k = 2: starting at 1, the first eliminated is 2 (count: 1, 2); next from 3, eliminates 4 (3, 4); next from 5, eliminates 1 (5, 1); next from 3, eliminates 5 (3, 5); leaving 3 as the survivor. The full elimination order is thus 2, 4, 1, 5.

Parameters and Variations in Counting

The Josephus problem is defined in terms of two key parameters: n, the total number of people arranged in a circle, and k, the fixed step size used for counting out every person to be eliminated, where both are positive integers satisfying n \geq 1 and k \geq 1.^[1]^[7] These parameters determine the sequence of eliminations and the position of the sole survivor, with the process continuing until only one person remains.^[8] Special cases arise depending on the value of k relative to n. When k = 1, counting eliminates each person in sequential order starting from the first, resulting in the survivor being the last person in the circle (position n in 1-based indexing).^[1] If k > n, the effective step size for the initial count reduces to k \mod n (with adjustment if the remainder is 0, equivalent to n), as the counting wraps around the circle multiple times before the first elimination.^[7] This modular reduction ensures the process remains well-defined even for large k.^[8] Variations in the counting procedure introduce additional flexibility while preserving the core elimination mechanism. The starting point for counting can differ across formulations; typically, it begins at position 1 (1-based), but some analyses start at position 0 for mathematical convenience. Direction of counting is usually clockwise, but counterclockwise variants exist, effectively reversing the order of eliminations and altering the survivor position accordingly—once a direction is chosen, it remains consistent throughout.^[9] Indexing conventions also vary: 1-based numbering (positions 1 to n) is common in historical and applied contexts, while 0-based (positions 0 to n-1) simplifies recursive computations, requiring an offset of +1 to convert results to 1-based positions.^[8]^[10] To illustrate the impact of changing k, consider n = 8 people numbered 1 to 8 in a circle, starting at position 1 and counting clockwise (1-based). For k = 3, the first eliminations proceed as position 3, then 6 (continuing from 4), then 1 (from 7), leading to a different sequence than for k = 5, where the first eliminations are position 5, then 2 (from 6), then 8 (from 3), demonstrating how larger steps accelerate wrapping and shift the elimination order.^[7] These parameter tweaks highlight the problem's sensitivity to counting rules without altering the fundamental circular elimination process.

Historical Background

Flavius Josephus's Account

Flavius Josephus (c. 37–c. 100 CE), a Jewish aristocrat, priest, and military commander during the First Jewish-Roman War (66–73 CE), described a pivotal personal episode from the siege of Jotapata (modern Yodfat) in his historical text The Jewish War, composed around 75 CE in Rome. As commander of the Jewish forces at Jotapata, Josephus defended the town against the Roman general Vespasian for 47 days before its fall in July 67 CE. When the city was overrun, Josephus and 40 companions sought refuge in a cave to evade capture by the Romans. The group, preferring death to enslavement or execution, resolved to commit collective suicide and drew lots to establish the sequence in which each would kill the next. This process continued systematically until only two remained: Josephus and one other soldier. Josephus then convinced his companion that surrender offered a path to survival, arguing against self-destruction when mercy might be possible from the Romans. The pair emerged from the cave and submitted to Roman custody; Vespasian initially imprisoned Josephus but later freed him, granting citizenship and patronage that enabled his later writings. The incident involved approximately 41 participants (Josephus plus 40 others), with the elimination method based on lots rather than a fixed counting rule, though subsequent analyses have retrofitted a step of every third person (k=3) to model it mathematically. Josephus implied he influenced the lot's outcome to ensure he was among the final survivors, a claim that underscores his narrative of providence and pragmatism. Scholars question the story's historical veracity, viewing it potentially as an allegorical or self-justifying device to explain Josephus's defection, which branded him a collaborator among some Jews.^[11] As the sole attestation, unconfirmed by archaeology or other records, the account may blend fact with rhetorical embellishment to portray Josephus as guided by reason and divine favor amid crisis.^[9]

Mathematical Interpretations Over Time

Following the account attributed to Flavius Josephus in the first century AD, mathematical interpretations of the problem remained sparse for centuries, with limited references appearing in medieval texts. A version of the counting-out puzzle is traced to the Jewish scholar Abraham ibn Ezra around 1140, who discussed a similar elimination process in his commentary on the Bible, potentially linking to earlier Talmudic riddles involving circular arrangements and selection.^[9] These early mentions treated the scenario more as a logical or interpretive exercise rather than a formalized mathematical query. The first explicit mathematical formulation of the puzzle appeared in Claude Gaspard Bachet de Méziriac's Problèmes plaisants et délectables (1624), which presented a version with 41 people and elimination every third (k=3), directly inspired by Josephus's account.^[2] The problem saw a revival in the 18th century among European mathematicians, notably Leonhard Euler, who in 1776 analyzed it in the context of progressions and recursive patterns, providing one of the first systematic treatments in Western mathematics.^[12] Concurrently, Japanese mathematicians such as Takebe Katahiro and Seki Takakazu explored generalizations during the Edo period, extending the counting rules to broader combinatorial scenarios and emphasizing its relevance to enumeration problems.^[13] In the 19th century, the Josephus problem gained popularity as a recreational puzzle through W. W. Rouse Ball's Mathematical Recreations and Essays (1892), which presented it as an engaging arithmetic challenge and helped disseminate it among amateur and professional mathematicians alike.^[14] Ball's work emphasized its intuitive appeal, drawing on historical anecdotes to illustrate the interplay between position and survival. By the early 20th century, the problem had evolved into a staple of discrete mathematics, recognized for its connections to combinatorics and recursion theory, with influential analyses in the 1960s highlighting its utility in understanding iterative processes.^[2] This period marked its transition from isolated curiosities to a foundational example in theoretical studies of permutations and elimination sequences.^[6]

Specific Solutions

Binary Case (k=2)

When every second person is eliminated in the circle (k=2), the Josephus problem simplifies significantly, allowing for an elegant closed-form solution that leverages the binary structure of n. This case is particularly insightful because it reveals a direct connection between the survivor's position and the binary representation of the total number of people n.^[15] The solution is derived recursively by distinguishing between even and odd values of n. Define f(n, 2) as the 1-based position of the survivor. The base case is f(1, 2) = 1. For even n = 2p, the first elimination round removes all even-positioned people, leaving p survivors starting the next round from position 1; thus, f(2p, 2) = 2 f(p, 2) - 1. For odd n = 2p + 1, the first round eliminates even positions up to 2p and then position 1, leaving p survivors starting from position 3 (which maps to 2 in the reduced circle); thus, f(2p + 1, 2) = 2 f(p, 2) + 1.^[15] These recurrences lead to the closed-form expression: write n = 2^m + l where m = \lfloor \log_2 n \rfloor is the highest power of 2 less than or equal to n, and l = n - 2^m with 0 \leq l < 2^m; then f(n, 2) = 2l + 1. Equivalently, the binary representation of f(n, 2) is obtained by rotating the binary digits of n one position to the left (cyclic shift), moving the leading 1 to the least significant bit. For instance, with n=1 (binary 1), f(1, 2)=1 (binary 1). For n=5 (binary 101), rotation yields 011 (decimal 3), so f(5, 2)=3. For n=10 (binary 1010), rotation yields 0101 (decimal 5), so f(10, 2)=5.^[15] This formula can be proved by induction on m. For the base case m=0, n=1=2^0 + 0, f(1, 2)=2\cdot0 + 1=1, which holds. Assume it holds for all values up to 2^m; for n=2^m + l with l < 2^m, the proof splits into cases using the recurrences: for n=2^{m+1}, l=0, f=1 by direct recursion from f(2^m)=1; for general l, apply the even/odd recurrences iteratively to reduce to the inductive hypothesis, yielding 2l + 1. The binary rotation follows similarly, as the recurrences preserve the bit-shift property under induction.^[15]

Ternary Case (k=3)

The ternary case of the Josephus problem, with every third person eliminated (k=3), lacks a simple closed-form solution like that for k=2, necessitating reliance on recursion, iterative algorithms, or tabulation for determining the survivor position f(n,3). This contrasts with the binary case's cyclic rotation around powers of 2, highlighting the ternary case's distinct structural irregularities.^[16] Computational approaches often use dynamic programming to build a table of survivor positions up to n, achieving O(n) time complexity, as direct simulation via linked lists would be less efficient for large n.^[17] A prominent example is the historical scenario with n=41, where the survivor occupies position 31 (1-based indexing), aligning with Flavius Josephus's described positioning to ensure survival. For n=7, the elimination proceeds as positions 3, 6, 2, 7, 5, 1, leaving the survivor at position 4.^[8]^[17] An explicit non-recursive formula for the survivor position in the k=3 case is provided by Halbeisen and Hungerbühler: using collapsing numbers c_m = \round(a \cdot (3/2)^m) where a \approx 0.8111 and m \approx \round(\log n / \log(3/2)), the position (0-based) is j(n,3,n) = 3(n - c_m) + d_m with d_m \in {0,1} determined by fractional part comparisons; adding 1 yields the 1-based f(n,3). For n=41, m=9, c_9=31, d_9=0, so f(41,3)=31.^[10] A useful approximation, exact for many n, is f(n,3) = 3n + 1 - \floor{ K(3) \cdot (3/2)^{\lceil \log_{3/2} ((2n+1)/K(3)) \rceil } }, where K(3) \approx 1.62227 is the constant solving x = e^{(3/2) \ln(1 + 1/x)} from functional iteration analysis. This stems from modeling the elimination as iterated maps, providing insight into the asymptotic behavior where f(n,3) grows roughly as (3/2)n offset by periodic adjustments tied to powers of 3.^[18] The sequence f(n,3) (OEIS A054995) displays notable irregularities, with increments (f(n+1,3) - f(n,3) + 3) \mod (n+1) forming cycles of lengths scaling with powers of 3, complicating pattern recognition beyond the binary case's bitwise simplicity. These cycles contribute to computational challenges for very large n, though the approximations and formulas mitigate this for practical purposes.^[19]

Recursive and Iterative Approaches

The Josephus problem can be solved using a recursive approach based on the observation that after eliminating the k-th person in a circle of n people, the problem reduces to finding the survivor in a circle of n-1 people, with the counting offset adjusted accordingly. The position of the survivor, denoted f(n, k) and assuming 1-indexed positions, satisfies the base case f(1, k) = 1 for any k ≥ 1. For n > 1, the recursive formula is f(n, k) = [(f(n-1, k) + k - 1) \mod n] + 1. Equivalently, in a form that directly uses modular arithmetic without the offset adjustment, f(n, k) = (f(n-1, k) + k) \mod n, where the result 0 is replaced by n to maintain 1-indexing.^[10]^[1] This naive recursive implementation computes f(n, k) in O(n) time, as it performs a linear number of recursive calls, each involving constant-time modular arithmetic; however, for the special case k=2, optimizations using binary representations allow computation in O(\log n) time by leveraging the closed-form relation to the highest power of 2 less than or equal to n. For general k, no such logarithmic-time recursion exists without additional structure, and the O(n) bound remains standard.^[1]^[20] An iterative approach simulates the elimination process directly using a data structure to represent the circle, such as a queue or doubly-linked list, where every k-th person is removed until one remains. In the queue-based variant, the n people are initially enqueued in order; for each elimination round, the first k-1 people are dequeued and re-enqueued to rotate the circle, and the k-th is dequeued and eliminated, repeating until the queue has one element. This simulation runs in O(n k) time due to the rotations per elimination, making it inefficient for large k relative to n.^[21] To illustrate the recursive or iterative computation, consider n=10 people and k=3, with positions labeled 1 through 10 and counting starting at position 1. The elimination order proceeds as follows: first, count to 3 and eliminate 3 (next start at 4); then eliminate 6 (next at 7); then 9 (next at 10); then 2 (next at 4); then 7 (next at 8); then 1 (next at 4); then 8 (next at 10); then 5 (next at 10); then 10, leaving survivor at position 4. This trace confirms f(10, 3) = 4 via direct simulation or by unfolding the recursive formula from the base case upward.^[17] For handling large n where full simulation becomes prohibitive, the iterative version of the recursive formula avoids explicit list structures by computing the survivor position using a loop over modular updates: initialize f = 0 (0-indexed equivalent), then for i from 2 to n, set f = (f + k) \mod i, and adjust to 1-indexed by adding 1 at the end; this achieves O(n time using only arithmetic operations, independent of k.^[21]

Generalizations and Extensions

Modified Counting Rules

In variants of the Josephus problem, the core elimination mechanics are altered to explore different survival dynamics, such as allowing multiple survivors or changing the spatial arrangement of participants. A key modification involves generalizing the process to leave r survivors rather than a single one, extending the historical scenario where Flavius Josephus and his accomplice positioned themselves as the last two remaining among 41 soldiers by eliminating every third person. In this setup, counting proceeds as in the classic case—every kth person is eliminated in a circle—but halts when exactly r individuals remain, with the goal of determining their positions. This generalization applies the same recursive structure as the standard problem but adjusts the termination condition; for r=2 and k=3 with n=41, the survivors occupy positions 16 and 31.^[1] Another significant alteration is the linear arrangement, where participants stand in a straight line instead of a circle, fundamentally changing the counting path. Here, n players are lined up, and elimination begins from one end, removing every kth person while traversing the line; upon reaching the end, the process may reverse direction or stop, depending on the specific rules. For example, with n=5 and k=2 starting from the left, the second and fourth are eliminated first, leaving the first, third, and fifth in adjusted positions for subsequent rounds. This non-circular variant introduces boundary effects absent in the circular case, leading to different survival patterns.^[22] The Feline Josephus problem further modifies the rules by assigning ℓ lives to each of n soldiers arranged in a circle, requiring multiple "hits" for elimination rather than instant removal. Counting eliminates or damages k consecutive soldiers per pass, skipping one after each group, and continues until all but one soldier's lives are depleted. For ℓ=2 (double elimination), n=7, and k=3, soldiers lose lives in groups of three, with soldier 4 surviving after two rounds where others are fully eliminated. This introduces layered elimination mechanics, generalizing to higher ℓ for more complex survival analysis.^[23] Some variants incorporate variable k, where the counting step changes after each elimination. For example, using pseudorandom sequences generated by chaotic systems, applied in a circular setup until one remains; however, closed-form solutions are rare, relying on simulation for specific n. This dynamic adjustment alters the permutation of eliminations compared to fixed k.^[24] Recent work has also explored randomized variants, where the elimination step includes probabilistic choices, further extending the problem's scope.^[25] Regarding counting resumption, the standard rule continues from the person immediately after the eliminated one, assigning count 1 to them for the next cycle. A contrasting variant restarts the full count from 1 at a fixed starting point after each elimination, though this is less common and leads to repetitive patterns favoring initial positions.

Applications in Computer Science

The Josephus problem serves as a foundational example in algorithm design, demonstrating techniques for handling circular data structures and elimination processes efficiently. Implementations often leverage queues or circular linked lists to simulate the counting-out procedure, achieving O(n time complexity for generating the full elimination order, where n is the number of participants. This approach is particularly useful for understanding resource allocation in systems where elements are processed in a cycle until depleted, such as in certain task elimination scenarios within operating systems.^[17] The recursive formulation provides a basis for these implementations, enabling straightforward adaptation to iterative methods for practical computation.^[16] In cryptography, the Josephus permutation is applied to generate pseudorandom rearrangements, enhancing security in encryption algorithms. For instance, it is integrated with chaotic maps to shuffle image pixels, ensuring high diffusion and resistance to statistical attacks by producing non-linear permutations that obscure pixel dependencies. This technique has been shown to improve avalanche effects in encrypted images, making it suitable for secure data transmission.^[26] Similar uses appear in constructing strong S-boxes for block ciphers, where the permutation's properties aid in achieving balanced substitution tables resistant to differential cryptanalysis.^[27] The problem is a common fixture in programming interviews, testing candidates' proficiency with dynamic data structures and optimization. A typical challenge involves simulating the elimination process using a singly linked list to model the circle, removing nodes in O(1) per elimination after initial setup, resulting in overall O(n performance. Platforms like LeetCode feature variants, such as finding the winner in a circular game, to evaluate problem-solving under constraints. This relevance stems from its illustration of real-world circular traversals, like in network routing or buffer management. Modern extensions link the Josephus problem to combinatorial game theory and sequence generation. In game theory, it relates to impartial games like Maximum Nim, where elimination rules mirror heap reductions, leading to new O(k log n) algorithms for general k.^[28] These connections enable simulations of strategic decision-making in multi-player scenarios, such as resource contention games. Additionally, the binary variant (k=2) ties into de Bruijn sequences through cyclic binary representations, aiding in applications like DNA sequencing and pseudorandom number generation.^[29]

References

[1]
[PDF] Analytical Study and Efficient Evaluation of the Josephus Function
Oct 20, 2023 · The Josephus problem is a game of elimination that has been studied for nearly two millennia. The earliest known formulation of the problem ...
[2]
Josephus Problem -- from Wolfram MathWorld
Given a group of n men arranged in a circle under the edict that every mth man will be executed going around the circle until only one remains, ...
[3]
https://eulerarchive.maa.org/pages/E476.html
[4]
[PDF] Journal of Problem Solving Algorithmic Puzzles - Purdue e-Pubs
The Josephus Problem, named after the famous historian of the first century Flavius Josephus, provides an excellent example of puzzles that ask to find an ...
[5]
[PDF] A Comparative Study on the Algorithms for a Generalized Josephus ...
Jul 1, 2013 · The classic Josephus problem is defined as follows. Suppose that n objects, consecutively numbered from 1 through n, are arranged in a circle ...
[6]
[PDF] Analytical Study and Efficient Evaluation of the Josephus Function
1.1 Notation and definitions. The mathematical formulation of the classical Josephus problem can be stated as follows: Let n be the number of people arranged ...
[7]
None
### Summary of Parameters and Variations in Josephus Problem (https://web.pdx.edu/~caughman/501%20Zhao.pdf)
[8]
[PDF] The Josephus Problem
The Josephus problem in its original form goes back to the Roman historian Flavius. Josephus (see [3]). In the Romano-Jewish conflict of 67 A. D., the Romans ...
[9]
The Josephus Problem: Once More around - jstor
in a counterclockwise direction. Even so, a child from the first marriage is eventually chosen. Some version of the mathematical Josephus problem dates back ...
[10]
[PDF] The Josephus problem - Numdam
upon the mentioned bounds. 1. Introduction. The Josephus problem in its original form goes back to the Roman historian. Flavius Josephus (see [3]). In the ...
[11]
https://byustudies.byu.edu/article/suicide-at-masada-and-in-the-world-of-the-new-testament/
[12]
Observationes circa novum et singulare progressionum genus
Sep 25, 2018 · According to Eneström, this paper is about the Josephus problem. Published as. Journal article. Published Date. 1776. Written Date. 1771 ...
[13]
ON THE GENERALIZED JOSEPHUS PROBLEM - Project Euclid
Here we survey the leading traits of solutions by H. Schubert and by E. Busche of the generalized Josephus problem (cf. [2]). Let $n$ and $ ...
[14]
[PDF] Mathematical Recreations and Essays - Project Gutenberg
Oct 5, 2015 · The Project Gutenberg eBook of Mathematical Recreations and Essays, by W. W. Rouse Ball ... 1892. Reprinted, May, 1892. Second Edition ...
[15]
[PDF] Recurrence Relations and Their Solutions (Josephus Problem)
The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only k − 1 persons remain, who are ...
[16]
Josephus problem - Algorithms for Competitive Programming
Sep 24, 2023 · We are given the natural numbers and . All natural numbers from to are written in a circle. First, count the -th number starting from the first one and delete ...Missing: nk definition
[17]
Josephus Problem - GeeksforGeeks
Jul 23, 2025 · The simple approach is to create a list and add all values from 1 to N to it. Create a recursive function that takes a list, start (position at which counting ...Missing: nk | Show results with:nk
[18]
A054995 - OEIS
### Summary of A054995 (OEIS)
[19]
https://oeis.org/A054995
[20]
[PDF] The Survivor Problem - Computer Science | UC Davis Engineering
Oct 15, 2024 · As an example, let's compute J(5). We place people 1, 2, 3, 4, 5 around the circle. We then skip 1, remove 2, skip 3, remove ...
[21]
1.3 Bags, Queues, and Stacks - Algorithms, 4th Edition
Feb 13, 2020 · Write a Queue client Josephus. java that takes M and N from the command line and prints out the order in which people are eliminated (and thus ...
[22]
[PDF] Interesting Variants of the Josephus Problem.
In this variant of the Josephus Problem two persons are to be eliminated at the same time, but the two processes of elimination go in different directions.
[23]
https://arxiv.org/pdf/1803.11340.pdf
[24]
[PDF] An Image Encryption Algorithm Based on Hyperchaotic System and ...
Oct 21, 2020 · In this paper, an image encryption algorithm based on a hyperchaotic system and variable-step Josephus problem is proposed. Based on an in-depth ...
[25]
An image encryption scheme based on double chaotic cyclic shift ...
In this paper, a novel image encryption algorithm is proposed by combining chaotic map with Josephus problem. The whole encryption process adopts the classical ...
[26]
Strong s-box construction approach based on Josephus problem
Jul 10, 2024 · In this study, Josephus circle logic is used to solve this problem. Initially, with a random s-box structure, the elements are replaced according to their ...
[27]
[PDF] g5 integers 24 (2024) maximum nim and the josephus problem
Dec 9, 2024 · We prove that there is a simple relation between a Maximum Nim with the rule function f and the Josephus problem, in which every k-th number is ...
[28]
[PDF] arXiv:0811.0290v5 [math.NT] 2 Dec 2008
Dec 2, 2008 · In the case of r = 2, the sequence also was studied by N. G. de Bruijn [3] in connection with the representations of positive integers by ...