English Ukrainian German

Чи можна обчислити прості числа?

Коротка відповідь: так, довга відповідь полягає в тому, що визначити їх за допомогою певних методів значно складніше коли справа доходить до все більших і більших простих чисел.


Розділ 1 – Основи натуральних і простих чисел

Давайте пригадаємо, що таке прості числа. В Інтернеті є кілька визначень, які свідчать:

«Просте число — це ціле число, більше за 1, яке не можна точно поділити на жодне ціле число, окрім самого себе та 1»

Ну, звучить непогано, але виникає два питання: що таке «ціле число» і що означає «точно поділити»?

Для того щоб зробити пояснення більш наочним, візьміть кілька монет або якісь інші злічувані предмети. Саме прикметник «злічуваний» є ключем до розуміння «цілих чисел», також відомих як «натуральні числа».

Тепер спробуйте викласти прямокутники з усіма монетами.


Якщо ви не можете побудувати більше «двох» прямокутників без залишку монет, то кількість усіх використаних монет у створеному прямокутнику (включаючи залишки) є простим числом. «Точно поділити» означає: здатність викласти принаймні один прямокутник із певної кількістю злічуваних речей без залишку. Монети в одній лінії не зараховуються.

Як бачите, чим більше монет, тим більше нам потрібно прямокутників і місця.

Чи можемо ми прискорити цей метод?

Звісно, так, прямокутники можна викладати тільки до того моменту, як вони досягнуть форми квадрата. І не важливо, має цей квадрат залишок чи ні. Прямокутники після досягнення форми квадрата знаходяться просто в іншому положенні, ніж попередні. Є ще деякі покращення, але ця стаття присвячена вивченню природи простих чисел, і цей метод – включаючи ці «непотрібні» прямокутники – дуже підходить для демонстрації їх природи. Існують також інші методи для перевірки того чи є число простим чи ні.

Добре, наразі останнє запитання: скільки простих чисел існує чи їх нескінченна кількість?

Стародавній грек Евклід сказав, що простих чисел нескінченно багато. Він стверджував, що якщо помножити всі відомі прості числа разом і додати одиницю, то має утворитись нове ще не відоме просте число, яке або є результатом цього обчислення, або здатне поділити результат без залишку.

Звучить складно! Отже, забудьте про це, ми не хотіли займатися математикою – ми хотіли передбачити прості числа. Я маю на увазі,знайти відповідь на запитання: яке наступне просте число можна утворити з даного числа?

top

Розділ 2 – Пошук простих чисел без обчислень

Що ж, повертаємось до прямокутників, зроблених з монет, і дотримуємось наступних інструкцій:

  1. Додайте монету до кожного прямокутника – або в новому рядку, або після решти монет
  2. Якщо один із прямокутників не має залишку, повторіть крок 1
  3. Якщо всі прямокутники мають залишки, кількість монет у рядку є наступним простим числом

Якщо ви хочете знайти інші прості числа, виконайте наступний крок і повторіть інструкцію:

  1. Скопіюйте монети в рядок і помістіть нові монети з попереднього рядка в новий рядок

Ого! Чудово! Чи можемо ми удосконалити цей метод?

Ми можемо виявити, що лише залишки кожного прямокутника важливі для визначення того, чи є число простим чи ні. Таким чином, ми можемо видалити всі прямокутники та зосередитися на залишках, тоді як останній «прямокутник з одного рядку» містить кількість монет того числа, яке потрібно перевірити. Але щоб запам'ятати відповідний прямокутник, ми викладаємо ще один рядок, який містить необхідну кількість монет, щоб завершити наступний рядок прямокутника. Давайте назвемо цей рядок «завершенням».

Тепер алгоритм трохи змінюється:

  1. Замість того, щоб додавати нову монету до кожного прямокутника, перемістіть одну монету з «повного рядка» в «рядок, що залишився», і лише в останньому рядку, який не має «рядку завершення», ми додаємо нову монету
  2. Якщо «рядок завершення» порожній (усі монети знаходяться у відповідному «рядку, що залишився»), перемістіть усі монети з «рядка, що залишився» у відповідний «рядок завершення», а для наступного раунду повторіть крок 1
  3. Якщо всі «повні рядки» містять монети, кількість монет в останньому рядку є наступним простим числом

Для подальших простих чисел крок 4 не змінюється:

  1. Скопіюйте останній рядок із монетами та використовуйте попередній рядок як новий «рядок завершення» для наступного раунду, повторивши крок 1


top

Розділ 3 – Діаграма залишку та «завершення»

Насправді використання лише залишків математично означає використання модуля для числа. «Завершення» ми використовуємо лише для кращого орієнтування. Ми можемо використовувати діаграму для аналізу результатів – навіть для більших чисел:


З цієї діаграми можна багато чого зрозуміти:

«Прапорці» на діаграмі представляють рядки колишніх прямокутників:


Якщо ми порівняємо перші п’ять стовпчиків для чисел 60, 120, 180, 240, 300 (і так далі +60), ми не побачимо змін. Те саме відбувається з іншими числами, такими як 67, 127, 187, 247, 307 (і так далі +60). Є проміжки, в яких візерунки повторюються.


Інколи візерунок виглядає хаотично (наприклад, для перших 200 стовпців числа 700), а іноді здається, що з’являється дуга (наприклад, для перших 200 стовпців з числа 2500). Така поведінка вказує на коливання та перешкоди.


