Name: "Простые числа", часть 2, Наталия Макарова
Item: "Простые числа", часть 2, Наталия Макарова
Author: crottcync

Shadrinsk GIMPS Team
	Главная \| Каталог статей \| Регистрация \| Вход

Суббота 04.05.2024 14:43
	Приветствую Вас Гость \| RSS

Главная » Статьи » Немного истории...

"Простые числа", часть 2, Наталия Макарова

МАГИЧЕСКИЕ КВАДРАТЫ ИЗ ПРОСТЫХ ЧИСЕЛ

Если вы ещё не знаете, что такое магический квадрат, скачайте и прочтите книгу "Волшебный мир магических квадратов”:

Вопрос составления нетрадиционных магических квадратов из простых чисел давно занимает математиков. Первый такой квадрат построил Дьюдени, это был квадрат 3-го порядка. Его магическая константа равна 111. Дьюдени доказал, что это минимальная константа для магических квадратов, составленных из простых чисел. Вы видите квадрат Дьюдени на рис. 4.

Рис. 4

Примечание: в квадрате, правда, присутствует число 1, которое в современной теории чисел не считается простым числом.

В квадрате Дьюдени числа не последовательные. Понятно, что единственное чётное простое число 2 нельзя вписать ни в один магический квадрат, так как сумма чисел в той строке или в том столбце, на пересечении которых находится число 2, отличалась бы по чётности от суммы чисел во всех остальных строках и столбцах, и квадрат не был бы магическим. Поэтому магический квадрат из последовательных простых чисел был составлен без участия простого числа 2 (и опять же участвует число 1, которое не относится к простым числам). Этот магический квадрат составил Дж. Н. Манси в 1913 г. Это квадрат 12-го порядка, в его ячейках расположены 143 первых нечётных простых числа (число 1 не считаем). Манси доказал, что наименьший магический квадрат из последовательных нечётных простых чисел должен иметь порядок 12. Магический квадрат Манси изображён на рис. 5.

Рис. 5

Магическая константа этого квадрата равна 4514. [2]

В Википедии в статье "Магический квадрат” приведён ещё один нетрадиционный квадрат, заполненный простыми числами, показываю его на рис. 6.

Рис. 6

В этом квадрате нет числа 1, все числа простые. Магическая константа квадрата равна 177.

А теперь представьте, что вам надо построить другие нетрадиционные магические квадраты, скажем, тоже 3-го порядка, заполненные только простыми числами. Как вы будете строить такие магические квадраты? Ну, для порядка 3 можно обойтись без всякого особого алгоритма, а просто ввести некоторый массив простых чисел и перебирать все числа из этого массива на предмет их расположения в магическом квадрате 3х3. По такой программе вам удастся довольно быстро строить магические квадраты. Только надо учесть, что в нетрадиционном магическом квадрате 3-го порядка, составленном из простых чисел, не может быть записано не только число 2, но и число 3 (доказано в [7]). Поэтому массив простых чисел надо брать, начиная с числа 5. На рис. 7 вы видите три магических квадрата, построенные по такой программе.

Рис. 7

Для порядка 3 программа работает быстро и эффективно. Вы можете построить сколько угодно подобных магических квадратов.

Разумеется, это решение не является самым лучшим. В [7] приводится теория построения нетрадиционных магических квадратов из простых чисел не только 3-го порядка. Кстати, приводится нетрадиционный магический квадрат 9-го порядка (стр. 206), составленный из простых чисел. Этот квадрат состоит из девяти нетрадиционных магических квадратов 3-го порядка. В книге написано, что этот квадрат 9-го порядка является "наименьшим из всех магических квадратов такого рода”. Что автор имел в виду под "наименьшим”? Возможно, то, что этот квадрат имеет минимальную магическую константу. Воспроизведу этот квадрат (рис. 8):

Рис. 8

