The Josephus problem with golden-ratio steps

In the classical Josephus problem with every second person eliminated, the survivor among n = 2^r + j people is 2j + 1. We study the counting-out game in which the i-th elimination falls on the s_i-th person counted, where s_i = floor((i+1)φ²) − floor(iφ²) ∈ {2, 3}. Thus s = 3,2,3,3,2,3,2,3,3,2,... is the Fibonacci word, and the average step is φ², where φ is the golden ratio. We prove that if F_r is the largest Fibonacci number not exceeding n and n = F_r + j, then the survivor is floor(jφ²) + 2 for j ≥ 1. The survivor of F_r people is person 1 if r is even and person 2 if r is odd. So Fibonacci numbers play exactly the role that powers of two play in the classical problem. The proof uses the relabelling argument of Graham, Knuth and Patashnik. It reduces the problem to the integer iteration N ↦ ceil(φN + θ/φ), and the orbits of this iteration are shifted Fibonacci numbers. For every irrational average step α in (2, 3), the same reduction holds with φ replaced by α/(α−1). We also state computer-supported conjectures for the steps φ and 1 + 1/√2, where Fibonacci and Pell numbers appear. The record includes code for the computer verification (all n ≤ 60000) and the LaTeX source.