Покрывающее множество

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

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


 Использование термина «покрывающее множество» связано с числами Серпинского и Ризеля. Это нечётные натуральные числа k, для которых k2n+1 (число Серпинского) или k2n1 (число Ризеля) составные.
 С 1960 года известно, что существует бесконечно много как чисел Серпинского, так и Ризеля, но поскольку имеется бесконечно много чисел вида k2n+1 или k2n1 для любого k, то для доказательства принадлежности k числам Серпинского и Ризеля необходимо проверить, что любой член последовательности k2n+1 или k2n1 делится на простые числа покрывающего множества.
 Эти покрывающие множества формируются из простых чисел, которые в двоичном представлении имеют короткий период. Можно показать, что для получения полного покрывающего множества период должен быть не менее 24 чисел. Период длиной 24 даёт покрывающее множество {3,5,7,13,17,241}, а период длины 36 дает покрывающие множества: {3,5,7,13,19,37,73,}; {3,5,7,13,19,37,109}; {3,5,7,13,19,73,109} и {3,5,7,13,37,73,109}. Числа Ризеля имеют те же покрывающие множества, что и числа Серпинского.

Другие покрывающие множества


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

  • (8210n+17)/9 или 91+3
  • (8510n+41)/9 или 94+9
  • (8610n+31)/9 или 95+9

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

  • (7610n67)/99 (n должен быть нечетным) или (76)+7 [Последовательность: 7, 767, 76767, 7676767, 767676767 и т.д.]

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

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

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

  • (34310n1)/9 или 381+.

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

  • Если n=3k+1, то (34310n1)/9 делится на 3.
  • Если n=3k+2, то (34310n1)/9 делится на 3.
  • Если n=3k, то (34310n1)/9 разлагается на ((710k1)/3)((49102k+710k+1)/3).

 Поскольку (710k1)/3 можно записать как 23+, для последовательности 381+ мы имеем покрывающее множество {3,37,23+} — покрывающее множество с бесконечным числом членов.