Квадрат оказался с ошибками. Посчитав суммы в строках и в столбцах, я не получила магической константы в двух строках и в двух столбцах (белые строка и столбец содержат суммы чисел в строках и в столбцах). Исправляю ошибки, квадрат получается такой (рис. 9):

Рис. 9

И квадрат потерял свою привлекательность как квадрат с неповторяющимися числами (сначала я думала, что квадрат именно такой), в нём число 1187 повторяется. Ну, а квадратов подобного рода с повторяющимися числами я могу построить сколько угодно, и с меньшей магической константой. Для этого достаточно взять любой нетрадиционный магический квадрат 3-го порядка и заполнить его копиями квадрат 9х9. Один такой пример показан на рис. 10.

Рис. 10

Магическая константа этого квадрата равна 639. При этом каждый квадрат 3х3, входящий в квадрат 9х9, можно подвергать любому из семи основных преобразований. Например, квадраты 3х3 можно расположить таким образом (рис. 11):

Рис. 11

Замечу, что в нетрадиционных магических квадратах числам не запрещается повторяться. Поэтому и квадрат на рис. 9, и квадраты на рис. 10 - 11 имеют право на существование.

Интересно построить подобный квадрат 9-го порядка с неповторяющимися простыми числами и при этом с наименьшей магической константой.
Точно так же можно построить составной нетрадиционный магический квадрат из простых чисел любого порядка n = 3k, k = 2, 3, 4, …
На рис. 12 показан квадрат 6-го порядка, составленный таким способом.

Рис. 12

Ещё один метод построения нетрадиционных магических квадратов из простых чисел основан на применении латинских квадратов. В этом случае числа в магическом квадрате тоже повторяются. Первый пример для квадрата 3-го порядка. На рис. 13 показан латинский квадрат 3-го порядка, на основе которого строится нетрадиционный магический квадрат.

Рис. 13

Поскольку этот латинский квадрат недиагональный, подходит не любая тройка простых чисел, а только такие три простых числа, для которых выполняется условие: сумма этих чисел, поделённая на 3, даёт одно из этих чисел. На рис. 14 вы видите два нетрадиционных магических квадрата 3-го порядка, построенные этим методом.

Рис. 14

Для квадратов 4-го и всех следующих порядков всё проще. Берём диагональный латинский квадрат 4-го порядка (рис. 15):

Рис. 15

Теперь достаточно взять любые четыре простых числа, пронумеровать их и записать в матрицу 4х4 в том порядке, какой указан в латинском квадрате. На рис. 16 показаны два нетрадиционных магических квадрата 4-го порядка, построенные таким способом.

Рис. 16

Теперь возьмём совершенный латинский квадрат 4-го порядка (рис. 17):

Рис. 17

Этот латинский квадрат обладает свойством пандиагональности. Будет ли обладать таким же свойством построенный на его основе нетрадиционный магический квадрат 4-го порядка из простых чисел? Будет, но не для любой четвёрки простых чисел. Обозначим сумму четырёх простых чисел S, а сами эти числа x1, x2, x3, x4. Для того чтобы магический квадрат, построенный на основе латинского квадрата с рис. 17, был пандиагональным, достаточно, чтобы четвёрка простых чисел удовлетворяла условиям:

2*x1 + 2*x4 = S

2*x2 + 2*x3 = S

Простым подбором я легко нашла такую четвёрку простых чисел: x1 = 3, x2 = 5, x3 = 17, x4 = 19. И вот пандиагональный нетрадиционный магический квадрат 4-го порядка, построенный из этой четвёрки простых чисел на основе латинского квадрата с рис. 17 (рис. 18):

Рис. 18

Думаю, что четвёрка простых чисел, удовлетворяющая таким условиям, не единственная. Можно составить программу для поиска таких четвёрок простых чисел.

