Н. Макарова

 

П Р О С Т Ы Е    Ч И С Л А

 

В этой статье хочу представить ещё одну главу из рукописи моей книги “Компьютер решает головоломки”. Одна из представленных глав – “Магические квадраты” (http://www.klassikpoez.narod.ru/magich.htm ). Эта глава впоследствии выросла в большую книгу “Волшебный мир магических квадратов”. Читайте эту книгу (http://www.klassikpoez.narod.ru/glavnaja.htm )!

 

Конечно, сделаны некоторые дополнения к тому, что есть в рукописи, потому что книга была написана 17 лет назад, а с тех пор появилось много нового в этой области. В то же время хочу заметить, что всё это время ничуть не следила за новыми результатами, поэтому прошу не сетовать на пробелы, связанные с этим отставанием. Моя статья не претендует на научность и не представляет полные и исчерпывающие факты по теме. Цель статьи в популярной форме рассказать о простых числах тем, кто впервые знакомится с данным понятием.

 

Сразу замечу, что простые числа принадлежат множеству натуральных чисел. Евклид определял простые числа так: “Простое число есть измеряемое только единицей”. Иными словами, простые числа не имеют других делителей, кроме единицы и самого себя. Если p простое число, то его можно представить в виде произведения двух натуральных чисел только следующим образом: p = p*1. Числа, не являющиеся простыми, называются составными. Понятно, что всякое составное число имеет не меньше двух делителей отличных от 1. Кроме того, любое составное число N можно представить в виде следующего произведения:

 

N = p₁^q1 * p₂^q2 * … * p_m^qm, где p_i – простые числа, m ≥ 1, q_i ≥ 1 (при m = 1 q₁ > 1, при q_i =1 m > 1).

 

Таким образом, простые числа – это как бы “кирпичики” для строительства всех натуральных чисел. Например, число N = 500 представимо в виде такого произведения:

 

N = 2² * 5³

 

Представление составного числа в указанном виде называют разложением числа на простые множители. Все, наверное, хорошо помнят эту процедуру, с которой познакомились ещё на уроках арифметики. Помню, мы делали это так:

 

 

Деление производится до тех пор, пока слева не получается частное, равное 1; справа находятся простые множители, на которые разложено данное составное число. Однако не всегда так просто разложить заданное число на простые множители. Попробуйте-ка разложить на простые множители число N = 13593. Конечно, очевидно, что это число делится на 3, потому что сумма цифр числа делится на 3. Разделив число на 3, получаем число 4531. Это число не делится ни на 2, ни на 3, ни на 5, ни на 7. Итак, пока вы не дойдёте до первого простого числа, на которое полученное число делится, вы не продвинетесь ни на йоту в разложении этого числа на простые множители.

При разложении составного числа на простые множители используются признаки делимости. Признаки делимости на 2, 3 и 5 очень простые. Число делится: а) на 2 тогда и только тогда, когда его последняя цифра чётная; б) на 3 тогда и только тогда, когда сумма цифр этого числа делится на 3; в) на 5 тогда и только тогда, когда его последняя цифра 0 или 5. Признак делимости на 11: надо присвоить цифрам числа, начиная справа, попеременно знак “плюс” и знак “минус”, последняя цифра берётся со знаком “плюс”; затем сложить полученные значения. Исходное число делится на 11 тогда и только тогда, когда полученная сумма делится на 11. Пусть, например, надо определить, делится ли на 11 число 14399. Составляем сумму: 9 + (-9) + 3 + (-4) + 1 = 0. Полученная сумма делится на 11, следовательно, данное число тоже делится на 11. Так, можно сразу сказать, что любое число, составленное из чётного количества единиц (например: 1111, 11111111) делится на 11, а всякое число, составленное из нечётного количества единиц (например: 111, 1111111) не делится на 11. Точно так же можно определить, делится ли на 11, любое число, составленное другой цифрой, например: 3333333, 8888.

Признаков делимости на 7 существует несколько, но в [2] отмечается, что все они требуют не меньше затрат времени, чем обычное деление числа на 7. Это значит, что проще поделить число на 7 обычным образом, чем применять признак делимости. Подробнее о признаках делимости можно прочитать в [2].

 

Число 1 не относится к простым числам. “Математики предпочитают не считать 1 простым числом, поскольку в таком случае многие важные теоремы формулируются проще. Например, «основная теорема теории чисел» утверждает, что любое целое число допускает однозначное (с точностью до порядка множителей) разложение на простые множители. Так число 100 представимо в виде произведения четырёх простых множителей 2*2*5*5. Всякий другой набор (отличающийся хотя бы одним числом) простых множителей не даст в произведении числа 100. Если же считать единицу простым числом, то эта весьма важная теорема неверна: число 100 в этом случае представимо в виде произведения бесконечно многих различных наборов простых чисел, например, в виде 2*2*5*5*1*1”. [2]

 

Единственное чётное простое число 2. Все остальные простые числа нечётные, то есть любое простое число, отличное от 2, можно записать в виде: p = 2k + 1 (k ≥ 1).

Как уже сказано, множество простых чисел является подмножеством множества натуральных чисел. Как и множество натуральных чисел, множество простых чисел бесконечно. Это доказал Евклид. Приведу здесь доказательство этого утверждения, взятое в [3]. Положим, что ряд простых чисел ограничен и исчерпывается числами 2, 3, 5, …, p; в таком случае число N = (2*3*5* … *p) + 1, очевидно, не делится ни на 2, ни на 3, … ни на p, так как при делении на каждое из этих чисел мы получаем в остатке единицу. Поэтому должно иметь место одно из двух: либо это есть простое число, либо существуют простые числа, отличные от 2, 3, …, p. Но то и другое противоречит нашему предположению, и теорема, таким образом, доказана.

 

