Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 JosephusPermutation

Source Notebook

Find the solution of the Josephus problem

Contributed by: Wolfram Staff (original content by Sriram V. Pemmaraju and Steven S. Skiena)

ResourceFunction["JosephusPermutation"][n,m]

generates the inverse of the permutation defined by executing every mth member in a circle of n members.

Details and Options

In ResourceFunction["JosephusPermutation"], the number at a given position is the order in which the member at that position is executed.
The position of the highest value is the position of the last survivor.

Examples

Basic Examples (2) 

In a circle of four men in which every second man is iteratively slaughtered, the second man is executed first, the fourth man second, then the third man, and the first man last:

In[1]:=
ResourceFunction["JosephusPermutation"][4, 2]
Out[1]=

The ordered list of men consecutively slaughtered:

In[2]:=
InversePermutation[%]
Out[2]=

Properties and Relations (2) 

For n members, the position of the last survivor is the position of the value n:

In[3]:=
n = 41;
In[4]:=
perm = ResourceFunction["JosephusPermutation"][n, 3]
Out[4]=
In[5]:=
Position[perm, n]
Out[5]=

The position of the second-to-last survivor:

In[6]:=
Position[perm, n - 1]
Out[6]=

Version History

  • 1.0.0 – 05 March 2020

Related Resources

License Information