Аналогично на основе совершенного квадрата 9-го порядка построен нетрадиционный магический квадрат 9-го порядка, изображённый на рис. 20 (на рис. 19 показан совершенный латинский квадрат 9-го порядка, на основе которого выполнено построение).

Рис. 19

Рис. 20

Магическая константа этого квадрата равна 100. Ещё меньшую магическую константу будет иметь нетрадиционный магический квадрат 9-го порядка, заполненный копиями нетрадиционного магического квадрата 3-го порядка, изображённого на рис. 14 слева. Магическая константа этого квадрата равна 45.

Совершенный латинский квадрат, на основе которого выполнено построение, как и все совершенные латинские квадраты, обладает свойством пандиагональности. Однако нетрадиционный магический квадрат на рис. 20 не является пандиагональным. Обозначим девять простых чисел x1, x2, …, x9, их сумму S. Для того чтобы нетрадиционный магический квадрат 9-го порядка из простых чисел, построенный на основе латинского квадрата с рис. 19, был пандиагональным, достаточно, чтобы девять простых чисел удовлетворяли следующей системе уравнений:

x1 – x3 – x4 + x5 – x8 + x9 = 0
x1 – x2 + x5 – x6 – x7 + x9 = 0
x2 – x3 – x4 + x6 + x7 – x8 = 0
x2 – x3 + x4 – x5 – x7 + x9 = 0
x1 – x2 – x4 + x6 + x8 – x9 = 0
x1 – x3 – x5 + x6 – x7 + x8 = 0

Составив программу решения этой системы в простых числах, я выполнила её до первого решения. Вот это решение:

x1 = 3
x2 = 23
x3 = 5
x4 = 11
x5 = 31
x6 = 13
x7 = 17
x8 = 37
x9 = 19

На рис. 21 вы видите нетрадиционный пандиагональный магический квадрат 9-го порядка, построенный из этих простых чисел на основе латинского квадрата с рис. 19.

Рис. 21

Последний пример – построение идеального нетрадиционного магического квадрата 5-го порядка. Будем строить его на основе латинского квадрата 5-го порядка, обладающего свойствами ассоциативности и пандиагональности (рис. 22).

Рис. 22

Если взять произвольную пятёрку простых чисел, то нетрадиционный магический квадрат не получится идеальный. Например, возьмём первые пять простых чисел, нетрадиционный магический квадрат получится такой (рис. 23):

Рис. 23

Этот квадрат обладает свойством пандиагональности, но не является ассоциативным. Для того чтобы ассоциативность имела место, достаточно, чтобы пятёрка простых чисел удовлетворяла следующей системе уравнений:

x1 + x2 – 4*x3 + x4 + x5 = 0
x1 + x5 – 2*x3 = 0
x2 + x4 – 2*x3 = 0

Составив программу и выполнив её до первого решения, получаю нужную пятёрку простых чисел:

x1 = 3
x2 = 5
x3 = 11
x4 = 17
x5 = 19

На рис. 24 вы видите нетрадиционный идеальный магический квадрат 5-го порядка, построенный из данной пятёрки простых чисел на основе латинского квадрата с рис. 22.

Рис. 24

Интересно отметить, что построенный магический квадрат является бимагическим. Это значит, что если заполнить матрицу 5х5 квадратами всех элементов данного квадрата, то снова получится нетрадиционный магический квадрат. Вы видите этот квадрат на рис. 25.

Рис. 25

При этом полученный квадрат не утратил свойство пандиагональности; свойство ассоциативности, конечно, утрачено. Очевидно, что и последний квадрат также бимагический. А полученный из квадратов его элементов магический квадрат тоже бимагический, и так до бесконечности. Таким образом, мы получили бесконечный ряд бимагических пандиагональных квадратов 5-го порядка.

Задача построения бимагического квадрата 5-го порядка, заполненного разными числами (любыми числами, не обязательно простыми), не решена до сих пор.