Для начала приведу ряд простых чисел в интервале (1, 500). Cделаю это в форме таблицы, чтобы лучше увидеть, как распределяются простые числа в  ряду натуральных чисел (рис. 1). Ячейки, содержащие простые числа, выделены оранжевым цветом.

 

 

Рис. 1

 

Вот так причудливо располагаются простые числа в ряду натуральных чисел! Обратите внимание на простые числа, которые находятся рядом, например: 2 и 3; 5 и 7; 11 и 13; 17 и 19 и т. д. Такие пары простых чисел называются близнецами. До сих пор неизвестно, конечно или бесконечно число пар близнецов. Однако, ясно, что по мере возрастания чисел близнецы встречаются всё реже и реже.

 

Плотность распределения простых чисел среди натурального ряда различна, есть участки, где простые числа располагаются гуще. Вместе с тем, существуют целые оазисы, не содержащие ни одного простого числа. Справедливо следующее утверждение:

 

 

Предлагаю читателям доказать эту теорему.

 

Основная трудность в нахождении всех простых чисел состоит в том, что математикам не удаётся установить закон распределения простых чисел. Количество простых чисел, не превосходящих N, обозначается π(N). Около 1800 г. два математика (А. Лежандр и К. Гаусс) независимо друг от друга высказали гипотезу, согласно которой

 

π(N) ≈ N/lnN

 

и что данное приближение тем лучше, чем больше N. Эта гипотеза впоследствии получила название теоремы об асимптотическом распределении простых чисел и была строго доказана в 1896 г. [2]

Например, количество простых чисел, не превосходящих 1000, оценивается числом 1000/ln1000, что примерно равно 145. Точное значение количества простых чисел, не превосходящих 1000, π(1000) = 168.

Величина π(N)/N называется средней плотностью простых чисел среди первых N натуральных чисел. Изучение таблиц простых чисел показывает, что с ростом N простые числа встречаются в среднем всё реже. Эйлер доказал, что lim (π(N)/N) = 0 при N стремящемся к бесконечности. Отсюда, в частности, следует, что простые числа в среднем располагаются реже, чем члены какой угодно арифметической прогрессии. Можно доказать, что простые числа располагаются всё же гуще квадратов натуральных чисел.

В 1837 г. немецкий математик Л. Дирихле доказал, что в любой арифметической прогрессии, первый член и разность которой взаимно просты (определение взаимно простых чисел см. далее), есть бесконечно много простых чисел.

В 1852 г. П. Л. Чебышев доказал предположение французского математика Ж. Бертрана о том, что для любого натурального числа N между числами N и 2N всегда есть простое число. [5]

 

 

 

Примечание: портрет Леонарда Эйлера из [6].

 

Самый знаменитый квадратичный трёхчлен Л. Эйлера, производящий простые числа:

 

x² + x + 41

 

Первые 40 значений этого трёхчлена (при x = 0, 1, 2, …, 39) являются простыми числами.

Из 2398 первых значений, принимаемых этим трёхчленом, ровно половина - простые числа. Перебрав все значения знаменитого трёхчлена, не превышающие 10 000 000, Улам, Стейн и Уэллс обнаружили, что доля простых чисел среди них составляет 0, 475… . [2]

Составив программку вычисления значений данного трёхчлена Эйлера, я получила 200 первых значений (x принимает значения от 0 до 199). Вот они:

 

41 43  47  53  61  71  83  97  113  131  151  173  197  223  251  281  313  347  383  421  461  503  547  593  641  691  743  797  853  911  971  1033  1097  1163  1231  1301  1373  1447  1523  1601  1681  1763  1847  1933  2021  2111  2203  2297  2393  2491  2591  2693  2797  2903  3011  3121  3233  3347  3463  3581  3701  3823  3947  4073  4201  4331  4463  4597  4733  4871  5011  5153  5297  5443  5591  5741  5893  6047  6203  6361  6521  6683  6847  7013  7181  7351  7523  7697  7873  8051  8231  8413  8597  8783  8971  9161  9353  9547  9743  9941  10141  10343  10547  10753  10961  11171  11383  11597  11813  12031  12251  12473  12697  12923  13151  13381  13613  13847  14083  14321  14561  14803  15047  15293  15541  15791  16043  16297  16553  16811  17071  17333  17597  17863  18131  18401  18673  18947  19223  19501  19781  20063  20347  20633  20921  21211  21503  21797  22093  22391  22691  22993  23297  23603  23911  24221  24533  24847  25163  25481  25801  26123  26447  26773  27101  27431  27763  28097  28433  28771  29111  29453  29797  30143  30491  30841  31193  31547  31903  32261  32621  32983  33347  33713  34081  34451  34823  35197  35573  35951  36331  36713  37097  37483  37871  38261  38653  39047  39443  39841

 

                        Предлагаю читателям найти среди этих значений простые числа, не считая первые 40, выделенные красным цветом.

Впоследствии подобные трёхчлены получили название “генераторы простых чисел” [7].

Покажу спираль Улама (рис. 1а), начинающуюся с числа 41 (о спирали Улама см. в [2]).

 

 

Рис. 1а

 

В этой спирали все 40 простых чисел, которые даёт рассматриваемый трёхчлен Эйлера при x = 0, 1, 2, …, 39, расположились на диагонали квадрата 40х40.

