ヨセフスの問題
b m b 0 {\displaystyle f(n)=b_{1}b_{2}b_{3}\dots b_{m}b_{0}} となる。これの証明は n {\displaystyle n} を 2 m + l {\displaystyle 2^{m}+l} と表現する方法を使って得られる。
k を限定しない問題の最も簡単な解法は、動的計画法を使ったものである。次のような漸化式を用いる。
f ( n , k ) = ( f ( n − 1 , k ) + k ) mod n {\displaystyle f(n,k)=(f(n-1,k)+k){\bmod {n}}} 、 ただし f ( 1 , k ) = 0 {\displaystyle f(1,k)=0}
これは、 n − 1 {\displaystyle n-1} から n {\displaystyle n} に増やしたときに生存者の番号がどう変化するかを考えれば明らかである。この手法の計算量は O ( n ) {\displaystyle O(n)} だが、 k {\displaystyle k} が小さく n {\displaystyle n} が大きい場合にはもっと効率的な手法がある。それは、最初のステップで k番目、2k番目、...、 ⌊ n / k ⌋ {\displaystyle \lfloor n/k\rfloor } 番目の人を処刑し、番号付けを変更するというもので、 O ( k log  n ) {\displaystyle O(k\log n)} になる。