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

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

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


 Использование термина «покрывающее множество» связано с числамиСерпинского и Ризеля. Это нечётные натуральные числа 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\textsuperscript+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+} — покрывающее множество с бесконечным числомчленов.