Аналогичный квадратичный трёхчлен, который тоже найден Эйлером: x² + x + 17. Этот трёхчлен при x, принимающем значения от 0 до 15, даёт только простые числа. На рис. 1б вы видите спираль Улама для этого трёхчлена.

 

 

Рис. 1б

 

Все 16 первых простых чисел, которые порождает данный трёхчлен, тоже расположились на диагонали квадрата. В квадрате выделены также остальные простые числа, находящиеся на этой спирали Улама. Интересно отметить, что те же самые 16 простых чисел этот трёхчлен даёт при x, принимающем значения от -1 до -16. Преобразовав рассматриваемый трёхчлен, можно получить такое выражение:

 

(x + 1)² – (x + 1) + 17 = y² – y + 17

 

Новый трёхчлен порождает те же самые простые числа при y, принимающем значения от 1 до 16 (или при y = 0, -1, -2, …, -15). Точно так же можно записать и рассмотренный выше трёхчлен Эйлера:

 

y² – y + 41

 

Этот трёхчлен порождает те же самые 40 простых чисел при y = 1, 2, 3, …, 40 (или при y = 0, -1, -2, …, -39).

М. Гарднер в своей книге пишет: спираль Улама – забава, но её следует принимать всерьёз.

 

В [5] написано: легко доказать, что не существует многочлена от одной переменной, значения которого при всех целых значениях переменной есть простые числа. Вместе с тем, советский математик Ю. В. Матиясевич доказал, что существует многочлен от нескольких переменных, который принимает все простые значения по одному разу, причём все положительные его значения – простые числа.

 

И ещё одна формула для простых чисел была предложена П. Ферма. Он высказал предположение, что все числа вида 2^p + 1, где p = 2^k, простые. При k = 0, 1, 2, 3 , 4 получаются такие простые числа: 3, 5, 17, 257, 65537. Однако Эйлер опроверг это предположение, доказав, что при k = 5 число 2^p + 1 (p = 2⁵) составное. В самом деле:

 

2³² + 1 = 4294967297 = 641 * 6700417

 

В [3] написано, что вопрос о том, при каких значениях k числа указанного вида являются простыми, остаётся и по сей день нерешённым. Вполне возможно, что в настоящее время уже есть ответ на этот вопрос или хотя бы приближение к ответу.

 

 

 

Примечание: портрет Пьера Ферма из [5].

 

Кстати, с простыми числами указанного вида связана задача  о том, какие правильные многоугольники можно построить с помощью циркуля и линейки. Гаусс установил, что для всех простых n, имеющих вид:

 

n = 2^p + 1 (p = 2^k)

 

возможно деление окружности на равные части циркулем и линейкой; при других же простых значениях n такое деление невозможно.

Для случаев n = 3 и n = 5 деление окружности на n равных частей с помощью циркуля и линейки было хорошо известно ещё в древности. А вот построение правильного семнадцатиугольника посредством циркуля и линейки было обнаружено Гауссом впервые. [3]

 

Как уже было отмечено, современные компьютеры по составленным программам, заложенным в пакеты математических программ типа Maple, могут в считанные секунды проверить очень большие числа на простоту. Во времена Эйлера такая проверка даже для шести- и семизначных чисел требовала длительных вычислений. Эйлер однажды заявил, что число 1000009 простое, но потом обнаружил, что оно является произведением двух простых чисел: 293 и 3413. По тем временам это было крупное достижение, если к тому же учесть, что Эйлеру в это время было за 70 и он уже ослеп. Пьера Ферма в одном из писем спросили, простое ли число 100895598169. Он очень быстро ответил, что это число является произведением таких простых чисел: 898423 и 112303. В 1874 г. У. Стенли Джевонс вопрошал в своей книге “Основы науки”: “Может ли читатель сказать, произведение каких двух чисел равно 8616460799? Думаю, что вряд ли кто-нибудь, кроме меня самого, сумеет дать ответ на этот вопрос, ибо это два больших простых числа”. Конечно, Джевонс не мог знать, что современный компьютер найдёт оба эти числа быстрее, чем он мог бы их перемножить. [2]

 

Оказывается, натуральные числа раскладываются не только на произведение простых чисел, но и на сумму простых чисел. Это знаменитая проблема Х. Гольдбаха. Гольдбах высказал следующее предположение: а) всякое нечётное число, большее шести, есть сумма трёх простых чисел; б) всякое чётное число есть сумма двух простых чисел.

Например, 25 = 3 + 5 + 17, 26 = 7 + 19, 40 = 17 + 23.

В 1937 г. академик И. М. Виноградов с помощью разработанного им метода оценок тригонометрических сумм доказал, что каждое достаточно большое нечётное число действительно является суммой трёх простых чисел. [6]

Подробнее о других проблемах, связанных с простыми числами, смотрите в статье “Простые числа” в Википедии (ссылка в конце статьи). Как я поняла из этой статьи, проблема Гольдбаха не решена до сих пор.

 

Примечание: если число 1 не считать простым числом, то вторую часть гипотезы Гольдбаха следует сформулировать так: всякое чётное число большее 2 есть сумма двух простых чисел. Однако в [6], откуда я взяла приведённую формулировку этой гипотезы, написано так, как представлено выше. У меня возникает подозрение, что во времена Гольдбаха число 1 считалось простым числом. Тогда всё правильно, число 2 тоже представимо в виде суммы двух простых чисел: 1 + 1. В таком случае первая часть гипотезы автоматически следует из второй части, потому что любое нечётное число есть сумма чётного числа и единицы. Но тогда в первой части гипотезы непонятно ограничение “большее шести”.

