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

В математике покрывающим множеством для последовательности целых чисел называется множество простых чисел, таких, что каждый член последовательности делится по меньшей мере на одно число множества. Термин «покрывающее множество» используется только для экспоненциально растущих последовательностей.

Числа Серпинского и Ризеля

Использование термина «покрывающее множество» связано с числами Серпинского и Ризеля. Это нечётные натуральные числа ${\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 Архивная копия от 26 июля 2013 на Wayback Machine
• Sierpinski-like numbers Архивная копия от 17 июля 2012 на Wayback Machine
• Yves Gallot, A search for some small brier numbers Архивная копия от 9 апреля 2016 на Wayback Machine
• Louis Helm lhelm. Phil Moore, Payam Samidoost, George Woltman. Resolution of the mixed Sierpiński problem Архивная копия от 12 марта 2016 на Wayback Machine, INTEGERS: Electronic journal of combinatorial number theory 8 (2008), #A61