Josephus难题的线性变分

Question

这是维基上的Josephus problem。我遇到的问题是这个问题的线性变化，但为了清楚起见，我将重申整个问题。

(数字=自然数)

有一个通过以下方式消除数字的过程：

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是safe，因为这个过程将选择越来越高的值进行消除。

那么，在给定K的情况下，如何确定K是否为safe？

Answer 1

这个问题并没有确切地说明位置0的数字会发生什么。在该示例中，在步骤1中，数字1(位置0)被消除。但是在步骤2，数字2(在位置0)存活下来。

为了这个答案的目的，我将假设这个例子是错误的，位置0的数字总是存在的。因此，示例应如下所示：

初始位置

号码1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ...位置0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ...

在第1步之后：

号码1 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 ...位置0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ...

在第2步之后：

号码1 2 4 8 10 14 16 20 22 26 28 32 34 38 40 44 46 ...位置0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ...

这导致序列1，2，4，8，14，20，28，40，...这是not found in OEIS (但请参阅下面的附录)。

下面是你如何在不计算整个序列的情况下确定一个特定的数字K是否存在：

设J₁=K−1(K的初始位置)。

• K在第一步如果J₁>0和2|J

被消去，但如果不是，它的新索引是J₁= J₂=J₁−⌊J₁/2⌋i+1 K在第二步如果J₂>0和3|J₁被消去，但如果不是，它的新索引是J⌋J₂=J₂−⌊J₂/3⌋₁

• ，依此类推，直到K被消去，或者直到我们知道K还存在的时候，直到Ji

附录

当我得出这个序列不在OEIS中的结论时，我有点草率。假设我们从1而不是0开始对位置进行编号。然后我们得到序列1，3，7，13，19，27，39，...这是OEIS sequence A000960，“弗拉维乌斯·约瑟夫的筛子”。然而，仍然没有封闭形式的解决方案。

Answer 2

一种解决方案是在每次迭代时跟踪列表中K的索引。

在每一步中，我们首先检查K的索引是否可被整除。如果是，我们返回false。否则，我们简单地从K的索引中减去K之前可被i整除的元素的数量(即K向左移位那么多次)。

我们继续这样做，直到只剩下一个元素。