Читатели могут продолжить построение нетрадиционных магических квадратов из простых чисел описанным методом. Интересен вопрос: удастся ли построить нетрадиционный совершенный магический квадрат, например, 8-го порядка из простых чисел. Я не решала эту задачу. Оставляю её читателям. Скажу только, что для построения такого квадрата надо брать обобщённый латинский квадрат.

Не буду излагать теорию построения нетрадиционных магических квадратов, заполненных разными простыми числами. Заинтересовавшиеся читатели могут посмотреть её в [7]. Приведу только один пример нетрадиционного магического квадрата 4-го порядка, в котором все простые числа различны (стр. 242) [рис. 26]:

Рис. 26

На форуме dxdy.ru в теме "Магические квадраты” приведён очень оригинальный нетрадиционный магический квадрат 4-го порядка из различных простых чисел. Все простые числа в этом квадрате оканчиваются цифрой 7. Вы видите этот квадрат на рис. 26а.

Рис. 26а

Автор квадрата утверждает, что построил квадрат во сне.

ЗАДАЧИ

Задача 1. Найдите точное значение pi(500000). Сравните точное значение с оценочным значением.

Задача 2. Найдите с помощью компьютера все пары простых чисел-близнецов в интервале (50000, 100000). Сравните их количество с количеством таких пар в интервале (1, 1000) (см. в тексте ряд простых чисел в этом интервале).

Задача 3. Произведение каких простых чисел равно числу Джевонса 8616460799?

Задача 4. Докажите Теорему 1. Найдите ближайший к началу числовой оси отрезок, состоящий из а) 19; б) 21 последовательных натуральных чисел, среди которых нет ни одного простого.

Задача 5. Докажите Теорему 2. Решите задачу о числе, состоящем из 46 пятёрок: найдите номер строки и порядковый номер в строке таблицы Сундарама, где находится это число.

Задача 6. Докажите Теорему 3. На какое число делится число, состоящее из 25 единиц?

Задача 7. Далее приведены три криптарифма. Криптарифм – это какой-нибудь арифметический пример, в котором несколько или все цифры заменены значками или буквами. Требуется разгадать пример, то есть восстановить все зашифрованные цифры.
а)

В этом криптарифме одинаковыми буквами обозначены одинаковые цифры. Слагаемые – простые числа. (Регул – звезда в созвездии Льва).

б)

Здесь три слагаемых являются простыми числами, причём составлены они из цифр от 1 до 9, каждая из которых используется один раз. Сумма состоит из одинаковых цифр.

в) A * B * C * D = 571571

В этом примере все сомножители – простые числа. (Здесь звёздочка – знак умножения.)

Задача 8. Найдите простые числа среди следующих шести чисел:

10001, 14159, 76543, 77377, 123456789, 909090909090909090909090909090.

Задача 9. Найдите составное число среди следующих чисел:
31, 331, 3331, 33331, 333331, 3333331, 33333331, 333333331.

Задача 10. Из девяти цифр от 1 до 9 составьте три простых числа, чтобы их сумма была минимальной. Каждую цифру разрешается использовать один и только один раз. Например, числа 941, 827 и 653 простые и удовлетворяют условию задачи, но их сумма 2421 не минимальна.

Задача 11. Найдите отрезок числовой оси длиной в миллион единиц, не содержащий ни одного простого числа. (Задача аналогична задаче 4.)

Примечание: задачи 8 – 11 из [2].

Задача 12. Построить нетрадиционный магический квадрат 9-го порядка, заполненный различными простыми числами, состоящий из девяти нетрадиционных магических квадратов 3-го порядка (как на рис. 9, но чтобы не было одинаковых чисел). Дополнительное условие: с минимальной магической константой.

Примечание: мне удалось исправить нетрадиционный магический квадрат 9-го порядка, заполненный простыми числами, из книги Ю. В. Чебракова (см. рис. 8) так, что все числа в квадрате различны. Магическая константа при этом осталась такой же - 9171. Можно ли построить подобный квадрат с меньшей магической константой?

