Последовательность без простых чисел (Hkvly;kfgmyl,ukvm, Qy[ hjkvmd] cnvyl)

Перейти к навигации Перейти к поиску

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

.

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

[править | править код]

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

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

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

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

[править | править код]

Требование, чтобы начальные члены последовательности были взаимно простыми, необходимо для нетривиальности последовательности. Если мы позволим, чтобы два начальных члена делились на некоторое простое число p (например, положив и для некоторых x и y, больших 1), очевидно, что и все последующие члены последовательности будут делиться на p. В этом случае, конечно, все члены последовательности будут составными числами, но по тривиальной причине.

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

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

[править | править код]

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

a1 = 331635635998274737472200656430763, a2 = 1510028911088401971189590305498785 (Последовательность A083104 в OEIS; Грэм, 1964)
a1 = 62638280004239857, a2 = 49463435743205655 (Последовательность A083105 в OEIS; Кнут, 1990)
a1 = 407389224418, a2 = 76343678551 (Последовательность A082411 в OEIS; Николь, 1999)

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

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

Примечания

[править | править код]

Литература

[править | править код]
  • Ronald L. Graham. A Fibonacci-like sequence of composite numbers // Mathematics Magazine. — 1964. — Т. 37, вып. 5. — С. 322–324. — doi:10.2307/2689243. — JSTOR 2689243. (недоступная ссылка)
  • Donald E. Knuth. A Fibonacci-like sequence of composite numbers // Mathematics Magazine. — 1990. — Т. 63, вып. 1. — С. 21–25. — doi:10.2307/2691504. — JSTOR 2691504.
  • Herbert S. Wilf. Letters to the Editor // Mathematics Magazine. — 1990. — Т. 63. — С. 284.
  • John W. Nicol. A Fibonacci-like sequence of composite numbers // Electronic Journal of Combinatorics. — 1999. — Т. 6, вып. 1. — С. 44.
  • M.Vsemirnov. A new Fibonacci-like sequence of composite numbers // Journal of Integer Sequences. — 2004. — Т. 7, вып. 3. — С. 04.3.7. (Всемирнов Максим Александрович)