В знаменитом магическом квадрате 3-го порядка из простых чисел, построенном Дьюдени, присутствует число 1. Есть это число и в известном магическом квадрате 12-го порядка из простых чисел Дж. Манси, построенном в 1913 г.

 

 

Р Е Ш Е Т О   Э Р А Т О С Ф Е Н А

 

Как же искать простые числа в ряду последовательных натуральных чисел? Древнейший алгоритм такого поиска был предложен 2000 лет назад астрономом и географом из Александрии Эратосфеном. Этот алгоритм получил название “решето Эратосфена”.

Опишу подробно алгоритм Эратосфена. Пусть нам надо найти все простые числа в диапазоне от 1 до N. Выпишем подряд все числа от 2 до N. Зачеркнём в этом списке каждое второе число из следующих за числом 2. Таким образом мы отсеем все числа кратные числу 2. Число 2 является первым простым числом. Следующее не зачёркнутое число в списке после числа 2 – число 3. Это второе простое число. Повторим процедуру отсеивания, только теперь будем зачёркивать каждое третье число из следующих за числом 3. Так отсеем все числа кратные 3. Процедуру отсеивания следует повторять до тех пор, пока не доберёмся до простого числа, которое больше квадратного корня из N. Все числа, оставшиеся не зачёркнутыми в списке, будут простыми. Приведу иллюстрацию описанного метода для N = 50. Сначала покажу, как будет выглядеть список чисел после отсеивания чисел кратных 2:

 

2,  3,  /4/,  5,  /6/,  7,  /8/,  9,  /10/,  11,  /12/,  13,  /14/,  15,  /16/,  17,  /18/,  19,  /20/,  21,  /22/,  23,  /24/,  25,  /26/,  27,  /28/,  29,  /30/

31,  /32/,  33,  /34/,  35,  /36/,  37,  /38/,  39,  /40/,  41,  /42/,  43,  /44/,  45,  /46/,  47,  /48/,  49,  /50/

 

Примечание: зачёркнутые числа заключены в две наклонные черты / /.

 

Теперь покажу, как выглядит список после вычёркивания всех чисел кратных 3:

 

2,  3,  /4/,  5,  /6/,  7,  /8/,  /9/,  /10/,  11,  /12/,  13,  /14/,  /15/,  /16/,  17,  /18/,  19,  /20/,  /21/,  /22/,  23,  /24/,  25,  /26/,  /27/,  /28/,  29,  /30/

31,  /32/,  /33/,  /34/,  35,  /36/,  37,  /38/,  /39/,  /40/,  41,  /42/,  43,  /44/,  /45/,  /46/,  47,  /48/,  49,  /50/

 

Осталось два этапа: вычеркнуть все числа кратные 5 и кратные 7. Окончательно получим такой список простых чисел (простые числа выделены красным цветом):

 

2,  3,  /4/,  5,  /6/,  7,  /8/,  /9/,  /10/,  11,  /12/,  13,  /14/,  /15/,  /16/,  17,  /18/,  19,  /20/,  /21/,  /22/,  23,  /24/,  /25/,  /26/,  /27/,  /28/,  29,  /30/

31,  /32/,  /33/,  /34/,  /35/,  /36/,  37,  /38/,  /39/,  /40/,  41,  /42/,  43,  /44/,  /45/,  /46/,  47,  /48/,  /49/,  /50/

 

В этом примере процедура отсеивания (зачёркивания) завершилась на простом числе 7, то есть последний раз мы зачёркивали в этом списке каждое седьмое число, следующее за числом 7. Числа кратные 11 мы уже не будем зачёркивать (отсеивать), так как это число больше квадратного корня из 50.

 

Покажу ещё один оригинальный приём реализации решета Эратосфена из [2] (стр. 411 – 412). Здесь находятся все простые числа в интервале от 1 до 100. Все числа от 1 до 100 помещаются в прямоугольную таблицу (рис. 2).

 

 

Рис. 2

 

Процедура отсеивания выполняется следующим образом. Вычеркнем все числа кратные 2, за исключением самой двойки, проведя вертикальные черты во втором, четвёртом и шестом столбцах. Вычеркнем все числа кратные 3 (сама тройка остаётся), проведя вертикальную черту в третьем столбце. Следующее за 3 не вычеркнутое число равно 5. Чтобы вычеркнуть числа кратные 5, проведём диагонали, идущие вниз и влево (число 5 остаётся). Оставшиеся в таблице числа кратные 7 вычеркнем, проведя диагонали с наклоном вправо и вниз. Наша работа по составлению списка простых чисел, не превосходящих числа 100, на этом заканчивается, поскольку следующее простое число 11 больше квадратного корня из 100. Если бы таблица была больше, то нам пришлось бы исключать числа кратные 11, проводя диагонали с более крутым наклоном. Все не зачёркнутые числа в таблице на рис. 2, кроме числа 1, являются простыми (они выделены красным цветом).

 

Во времена Эратосфена писали на восковых дощечках, а вместо того, чтобы числа зачёркивать, дощечку в нужном месте прокалывали. Отсюда и произошло название способа – “решето Эратосфена”: составные числа как бы “просеивались” в проколотые дырки, а простые числа оставались в “решете”.

 

Понятно, что алгоритм Эратосфена нетрудно реализовать. Существует множество программ, составленных разными авторами. Есть программа, например, в [4] (стр. 305). Можно посмотреть и реализацию алгоритма, выполненную в Википедии:

 

