Решето Иосифа Флавия

[kthxbye]

По аналогии с решетом Эратосфена существует решето Иосифа Флавия. Условия следующие:

Цитата:

Start with the natural numbers; at the k-th sieving step, remove every (k+1)-st term of the sequence remaining after the (k-1)-st sieving step; iterate.

Начните с натуральных чисел; на $k$-м шаге просеивания удалите каждый $(k+1)$-й член последовательности, оставшийся после $(k-1)$-го шага просеивания; повторите.

Вот как это работает:

$$[1], (2), 3, (4), 5, (6), 7, (8), 9, (10), 11, (12), 13, (14), 15, (16), 17, (18), 19, (20)$$

$$[1], [3], (5), 7, 9, (11), 13, 15, (17), 19, 21, (23), 25, 27, (29), 31, 33, (35)$$

$$[1], [3], [7], (9), 13, 15, 19, (21), 25, 27, 31, (33), 37, 39, 43, (45)$$

$$[1], [3], [7], [13], (15), 19, 25, 27, 31, (37), 39, 43, 49, 51, (55)$$

$$[1], [3], [7], [13], [19], (25), 27, 31, 39, 43, 49, (51)$$

Результирующая последовательность $a(n)$ (A000960) начинается так:

$$1, 3, 7, 13, 19, 27, 39, 49, 63, 79, 91, 109, 133, 147, 181, 207, 223, 253, 289, 307, 349, 387, 399$$

В отличии от простых чисел здесь существует относительно простая закономерность, которая позволяет за $n-1$ итераций превращать $n$ в $a(n)$:

Цитата:

(PARI) a(n)=local(A=n, D); for(i=1, n-1, D=n-i; A=D*ceil(A/D+1)); return(A) \\ Paul D. Hanna, Oct 10 2005

Пусть задана последовательность $b(n)$ (A278528) - номер шага просеивания, на котором $n$ выбывает при применении решета Иосифа Флавия. Если же $n$ остается, то $b(n)=0$.

Пусть задано относительно большое число $m$. Известно, что оно гарантированно выбывает при просеивании. Известно также, что $n<k$, где $n$ это номер шага просеивания, на котором выбывает $m$, а $k$ это некоторое число, удовлетворяющее условиям неравенства.

Определите $n$ вычисляя максимум $2k$ различных значений.

[kthxbye]

Подсказка: начните с $m$ и $m-1$, используйте остаток от деления и ищите равенство.

[kthxbye]

Если в одном месте поменять знак и использовать модуль, то условие

kthxbye в сообщении #1549540 писал(а):

Известно, что оно гарантированно выбывает при просеивании.

можно опустить. Т.е. у нас все так же заданы $m$ и $k$, требуется отыскать $n$ и дополнительно указать, выбывает число при просеивании или же остается.

Если совсем нет никаких идей, но хочется хоть как-нибудь приблизиться к решению, можете заглянуть на страничку A082447.

[kthxbye]

Сохраняем условие

kthxbye в сообщении #1549895 писал(а):

Т.е. у нас все так же заданы $m$ и $k$, требуется отыскать $n$ и дополнительно указать, выбывает число при просеивании или же остается.

где под $n$ для случая когда число остается подразумевается его номер в последовательности $a(n)$.

В условии

kthxbye в сообщении #1549540 писал(а):

Определите $n$ вычисляя максимум $2k$ различных значений.

заменяем $2k$ на $k$.

Тогда предыдущая задача не актуальна, ввиду чего привожу ее решение:

f(m)=local(A=m, B=m-1, C, q=0); until(A==B, q=q+1; C=A-B; A=abs(A-q-A%q); B=abs(B-q-B%q)); C

Т.е. у нас имеется функция

$$g(n,m)=|g(n-1,m)-n-(g(n-1,m)\bmod n)|, g(0,m)=m$$

и мы ищем наименьшее $n$, такое, что $g(n,m)=g(n,m-1)$. Тогда разность предыдущих значений $g(n-1,m)-g(n-1,m-1)$ равна $f(m)$. Если число выбывает при просеивании, функция возвращает номер шага просеивания на котором это происходит; если же число остается, она возвращает его номер в последовательности $a(n)$ с отрицательным знаком.