Что такое некоторые числа
Простые числа — это чудеса деления
Здравствуйте, уважаемые читатели блога KtoNaNovenkogo.ru. Сегодня мы поговорим о таком математическом понятии, как ПРОСТЫЕ ЧИСЛА.
В школе это проходят в 5 или 6 классе, в зависимости от программы обучения.
И интересно, что если спросить школьников, что такое простые числа, то они, скорее всего, ответят правильно.
А вот взрослые задумаются и не факт, что вспомнят точное определение. Так что это статья скорее для них.
Простые числа — это.
Итак, вот как выглядит официальное определение:
Простые числа – это такие числа, которые имеют только два делителя. Один из них – единица, а другое – само число.
Чтобы было более понятно, приведем простой пример. Для чисел 5 и 7 надо найти все возможные делители, чтобы в результате образовалось целое число.
Если вы попробуете решить эту задачку, то получите, что 5 и 7 делятся только на 1 и 5, и 1 и 7 соответственно. Во всех других случаях вы получите дробное число. И это как раз означает, что числа 5 и 7 относятся к простым.
А вот попробуем по той же схеме разобрать числа 6 и 9. В первом случае мы получим, что 6 можно поделить на 1, 2, 3 и 6, а число 9 – на 1, 3 и 9. И это уже противоречит определению простых чисел, значит, 6 и 9 таковыми не являются.
Они называются в математике – СОСТАВНЫМИ ЧИСЛАМИ.
Список и таблица простых чисел
Некоторые ошибочно полагают, что наименьшее простое число – это единица.
С одной стороны, в этом есть логика, так как 1 делится только на 1. Но это получается одно и то же число (единица), что противоречит определению простых чисел, в котором четко прописано – «делителей должно быть два».
Значит, минимальное простое число – это 2. А первоначальный ряд выглядит следующим образом:
2, 3, 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…
При желании можете проверить эти числа на предмет деления. Мы же скажем, что этот ряд на самом деле не окончательный.
Количество простых чисел не ограничено. Или говоря математическим языком, оно стремится к бесконечности.
История простых чисел
Первые упоминания о простых числах относятся к Древнему Египту. В Британском музее хранится папирус, который датируется 2000 годом до нашей эры. И на нем, согласно расшифровке, содержится учебное пособие по арифметике.
В том числе и про деление чисел. Называется этот артефакт – папирус Райнда, по имени его первого владельца.
В этом документе есть таблица, в которой указаны числа, делящиеся на различные знаменатели. Причем они разделены таким образом, что становится понятно – древние египтяне может и не пользовались понятиям «простое число», но хотя бы имели о нем представление.
Ну а первые исследования простых чисел датируются 300 годом до нашей эры. И связаны они с именем знаменитого древнегреческого математика Евклида.
Как и многое другое, он описал простые и составные числа в своем известном произведении «Начала».
В частности, Евклид описал такие вещи, как:
Сейчас расскажем об этих понятиях подробнее.
Основная теорема арифметики
Основная теорема арифметики, которую придумал еще Евклид, гласит:
Любое натуральное число (это что?), которое больше единицы, может быть представлено в виде произведения простых чисел. Причем их количество не ограничено, а порядок следования неважен.
Если обозначить исходное число буквой N, а простые числа буквами Р1, Р2, Р3 и так далее, то можно записать эту теорему следующим образом:
N = Р1 * Р2 * Р3 * … * РК
Например, возьмем число 100. Его можно разложить на следующие простые числа:
Или более сложный пример – число 23244:
23244 = 149 * 13 * 3 * 2 * 2
Раскладывать на простые числа легко. Можно сперва делить на 2 и 3, а уже в конце автоматически получить более сложные делители.
Ради интереса придумайте любое число и сами найдите его составляющие.
Лемма Евклида
Еще одна теорема, которая имеет прямое отношение к простым числам. Она гласит;
Если некое простое число Р делит произведение чисел X и Y без остатка, то оно может точно так же поделить или X, или Y.
Звучит несколько сложновато, хотя на деле все это просто. Так, возьмем для примера P = 2, X = 6, Y = 9. И тогда получается, что
В нашем примере P делит это произведение без остатка:
А значит наша P может поделить без остатка или X, или Y. Очевидно, что это X:
Y/P = 9/2 = 4,5 (не подходит)
Как быстро и легко определить простые числа
И еще одно понятие, которое связано с простыми числами. Оно названо в честь другого древнегреческого математика Эратосфена Киренского.
Этот человек придумал, как быстро и легко определить простые числа. В частности, он сделал таблицу, в которой были указаны значения до 1000.
Свою таблицу он нарисовал на глиняной дощечке. А после прокалывал те клеточки, на которых были написаны составные числа. В результате получилось нечто вроде решета, отсюда собственно и название метода.
Кстати, пользоваться решетом Эратосфена весьма просто. Например, сделаем таблицу до 50.
После этого из нее надо поочередно вычеркивать числа, которые кратны 2, 3, 5, 7 и 11. В результате получится вот это:
Те числа, которые остались, и есть простые. Можете сравнить этот ряд с тем, который мы давали в начале статьи. Точно таким же способом можно составить абсолютно любой ряд простых чисел = хоть до тысячи, хоть до миллиона и больше.
Вот и все, что мы хотели рассказать о ПРОСТЫХ ЧИСЛАХ в математике.
Удачи вам! До скорых встреч на страницах блога KtoNaNovenkogo.ru
Эта статья относится к рубрикам:
Комментарии и отзывы (1)
Математика весьма хитрая наука, да и простые числа не такие уж и простые, понимание простых и составных чисел привело человечество к тому техническому прогрессу, что окружает нас сейчас.
Неисчислимое: в поисках конечного числа
Древние греки — приверженцы концепций, имеющих строгий логический смысл — всячески избегали концепции бесконечности. Действительно, какое нам дело до бесконечного ряда чисел, если ни записать, ни представить его мы не можем.
В средние века логическую строгость отбросили ради математических результатов и разработали чрезвычайно эффективные алгоритмические методы, оперирующие в вычислениях бесконечностью.
В XX в. стала отчетливо проступать другая проблема. С бесконечностью мы можем разобраться при помощи одного символа (∞), но что делать с числами, которые меньше бесконечности, но при этом невообразимо огромны?
Мы вплотную подошли к числам, едва уступающим «уроборосу», но при этом все еще имеющим теоретическое и практическое значение. Вы, вероятно, могли слышать о числе Грэма, которое является верхней границей для решения определенной проблемы в теории Рамсея. Спустя 88 лет после появления теоремы Рамсея математики готовы отбросить старые методы и пойти еще дальше.
Добро пожаловать в кроличью нору без дна.
Вступление, в котором нужно вспомнить прошлое
В XVII в. математик и философ Блез Паскаль писал о своем страхе перед бесконечностью, о чувстве собственной незначительности при мысли о безбрежных просторах космоса. Интересно, что сказал бы Паскаль о числе Грэма, состоящем из башни чисел высотой от Земли до самой отдаленной звезды, в каждом числе которой прячется своя башня из чисел? Каждый изгиб числа в башне чисел, которая состоит из башни чисел, вмещает в себя башню других чисел — но даже с такой формулировкой мы и близко не подошли к открытию, сделанному Грэмом.
Истоки числа Грэма следует искать в 1928 г., когда молодой математик Фрэнк Рамсей во время работы над статьей о логике заметил удивительную вещь: полная неупорядоченность невозможна. Каждое достаточно большое множество чисел, точек или объектов обязательно содержит высокоупорядоченную структуру.
Догадка, которая была лишь небольшой частью работы о логике, положила начало совершенно новой области математики, называемой теорией Рамсея. Ее часто объясняют на примере вечеринки: предположим, вы хотите найти идеальный баланс между теми, кто знает друг друга, и незнакомцами. Вы рисуете карту отношений всех ваших друзей, связывая двух людей, если они являются друзьями, синей линией, и красной — если они не знакомы друг с другом. Тогда может получиться подобная иллюстрация:
Красота теории Рамсея заключается в том, что задачи в этой области всегда очень легко формулировать. Рассматривая пример с вечеринкой, очень интересно понять, какого количества людей достаточно для образования группы, в которой всегда окажется четверо людей либо знакомых, либо не знакомых друг с другом.
В группе из 17 точек, изображенных на рисунке выше, невозможно найти четыре точки, для которых сеть соединяющих их ребер была бы целиком красной или синей. Поэтому требуется более 17 человек, чтобы среди них обязательно оказалось четверо людей, знакомых или не знакомых друг с другом. На самом деле в группе из 18 человек всегда найдутся либо четверо знакомых, либо четверо не знакомых друг с другом.
Возьмем любое звездное скопление. В нем всегда можно найти группу, которая с очень большой точностью образует какую-нибудь заданную конфигурацию — прямую линию, прямоугольник, ковш.
Математики стараются вычислить, сколь велико должно быть множество звезд, чисел или каких-либо объектов, чтобы можно было гарантировать существование определенной желаемой подструктуры. На решение таких задач часто уходят десятилетия.
Теория Рамсея также имеет большое практическое значение — от организации хорошей вечеринки до построения более совершенных сетей коммуникации и систем передачи и поиска информации. На самом деле очень сложно представить, для каких целей могут послужить многие методы, разработанные для решения задач в теории Рамсея — это самый передовой край математики.
Как и почему Грэм пришел к своему числу
Американский математик Рональд Льюис Грэм (родился в 1935 г.) внес значительный вклад в дискретную математику. Грэм — личность разносторонняя. В свое время он даже был президентом международной ассоциации жонглеров, но прославился исключительно за счет большого положительного целого числа, которое служит верхней границей конкретной проблемы в теории Рамсея.
N-мерный куб всегда содержит 2n вершин. Несмотря на их размерность, n-мерные кубы — это просто графы, вершины которых связаны ребрами
Любой n-мерный куб мы можем превратить в полный граф, просто соединив все вершины. Остальные ребра, сформированные таким образом, находятся внутри или на одной из граней. Представим, что эти края имеют два цвета — красный и синий. Таким образом, Грэм сформулировал интересный вопрос, лежащий в плоскости классической теории Рамсея: при каком минимальном значении N двухцветного k-мерного куба каждая такая раскраска обязательно содержит раскрашенный в один цвет полный подграф с четырьмя вершинами, каждая из которых лежит в одной плоскости?
Полный граф на трехмерном кубе с раскраской ребер в два цвета
В 1971 г. Рональд Грэм и Брюс Ли Ротшильд доказали, что у этой задачи есть решение, и оно представляет собой число, которое больше 6 (нижняя граница), и меньше некоего N. Нижняя граница впоследствии была повышена до 13, а верхняя граница получила название малого числа Грэма. Малое число Грэма меньше числа, попавшего в Книгу рекордов Гиннесса, но это все равно невообразимо огромное число.
В общем-то, задача Грэма не звучит как нечто сверхъестественное — ее может понять и пятиклассник. Но на простые вопросы иногда очень трудно получить ответы. Если решение меньше, чем число Грэма, которое мы знаем, то каков же ответ? Число Грэма, как и некоторые другие большие числа, просто говорит нам, что у некоторой задачи в принципе есть решение, и это решение можно найти. Оптимизировав решение задачи, мы можем сдвинуть число Грэма ближе к 1, и двигать его до тех пор, пока не найдем реального решения.
Как число стало легендой
Итак, Рональд Грэм написал профессиональную математическую работу по теории Рамсея, которая привлекла внимание журналиста Мартина Гарднера. Именно Гарднер ипоспособствовал попаданию числа Грэма в Книгу рекордов Гиннесса, после чего число привлекло внимание широкой общественности.
Проблема, которую Грэм пытался решить, на самом деле была лишь одним конкретным примером применения теории Рамсея. Дальнейшие исследования в этой теории дали математикам бóльшие числа, чем даже число Грэма. Эти числа не являются точным решением проблем, а выступают верхней границей.
Чем же очаровал Грэм людей? Красотой и наглядностью.
Чтобы оперировать гигантскими числами, Грэм использовал быстрорастущие функции. Многие из этих функций знакомы всем — сложение, умножение и возведение в степень. Математики создали новые функции, которые масштабируются намного быстрее.
Для записи числа Грэм использовал стрелочную нотацию Кнута — расширение возведения в степень. Точно так же, как возведение в степень является повторным умножением и обозначается одной стрелкой, направленной вверх, две стрелки вверх обозначают итерационное возведение в степень, три стрелки — повторное итерационное возведение в степень и т.д.
3↑↑5 = 3↑3↑3↑3↑3 = три в степени три в степени 7 625 597 484 987.
Математики поняли, что, имея дело с большими числами, требуется каждый раз использовать новый оператор, который должен быть мощнее предыдущего. ↑↑ — следующий оператором от ↑, так же как ↑ — следующий оператор от умножения, и точно так же, как умножение — это один оператор от сложения. Таким образом, увеличение количества последовательных стрелок увеличивает способность работать с большими числами.
Если добавить еще одну стрелку, то скорость формирования новых чисел значительно возрастет:
3 ↑↑↑ 3 дает нам башню из степеней троек высотой в 7 трлн чисел.
Четыре стрелочки даст число, записать которое будет уже очень трудно. Обратимся к примеру из замечательной статьи «Число Грэма на пальцах»:
А вот оригинальная иллюстрация, которую Гарднер использовал для объяснения числа Грэма:
Самый верхний уровень равен 3 ↑↑↑↑ 3. Формулу вы видели выше. Под ним находится слой, в котором число стрелочек равно 3 ↑↑↑↑ 3. Далее идет слой, в котором число стрелочек равно числу стрелочек в предыдущем слое. И так до 64-го слоя.
Красота этого выражения в том, что если вы захотите превзойти число Грэма и напишите «супербольшое число = число Грэма + 1», то в математических масштабах ничего не изменится. Все равно что залезть на вершину Эвереста и прыгать на ней — Эверест все равно останется самой высокой горой, на вершину которой вы можете взобраться.
Но где-то в Солнечной системе есть и Олимп, не так ли?
Нотация Бауэрса: начало кроличьей норы
Дальнейшая работа с теорией Рамсея математиков Джозефа Краскала и Харви Фридмана привела к числу TREE(3), у которого даже самая нижняя граница решения является сверхогромной, не говоря о верхней.
Если число Грэма мы хотя бы можем записать, то число TREE(3) невозможно поместить в рамки нотации Кнута. Судите сами:
TREE (3) = … > A A(187196) (4), где даже A 2 (4) больше, чем число атомов во Вселенной, ведь А — функция Аккермана, которая определяется рекурсивно для неотрицательных целых чисел m и n следующим образом:
Используя функцию Аккермана, можно очень легко записать число Грэма ≈ A64(4).
Математики вычислили, что у TREE(3) есть теоретическая граница, которую можно записать с помощью массивной нотации, предложенной в 2002 г. Джонатаном Бауэрсом. В массивной нотации существует пять правил:
Функция возрастает невероятно быстро. Массив из трех элементов <10,100,2>в стрелочной нотации Кнута будет иметь следующий вид: 10 ↑ 2 100.
Тройные массивы Бауэрса полностью идентичны тройным цепочкам обозначения Конвея (еще один метод записи — соединенные горизонтальными стрелками (цепочками) числа, растут быстрее нотации Кнута):
<3,3,3>= 3 → 3 → 3 = 3 ^ (3 ^ (3 ^ (3 ^… 7 625 597 484 987 раз… ^ 3) ^ 3) ^ 3)
Массив из четырех элементов (например <10,100,1,2>) уже больше самого числа Грэма — благодаря хитрости, придуманной Бауэрсом: на четвертом элементе он «оптимизирует» формулу, как раньше мы оптимизировали умножение и возведение в степень, только теперь математик занимается удвоением скобок:
Более подробный разбор этой операции вы можете найти в статье «Bird’s Linear Array Notation».
При этом «самое больше число, использованное в серьезном математическом доказательстве», ограничено между <3,65,1,2>и <3,66,1,2>. Речь сейчас идет только о линейных массивах, а ведь они могут быть и гипермерными. В принципе массив Бауэрса из четырех элементов способен вместить в себя всю нотацию Конвея, а гипермерные массивы (на иллюстрации выше) уже становятся математической гиперигрой.
Красота математики в том, что мы можем работать с данными, которые даже представить невозможно. Любую сложную задачу можно облегчить до невероятно простых значений. Возможно, ответы на некоторые вопросы мы никогда не найдем, но методы, использованные для их решения, могут пригодиться в других областях знаний. Сама проработка этих методов построения иерархий по скорости роста функций совершенствует многие разделы математики.
Бауэрс сделал удачную попытку ответить на вопрос, как с помощью иерархии приемов расширить возможности формальной системы. Фактически мы записываем не само число иносказательным образом, а способ когда-нибудь прийти к этому числу хотя бы в теории.
Нотации Бауэрса стали отличной возможностью подобраться к пониманию функции TREE. Конечно, определить величину TREE(3) мы не можем, но с помощью итерационного «улучшения» нотации, проведенного английским математиком Крисом Бердом, удалось выяснить, что TREE(3) > <3,6,3[1[1¬1,2]2]2>.
TREE(3)
TREE — быстрорастущая функция в теории графов, разработанная математиком Харви Фридманом.
Предположим, что мы имеем последовательность k-пронумерованных деревьев T1, T2,… со следующими свойствами:
BIG FOOT является аналогом числа Райо — его определение почти идентично. BIG FOOT расширяет теорию множеств первого порядка, используя уникальную область дискурса, называемую oodleverse, с использованием языка, называемого first-orderoodletheory (FOOT), и обобщая теорию множеств n-го порядка сколь угодно большого n.
Пусть FOOT(n) обозначает наибольшее натуральное число, однозначно определяемое в языке FOOT не более чем в n символах. BIG FOOT определяется как FOOT 10 (10 100 ), где FOOT a (n) — это FOOT(n) (рекурсия).
BIG FOOT таким образом равен
Поиски конечного числа продолжаются. Будет ли оно когда-нибудь найдено?
Блез Паскаль так описал экзистенциальный ужас, охватывающий его при мысли о безграничности мира: «Вечная тишина этого бесконечного пространства пугает меня». Числа дают нам возможность установить рамки понимания и границы дозволенного, взять под контроль страх уробороса. Они — наше реликтовое излучение, возможность подойти к метафорическому краю мира. Но, как в космосе нельзя долететь до такого места, где будет висеть табличка «конец Вселенной», так и в математике невозможно достичь последнего рубежа. Впрочем, это нам еще предстоит проверить.
5 самых старых нерешенных задач Математики о простых числах
Математика была предметом, который веками бросал вызов величайшим умам в истории человечества. Пожалуй, одной из наиболее исследуемых областей Математики является изучение простых чисел.
Наши размышления о закономерностях в простых числах привели к некоторым сложнейшим проблемам, нерешенным даже величайшими математическими гениями. Сегодня мы рассмотрим 5 старейших математических задач о простых числах, которые интуитивно понятны старшекласснику, но все еще не доказаны даже после упорных попыток в течение 500-2000 лет.
1. Совершенные числа: существуют ли нечетные совершенные числа? Бесконечны ли четные совершенные числа?
Рассмотрим числа 6, 28, 496, 8128…
Что в них особенного? Если вы не знаете, то я бы посоветовал сделать небольшую паузу и попытаться найти красивое свойство, которым обладают эти числа.
Если посмотреть на собственные делители этих чисел, то нетрудно заметить то самое «красивое» свойство:
Числа, для которых сумма собственных делителей равна самому числу, называются совершенными числами. Самое раннее исследование совершенных чисел затеряно в истории. Однако, мы знаем, что пифагорейцы 525годдон.э. изучали совершенные числа.
Что мы знаем о таких числах?
Евклид доказал, что для данного n, если 
— простое число, то 
— совершенное число. В качестве упражнения попробуйте доказать это самостоятельно.
Окей, краткий экскурс.
Простые числа Мерсенна: простые числа вида 
для некоторого n. Мерсенн предположил, что все числа вида 
простые, когда n простое. (Мы знаем, что это неправда. Например, 
).
Открытый вопрос: существует ли бесконечно много простых чисел Мерсенна? На данный момент нам известно 47 простых чисел Мерсенна.
В 18 веке Эйлер показал обратное: любое четное совершенное число имеет вид 
Другими словами, существует взаимно однозначное соответствие между четными совершенными числами и простыми числами Мерсенна.
Как видите, мы знаем о четных совершенных числах и способах их получения еще со времен Евклида около300годдон.э.. Но нам неизвестно, существую ли нечетные совершенные числа. насамомделе,прогрессврешенииэтойпроблемыпрактическиотсутствует.
Подводя итог, можно сказать, что изучение совершенных чисел ставит две давние открытые проблемы, а именно «существование нечетных совершенных чисел» и «существование бесконечно большого числа простых чисел Мерсенна».
Евклид (ок. 300 г. до. н. э.) первым доказал то, что простых чисел бесконечно много.
2. Гипотеза о близнецах: простых чисел-близнецов бесконечно много
Простые числа-близнецы — это пара вида (p, p + 2), где p и p + 2 являются простыми числами.
Точное происхождение гипотезы о простых числах-близнецах не установлено. Первая формулировка гипотезы о простых числах-близнецах была дана в 1846 году французским математиком Альфонсом де Полиньяком. Однако греческий математик Евклид дал старейшее из известных доказательств существования бесконечного числа простых чисел. Но он не предполагал, что существует бесконечное число простых чисел-близнецов.
На протяжении 2000 лет в доказательстве этого утверждения практически не было прогресса.
Что мы знаем!
Существует бесконечно много простых пар вида (p, p + k), где k = 4 на самом деле является суммой не более чем 6 простых чисел (т.е. С
Дата-центр ITSOFT — размещение и аренда серверов и стоек в двух дата-центрах в Москве. За последние годы UPTIME 100%. Размещение GPU-ферм и ASIC-майнеров, аренда GPU-серверов, лицензии связи, SSL-сертификаты, администрирование серверов и поддержка сайтов.