http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D1%88%D0%B5%D1%82%D0%BE_%D0%AD%D1%80%D0%B0%D1%82%D0%BE%D1%81%D1%84%D0%B5%D0%BD%D0%B0

 

А лучше всего составить свою программу.

 

 

Р Е Ш Е Т О   С У Н Д А Р А М А

 

Ещё одно интересное “решето” для нахождения простых чисел было предложено в 1934 году индийским математиком С. П. Сундарамом. Он придумал очень оригинальную таблицу, состоящую из бесконечного количества бесконечных арифметических прогрессий, причём каждый член первой прогрессии начинает новую прогрессию (с новой строки таблицы). Разностями прогрессий являются все нечётные числа, начиная с 3. На рис. 3 вы видите начало таблицы Сундарама.

 

 

Рис. 3

 

Таблица бесконечно продолжается вправо и вниз. Разность арифметической прогрессии, записанной в первой строке таблицы, равна 3, разность арифметической прогрессии, записанной во второй строке таблицы, равна 5 и т. д. (все нечётные числа подряд являются разностями прогрессий).

Как же находить простые числа с помощью таблицы Сундарама? Оказывается, эта таблица обладает таким свойством: если некоторое число N содержится в таблице Сундарама, то число 2*N + 1 будет обязательно составным, а если число N не содержится в этой таблице, то число 2*N + 1 будет простым. Например, число 4 содержится в таблице, следовательно, число 2*4 + 1 = 9 составное; числа 5 нет в таблице, следовательно, число 2*5 + 1 = 11 простое. Доказательство этого свойства таблицы Сундарама вы можете найти в [1] (стр. 563 – 564).

 

Я реализовала метод Сундарама. Вот текст программы, написанный на языке QBASIC:

 

 

Программа работает очень просто. Надо ввести в программу чётное натуральное число M ≥ 4 и любое натуральное число L > M. Программа выдаст все простые числа в диапазоне от M+1 до L. Недостаток программы: при M = 4 теряются два простых числа: 2 и 3. Но этот недостаток очень легко устранить, если вставить в программу блок простой печати указанных простых чисел в случае, когда M = 4. По этой программе я получила следующий ряд простых чисел в интервале от 5 до 1000 (M = 4, L = 1000):

 

5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199  211  223  227  229  233  239  241  251  257  263  269  271  277  281  283  293  307  311  313  317  331  337  347  349  353  359  367  373  379  383  389  397  401  409  419  421  431  433  439  443  449  457  461  463  467  479  487  491  499  503  509  521  523  541  547  557  563  569  571  577  587  593  599  601  607  613  617  619  631  641  643  647  653  659  661  673  677  683  691  701  709  719  727  733  739  743  751  757  761  769  773  787  797  809  811  821  823  827  829  839  853  857  859  863  877  881  883  887  907  911  919  929  937  941  947  953  967  971  977  983  991  997

 

Замечу, что при выполнении программы был открыт файл для вывода простых чисел. В приведённом варианте программы простые числа выводятся только на экран монитора. При этом перед каждым простым числом выводится его порядковый номер.

 

А это результат, выданный программой при M = 1000, L = 2000:

 

1009  1013  1019  1021  1031  1033  1039  1049  1051  1061  1063  1069  1087  1091  1093  1097  1103  1109  1117  1123  1129  1151  1153  1163  1171  1181  1187  1193  1201  1213  1217  1223  1229  1231  1237  1249  1259  1277  1279  1283  1289  1291  1297  1301  1303  1307  1319  1321  1327  1361  1367  1373  1381  1399  1409  1423  1427  1429  1433  1439  1447  1451  1453  1459  1471  1481  1483  1487  1489  1493  1499  1511  1523  1531  1543  1549  1553  1559  1567  1571  1579  1583  1597  1601  1607  1609  1613  1619  1621  1627  1637  1657  1663  1667  1669  1693  1697  1699  1709  1721  1723  1733  1741  1747  1753  1759  1777  1783  1787  1789  1801  1811  1823  1831  1847  1861  1867  1871  1873  1877  1879  1889  1901  1907  1913  1931  1933  1949  1951  1973  1979  1987  1993  1997  1999

 

На форуме dxdy.ru по моей просьбе приведённая программа переписана на двух других языках программирования: Pascal и Turbo C++ 3.0. Вы можете посмотреть эти программы по следующей ссылке:

http://dxdy.ru/post218607.html?sid=6723a4a0d1a58ddd42ca1a8eb19a8f9c#p218607

 

В моей реализации решета Сундарама использовано следующее утверждение:

 

 

Теорема доказывается просто. Оставляю доказательство читателям.

 

Другую программу для решета Сундарама вы можете найти в Википедии в статье “Решето Сундарама”:

 

http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D1%88%D0%B5%D1%82%D0%BE_%D0%A1%D1%83%D0%BD%D0%B4%D0%B0%D1%80%D0%B0%D0%BC%D0%B0

 

Отмечу, что в программе, приведённой в указанной статье Википедии, простые числа находятся только с начала ряда натуральных чисел до некоторого n. В этом неудобство программы в тех случаях, когда простые числа надо найти в некотором интервале, находящемся не в начале натурального ряда. Кроме того, моя реализация принципиально отличается от реализации, приведённой в Википедии. В моей программе меньше циклов и поэтому выполняется она быстрее.

 

Однако решето Сундарама в любом случае не работает для очень больших чисел за реальное время. Так, например, я смогла выполнить свою программу для интервала [10⁷ + 1, 10⁷ + 100) довольно быстро, а при M = 10⁸, L = 10⁸ + 100 программа надолго “задумалась”; я не стала ждать, когда она что-нибудь выдаст, и прервала её.

 

