约瑟夫环

约瑟夫问题是一个经典的算法问题.

人们围成一圈, 从圆圈中的指定位置开始计数, 并沿指定方向绕圆圈进行. 在跳过指定数量的人之后, 处刑下一个人. 对剩下的人重复该过程, 从下一个人开始, 继续朝同一方向跳过相同数量的人, 直到只剩下一个人, 并被释放.

那么问题来了, 给定人数、起点、方向和要跳过的数字, 选择初始圆圈中的哪个位置可以避免被处决呢？

这个问题是以弗拉维奥·约瑟夫命名的, 他是1世纪的一名犹太历史学家. 他在自己的日记中写道, 他和他的个战友被罗马军队包围在洞中. 他们讨论是自杀还是被俘, 最终决定自杀.

自杀方式是个人围成一个圆圈, 由第个人开始报数, 每报数到第人该人就必须自杀, 然后再由下一个重新报数, 直到所有人都自杀身亡为止. 然而约瑟夫和他的朋友并不想死. 由于这个过程沿着圆圈一直进行, 直到最终只剩下一个人, 这个人就可以继续活着. 于是约瑟夫要他的朋友先假装遵从, 他将朋友与自己安排在第个与第个位置, 于是逃过了这场死亡游戏.

这个问题有很多种解决的办法, 但是大多数情况下都需要计算机的帮助. 那有没有一种情况我们可以直接口算呢？ 有.

当报数到第二个人就得自杀, 并且总人数是时, 活下来的肯定是第一个人.

以人为例：

可以看出每一轮结束后总人数减半, 仍然是, 因此号活到了最后.

那么按照这个游戏规则当人数为人时, 站在哪里会生存下来呢？