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

'''Последовательность без простых чисел''' — это [[последовательность]] [[Целое число|целых чисел]], не содержащая каких-либо [[Простое число|простых чисел]]. Как правило, при этом предполагается, что последовательность задана той же [[Рекуррентная формула|рекуррентной формулой]], что и для [[Числа Фибоначчи|чисел Фибоначчи]], но с другими [[Начальные условия|начальными условиями]], и все члены последовательности должны быть [[Составное число|cоставными числами]], не имеющими общего для всех членов [[Делимость|делителя]]. Таким образом, последовательность этих чисел определяется путём выбора двух составных чисел ''a''<sub>1</sub> и ''a''<sub>2</sub>, для которых [[наибольший общий делитель]] НОД(''a''<sub>1</sub>,''a''<sub>2</sub>)&nbsp;=&nbsp;1, и таких, что для ''n''&nbsp;&gt;&nbsp;2 не имеется простых чисел в последовательности, полученной из формулы
: ''<math>a_n = a_{n-1}+a_{n-2}</math>.''

== После''<sub>''дователь''</sub>''ность Вильфа ==
Наверное, наиболее известная последовательность без простых чисел была найдена {{не переведено 5|Вильф, Герберт|Гербертом Вильфом||Herbert Wilf}} с начальными членами

: ''a''<sub>1</sub> = 20615674205555510, ''a''<sub>2</sub> = 3794765361567513 ({{OEIS|id=A083216}}).

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

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

Порядок начальных значений также важен. В биографии [[Эрдёш, Пал|Пала Эрдёша]] «''{{не переведено 5|Человек, любивший только числа|||The man who loved only numbers}}''», написанной {{не переведено 5|Хоффман, Пауль|Паулем Хоффманом||Paul Hoffman (science writer)}}, цитируется последовательность Вильфа, но с переставленными начальными значениями. Результирующая последовательность остаётся свободной от простых чисел только примерно для ста первых членов, а 138-й член с 45 десятичными знаками  439351292910452432574786963588089477522344721 является простым ({{OEIS|id= A108156}}).

== Другие последовательности ==
Известны несколько других последовательностей без простых чисел:
: ''a''<sub>1</sub> = 331635635998274737472200656430763, ''a''<sub>2</sub> = 1510028911088401971189590305498785 (Последовательность [[OEIS:A083104|A083104]] в [[Энциклопедия целочисленных последовательностей|OEIS]]; Грэм, 1964)
: ''a''<sub>1</sub> = 62638280004239857, ''a''<sub>2</sub> = 49463435743205655 (Последовательность [[OEIS:A083105|A083105]] в OEIS; Кнут, 1990)
: ''a''<sub>1</sub> = 407389224418, ''a''<sub>2</sub> = 76343678551 (Последовательность [[OEIS:A082411|A082411]] в OEIS; Николь, 1999)
Последовательность этого типа с минимальными начальными членами (известная на текущий момент) найдена Максимом Александровичем Всемирновым
: ''a''<sub>1</sub> = 106276436867, ''a''<sub>2</sub> = 35256392432 (Последовательность [[OEIS:A221286|A221286]] в OEIS; Всемирнов, 2004).

== Примечания ==
{{примечания|2}}

== Литература ==
{{refbegin|colwidth=30em}}
* {{статья
 |doi              = 10.2307/2689243
 |ref              = Graham
 |автор       = [[Грэм, Рональд|Ronald L. Graham]]
 |заглавие = A Fibonacci-like sequence of composite numbers
 |издание   = Mathematics Magazine
 |том           = 37
 |год           = 1964
 |выпуск     = 5
 |url              = http://www.math.ucsd.edu/~sbutler/ron/64_06_fibonacci.pdf
 |страницы = 322–324
 |jstor            = 2689243
}}{{Недоступная ссылка|date=Март 2018 |bot=InternetArchiveBot }}
* {{статья
|doi=10.2307/2691504
|автор=[[Кнут, Дональд Эрвин|Donald E. Knuth]]
|ref=Knuth
|заглавие=A Fibonacci-like sequence of composite numbers
|ссылка=https://archive.org/details/sim_mathematics-magazine_1990-02_63_1/page/21
|издание=Mathematics Magazine
|том=63
|выпуск=1
|страницы=21–25
|год=1990
|mr=1042933
|jstor=2691504
}}
* {{статья
|ref=Wilf
|автор=Herbert S. Wilf
|заглавие=Letters to the Editor
|ссылка=https://archive.org/details/sim_mathematics-magazine_1990-10_63_4/page/284
|издание=Mathematics Magazine
|том=63
|страницы=284
|год=1990
}}
* {{статья
|автор=John W. Nicol
|ref=Nicol
|заглавие=A Fibonacci-like sequence of composite numbers
|издание=Electronic Journal of Combinatorics
|том=6
|выпуск=1
|год=1999
|страницы=44
|url = http://www.combinatorics.org/Volume_6/PDF/v6i1r44.pdf
|mr=1728014}}
* {{статья
|автор= M.Vsemirnov 
|заглавие=A new Fibonacci-like sequence of composite numbers
|издание=Journal of Integer Sequences
|том=7
|год=2004
|выпуск=3
|страницы=04.3.7
|mr=2110778
|url=http://www.emis.ams.org/journals/JIS/VOL7/Vsemirnov/vsem5.pdf
}} (Всемирнов Максим Александрович)
{{refend}}

== Ссылки ==
* [http://www.primepuzzles.net/problems/prob_031.htm Problem 31.  Fibonacci- all composites sequence]. The prime puzzles and problems connection.
* [http://planetmath.org/?op=getobj&from=objects&id=7917 «Primefree sequence»] [[PlanetMath]]
* {{mathworld | title = Primefree Sequence | urlname = PrimefreeSequence}}

{{rq|checktranslate|style}}

[[Категория:Целочисленные последовательности]]
[[Категория:Теория чисел]]
[[Категория:Рекуррентные соотношения]]