Задача 12а. Построить нетрадиционный магический квадрат 12-го порядка, заполненный различными простыми числами.
(см. подобный квадрат на рис. 5; но этот квадрат содержит число 1, которое не является простым числом).

Примечание: решение задачи мне пока неизвестно, я такой квадрат не строила. Думаю, что решение существует.

Задача 13. Доказать, что любые два числа из последовательности

2 + 1, 2^2 + 1, 2^4 + 1, 2^8 + 1, …, 2^m + 1 (m = 2^k, k = 0, 1, 2, … )

взаимно просты.

Примечание: задача с форума. А там даётся ссылка на книгу "Лекции по теории чисел” (С. В. Сизый).

Задача 14. Придумать алгоритм построения нетрадиционных магических квадратов 4-го порядка, заполненных разными простыми числами.

Задача 15. Задача связана с проблемой Гольдбаха. Действительно ли всякое чётное число представимо в виде суммы двух простых чисел? Представьте в виде суммы двух простых чисел следующие чётные числа: 100, 150, 200, 250, 300, 350, 400, 450, 500, 550, 600, 650, 700, 750, 800, 850, 900, 950, 1000.

Задача 16. Найти все простые числа p и q, для которых p^2 – 2*q^2 = 1.

Задача 17. Доказать, что если числа m и m^2 + 2 простые, то число m^3 + 2 тоже простое.

Задача 18. Обозначим n-ое простое число pn. Доказать, что если n >= 12, то pn > 3*n.

Задача 19. Числа p и q простые; q^3 – 1 делится на p, а p – 1 делится на q. Доказать, что p = 1 + q + q^2.

Задача 20. Доказать, что среди любых девяти последовательных натуральных чисел найдётся по крайней мере одно число, взаимно простое с каждым из остальных чисел.

Примечание: задачи 16 – 20 из [8]

ОЛИМПИАДНЫЕ ЗАДАЧИ

Задача 21. Решить уравнение

(x^2 + y^2 + z^2) * 11 = x*y*z

если известно, что x^2 + y^2 + z^2 – простое число.

Задача 22. k, m, n – положительные целые числа и m + k + 1 – простое число, большее n + 1. Обозначим: Cp = p (p+1). Доказать, что произведение (Cm+1 – Ck) * (Cm+2 – Ck) * … * (Cm+n – Ck) делится на произведение C1 * C2 * … * Cn.

Задача 23. Доказать, что существует бесконечное множество натуральных чисел a со следующим свойством: число z = n4 + a не является простым ни для какого натурального n.

Задача 24. Решить уравнение 2^x = 3^y + 5, если x и y – простые числа. Доказать, что есть только одна пара простых чисел x, y, удовлетворяющая этому уравнению.

Задача 25. Дано простое нечётное число p. Найти необходимое и достаточное условие того, что сумма квадратов p - 1 последовательных натуральных чисел делится на сумму этих чисел.

Задача 26. Доказать, что остаток от деления любого простого числа на 30 есть 1 или простое число.

Задача 27. Найти все тройки простых чисел a, b, c, для которых справедливо неравенство:

a*b*c < a*b + b*c + c*a

Примечание: задачи 21 – 27 из [9].

Задача 28. Сколько существует натуральных чисел, меньших 1000, которые не делятся ни на 5, ни на 7?

Задача 29. Доказать, что если n – m кратно 6, то 10^n – 10^m кратно 7 (n и m – натуральные числа).

Задача 30. Пусть число n = 100! (сто факториал) разложено на простые множители:

n = 100! = p1^q1 * p2^q2 * … * 5^qk * … pm^qm

Чему равен показатель qk у простого множителя 5?

Задача 31. Сколько существует таких пар натуральных чисел n и m, заключённых между 1 и 1000, что n^2 + m^2 делится на 7^2?

