约瑟夫环：围成一圈，数到几就出局

题目

$n$ 个人围成一圈，编号 1 到 $n$。从 1 号开始，每数到 2 的人出局（杀 2、4、6……绕圈继续），剩下的人重新接续计数。最后活下来的那个人，原位号是多少？

例如 $n=7$：出局顺序 2,4,6,1,5,3，幸存者是 7 号。

答案与解析

当 $k=2$ 时，幸存位置有漂亮公式。把 $n$ 写成 $n = 2^m + L$（$0\le L<2^m$），则 $J(n) = 2L + 1$

例如 $n=7=4+3$，则 $J=2\times3+1=7$； $n=41=32+9$，则 $J=2\times9+1=19$。

推导思路（递推）：设 $f(n)$ 为 $n$ 人时幸存者（从 1 起）。第一圈杀掉所有偶数，剩下奇数 $1,3,5,\dots$，重新编号后等价于 $n/2$ 人的子问题，再映射回去，得到 $f(2m)=2f(m)-1,\ f(2m+1)=2f(m)+1$。配合二进制：$J(n)$ 就是把 $n$ 的二进制首位 1 移到末尾。

背后的数学

这是公元 1 世纪犹太历史学家约瑟夫斯记载的约瑟夫问题（Josephus Problem）。推广到任意步长 $k$ 用递推 $J(n,k)=(J(n-1,k)+k)\bmod n$（从 $J(1,k)=0$ 起）。它是最早把“圈”与“递推”结合的经典，也是模运算与循环Buffer的雏形。