І здається, що щось рухається, коли одночасно порівняти отримані візерунки:


top

Розділ 4 – Годинники та синусоїди з простими числами

Як ми могли бачити в попередніх розділах, кожен стовпчик залишків і «завершень» скидає свою позицію після того, як залишок «повний». Цю поведінку можна проілюструвати так:


Таким чином, ми можемо замінити кожен стовпчик діаграми годинниками. Інша ідея - використовувати шестерні або маятники. Головна ідея полягає в тому, що різниця між цим «природним рахунком» і нашим людським рахунком полягає в тому, що ми використовуємо системи числення, де «годинники» рухаються не одночасно, а після досягнення певної позиції.


Оскільки ми вставляємо прості числа в людську систему числення, нам здається, що прості числа з’являються спонтанно і випадково. Однак ми любимо виявляти закономірності, впорядковуючи числову пряму у двох вимірах.

Тут ви бачите, що прості числа (та їх квадрати) з’являються лише в певних стовпцях, якщо ми вибираємо спеціальні стовпці (наприклад: 4, 6, 10, 24, 30, 42). Якщо вибрати інші стовпці, розподіл буде виглядати хаотичним.


Ми могли б сказати, що в слові просте число прикметник «просте» означає просто «порціонування» чисел на числовій прямій. Існує дитяча іграшка, яка показує саме це:


Можливо, ви вже знаєте функцію, яка робить щось подібне: функцію синуса. Використовуючи кілька синусоїдальних кривих, кожна з довжиною періоду, що дорівнює двом простим числам, позначте в нульових точках на графіку складені числа. Синусоїди пропускають нові прості числа.


top

Розділ 5 – Два методи передбачення простих чисел

Власне, «решето Ератосфена» використовує цю ідею для передбачення нових простих чисел. Цей алгоритм в основному використовується, для того щоб показати в квадраті 10 x 10, як викреслити всі складені числа:


Ви можете легко знайти нові прості числа, якщо позначити всі множники всіх простих чисел, які ви знайшли в певному діапазоні. Ви можете припинити позначення множників, якщо знайдене просте число більше, ніж квадратний корінь діапазону, який ви хочете знайти. Усі непомічені числа тепер є простими числами.

Це є непрямим методом визначення простих чисел: те, що залишилося, є простим. Однак прості числа генерують нові прості числа, повторно використовуючи їх у тому самому методі (решета, синусоїдів, годинників, шестерні та маятників…). Це свого роду ітерація/рекурсія. І ми знаємо з фракталів, що виникає самоподібність. Такі властивості також можна знайти в графічних зображеннях простих чисел. Однак ці структури «руйнуються» під час використання іншого простого числа.


Діаграми із залишками дозволяють нам виявити прості числа за допомогою так званої «китайської теореми про залишки». Це спосіб знайти число X для різних залишків за модулем. А просте число завжди має залишок. Тож чому б не використати алгоритм введення відомих простих чисел з різними залишками? Насправді, я не хочу пояснювати цей метод докладно (ви можете знайти статті та відео, що пояснюють «китайську теорему про залишки»).

На жаль, алгоритм викидає не тільки прості, а й комплексні числа. Однак перевага полягає в тому, що отриманий пул чисел не містить жодного складеного числа з використаних простих чисел. Таким чином, метод значно скорочує кількість досліджуваних. І, можливо, є «шаблон» у результатах «китайської теореми про залишки»?


top

Розділ 6 – Висновок

Описані думки про прості числа можуть бути корисними для розуміння природи чисел. Про прості числа можна ще багато досліджувати та говорити про них. Цікаво, чи такі великі математики, як Евклід, Ферма, Гольдбах, Ейлер, Фур’є, Гаусс, Ріман та інші, також уявляли прості числа таким чином.

Базуючись на ідеї, що прості числа «розкривають» нові прості числа, я з цікавістю думаю про те, скільки простих чисел «генерує» скільки нових простих чисел? Однак я не фахівець, щоб відповісти на це питання. Мені здається, що існує спосіб для точного розрахунку, який дасть відповідь на це питання.

Якщо ви очікували прочитати в цій статті щось про гіпотезу про прості числа-близнюки, гіпотезу Ґольдбаха, скатертину Уляма чи гіпотезу Рімана, я повинен вас розчарувати. Я навіть не уявляю, чи можуть описані тут думки сприяти вирішенню цих гіпотез. Насправді я зовсім не фахівець у галузі простих чисел. Але я заперечую думку про те, що прості числа є «випадковими».

Ну, я не сам "винайшов" метод знаходження простих чисел без арифметики. Кілька років тому я якось побачив відео, в якому пояснювали цей метод, не вдаючись до того, чому він працює. І мені захотілося зрозуміти, як це працює. Я люблю розв'язувати задачі, а потім пояснювати, як я їх вирішив. Це і стало причиною написання цієї статті.

Інші методи пошуку простих чисел можна знайти в Інтернеті. Існує ще багато теорій і варіантів обчислення простих чисел – деякі серйозні, хоч і походять від непрофесіоналів, інші викликають у мене посмішку. Однак я ніколи не бачив відео чи статей, які б описували діаграму залишків або ідею з синусоїдами та її можливі наслідки. Але, можливо, я не витрачав багато зусиль на пошук такого контенту.

top





Автор: Йорг Дрешер, Київ, січень 2024 р

    https://creativecommons.org/licenses/by-sa/4.0/