Задача 32. Сколько существует натуральных чисел n меньших 10000, для которых 2^n – n^2 делится на 7?

Задача 33. Доказать, что квадрат любого простого числа p > 3 при делении на 12 даёт в остатке 1.

Задача 34. Решить уравнение xy + 3x – 5y = -3, если |x| и |y| - простые числа.

Задача 35. Доказать, что среди любых шестнадцати последовательных натуральных чисел всегда можно выбрать одно число, взаимно простое с каждым из остальных чисел (см. аналогичную задачу 20).

Задача 36. Имеется p простых чисел a1, a2, …, ap образуют возрастающую арифметическую прогрессию и a1 > p. Доказать, что если p – простое число, то разность арифметической прогрессии делится на p.

Задача 37. Доказать, что число делителей числа n не превосходит 2.

Задача 38. Доказать, что существует бесконечно много натуральных чисел, не представимых в виде p + n^(2*k) ни при каких простых p и натуральных n и k.

Примечание: задачи 28 – 38 из [10].

ПРИЛОЖЕНИЕ

ТАБЛИЦА СУНДАРАМА

Здесь приведена программа (язык QBASIC), с помощью которой вы можете составить таблицу Сундарама для наперёд заданного количества строк (N) и количества элементов в каждой строке (K). Такая таблица может служить простым подручным средством для проверки не очень больших чисел на простоту. Как пользоваться таблицей, разъяснялось в тексте.

Программа составления таблицы Сундарама

10 OPEN "MK.txt" FOR OUTPUT AS #1
15 PRINT "Vvedite N"
20 INPUT N
25 PRINT "Vvedite K"
30 INPUT K
35 DIM A(N, K)
40 I = 1: A(1, 1) = 4: D = 3
45 FOR J = 2 TO K: A(I, J) = A(I, J - 1) + D: NEXT J
55 I = I + 1
60 IF I > N THEN 100
65 A(I, 1) = A(1, I): D = D + 2: GOTO 45
100 FOR P = 1 TO N
105 FOR Q = 1 TO K
110 PRINT #1, A(P, Q);
115 NEXT Q
120 PRINT #1,
125 NEXT P
130 CLOSE #1
1435 END

По этой программе при N = 30, K = 35 получена такая таблица Сундарама:

