约瑟夫斯谜题的线性变化
这是 wiki 上的约瑟夫问题。 我遇到的问题是它的线性变化，但为了清楚起见，我将重述整个问题。
( 数字 = 自然数 )
有一个消除数字的过程，其方式如下：
i=2
while 1:
remove numbers that are *placed* at positions divisible by i
i+=1
同时给你一个数字K，你必须确认这个数字K是否会出现。生存淘汰。
例如（假设索引从 0 开始）
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 ...
0,1,2,3,4,5,6,7,8, 9,10,11,12,13,14,15 ... (indices)
After step 1 ( elimination at i=2 )
2,4,6,8,10,12,14,16 ...
0,1,2,3, 4, 5, 6, 7 ... (indices)
After step 2 (elimination at i=3 )
2,4,6,10,12,16 ... ( 8 and 14 got removed cause they were at index 3 and 6 resp. )
0,1,2, 3, 4, 5 ... (indices)
我们可以看到，在此步骤之后 2,4,6 是安全，因为该过程将选择越来越高的值进行消除。
那么，再一次，给定一个 K ，您如何确定 K 是否安全 ？
So here is the Josephus problem on wiki.
The problem that I have is a linear variation of this, but I will restate the whole problem for clarity.
( Numbers = Natural Numbers )
There is a process that is eliminating numbers in the following manner:
i=2
while 1:
remove numbers that are *placed* at positions divisible by i
i+=1
You are also given a number K, you have to confirm if this number K will survive the elimination.
E.g. ( assuming index starts at 0 )
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 ...
0,1,2,3,4,5,6,7,8, 9,10,11,12,13,14,15 ... (indices)
After step 1 ( elimination at i=2 )
2,4,6,8,10,12,14,16 ...
0,1,2,3, 4, 5, 6, 7 ... (indices)
After step 2 (elimination at i=3 )
2,4,6,10,12,16 ... ( 8 and 14 got removed cause they were at index 3 and 6 resp. )
0,1,2, 3, 4, 5 ... (indices)
As we can see 2,4,6 are safe after this step, since the process will be choosing higher and higher values for elimination.
So once again, given a K how do you determine if K will be safe ?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
一种解决方案是在每次迭代时跟踪列表中 K 的索引。
在每一步中，我们首先检查 K 的索引是否可以整除。如果是，我们返回 false。否则，我们只需从 K 的索引中减去 K 之前可被 i 整除的元素数量（即 K 向左移动多次）。
我们继续这样做，直到只剩下一个元素。
One solution is to keep track of the index of K within the list at every iteration.
At every step, we first check if the index of K is divisible by. If it is, we return false. Otherwise, we simply subtract the number of elements before K that are divisible by i from the index of K (i.e. K is shifted that many times to the left).
We continue doing this until only one element is left.
该问题并没有明确说明位置 0 处的数字会发生什么情况。在示例中，在步骤 1 中，数字 1（位置 0 处）被消除。但在第 2 步，数字 2（位置 0）幸存下来。
出于本答案的目的，我假设该示例是错误的，并且位置 0 处的数字始终保留。所以这个例子应该是这样的：
这导致序列 1, 2, 4, 8, 14, 20, 28, 40, ... ，即 在 OEIS 中找不到（但请参阅下面的附录）。
下面介绍了如何确定特定数字 K 是否存在，而无需计算整个序列：
令 J₁ = K − 1（K 的初始位置）。
附录
当我得出这个序列不在 OEIS 中的结论时，我有点仓促。假设我们从 1 而不是 0 开始对位置进行编号。然后我们会得到序列 1, 3, 7, 13, 19, 27, 39, ... ，即 OEIS 序列 A000960，“Flavius Josephus 筛”。但仍然没有封闭式的解决方案。
The question doesn't make it clear exactly what happens to the number at position 0. In the example, at step 1, the number 1 (at position 0) is eliminated. But then at step 2 the number 2 (at position 0) survives.
I'm going to assume for the purposes of this answer that the example is in error and the number at position 0 always survives. So the example should look like this:
This leads to the sequence 1, 2, 4, 8, 14, 20, 28, 40, ... which is not found in OEIS (but see addendum below).
Here's how you might determine if a particular number K survives, without computing the whole sequence:
Let J₁ = K − 1 (the initial position of K).
ADDENDUM
I was a bit hasty when I concluded that this sequence isn't in OEIS. For suppose we had numbered the positions starting at 1 instead of 0. Then we'd get the sequence 1, 3, 7, 13, 19, 27, 39, ... which is OEIS sequence A000960, "Flavius Josephus's sieve". Still no closed-form solution, though.