Последовательность Primefree

В математике последовательность без простых чисел — это последовательность целых чисел , которая не содержит простых чисел . Более конкретно, это обычно означает последовательность, определяемую тем же рекуррентным соотношением, что и числа Фибоначчи , но с разными начальными условиями, в результате чего все члены последовательности являются составными числами , которые не все имеют общий делитель . Выражаясь алгебраически, последовательность этого типа определяется соответствующим выбором двух составных чисел a ₁ и a ₂ , таких, что наибольший общий делитель $\mathrm {gcd} (a_{1},a_{2})$ равен 1 и такой, что для $n>2$ в последовательности чисел, рассчитанной по формуле, нет простых чисел

a_{n}=a_{n-1}+a_{n-2}

.

Первая последовательность этого типа без праймов была опубликована Рональдом Грэмом в 1964 году.

Последовательность Уилфа [ править ]

Последовательность без простых чисел, найденная Гербертом Уилфом, имеет начальные члены

a_{1}=20615674205555510,a_{2}=3794765361567513

(последовательность A083216 в OEIS )

Доказательство того , что каждый член этой последовательности является составным, основано на периодичности числовых последовательностей типа Фибоначчи по модулю членов конечного набора простых чисел. Для каждого простого числа $p$ , позиции в последовательности, где числа делятся на $p$ повторяются по периодическому шаблону, и разные простые числа в наборе имеют перекрывающиеся шаблоны, в результате чего образуется покрывающий набор для всей последовательности.

Нетривиальность [ править ]

Требование, чтобы начальные члены последовательности без простых чисел были взаимно простыми, необходимо для того, чтобы вопрос был нетривиальным. Если первоначальные члены имеют общий простой делитель $p$ (например, установить $a_{1}=xp$ и $a_{2}=yp$ для некоторых $x$ и $y$ оба больше 1) из-за свойства умножения распределительного $a_{3}=(x+y)p$ и, в более общем смысле, все последующие значения в последовательности будут кратны $p$ . В этом случае все числа в последовательности будут составными, но по тривиальной причине.

Порядок начальных членов также важен. В Хоффмана биографии Пола Эрдёша Пола « Человек, который любил только числа» цитируется последовательность Уилфа, но с заменой начальных терминов. Полученная последовательность кажется свободной от простых чисел примерно в первых сотнях членов, но член 138 представляет собой 45-значное простое число. $439351292910452432574786963588089477522344721$ . ^[1]