4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61 64 67 70 73 76 79 82 85 88 91 94 97 100 103 106 …
7 12 17 22 27 32 37 42 47 52 57 62 67 72 77 82 87 92 97 102 107 112 117 122 127 132 137 142 147 152 157 162 167 172 177 …
10 17 24 31 38 45 52 59 66 73 80 87 94 101 108 115 122 129 136 143 150 157 164 171 178 185 192 199 206 213 220 227 234 241 248 …
13 22 31 40 49 58 67 76 85 94 103 112 121 130 139 148 157 166 175 184 193 202 211 220 229 238 247 256 265 274 283 292 301 310 319 …
16 27 38 49 60 71 82 93 104 115 126 137 148 159 170 181 192 203 214 225 236 247 258 269 280 291 302 313 324 335 346 357 368 379 390 …
19 32 45 58 71 84 97 110 123 136 149 162 175 188 201 214 227 240 253 266 279 292 305 318 331 344 357 370 383 396 409 422 435 448 461 …
22 37 52 67 82 97 112 127 142 157 172 187 202 217 232 247 262 277 292 307 322 337 352 367 382 397 412 427 442 457 472 487 502 517 532 …
25 42 59 76 93 110 127 144 161 178 195 212 229 246 263 280 297 314 331 348 365 382 399 416 433 450 467 484 501 518 535 552 569 586 603 …
28 47 66 85 104 123 142 161 180 199 218 237 256 275 294 313 332 351 370 389 408 427 446 465 484 503 522 541 560 579 598 617 636 655 674 …
31 52 73 94 115 136 157 178 199 220 241 262 283 304 325 346 367 388 409 430 451 472 493 514 535 556 577 598 619 640 661 682 703 724 745 …
34 57 80 103 126 149 172 195 218 241 264 287 310 333 356 379 402 425 448 471 494 517 540 563 586 609 632 655 678 701 724 747 770 793 816 …
37 62 87 112 137 162 187 212 237 262 287 312 337 362 387 412 437 462 487 512 537 562 587 612 637 662 687 712 737 762 787 812 837 862 887 …
40 67 94 121 148 175 202 229 256 283 310 337 364 391 418 445 472 499 526 553 580 607 634 661 688 715 742 769 796 823 850 877 904 931 958 …
43 72 101 130 159 188 217 246 275 304 333 362 391 420 449 478 507 536 565 594 623 652 681 710 739 768 797 826 855 884 913 942 971 1000 1029 …
46 77 108 139 170 201 232 263 294 325 356 387 418 449 480 511 542 573 604 635 666 697 728 759 790 821 852 883 914 945 976 1007 1038 1069 1100 …
49 82 115 148 181 214 247 280 313 346 379 412 445 478 511 544 577 610 643 676 709 742 775 808 841 874 907 940 973 1006 1039 1072 1105 1138 1171 …
52 87 122 157 192 227 262 297 332 367 402 437 472 507 542 577 612 647 682 717 752 787 822 857 892 927 962 997 1032 1067 1102 1137 1172 1207 1242 …
55 92 129 166 203 240 277 314 351 388 425 462 499 536 573 610 647 684 721 758 795 832 869 906 943 980 1017 1054 1091 1128 1165 1202 1239 1276 1313 …
58 97 136 175 214 253 292 331 370 409 448 487 526 565 604 643 682 721 760 799 838 877 916 955 994 1033 1072 1111 1150 1189 1228 1267 1306 1345 1384 …
61 102 143 184 225 266 307 348 389 430 471 512 553 594 635 676 717 758 799 840 881 922 963 1004 1045 1086 1127 1168 1209 1250 1291 1332 1373 1414 1455 …
64 107 150 193 236 279 322 365 408 451 494 537 580 623 666 709 752 795 838 881 924 967 1010 1053 1096 1139 1182 1225 1268 1311 1354 1397 1440 1483 1526 …
67 112 157 202 247 292 337 382 427 472 517 562 607 652 697 742 787 832 877 922 967 1012 1057 1102 1147 1192 1237 1282 1327 1372 1417 1462 1507 1552 1597 …
70 117 164 211 258 305 352 399 446 493 540 587 634 681 728 775 822 869 916 963 1010 1057 1104 1151 1198 1245 1292 1339 1386 1433 1480 1527 1574 1621 1668 …
73 122 171 220 269 318 367 416 465 514 563 612 661 710 759 808 857 906 955 1004 1053 1102 1151 1200 1249 1298 1347 1396 1445 1494 1543 1592 1641 1690 1739 …
76 127 178 229 280 331 382 433 484 535 586 637 688 739 790 841 892 943 994 1045 1096 1147 1198 1249 1300 1351 1402 1453 1504 1555 1606 1657 1708 1759 1810 …
79 132 185 238 291 344 397 450 503 556 609 662 715 768 821 874 927 980 1033 1086 1139 1192 1245 1298 1351 1404 1457 1510 1563 1616 1669 1722 1775 1828 1881 …
82 137 192 247 302 357 412 467 522 577 632 687 742 797 852 907 962 1017 1072 1127 1182 1237 1292 1347 1402 1457 1512 1567 1622 1677 1732 1787 1842 1897 1952 …
85 142 199 256 313 370 427 484 541 598 655 712 769 826 883 940 997 1054 1111 1168 1225 1282 1339 1396 1453 1510 1567 1624 1681 1738 1795 1852 1909 1966 2023 …
88 147 206 265 324 383 442 501 560 619 678 737 796 855 914 973 1032 1091 1150 1209 1268 1327 1386 1445 1504 1563 1622 1681 1740 1799 1858 1917 1976 2035 2094 …
91 152 213 274 335 396 457 518 579 640 701 762 823 884 945 1006 1067 1128 1189 1250 1311 1372 1433 1494 1555 1616 1677 1738 1799 1860 1921 1982 2043 2104 2165…

