Josephus problem

Josephus problem is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Josephus problem is a math puzzle with a grim description: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} prisoners are standing on a circle, sequentially numbered from Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0} to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-1} . An executioner walks along the circle, starting from prisoner Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0} , removing every Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} -th prisoner and killing him. As the process goes on, the circle becomes smaller and smaller, until only one prisoner remains, who is then freed. For example, if there are Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=5} prisoners and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k=2} , the order the prisoners are killed in (let's call it the "killing sequence") will be 1, 3, 0, and 4, and the survivor will be #2.

Task Given any Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n, k > 0} , find out which prisoner will be the final survivor. In one such incident, there were 41 prisoners and every 3rd prisoner was being killed (Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k=3} ). Among them was a clever chap name Josephus who worked out the problem, stood at the surviving position, and lived on to tell the tale. Which number was he?

Extra The captors may be especially kind and let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} survivors free, and Josephus might just have $m-1$ friends to save. Provide a way to calculate which prisoner is at any given position on the killing sequence.

Notes

1. You can always play the executioner and follow the procedure exactly as described, walking around the circle, counting (and cutting off) heads along the way. This would yield the complete killing sequence and answer the above questions, with a complexity of probably $O(kn)$. However, individually it takes no more than $O(m)$ to find out which prisoner is the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} -th to die.
2. If it's more convenient, you can number prisoners from Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1} to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} instead. If you choose to do so, please state it clearly.
3. An alternative description has the people committing assisted suicide instead of being executed, and the last person simply walks away. These details are not relevant, at least not mathematically.

Perl

Translation of: Perl6

<lang Perl>sub Josephus {

   my ($n, $k) = @_;
   my @prisoner = 0 .. $n-1;
   until (@prisoner == 1) {

push @prisoner, shift @prisoner for 1 .. $k-1; printf "Prisoner %2d was killed.\n", shift @prisoner;

   }
   printf "Prisoner %2d survived.\n", pop @prisoner;

}

Josephus 41, 3;</lang>

Output is the same as the Perl6 solution.

Perl 6

Naïve, straightforward implementation of the killing algorithm: <lang Perl6>sub Josephus($n, $k) {

   my @prisoner = ^$n;
   until @prisoner == 1 {

@prisoner.=rotate($k - 1); printf "Prisoner %2d was killed.\n", @prisoner.shift;

   }
   printf "Prisoner %2d survived.\n", @prisoner.pop;

}

Josephus(41, 3);</lang>

Output:

Prisoner  2 was killed.
Prisoner  5 was killed.
Prisoner  8 was killed.
Prisoner 11 was killed.
Prisoner 14 was killed.
Prisoner 17 was killed.
Prisoner 20 was killed.
Prisoner 23 was killed.
Prisoner 26 was killed.
Prisoner 29 was killed.
Prisoner 32 was killed.
Prisoner 35 was killed.
Prisoner 38 was killed.
Prisoner  0 was killed.
Prisoner  4 was killed.
Prisoner  9 was killed.
Prisoner 13 was killed.
Prisoner 18 was killed.
Prisoner 22 was killed.
Prisoner 27 was killed.
Prisoner 31 was killed.
Prisoner 36 was killed.
Prisoner 40 was killed.
Prisoner  6 was killed.
Prisoner 12 was killed.
Prisoner 19 was killed.
Prisoner 25 was killed.
Prisoner 33 was killed.
Prisoner 39 was killed.
Prisoner  7 was killed.
Prisoner 16 was killed.
Prisoner 28 was killed.
Prisoner 37 was killed.
Prisoner 10 was killed.
Prisoner 24 was killed.
Prisoner  1 was killed.
Prisoner 21 was killed.
Prisoner  3 was killed.
Prisoner 34 was killed.
Prisoner 15 was killed.
Prisoner 30 survived.

Python

<lang python>>>> def j(n, k): p, i, seq = list(range(n)), 0, [] while p: i = (i+k-1) % len(p) seq.append(p.pop(i)) return 'Prisoner killing order: %s.\nSurvivor: %i' % (', '.join(str(i) for i in seq[:-1]), seq[-1])

>>> print(j(5, 2)) Prisoner killing order: 1, 3, 0, 4. Survivor: 2 >>> print(j(41, 3)) Prisoner killing order: 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 0, 4, 9, 13, 18, 22, 27, 31, 36, 40, 6, 12, 19, 25, 33, 39, 7, 16, 28, 37, 10, 24, 1, 21, 3, 34, 15. Survivor: 30 >>> </lang>