Приведу интересную задачу о простых числах, состоящих из единиц. Генри Э. Дьюдени ещё в 1907 году отметил, что  11 – единственное из известных в то время простых чисел, которое состоит из одних единиц. Понятно, что число, в записи которого участвует любая другая цифра, составное, например: 3333, 55555. Дьюдени доказал, что все числа, состоящие из 3, 4, 5, … , 18 единиц, составные.

Следует заметить, что справедлива следующая теорема:

 

 

Теорема доказывается очень просто.

Дьюдени заинтересовался такими “единичными” простыми числами. Один из его читателей доказал, что число, состоящее из 19 единиц, простое. Позднее было установлено, что число, записанное с помощью 23 единиц, также простое. В то время, когда я писала книгу, было известно, что числа, состоящие из 29, 31, 37, 41, 43, 53, 61 и 73 единиц, составные. Первым кандидатом на простое было число, составленное из 47 единиц. Я попробовала решить эту задачу, то есть установить, является ли число, состоящее из 47 единиц, простым. И сделать это пыталась как раз с помощью приведённой в теореме 2 формулы. Обозначим число, состоящее из 47 единиц, В. Чтобы ответить на вопрос, является число В простым или составным, надо установить, находится ли соответствующее ему число А в таблице Сундарама. Число А находится из уравнения:

 

2 * A + 1 = B

 

Получаем, что число А = 55…5 (в записи числа А имеется 46 пятёрок).

Согласно теореме 2, если число А находится в таблице Сундарама, то оно должно быть представимо в виде:

 

A = (1 + 2 * N) * K + N,

 

где K и N – натуральные числа. Следовательно, задача свелась к решению приведённого уравнения в натуральных числах. Удобнее представить это уравнение в таком виде:

 

[1]                                 K = (A – N)/(1 + 2 * N)

 

Эта формула и положена в основу моей реализации решета Сундарама. Если данное уравнение не имеет решения в натуральных числах, то числа А нет в таблице Сундарама, а это означает, что соответствующее число В = 2 * А + 1 простое.

Однако для числа А, состоящего из 46 пятёрок, мне не удалось решить это уравнение (язык QBASIC не работает с такими большими числами). Поэтому эта задача тогда так и осталась у меня нерешённой.

Сейчас существует пакет математических программ Maple, который позволяет решать аналогичные задачи за одну секунду. На форуме, где я привела эту задачу, её решили сразу с помощью Maple. Оказалось, что число, составленное из 47 единиц, составное. Однако мне так и не ответили на вопрос, чему равны K и N, то есть в какой строке и с каким порядковым номером в этой строке находится в таблице Сундарама число А, состоящее из 46 пятёрок. А коль скоро число В, состоящее из 47 единиц, составное, число А, состоящее из 46 пятёрок, обязательно содержится в таблице Сундарама.

Приведу пример для небольшого числа А. Пусть А = 5555. В этом случае уравнение [1] имеет такое решение: N = 20, K = 135. Это значит, что в 20-ой строке таблицы Сундарама 135-ый член равен 5555, следовательно, число В = 2 * 5555 + 1 = 11111 составное.

 

Примечание: отмечу, что уравнение [1] в случае, когда число A содержится в таблице Сундарама, имеет не единственное решение. Рассмотрим пример для A = 22. Это число находится в таблице Сундарама в четырёх строках: первой, второй, четвёртой и седьмой.. Соответственно уравнение [1] имеет четыре решения:

 

1. N = 1, K = 7

2. N = 2, K = 4

3. N = 4, K = 2

4. N = 7, K = 1.

 

Только при A = 4 решение уравнения [1] будет единственным: N = 1, K = 1.

Для решения вопроса, является число B = 2*A + 1 простым или составным, достаточно найти одно решение уравнения [1] в натуральных числах.

 

С помощью приведённой выше программы для решета Сундарама можно проверить не очень большое число, является ли оно простым. Приведу два примера.

 

Пример 1. Требуется проверить число 10⁵ + 1. Введём в программу M = 10⁵, L = 10⁵ + 1. Программы выполнит проверку только одного числа M + 1 = 10⁵ + 1. Результат – данное число составное.

 

Пример 2. Требуется проверить число 10⁶ + 121. Введём в программу M = 10⁶ + 120, L = 10⁶ + 121. Программы выполнит проверку числа M + 1 = 10⁶ + 121. Результат выполнения программы – это число простое (программа выведет его на экран монитора).

 

Ещё один алгоритм нахождения простых чисел не связан ни с решетом Эратосфена, ни с решетом Сундарама. Здесь всё выполняется, что называется, “в лоб”: для каждого числа N проверяется, нет ли у него делителей в интервале от 2 до [√ N]. Реализацию этого алгоритма тоже можно найти в [4] (стр. 306). Впрочем, алгоритм очень просто реализовать.

 

 

Р Е Ш Е Т О   А Т К И Н А

 

Решето Аткина – это современный оптимизированный вариант решета Эратосфена. Прежде всего, дам ссылку на статью об этом решете в Википедии:

 

http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D1%88%D0%B5%D1%82%D0%BE_%D0%AD%D1%80%D0%B0%D1%82%D0%BE%D1%81%D1%84%D0%B5%D0%BD%D0%B0

 

