Формула простых чисел, которая ломается на 40
При n = 40 выходит составное число: 41 × 41 = 1681.
До этого она выдерживает сорок проверок подряд: подставляешь 0, 1, 2 и дальше до 39, каждый раз получается простое число. Легко решить, что найдено безотказное правило. Но на следующем шаге в ответе появляется делитель 41. Его можно увидеть прямо в вычислении, без долгого перебора.
В статье вы узнаете:
Подставим несколько чисел
В этом опыте вместо буквы n будем брать целые числа от нуля: 0, 1, 2 и дальше. Выбранное число сначала умножаем на себя, затем прибавляем само число и ещё 41:
n² + n + 41.
Например, при n = 3 получаем:
3 × 3 + 3 + 41 = 9 + 3 + 41 = 53.
Число 53 простое. Это значит, что среди положительных целых чисел оно делится без остатка только на 1 и на себя. Для проверки откройте калькулятор простых чисел, введите 53 в поле «Целое число n» и нажмите «Проверить число». Ответ подтвердит простоту.
Здесь легко перепутать два ввода. В нашей формуле мы выбрали 3, а калькулятору передали полученный результат 53. Он проверяет отдельное число, а не подставляет значение в формулу Эйлера. Выражение n² + n + 41 в его поле вводить не нужно.
Вот как начинается ряд результатов:
| Число n | Результат n² + n + 41 |
|---|---|
| 0 | 41 |
| 1 | 43 |
| 2 | 47 |
| 3 | 53 |
| 4 | 61 |
| 5 | 71 |
Все шесть чисел простые. И это не короткое совпадение: простыми оказываются все сорок результатов при n от 0 до 39 включительно. Последний из них, при 39, равен 1601. Самостоятельно вводить все сорок чисел необязательно: интереснее посмотреть на следующий шаг.
При 40 в ответе появляется квадрат числа 41
Подставим n = 40:
40 × 40 + 40 + 41 = 1600 + 40 + 41 = 1681.
Внешне 1681 ничем не выдаёт свою составность. Оно нечётное, не заканчивается на 5 или 0. Но посмотрите на первые два слагаемых до сложения:
40 × 40 + 40 = 40 × 41.
К сорока группам по 40 мы прибавили ещё 40. Это то же самое, что взять число 40 сорок один раз. Теперь возвращаем последнее слагаемое формулы:
40 × 41 + 41 = 41 × 41 = 1681.
Ответ делится на 41. Значит, кроме 1 и самого 1681 у него есть ещё один делитель, и простым он быть не может. Если ввести 1681 в калькулятор, он покажет составное число и делитель 41. Равенство 41 × 41 мы уже получили сами.
Следующее значение тоже не спасает правило. При n = 41 удобнее сразу собрать первые два слагаемых:
41 × 41 + 41 + 41 = 41 × 42 + 41 = 41 × 43 = 1763.
Здесь делитель 41 виден ещё до перемножения. Это не случайная ошибка калькулятора: сама запись вынуждает результат делиться на 41.
После сбоя простые числа возвращаются
Сказать «после 40 формула перестаёт давать простые числа» было бы неверно. Уже при n = 42 она выдаёт:
42 × 42 + 42 + 41 = 1847.
Это простое число. Сломалась не формула, которую по-прежнему можно вычислять, а ожидание, что каждый её ответ будет простым.
Формула не перечисляет все простые числа по порядку
Вернёмся к первым результатам: 41, 43, 47, 53, 61, 71. Между 53 и 61 находится ещё одно простое число, 59. В нашей последовательности его нет.
Это не пропуск в таблице. При n = 3 получается 53, а уже при n = 4 получается 61. С дальнейшим увеличением неотрицательного n результат только растёт, поэтому до 59 формула не вернётся.
Так что «сорок простых результатов подряд» означает сорок удачных подстановок n от 0 до 39. Это не сорок соседних простых чисел из полного ряда. Формула выдаёт свои значения, иногда перескакивая через другие простые.
Если нужен список простых чисел до некоторой границы, одна эта запись его не заменяет. А если нужно проверить конкретное найденное число, знание того, как оно получено, тоже не освобождает от проверки.
Отсеять делитель 41 недостаточно
После объяснения первого сбоя хочется слегка починить правило: просто отбрасывать ответы, которые делятся на 41 и больше самого 41. Однако это уберёт только одну причину составности.
Попробуйте n = 44. Вычислим результат:
44 × 44 + 44 + 41 = 2021.
На 41 число 2021 не делится. Но теперь введите 2021 в поле проверки простоты. Число окажется составным по другой причине:
2021 = 43 × 47.
Поэтому у опыта два отдельных шага. Формула получает число из выбранного n. Проверка выясняет, есть ли у полученного числа делители, кроме 1 и него самого. Успешные проверки предыдущих значений не выполняют второй шаг за новое число.
Для сравнения проверьте рядом 1847 и 2021. Оба результата получены одной формулой, при близких n = 42 и n = 44. Но первый простой, а второй составной. Теперь различие объясняется конкретными числами и делителями, а не впечатлением от длинного удачного начала.
Есть что добавить?
Напишите своё мнение, комментарий или предложение.