Последовательность без простых чисел

Последовательность без простых чисел — это последовательность целых чисел, не содержащая каких-либо простых чисел. Как правило, при этом предполагается, что последовательность задана той же рекуррентной формулой, что и для чисел Фибоначчи, но с другими начальными условиями, и все члены последовательности должны быть cоставными числами, не имеющими общего для всех членов делителя. Таким образом, последовательность этих чисел определяется путём выбора двух составных чисел a₁ и a₂, для которых наибольший общий делитель НОД(a₁,a₂) = 1, и таких, что для n > 2 не имеется простых чисел в последовательности, полученной из формулы

a_n = an − 1 + an − 2.

Последовательность Вильфа

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

a₁ = 20615674205555510, a₂ = 3794765361567513 (последовательность A083216 в OEIS).

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

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

Требование, чтобы начальные члены последовательности были взаимно простыми, необходимо для нетривиальности последовательности. Если мы позволим, чтобы два начальных члена делились на некоторое простое число p (например, положив [math]\displaystyle{ a_1 = xp }[/math] и [math]\displaystyle{ a_2 = yp }[/math] для некоторых x и y, больших 1), очевидно, что [math]\displaystyle{ a_3 = (x + y)p }[/math] и все последующие члены последовательности будут делиться на p. В этом случае, конечно, все члены последовательности будут составными числами, но по тривиальной причине.

Порядок начальных значений также важен. В биографии Пала Эрдёша «Человек, любивший только числа», написанной Паулем Хоффманом, цитируется последовательность Вильфа, но с переставленными начальными значениями. Результирующая последовательность остаётся свободной от простых чисел только примерно для ста первых членов, а 138-ой член с 45 десятичными знаками 439351292910452432574786963588089477522344721 является простым (последовательность A108156 в OEIS).

Другие последовательности

Известны несколько других последовательностей без простых чисел:

a₁ = 331635635998274737472200656430763, a₂ = 1510028911088401971189590305498785 (Последовательность A083104 в OEIS; Грэм, 1964)

a₁ = 62638280004239857, a₂ = 49463435743205655 (Последовательность A083105 в OEIS; Кнут, 1990)

a₁ = 407389224418, a₂ = 76343678551 (Последовательность A082411 в OEIS; Николь, 1999)

Последовательность этого типа с минимальными начальными членами (известная на текущий момент) найдена Максимом Александровичем Всемирновым

a₁ = 106276436867, a₂ = 35256392432 (Последовательность A221286 в OEIS; Всемирнов, 2004).

Ссылки

• Problem 31. Fibonacci- all composites sequence. The prime puzzles and problems connection.
• «Primefree sequence» PlanetMath
• Weisstein, Eric W. Primefree Sequence (англ.) на сайте Wolfram MathWorld.