Я не разбиралась с этим решетом. Предоставляю данный метод читателям для самостоятельного изучения. В помощь даю ссылку на форум “Портал Естественных Наук”, где в теме “Алгоритм «решета Эратосфена»” подробно рассматривается вопрос о решете Аткина, приведён текст программы, как я поняла, полученный из текста в Википедии незначительными изменениями. Вот ссылка:

 

http://e-science.ru/forum/index.php?s=80eab7d3816a082e5ee44635ec254896&showtopic=12506&st=80

 

 

Ч И С Л А   М Е Р С Е Н Н А

 

Числа вида 2^p – 1, где p – простое число, называются числами Мерсенна, впервые заметившего, что среди таких чисел много простых. В течение почти 200 лет математики считали, что число Мерсенна 2⁶⁷ – 1 простое. Эрик Темриль Белл в своей книге “Математика – царица и служанка науки” рассказывает о заседании американского математического общества, состоявшемся в октябре 1903 г. в Нью-Йорке, на котором выступил с сообщением профессор Коул. “Коул, человек немногословный, подошёл к доске и, не говоря ни слова, начал возводить 2 в степень 67. Затем он вычел из полученного числа 1 и, по-прежнему не говоря ни слова, перешёл на чистую часть доски, где столбиком перемножил два числа: 193707721 и 761838257287. Оба результата совпали… Впервые в истории американского математического общества его члены бурными аплодисментами приветствовали докладчика. Коул, так и не проронив ни слова, сел на место. Никто не задал ему ни одного вопроса. Через несколько лет Белл спросил у Коула, сколько времени тот потратил, чтобы разложить число на множители. ”Все воскресенья в течение трёх лет”, - ответил Коул. [2]

 

Далее приведены девять первых чисел Мерсенна, среди которых выделены красным цветом простые числа:

 

3,   7,   31,  127,   2047,  8191,  131071,  524287,  8388607

Как видите, среди первых девяти чисел Мерсенна только два составные. В то время, когда Гарднер писал свою книгу “Математические досуги”, было известно такое максимальное простое число Мерсенна: 2¹¹²¹³ – 1. Запись этого числа содержит около 3376 цифр. Это число обнаружил в 1963 г. с помощью ЭВМ Дональд Б. Джиллис. Это же число являлось и самым большим из известных простых чисел. [2]

В [5] уже приводится гораздо большее простое число Мерсенна:  2¹³²⁰⁴⁹ – 1. И опять же это число было самым большим из известных простых чисел.

В настоящее время составлены специальные программы для поиска чисел Мерсенна. Смотрите, например, тему “Взаимно простые числа” форума “Портал Естественных Наук”:

 

http://e-science.ru/forum/index.php?showtopic=9777

 

В статье “Простые числа” Википедии (ссылку см. в конце статьи) сообщается, что самым большим простым числом по состоянию на сентябрь 2008 г. является число Мерсенна  2^43112609 – 1. Оно было найдено 23 августа 2008 г. на математическом факультете университета UCLA в рамках проекта по распределённому поиску чисел Мерсенна GIMPS. В десятичной записи этого числа содержится около 13 миллионов цифр. Это 46-ое число Мерсенна. Насколько  понимаю, 47-ое число Мерсенна ещё не найдено.

Поскольку для чисел Мерсенна существует тест проверки на простоту, уже несколько лет именно эти числа держат рекорд самого большого простого числа.

 

 

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

 

Два числа n и m называются взаимно простыми, если они не имеют общих делителей, кроме 1. Обычно это записывают так: (n, m) = 1.

Так, например, числа 10 и 33 взаимно просты. Чтобы определить, являются ли два числа взаимно простыми, надо разложить их на простые множители.

Если p – простое число и a не делится на p, то n = (a^p-1 – 1) всегда делится на p. Эта теорема носит название “малой теоремы Ферма”; она имеет очень большое значение для теории сравнений.

Эйлер ввёл функцию φ(m), которая называется функцией Эйлера. Эта функция определяет количество натуральных чисел меньших числа m и взаимно простых с ним. Так, φ(6) = 2, φ(10) = 4. Если m простое число, то все меньшие числа взаимно просты с m и φ(m) = m – 1. Например, φ(11) = 10.

Эйлер обобщил малую теорему Ферма и доказал, что если a и m взаимно простые числа, то (a^φ(m) – 1) делится на m. Это утверждение называется теоремой Эйлера о сравнениях. [6]

 

 

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

 

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

 

http://narod.ru/disk/5834353000/Magic_squares.pdf.html

 

Вопрос составления нетрадиционных магических квадратов из простых чисел давно занимает математиков. Первый такой квадрат построил Дьюдени, это был квадрат 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, а сами эти числа x₁, x₂, x₃, x₄. Для того чтобы магический квадрат, построенный на основе латинского квадрата с рис. 17, был пандиагональным, достаточно, чтобы четвёрка простых чисел удовлетворяла условиям:

 

2x₁ + 2x₄ = S

2x₂ + 2x₃ = S

 

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

 

 

Рис. 18

 

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

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

 

 

Рис. 19

 

 

Рис. 20

 

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

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

 

x₁ – x₃ – x₄ + x₅ – x₈ + x₉ = 0

x₁ – x₂ + x₅ – x₆ – x₇ + x₉ = 0

x₂ – x₃ – x₄ + x₆ + x₇ – x₈ = 0

x₂ – x₃ + x₄ – x₅ – x₇ + x₉ = 0

x₁ – x₂ – x₄ + x₆ + x₈ – x₉ = 0

x₁ – x₃ – x₅ + x₆ – x₇ + x₈ = 0

 

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

 

x₁ = 3

x₂ = 23

