Линейное изменение головоломки Иосифа
Итак, вот проблема Иосифа на вики. Проблема, которая у меня есть, - это линейная вариация, но для ясности я переформулирую всю проблему.
(Числа = натуральные числа)
Существует процесс, который устраняет числа следующим образом:
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?
2 ответа
Вопрос не проясняет, что именно происходит с числом в позиции 0. В примере на шаге 1 число 1 (в позиции 0) исключается. Но затем на шаге 2 число 2 (в позиции 0) выживает.
Для целей этого ответа я предполагаю, что пример ошибочен, а число в позиции 0 всегда сохраняется. Так что пример должен выглядеть так:
Начальная позиция
Number 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ... Position 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ...После шага 1:
Number 1 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 ... Position 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ...После шага 2:
Number 1 2 4 8 10 14 16 20 22 26 28 32 34 38 40 44 46 ... Position 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, ..., которая не найдена в OEIS (но см. Приложение ниже).
Вот как вы можете определить, выживет ли конкретное число K, не вычисляя всю последовательность:
Пусть J₁ = K - 1 (начальная позиция K).
- K исключается на шаге 1, если J₁>0 и 2|J₁, но если нет, то его новый индекс J₂ = J₁ - ⌊J₁ / 2⌋
- K удаляется на шаге 2, если J₂>0 и 3|J₂, но если нет, то его новый индекс J₃ = J₂ - ⌊J₂/3⌋
- и так далее, пока либо K не будет устранено, либо пока Ji
ДОПОЛНЕНИЕ
Я немного поспешил, когда пришел к выводу, что этой последовательности нет в OEIS. Предположим, что мы пронумеровали позиции, начинающиеся с 1, а не с 0. Затем мы получили бы последовательность 1, 3, 7, 13, 19, 27, 39, ..., которая является последовательностью OEIS A000960, "Сито Флавиуса Иосифа". Тем не менее, пока нет решения в закрытой форме.
Одним из решений является отслеживание индекса K в списке на каждой итерации.
На каждом шаге мы сначала проверяем, делится ли индекс K на. Если это так, мы возвращаем false. В противном случае мы просто вычитаем количество элементов перед K, которые делятся на i, из индекса K (т.е. K смещается так много раз влево).
Мы продолжаем делать это, пока не останется только один элемент.