Последовательность Евклида – Маллина - Euclid–Mullin sequence

В Последовательность Евклида – Маллина бесконечная последовательность различных простые числа, в котором каждый элемент наименее главный фактор одного плюс произведение всех предыдущих элементов. Они названы в честь древнегреческого математика. Евклид, потому что их определение опирается на идею в Доказательство Евклида, что простых чисел бесконечно много, и после Альберт А. Муллин, который спросил о последовательности в 1963 году.[1]

Первые 51 элемент последовательности

2, 3, 7, 43, 13, 53, 5, 6221671, 38709183810571, 139, 2801, 11, 17, 5471, 52662739, 23003, 30693651606209, 37, 1741, 1313797957, 887, 71, 7127, 109, 23, 97, 159227, 643679794963466223081509857, 103, 1079990819, 9539, 3143065813, 29, 3847, 89, 19, 577, 223, 139703, 457, 9649, 61, 4357, 87991098722552272708281251793312351581099392851768893748012603709343, 107, 127, 3313, 227432689108589532754984915075774848386671439568260420754414940780761245893, 59, 31, 211 ... (последовательность A000945 в OEIS )

Это единственные известные элементы по состоянию на сентябрь 2012 г.. Чтобы найти следующее, нужно найти наименьший простой множитель 335-значного числа (которое, как известно, составной ).

Определение

В -й элемент последовательности, , является наименьшим простым делителем

Таким образом, первый элемент является наименьшим простым фактором числа пустой продукт плюс один, что равно 2. Третий элемент равен (2 × 3) + 1 = 7. Лучшей иллюстрацией является пятый элемент в последовательности, 13. Он рассчитывается как (2 × 3 × 7 × 43) + 1 = 1806 + 1 = 1807, произведение двух простых чисел, 13 × 139. Из этих двух простых чисел 13 является наименьшим и поэтому включено в последовательность. Точно так же седьмой элемент, 5, является результатом (2 × 3 × 7 × 43 × 13 × 53) + 1 = 1,244,335, простые множители которого равны 5 и 248,867. Эти примеры показывают, почему последовательность может перескакивать с очень больших чисел на очень маленькие.

Свойства

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

Гипотеза

Вопрос, Web Fundamentals.svgНерешенная проблема в математике:
Каждое ли простое число входит в последовательность Евклида – Маллина?
(больше нерешенных задач по математике)

Муллин (1963) спросили, каждое ли простое число входит в последовательность Евклида – Маллина, и если нет, то является ли проблема проверки данного простого числа на членство в последовательности вычислимый. Дэниел Шэнкс  (1991 ) предположил, на основе эвристических предположений, что распределение простых чисел является случайным, что каждое простое число действительно появляется в последовательности.[2]Однако, хотя аналогичные рекурсивные последовательности в других доменах не содержат всех простых чисел,[3]обе эти проблемы остаются открытыми для исходной последовательности Евклида – Маллина.[4] Наименьшее простое число, которое, как известно, не является элементом последовательности, равно 41.

Позиции простых чисел от 2 до 97:

2: 1, 3: 2, 5: 7, 7: 3, 11:12, 13: 5, 17:13, 19:36, 23:25, 29:33, 31:50, 37:18, 41: ?, 43: 4, 47:?, 53: 6, 59:49, 61:42, 67:?, 71:22, 73:?, 79:?, 83:?, 89:35, 97:26 ( последовательность A056756 в OEIS )

где ? указывает на то, что позиция (или существует ли она вообще) неизвестна по состоянию на 2012 год.[5]

Связанные последовательности

Связанная последовательность чисел, определяемая наибольшим простым множителем единицы и произведением предыдущих чисел (а не наименьшим простым множителем), также известна как последовательность Евклида – Маллина. Он быстрее растет, но не монотонен.[6] Цифры в этой последовательности

2, 3, 7, 43, 139, 50207, 340999, 2365347734339, 4680225641471129, 1368845206580129, 889340324577880670089824574922371,… (последовательность A000946 в OEIS ).

Не все простые числа появляются в этой последовательности,[7] и последовательность пропущенных простых чисел,

5, 11, 13, 17, 19, 23, 29, 31, 37, 41, 47, 53, 59, 61, 67, 71, 73, ... (последовательность A216227 в OEIS )

было доказано, что оно бесконечно.[8][9]

Также возможно сгенерировать модифицированные версии последовательности Евклида – Маллина, используя то же правило выбора наименьшего простого множителя на каждом шаге, но начиная с другого простого числа, чем 2.[10]

В качестве альтернативы, если взять каждое число равным единице плюс произведение предыдущих чисел (а не разложить его на множители), получим Последовательность Сильвестра. Последовательность, построенная путем многократного сложения всех множителей единицы плюс произведение предыдущих чисел, такая же, как последовательность простых множителей последовательности Сильвестра. Как и последовательность Евклида – Маллина, это немонотонная последовательность простых чисел, но известно, что она не включает все простые числа.[11]

Смотрите также

использованная литература

  1. ^ Муллин, Альберт А. (1963), "Теория рекурсивных функций (современный взгляд на евклидову идею)", Проблемы исследования, Бюллетень Американского математического общества, 69 (6): 737, Дои:10.1090 / S0002-9904-1963-11017-4.
  2. ^ Шанкс, Дэниел (1991), «Простые числа Евклида», Вестник Института комбинаторики и его приложений, 1: 33–36, Г-Н  1103634.
  3. ^ Курокава, Нобусигэ; Сато, Такакадзу (2008), «Последовательности простых чисел Евклида над уникальными областями факторизации», Экспериментальная математика, 17 (2): 145–152, Г-Н  2433881.
  4. ^ Букер, Эндрю Р. (2016), «Вариант последовательности Евклида-Маллина, содержащий каждое простое число», Журнал целочисленных последовательностей, 19 (6): Статья 16.6.4, 6, Г-Н  3546618.
  5. ^ Список с вопросительными знаками приводится в поле Extensions записи OEIS, тогда как основной список заканчивается на 33 и не имеет вопросительных знаков.
  6. ^ Наур, Торкил (1984), "Последовательность простых чисел Маллина не монотонна", Труды Американского математического общества, 90 (1): 43–44, Дои:10.2307/2044665, Г-Н  0722412.
  7. ^ Cox, C.D .; Ван дер Поортен, А. Дж. (1968), «О последовательности простых чисел», Австралийское математическое общество, 8: 571–574, Г-Н  0228417
  8. ^ Букер, Эндрю Р. (2012), "О второй последовательности простых чисел Маллина", Целые числа, 12 (6): 1167–1177, arXiv:1107.3318, Дои:10.1515 / целые числа-2012-0034, Г-Н  3011555.
  9. ^ Поллак, Пол; Тревиньо, Энрике (2014), «Простые числа, которые забыл Евклид», Американский математический ежемесячный журнал, 121 (5): 433–437, Дои:10.4169 / amer.math.monthly.121.05.433, Г-Н  3193727.
  10. ^ Шеппард, Барнаби (2014), Логика бесконечности, Cambridge University Press, стр. 26, ISBN  9781139952774
  11. ^ Гай, Ричард; Новаковски, Ричард (1975), «Открытие простых чисел с Евклидом», Дельта (Ваукеша), 5 (2): 49–63, Г-Н  0384675.

внешние ссылки