Is there a closed form for the Josephus Problem on a line?

Question

Consider the following variation of the famous Josephus problem:

The numbers 1 through $n$ are lined up. Each round, every $k$th number is eliminated, starting from the first one (so the numbers in positions $1$, $k+1$, $2k+1$ get eliminated, and the positions of the remaining numbers change after each elimination). Eventually, after many rounds, there will be only one number left. Which one will it be?

My progress so far: For the $k=2$ case, the answer is simply the max power of 2 in $[1, n]$. I also got the recursion $f(n)=m+\lceil \frac{m}{k-1}\rceil$, where $m=f(n-1-\lfloor \frac{n-1}{k}\rfloor)$ (though I may have screwed up somewhere here). However, I was wondering if there is a closed form solution to this variation of the Josephus problem.

Answer 1

This is a nice case study in doing experiments and using tools. I'll use the notation $f_k(n)$ to denote the value of $f(n)$ when using a particular $k$.

• Writing a program to calculate the answer reveals that $f_k(n)$ is a nondecreasing function of $n$ that consisted of blocks of the same number repeated several times. For example, $$ (f_2(n))_{n=1}^{20} = (1, 2, 2, 4, 4, 4, 4, 8, 8, 8, 8, 8, 8, 8, 8, 16, 16, 16, 16, 16) $$ while $$ (f_3(n))_{n=1}^{20} = (1, 2, 3, 3, 5, 5, 5, 8, 8, 8, 8, 12, 12, 12, 12, 12, 12, 18, 18, 18). $$ Moreover, each sequence of repetitions of the value $v$ starts when $n=v$. In other words, there seems to be some set $A_k$ of positive integers such that $f_k(n)$ is simply the largest element of $A_k$ not exceeding $n$. For example, $A_2 = \{1,2,4,8,16,\dots\}$ and $A_3 = \{1,2,3,5,8,12,18,\dots\}$.
• Copy-pasting these sequences into the Online Encyclopedia of Integer Sequences revealed some matches. For example, when $k=3$, the sequence matches sequence A061419, which is given by the recursive $a_1 = 1$ and $a_m = \lceil \frac32 a_{m-1} \rceil$. When $k=4$, the sequence matches sequence A087192, which is given by the recursive $a_1 = 1$ and $a_m = \lceil \frac43 a_{m-1} \rceil$.
• These emperical observations suggest that $A_k$ is always equal to the sequence $(a_{k,m})_{m=1}^\infty$ where $a_{k,1}=1$ and $a_{k,m} = \lceil \frac m{m-1} a_{k,m-1} \rceil$. (In other words, $f_k(n)$ is the largest $a_{k,m}$ not exceeding $n$.) And we check that this recursion does appropriately yield the powers of $2$ in the case $k=2$.

I think this is a provable formula, and indeed the form of the recursions does seem very closely related to the original definition. Even more importantly, it's far easier to prove (or disprove) a specific formula than it is to try to guess or justify an answer out of the blue.

Morals of the story: always do some examples! Look for patterns! Use existing tools like OEIS!