РАЗЛОЖЕНИЕ НА ПРОСТЫЕ МНОЖИТЕЛИ ПЕРВЫХ 299 ЧИСЕЛ

Думаю, читателям понятно, как устроена таблица. Если внимательно присмотреться к тому, как числа раскладываются на простые множители, можно увидеть много интересного. Любознательным читателям рекомендую расширить эту таблицу хотя бы до N = 500 и внимательно её изучить. Посмотрите, даже простые числа в этой таблице расположились не совсем уж хаотично. Все простые числа расположились в четырёх столбцах таблицы (кроме чисел 2 и 5), потому что все простые числа оканчиваются одной из следующих цифр: 1, 3, 7, 9 (за исключением чисел 2 и 5). В таблице выделены ячейки, в которых находятся простые числа.

Понятно, что по данной таблице можно раскладывать не только числа до 299, а также все числа кратные числам, имеющимся в этой таблице. Например, нам надо разложить на простые множители число 594, очевидно, что это число делится на 2, поделив, получаем число 297, а разложение этого числа имеется в таблице, таким образом, 594 = 2*3^3*11.

Читателям, наверное, известно, что разложение составных чисел на простые множители используется при нахождении наименьшего общего кратного (НОК) и наибольшего общего делителя (НОД) двух или более чисел. Пример: найти НОК и НОД чисел 126 и 258. Находим в таблице разложения этих чисел: 126 = 2*3^2*7, 258 = 2*3*43. НОК = 2*3^2*7*43 = 5418 (берутся все простые множители, составляющее первое число, плюс те простые множители из разложения второго числа, которых нет в разложении первого числа), НОД = 2*3 = 6 (берутся простые множители, присутствующие в разложении обоих чисел одновременно). Это, конечно, школьная арифметика, но для школьников может пригодиться. Имея таблицу разложения чисел на простые множители (которую при желании можно расширить), вы очень быстро сможете находить НОК и НОД.

ЛИТЕРАТУРА

ИСПОЛЬЗОВАННАЯ ЛИТЕРАТУРА

[1] Б. А. Кордемский. Математическая смекалка. – М.: Государственное издательство технико-теоретической литературы, 1957.
[2] Мартин Гарднер. Математические досуги. – М.: Мир, 1972.
[3] Клейн Ф. Элементарная математика с точки зрения высшей. В 2-х томах. Т. 1. Арифметика. Алгебра. Анализ: Пер. с нем. / Под ред. В. Г. Болтянского. – М.: Наука. Главная редакция физико-математической литературы. 1987.
[4] Светозарова Г. И., Мельников А. А., Козловский А. В. Практикум по программированию на языке Бейсик. – М.: Наука. Главная редакция физико-математической литературы, 1988.
[5] Энциклопедический словарь юного математика. – М.: Педагогика, 1989.
[6] Яковлев А. Я. Леонард Эйлер. (Серия "Люди науки”) – М.: Просвещение, 1983.
[7] Ю. В. Чебраков. Магические квадраты. Теория чисел, алгебра, комбинаторный анализ. – С. – Петербург, 1995.
[8] Математика и естествознание. Составитель С. И. Шварцбурд. – М.: Просвещение, 1969.
[9] Е. А. Морозова, И. С. Петраков. Международные математические олимпиады. – М.: Просвещение, 1971.
[10] Гальперин Г. А., Толпыго А. К. Московские математические олимпиады. Под ред. А. Н. Колмогорова. – М.: Просвещение, 1986.