Покрывающее множество (теория чисел)

Использование термина «покрывающее множество» связано с числами Серпинского и Ризеля. Это нечётные натуральные числа ${\displaystyle k}$, для которых ${\displaystyle k2^{n}+1}$ (число Серпинского) или ${\displaystyle k2^{n}-1}$ (число Ризеля) составные.

С 1960 года известно, что существует бесконечно много как чисел Серпинского, так и Ризеля, но поскольку имеется бесконечно много чисел вида ${\displaystyle k2^{n}+1}$ или ${\displaystyle k2^{n}-1}$ для любого ${\displaystyle k}$, то для доказательства принадлежности ${\displaystyle k}$ числам Серпинского и Ризеля необходимо проверить, что любой член последовательности ${\displaystyle k2^{n}+1}$ или ${\displaystyle k2^{n}-1}$ делится на простые числа покрывающего множества.

Эти покрывающие множества формируются из простых чисел, которые в двоичном представлении имеют короткий период. Можно показать, что для получения полного покрывающего множества период должен быть не менее 24 чисел.^{[прояснить]} Период длиной 24 даёт покрывающее множество ${\displaystyle \{\,3,5,7,13,17,241\,\}}$, а период длины 36 дает покрывающие множества: ${\displaystyle \{\,3,5,7,13,19,37,73,\}}$; ${\displaystyle \{\,3,5,7,13,19,37,109\,\}}$; ${\displaystyle \{\,3,5,7,13,19,73,109\,\}}$ и ${\displaystyle \{\,3,5,7,13,37,73,109\,\}}$. Числа Ризеля имеют те же покрывающие множества, что и числа Серпинского.

Покрывающие множества применяются также для доказательства существования составных последовательностей Фибоначчи (свободная от простых последовательность).

Концепцию покрывающих множеств легко обобщить на другие последовательности. В следующих примерах + используется так же, как в регулярных выражениях – означает 1 и больше. Например 91⁺3 означает множество {913, 9113, 91113, 911113…}

В качестве примера можно привести последовательность:

• ${\displaystyle (82\cdot 10^{n}+17)/9}$ или ${\displaystyle 91^{+}3}$
• ${\displaystyle (85\cdot 10^{n}+41)/9}$ или ${\displaystyle 94^{+}9}$
• ${\displaystyle (86\cdot 10^{n}+31)/9}$ или ${\displaystyle 95^{+}9}$

В каждом случае, каждый член делится на одно из простых чисел {3,7,11,13}. Эти простые формируют покрывающее множество в точности как для чисел Серпинского и Ризеля.

Ещё более простой случай — такая последовательность:

• ${\displaystyle (76\cdot 10^{n}-67)/99}$ (n должен быть нечетным) или ${\displaystyle (76)^{+}7}$ [Последовательность: 7, 767, 76767, 7676767, 767676767 и т.д.]

Можно показать, что:

• Если ${\displaystyle n=6k+1}$, то ${\displaystyle (76)^{+}7}$ (с соответствующим количеством повторений) делится на 7.
• Если ${\displaystyle n=6k+3}$, то ${\displaystyle (76)^{+}7}$ делится на 13.
• Если ${\displaystyle n=6k+5}$, то ${\displaystyle (76)^{+}7}$ делится на 3.

Таким образом, мы имеем покрывающее множество всего из трех простых чисел {3,7,13}. Это стало возможным только потому, что мы наложили условие, что n должен быть нечетным.

Покрывающее множество также обнаруживается в последовательности:

• ${\displaystyle (343\cdot 10^{n}-1)/9}$ или ${\displaystyle 381^{+}}$.

Можно показать, что:

• Если ${\displaystyle n=3^{k}+1}$, то ${\displaystyle (343\cdot 10^{n}-1)/9}$ делится на 3.
• Если ${\displaystyle n=3^{k}+2}$, то ${\displaystyle (343\cdot 10^{n}-1)/9}$ делится на 3.
• Если ${\displaystyle n=3^{k}}$, то ${\displaystyle (343\cdot 10^{n}-1)/9}$ разлагается на ${\displaystyle ((7\cdot 10^{k}-1)/3)\cdot ((49\cdot 10^{2}k+7\cdot 10^{k}+1)/3)}$.

Поскольку ${\displaystyle (7\cdot 10^{k}-1)/3}$ можно записать как ${\displaystyle 23^{+}}$, для последовательности ${\displaystyle 381^{+}}$ мы имеем покрывающее множество ${\displaystyle \{\,3,37,23^{+}\,\}}$ — покрывающее множество с бесконечным числом членов.

• Plateau and Depression Primes
• Sierpinski-like numbers
• Yves Gallot, A search for some small brier numbers
• Louis Helm lhelm. Phil Moore, Payam Samidoost, George Woltman. Resolution of the mixed Sierpiński problem, INTEGERS: Electronic journal of combinatorial number theory 8 (2008), #A61