x₃ = 5

x₄ = 11

x₅ = 31

x₆ = 13

x₇ = 17

x₈ = 37

x₉ = 19

 

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

 

 

Рис. 21

 

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

 

 

Рис. 22

 

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

 

 

Рис. 23

 

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

 

x₁ + x₂ – 4x₃ + x₄ + x₅ = 0

x₁ + x₅ – 2x₃ = 0

x₂ + x₄ – 2x₃  = 0

 

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

 

x₁ = 3

x₂ = 5

x₃ = 11

x₄ = 17

x₅ = 19

 

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

 

 

Рис. 24

 

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

 

 

Рис. 25

 

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

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

 

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

 

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

 

 

Рис. 26

 

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

 

 

Рис. 26а

 

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

 

 

З А Д А Ч И

 

Задача 1. Найдите точное значение π(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² + 1, 2⁴ + 1, 2⁸ + 1, …, 2^m + 1 (m = 2^k, k = 0, 1, 2, … )

 

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

 

Примечание: задача с форума: http://e-science.ru/forum/index.php?showtopic=9777 . А там даётся ссылка на книгу “Лекции по теории чисел” (С. В. Сизый).

 

Задача 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² – 2q² = 1.

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

(x² + y² + z²) * 11 = xyz

 

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

 

Задача 22. k, m, n – положительные целые числа и m + k + 1 – простое число, большее n + 1. Обозначим: C_p = p (p+1). Доказать, что произведение (C_m+1 – C_k) * (C_m+2 – C_k) * … * (C_m+n – C_k) делится на произведение C₁ * C₂ * … * C_n.

 

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

 

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

 

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

 

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

 

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

 

abc < ab + bc + ca

 

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

 

                  

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

 

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

 

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

 

n = 100! = p₁^q1 * p₂^q2 * … * 5^qk * … p_m^qm

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

 

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

 

 

П Р И Л О Ж Е Н И Е

 

 

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

 

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

 

 

 

 

По этой программе при 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³*11.

Читателям, наверное, известно, что разложение составных чисел на простые множители используется при нахождении наименьшего общего кратного (НОК) и наибольшего общего делителя (НОД) двух или более чисел. Пример: найти НОК и НОД чисел 126 и 258. Находим в таблице разложения этих чисел: 126 = 2*3²*7, 258 = 2*3*43. НОК = 2*3²*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.

 

 

Р Е К О М Е Н Д У Е М А Я   Л И Т Е Р А Т У Р А

 

Делоне Б. Н. Петербургская школа теории чисел, изд-во АН СССР, 1947

Депман И. Я. Совершенные числа. Квант, № 8, 1 – 6 (1971)

Серпинский В. Что мы знаем и чего не знаем о простых числах. – М. Физматгиз, 1963

Трост Э. Простые числа. М.: Физматгиз, 1959.

Виноградов И. М. Основы теории чисел. – М.: Наука, 1981.

Дьюдени Г. Э. 520 головоломок. – М.: Мир, 1975.

Оре О. Приглашение в теорию чисел. – М.: Наука, 1980. (Библиотечка “Квант”).

Хинчин А. Я. Три жемчужины теории чисел. – М.: Наука, 1979.

Ф. Курант, Г. Роббинс. Что такое математика? – М.: Просвещение, 1967.

 

 

В Е Б  -  С А Й Т Ы

 

 

1. Википедия. Статья “Решето Эратосфена”. http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D1%88%D0%B5%D1%82%D0%BE_%D0%AD%D1%80%D0%B0%D1%82%D0%BE%D1%81%D1%84%D0%B5%D0%BD%D0%B0
2. Википедия. Статья “Решето Сундарама”.

http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D1%88%D0%B5%D1%82%D0%BE_%D0%A1%D1%83%D0%BD%D0%B4%D0%B0%D1%80%D0%B0%D0%BC%D0%B0

         

 3. Википедия. Статья “Решето Аткина”.

http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D1%88%D0%B5%D1%82%D0%BE_%D0%AD%D1%80%D0%B0%D1%82%D0%BE%D1%81%D1%84%D0%B5%D0%BD%D0%B0

          

4. Википедия. Статья “Магический квадрат”.

http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D0%B3%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%BA%D0%B2%D0%B0%D0%B4%D1%80%D0%B0%D1%82

 

           5. Википедия. Статья “Простые числа”.

http://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D1%81%D1%82%D1%8B%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%B0

           

 6. Форум “Портал Естественных Наук”. Тема “Взаимно простые числа”.

http://e-science.ru/forum/index.php?showtopic=9777

 

             7. Форум “Портал Естественных Наук”. Тема “Алгоритм «решета Эратосфена»”.

     http://e-science.ru/forum/index.php?s=80eab7d3816a082e5ee44635ec254896&showtopic=12506&st=80

 

             8. Научный форум dxdy.ru. Тема “Программирование”.

http://dxdy.ru/post218607.html?sid=6723a4a0d1a58ddd42ca1a8eb19a8f9c#p218607

 

 

Уважаемые читатели! Просьба присылать свои отзывы и предложения о статье по адресу natalimak1@yandex.ru или в Гостевую книгу сайта.

Вы можете скачать новеллу в формате pdf. Ссылка для скачивания:

 

http://narod.ru/disk/10037356000/prost.pdf.html

 

Эта версия не содержит небольших добавлений, сделанных при последнем редактировании новеллы.

 

 

7 – 22 июня 2009 г.

г. Саратов

 

 

       Пишите мне!

Приглашаю всех на форум!

На главную страницу