Теория чисел

Перевод Математики открыли новый фронт в битве с древней числовой задачей

24.09.2020 14:19:46 |

Автор: admin

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

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

Будучи ещё старшеклассником, Пэйс Нильсен в середине 90-х столкнулся с математическим вопросом, над которым бьётся и по сей день. Но он не расстраивается: очаровавшая его задача, гипотеза о нечётных совершенных числах, остаётся открытой уже более 2000 лет, что делает её одной из старейших нерешённых задач математики.

Частично таким долгоживущим шармом она обязана простоте формулировки. Число называется совершенным, если это положительное целое, n, сумма делителей которого даёт удвоенное число, 2n. Первый и самый простой пример это 6, делители которого, 1, 2, 3 и 6, в сумме дают 12, или 2*6. Затем идёт 28, с делителями 1, 2, 4, 7, 14 и 28, дающими в сумме 56. Следующие примеры 496 и 8128.

Леонард Эйлер формализовал это определение в XVIII веке, введя свою сигма-функцию, обозначающую сумму делителей числа. Таким образом, для совершенных чисел (n) = 2n.

Леонард Эйлер сформулировал множество формальных правил, касающихся работы с совершенными числами

Однако Пифагор знал о совершенных числах ещё в 500 году до н.э., а два столетия спустя Евклид вывел формулу для получения чётных простых чисел. Он показал, что если p и 2^p 1 простые числа (делители которых только 1 и само это число), тогда 2^p1 * (2^p 1) будет совершенным числом. К примеру, если p = 2, то формула даёт 2¹ * (2² 1), или 6. Если p = 3, то формула даёт 2² * (2³ 1), или 28 два первых совершенных числа. 2000 лет спустя Эйлер доказал, что эта формула выдаёт все чётные совершенные числа, хотя до сих пор неизвестно, конечно или бесконечно множество совершенных чисел.

Нильсен, сегодня работающий профессором в Университете Бригама Янга, увлёкся связанным с этим вопросом: существуют ли нечётные совершенные числа? Греческий математик Никомах Герасский около 100 года н.э. заявил, что все совершенные числа должны быть чётными, но никто не доказал этого утверждения.

Как и многие его коллеги из XXI века, Нильсен считает, что совершенные числа существует не особенно много. И, вместе с ними он считает, что доказательство этой гипотезы будет получено нескоро. Однако в июне он наткнулся на новый подход к этой задаче, возможно, способный продвинуть её далее. И он связан с ближайшим к нечётным совершенным числам объектом из всех пока обнаруженных.

Сжимающаяся сеть

Впервые Нильсен узнал о совершенных числах на соревновании по математике в школе. Он углубился в литературу, и наткнулся на работу 1974 года Карла Померанца, математика, сегодня служащего в Дартмутском колледже. Тот доказал, что у любого нечётного совершенного числа должно быть не менее семи различных простых множителей.

Я в своей наивности решил, что я могу сделать что-то в этой области, если в ней вообще возможен прогресс, сказал Нильсен. Это вдохновило меня на изучение теории чисел в колледже, и попытки развить прогресс. Его первая работа по нечётным совершенным числам, опубликованная в 2003 году, наложила дополнительные ограничения на эти гипотетические числа. Он показал, что не только количество нечётных совершенных чисел с k различными простыми делителями конечно, как доказал в 1913 году Леонард Диксон, но и что размер этого числа не должен превышать 2^{4^k}.

И это было не первым и не последним ограничением, наложенным на гипотетические нечётные совершенные числа. К примеру, в 1888 году Джеймс Сильвестер доказал, что нечётное совершенное число не может делиться на 105. В 1960 году Карл К. Нортон доказал, что, если нечётное совершенное число не делится на 3, 5 или 7, у него должно быть не менее 27 простых делителей. Пол Дженкинс в 2003 году доказал, что крупнейший простой делитель нечётного совершенного числа должен быть больше 10 000 000. Паскаль Очем и Михаёль Рао после этого обнаружили, что нечётное совершенное число должно быть больше 10¹⁵⁰⁰, а потом отодвинули эту границу до 10²⁰⁰⁰. Нильсен в 2015 году показал, что нечётное совершенное число должно иметь не менее 10 различных простых делителей.

Пэйс Нильсен, математик из Университета Бригама Янга

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

Доказать существование чего-либо легко, если получится найти хотя бы один пример, сказал Джон Войт, профессор математики из Дартмута. Но доказать, что нечто не существует, может быть очень тяжело.

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

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

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

Разбираемся в совершенных числах

Сигма-функция обозначает сумму делителей числа. (n) = 2n, если это совершенное число.

Примеры:

(20) = 1 + 2 + 4 + 5 + 10 + 20 = 42; 2 * 20 42, поэтому 20 не совершенное число.
(28) = 1 + 2 + 4 + 7 + 14 + 28 = 56; 2 * 28 = 56, поэтому 28 совершенное число.

Правила Эйлера

1. (a b) = (a) (b) в том, и только в том случае, если a и b взаимно простые.
2. (p^a) = 1 + p + p² + + p^a для любого простого p с положительной целой степенью a.

Примеры:

(20) = (2² 5) = (2²) (5) [по первому правилу] = (1 + 2 + 2²)(1+5) [по второму правилу] = 42

(28) = (2² 7) = (2²) (7) [по первому правилу] = (1 + 2 + 2²)(1+7) [по второму правилу] = 56

Новые соблазнительные промахи

Первую имитацию нечётного совершенного числа нашёл в 1638 году Рене Декарт и он был одним из первых выдающихся математиков, посчитавших возможным существование нечётных совершенных чисел. Я считаю, что Декарт пытался найти нечётные совершенные числа, и его вычисления привели его к первой имитации, сказал Уильям Бэнкс, специалист по теории чисел из Университета Миссури. Судя по всему, Декарт надеялся, что созданное им число можно изменить, получив настоящее нечётное совершенное число.

Но прежде чем углубиться в декартовскую имитацию, полезно будет немного разобраться в том, как математики описывают совершенные числа. Теорема времён Евклида утверждает, что любое целое число, большее 1, можно выразить в виде произведения простых чисел, возведённых в определённые степени. К примеру, 1260 можно так разложить на множители: 1260 = 2² 3² 5¹ 7¹, и не перечислять все 36 множителей по отдельности.

Если число принимает такую форму, вычислять сигма-функцию Эйлера, суммирующую его делители, становится гораздо проще благодаря двум формулам, которые тоже доказал Эйлер. Во-первых, он продемонстрировал, что (a b) = (a) (b), тогда, и только тогда, когда a и b взаимно простые то есть, у них нет общих простых делителей. К примеру, числа 14 (2 7) и 15 (3 5) взаимно простые. Во-вторых, он показал, что для любого простого числа p в положительной целой степени a, (p^a) = 1 + p + p² + + p^a.

Возвращаясь к нашему предыдущему примеру, (1 260) = (2² 3² 5¹ 7¹) = (2²) (3²) (5¹) (7¹) = (1 + 2 + 2²)(1 + 3 + 3²)(1 + 5)(1 + 7) = 4 368. Обратите внимание, что в данном случае (n) не равняется 2n, а, значит, 1260 не совершенное число.

Рене Декарт нашёл первую имитацию совершенного числа

Теперь мы можем разобрать декартову имитацию число 198 585 576 189, или 3² 7² 11² 13² 22 021¹. Повторяя описанные выше вычисления, мы обнаружим, что (198 585 576 189) = (3² 7² 11² 13² 22,021¹) = (1 + 3 + 3²)(1 + 7 + 7²)(1 + 11 + 11²)(1 + 13 + 13²)(1 + 22,021¹) = 397 171 152 378. И это равно удвоенному изначальному числу, что означает, что оно должно быть настоящим совершенным числом вот только число 22 021 не является простым.

Поэтому это число Декарта является имитацией. Если мы притворимся, что 22 021 простое, и применим правила Эйлера для сигма-функции, число Декарта ведёт себя как совершенное число. Однако 22 021 на деле является произведением 19² и 61. Если бы мы правильно записали число Декарта, как 3² 7² 11² 13² 19² 61¹, тогда (n) не равнялась бы 2n. Ослабляя некоторые правила, мы получаем число, вроде бы удовлетворяющее нашим требованиям такова суть имитации.

На то, чтобы открыть второе число-имитацию нечётного совершенного числа, ушёл 361 год. Войт сделал это в 1999 году, и опубликовал открытие через четыре года. Почему так долго? Находка числа-имитации похожа на находку нечётного совершенного числа; оба они сходным образом арифметически сложны, сказал Бэнкс. Да и их поиски не были в приоритете у математиков. Однако Войта вдохновил отрывок из книги Ричарда Гая Нерешённые задачи теории чисел, где писали о поисках новых имитаций. Войт попытался, и в итоге нашёл новую имитацию, 3⁴ 7² 11² 19² (127)¹, или 22 017 975 903.

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

Имитации нечётных совершенных чисел

Число Декарта:

198 585 576 189, или 3² 7² 11² 13² 22 021¹.

Повторим вычисления сигма-функции: (198 585 576 189) = (3² 7² 11² 13² 22,021¹) = (1 + 3 + 3²)(1 + 7 + 7²)(1 + 11 + 11²)(1 + 13 + 13²)(1 + 22,021¹) = 397 171 152 378 = 2 198 585 576 189.

Но число 22 021 не является простым, это 19² 61. Число Декарта является лишь имитацией нечётного совершенного числа.

Число Войта:

22 017 975 903, или 3⁴ 7² 11² 19² (127)¹.

Повторим вычисления сигма-функции: (22 017 975 903) = (3⁴ 7⁴ 11² 19² (-127)¹) = (1 + 3 + 3² + 3³ + 3⁴)(1 + 7 + 7²)(1 + 11 + 11²)(1 + 19 + 19²)(1 + (-127)¹) = -44 035 951 806 = 2 22 017 975 903

-127 число отрицательное, поэтому число Войта ещё одна имитация совершенного числа.

После того, как Войт в декабре 2016 года провёл семинар в университете Бригама Янга, он обсудил это число с Нильсеном, Дженкинсом и другими. Вскоре после этого команда университета отправилась на систематические вычислительные поиски других имитаций. Они выбирали наименьшие основания и показатели степени, вроде 3², и потом компьютеры прочёсывали варианты дополнительных оснований и степеней, которые давали бы имитацию совершенного числа. Нильсен решил, что этот проект просто будет неким стимулирующим опытом исследований для его студентов, однако результаты анализа превзошли его ожидания.

Просеивая возможности

После непрерывной работы 20 процессоров в течение трёх лет, команда обнаружила все возможные имитации совершенного числа, которые можно записать при помощи шести или менее оснований всего 21 штука, включая примеры Декарта и Войта а ещё две имитации с семью делителями. Искать имитации с большим числом делителей на компьютерах было непрактично, и слишком затратно по времени. Тем не менее, группа набрала достаточно примеров для того, чтобы открыть неизвестные ранее свойства имитаций.

Группа обнаружила, что для любого заданного количества оснований, k, существует конечно число имитаций, что совпадает с результатом Диксона от 1913 года для настоящих нечётных совершенных чисел. Однако если k уйдёт в бесконечность, количество имитаций также становится бесконечным, сказал Нильсен. Это было неожиданно, добавил он, учитывая, что начиная этот проект, он не был уверен в открытии хотя бы одной новой нечётной имитации, не говоря уже о том, чтобы показать, что их число бесконечно.

Ещё один сюрприз, зародившийся из результата, впервые доказанного Эйлером: все простые основания нечётного совершенного числа, кроме одного, должны иметь чётные степени. Одно должно иметь нечётную степень она называется степенью Эйлера. Большинство математиков считает, что степень Эйлера для нечётных совершенных чисел всегда 1, однако команда показала, что у имитаций она может быть сколько угодно большой.

Некоторые находки команда обнаружила, ослабив требования в определении имитации, поскольку не существует чётких математических правил для их описания только то, что они должны удовлетворять равенству (n) = 2n. Исследователи допустили существование оснований, не являющихся простыми числами (как в примере Декарта) и отрицательных оснований (как в примере Войта). Однако они пошли дальше, разрешив имитациям иметь несколько одинаковых оснований. Одно основание, к примеру, может быть 7², а другое 7³, и записываются они отдельно, а не как 7⁵. Или они позволяли основаниям повторяться, как в имитации 3² 7² 7² 13¹ (19)². Член 7² 7² можно записать как 7⁴, но тогда имитации не получится, потому что раскрытие скобок в изменённой сигма-функции было бы другим.

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

Путь вперёд?

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

Любое поведение более крупного множества должно соблюдаться и для мелкого подмножества, сказал Нильсен. Так что, если мы найдём поведение имитаций, неприменимое к более ограниченному классу, мы автоматически сможем отказаться от возможности существования нечётных совершенных чисел. Если, к примеру, можно будет показать, что все имитации делятся на 105 что невозможно для нечётных совершенных чисел, как Сильвестер показал в 1888 тогда задача будет решена.

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

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

Другие эксперты по нечётным совершенным числам настроены не так оптимистично. Команда из университета Бригама Янга проделала отличную работу, сказал Войт, но я не уверен, что мы приблизились к вариантам атаки на проблему нечётных совершенных чисел. Это и правда задача на века, и, вероятно, она будет таковой оставаться.

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

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

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

Эта задача кажется более трудной, сказал Нильсен, поскольку она касается более крупной и общей категории чисел. Но иногда, когда ты преобразуешь задачу в более, казалось бы, сложную, можно увидеть путь к решению.

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

Подробнее..

Категории: Научно-популярное , Математика , Совершенные числа , Эйлер , Теория чисел

Закономерности в распределении простых чисел

26.12.2020 14:17:21 |

Автор: admin

<meta http-equiv="content-type" content="text/html; charset=utf-8"><title></title><meta name="generator" content="LibreOffice 7.0.3.1 (Windows)"><meta name="created" content="00:00:00"><meta name="changed" content="00:00:00"><style type="text/css">    @page { size: 21cm 29.7cm; margin: 2cm }    p { text-indent: 0.3cm; margin-bottom: 0.6cm; line-height: 120%; background: transparent }    a:visited { color: #800000; so-language: zxx; text-decoration: underline }    a:link { color: #000080; so-language: zxx; text-decoration: underline }</style>

Введение

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

Ещё до нашей эры Евклид сформулировал и доказал первые теоремы о простых числах. С тех пор математики, среди них Гаусс, Ферма, Риман, Эйлер, продолжали исследования и надо отдать им должное заметно продвинулись. Было обнаружено много интересных свойств простых чисел, выдвинуто много предположений, некоторые из которых были доказаны. Однако много гипотез связанных с простыми числами до сих пор остаются необоснованными.

Распределение простых чисел

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

Получить рекуррентную формулу для очередного простого числа

$p_{n+1} = f(n, p_1, p_2, ...,p_n),$

p_n n-е простое число (p₁ = 2, p₂ = 3, p₃ = 5, ... )

Существует родственная ей задача о количестве простых чисел, не превосходящих заданной величины:

Найти функцию p(x), значение которой в точке x равно числу простых чисел на отрезке [1, x]. Где x любое действительное число не меньшее единицы.

Функция $\pi(x)$ называется функцией распределения простых чисел.

К решению вышеуказанных задач существует множество подходов. Рассмотрим некоторые из них.

Основная теорема арифметики гласит, что любое натуральное число большее единицы может быть представлено в виде произведения простых множителей (причём единственным образом, с точностью до порядка множителей).

Отсюда и из определения простого числа следует, что натуральное число, большее двух, является простым тогда и только тогда, когда оно не делится ни на одно из простых чисел меньших самого себя.

Первое простое число p₁ =2. Значит все последующие простые числа должны не делиться на 2, то есть иметь вид 2k+1, где k натуральное. То есть все простые числа начиная со второго нечётные.

Второе простое число p₂ = 3. Значит все последующие простые числа должны иметь вид 3m+1, либо 3m+2, где m целое. Это равносильно утверждению о том, что все простые числа начиная с третьего не делятся на три. Однако при этом числа ещё должны не делиться на два, то есть иметь вид 2k+1.

Решая диофантовы уравнения

$\begin{array}{} {2k + 1 = 3m+1, \\ 2k+1= 2m+2,} \end{array}$

найдём k и m и получим, что все простые числа начиная с p₃ обязательно представимы в виде p=6t+1 , либо в виде p = 6t+5 , где t целое.

И правда, какое бы простое число мы не взяли оно представимо таким образом:

$\begin{array}{} {5 = 6*0 +5, \\ 7 = 6*1 + 1,\\ 11 = 6*1 + 5,\\13 = 6*2+1.} \end{array}$

Однако обратное не верно, то есть любое натуральное число вида 6k+1 или 6k-1 не обязательно простое. Например, 25 = 6*4+1 .

Третье простое число p₃ = 5. И если по аналогии учесть, что любое простое число начиная с четвёртого не делиться на 5, также не делится на p₁ = 2 и на p₂ = 3, то получим, что все простые числа начиная с p₄ обязательно имеют одно из представлений

$\begin{array}{} {p=30t+1, \;\;\;\;\;\; p=30t+11,\\ p=30t+7, \;\;\;\;\;\; p= 30t+17,\\p=30t+13, \;\;\;\; p=30t+23,\\ p=30t+19, \;\;\;\; p=30t+29} \end{array}$

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

На самом деле, при различных попытках решения поставленной нами задачи в большом количестве случаев появляются одни и те же конструкции. Например, произведение Эйлера. Рассмотрим, как это происходит, на следующем примере.

Часто легче оценивать не сами простые числа, а их количество на заданном промежутке. Допустим нам окажется известна функция F(x) которая позволяет найти количество чисел, не превосходящих x и не кратных ни одному из простых p₁, p₂, , p_n? Почему она нам нужна? Да потому что первое из чисел (не считая единицы), которые не делятся ни на p₁, ни на p₂, , ни на p_n - это p_n+1 (этот факт легко доказать с помощью основной теоремы арифметики и определения простого числа). Таким образом, F(p_n+1 -1) = 1 (одно число единица), F(p_n+1) = 2 (единица и p_n+1). И, зная это свойство функции F(x) и её аналитическое выражение, мы могли бы получить некое выражение для p_n+1.

Итак, как же найти функцию F(x)? Сначала рассмотрим множество всех натуральных чисел. Какова доля чисел, которые не делятся ни на одно из простых p₁, p₂, , p_n?

Каждое второе число делится на p₁ = 2. Значит, $\frac {1}{2}$ часть всех чисел делится на p₁.

Каждое третье число делится на 3. Значит, $\frac {1}{3}$ всех чисел делится на p₂. При этом надо учесть, что каждое шестое число делится и на 2 и на 3 одновременно.

Значит, доля чисел не делящихся ни на 2, ни на 3 равна

$1 - \frac {1}{p_1}-\frac {1}{p_2}+\frac {1}{p_1*p_2} = 1 - \frac {1}{2}-\frac {1}{3}+\frac {1}{2*3}.$

Если преобразовать выражение, то оно примет вид:

$(1-\frac{1}{p_1})(1-\frac{1}{p_2})$

Действуя по аналогии получим, что доля натуральных чисел не делящихся на p₁, p₂, , p_n , равна

$1 - \frac {1}{p_1}-\frac {1}{p_2}-...- \frac {1}{p_n}+\frac {1}{p_1*p_2}+\frac {1}{p_1*p_3}+...+\frac {1}{p_{n-1}*p_{n}}-\frac {1}{p_1*p_2*p_3}-...+(-1)^n\frac{1}{p_1*p_2*...*p_n}.$

Опять же можно представить выражение в виде

$P(n) = (1-\frac{1}{p_1})(1-\frac{1}{p_2})(1-\frac{1}{p_3})...(1-\frac{1}{p_n})\qquad\qquad(1)$

Будем обозначать такое произведение P(n). Кстати, если учесть все простые числа (n), то мы получим обратную величину от так называемого произведения Эйлера.

Сразу возникает желание сказать, что функция F(x) = x*P(n) . Но проблема в том, что P(n) описывает долю чисел не кратных первым n простым среди всех натуральных чисел. А если описывать долю чисел не кратных первым n простым среди чисел от 1 до N, где N - конечно, с помощью P(n), то будет возникать погрешность.

Почему так происходит? Когда мы получали формулу (1), мы пользовались рассуждениями, что среди всех натуральных чисел доля, делящихся на p_n, равна $\frac{1}{p_n}$ . Но нельзя сделать такое утверждение о конечном наборе последовательных натуральных чисел. Например, возьмём набор 1,2, 3,4,5,6,7,8,9. Здесь 4 числа из 9 делятся на два. И не сложно заметить, что $\frac{4}{9}$ отличается от $\frac{1}{2}$ . То есть при применении к конечному набору чисел, данный метод даёт результат с некоторой погрешностью.

Это будет мешать далее получать точные формулы. Но если оценить эту погрешность, то можно (например, приняв и используя приведённые выше рассуждения) получить оценку для p_n+1-го простого числа. Однако, получение таких оценок это тема отдельной работы. И поэтому здесь я не буду на этом останавливаться, а приведу лишь некоторые результаты, полученные математиками.

Одна из оценок для простого числа с номером n:

$n*ln(n)+n *ln(ln(n))-\frac{3}{2}n<\pi(x)<n*ln(n)+n *ln(ln(n))$

оценка верна для всех n, начиная с 6.

А вот формула для функции распределения простых чисел:

$\frac{x}{ln(x)}<\pi(x)<1,25506\frac{x}{ln(x)}$

Для функции $\pi(x)$ Риман получил приближение, используя интегральный логарифм и нетривиальные нули дзета-функции Римана. Однако, это приближение верно, только если верна гипотеза Римана. Причём если гипотеза Римана верна, то оно является наилучшим.

Гипотеза Римана до сих пор не доказана и не опровергнута. Она, как мы могли видеть она тесно связана с простыми числами и, вообще, имеет огромное значение для теории чисел. Из-за своей важной роли в математике, гипотеза Римана была объявлена одной из семи задач тысячелетия.

Проблемы Ландау

Насчёт простых чисел выдвинуто очень много интересных гипотез. Среди них видное место занимают гипотезы Ландау (проблемы Ландау). Формулируются они так:

1. Гипотеза Гольдбаха

Можно ли любое целое чётное число, большее 2, записать в виде суммы двух простых?

2. Гипотеза о числах-близнецах

Бесконечно ли число простых p таких, что p + 2 тоже простое?

3. Гипотеза Лежандра

Всегда ли существует по меньшей мере одно простое число, лежащее между двумя последовательными полными квадратами?

4. Гипотеза о почти квадратных простых числах

Существует ли бесконечно много простых чисел p вида .

Проблемы Ландау ни доказаны, ни опровергнуты по состоянию на 2020 год. Далее кратко расскажу про каждую из них.

1. Гипотеза Гольдбаха

Существуют две гипотезы Гольдбаха: слабая (тернарная) и сильная (бинарная).

Слабая гипотеза Гольдбаха: Каждое нечётное число, большее 5, можно представить в виде суммы трёх простых чисел.

Эту гипотезу доказал Харольд Гельфготт в 2013 году используя так называемые большие дуги. Финальная часть доказательства заняла 133 страницы.

Сильная гипотеза Гольдбаха: Каждое чётное число, большее двух, можно представить в виде суммы двух простых чисел.

Надо заметить, что в обоих случаях гипотезы Гольдбаха простые числа не обязательно должны быть различными.

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

Но переформулируем проблему так: существует ли такое число, что любое нечётное, большее этого числа, представимо в виде суммы двух простых чисел? Давайте проверим. Пусть существует некоторое нечётное натуральное число N, такое, что любое нечётное число представимо в виде суммы двух простых чисел.

Возьмём произвольное нечётное $K \geq N$ . По предположению существуют такие простые p₁ и p₂, что K = p_1 + p_2 . Если сумма двух натуральных чисел нечётна, то это значит, что одно из слагаемых чётно, а другое нет. Пусть для определённости p₁ чётное. Единственное чётное простое число это 2. Значит, $2+p_2=K \rightarrow p_2 = K-2$ . То есть, K-2 (предыдущее перед K нечётное число) является простым. Поскольку всё вышесказанное верно для любого нечётного большего N, то получается, что все нечётные числа, начиная с N-2, являются простыми. Это неверно. Если бы это было так, то $\pi(n) \rightarrow \frac{n}{2}$ при n . Однако, как говорилось выше $\pi(n) \rightarrow n*ln(n)$ при n .

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

А что же насчёт чётных? Гипотеза не была опровергнута, не было найдено ни одного контрпримера. Но это не значит, что их не существует. Доказать же гипотезу полностью пока никому не удалось.

2. Гипотеза о числах-близнецах

Бесконечно ли число простых чисел близнецов?

Для начала сформулируем определение. Два простых числа называются близнецами если отличаются друг от друга на 2.

Примеры: 5 и 6, 11 и 13, 41 и 43.

Чэнь Цзинжунь доказал, что существует бесконечно много чисел p таких, что p+2 - простое или полупростое. Полупростое число число, представимое в виде произведения двух простых чисел.

Так же доказано, что существует бесконечно много простых чисел, разница между которыми составляет 246. Это наилучшая из обоснованных на данный момент оценок. Если же использовать некоторые недоказанные гипотезы о простых числах, то оценку можно улучшить.

3. Гипотеза Лежандра

Всегда ли существует, по меньшей мере, одно простое число, лежащее между двумя последовательными полными квадратами?

Аналогичная гипотеза доказана для кубов, начиная с некоторого n. То есть, существует, по меньшей мере, одно простое число, лежащее между n^3 и n^3+1 для достаточно большого n. Для квадратов же, гипотеза Лежандра пока не доказана.

4. Почти квадратные простые числа

Существует ли бесконечно много простых чисел p вида ?

Можно точно утверждать, что не существует простых чисел вида n^2 - 1 , кроме p = 3. Действительно, n^2 - 1 = (n-1)(n+1) , где множители $n-1\; и \; n+1$ различные натуральные числа, отличные от 1 и от n во всех случаях кроме n = 2. Значит число вида n^2-1 составное для всех n > 2 . А вот с числами вида n^2 + 1 всё немного сложнее. Однако удалось, например, доказать, что существует бесконечно много чисел вида n^2+1 , которые являются или простыми, или полупростыми.

Заключение

Как мы видим, в этой области теории чисел существует очень много пробелов, а также недоказанных гипотез. Отдельно хочется сказать про численную проверку утверждений. Например, ни для одной из гипотез Ландау не был найден контрпример, даже с использованием значительных вычислительных мощностей в течение большого времени. Однако, в истории математики 20-го и 21-го века были случаи, когда контрпример, опровергающий гипотезу, был настолько огромным числом, что его не удавалось найти с помощью вычислительных машин.

Также, постоянный интерес к простым числам обусловлен их обширным применением в криптографии. Итак, как мы убедились, исследование простых чисел это, действительно, важная и очень интересная задача.

Подробнее..

Категории: Научно-популярное , Математика , Теория чисел , Простые числа , Проблемы ландау , Распределение простых чисел

Нумерология никакого гадания, только теория чисел

10.05.2021 12:10:00 |

Автор: admin

В данной статье речь пойдёт о таких понятиях теории чисел, как цифровой корень и ведический квадрат.

Данная статья ничего не говорит о нумерологии, кроме того, что это псевдонаучная концепция.

Цель данной статьи: показать математические закономерности вокруг вычисления цифрового корня и его связь с циклическими числами.

Введение

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

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

Сумма цифр и цифровой корень

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

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

Пример:Цифровая сумма числа 142857 равна 1 + 4 + 2 + 8 + 5 + 7 = 27

Цифровая сумма числа 27 равна 2 + 7 = 9

Как следствие, цифровой корень числа 142857 = 9, аддитивная стойкость 142857 = 2.

Код для вычисления цифрового корня в произвольной системе счисления, на языке Python:

def digitalRootRecurrent(number, base):    digitSum = 0    while number > 0:        digitSum += number % base         number //= base    if digitSum >= base:        digitSum = digitalRoot(digitSum, base)    return digitSum

Применение цифровой суммы

Цифровые суммы применялись при расчёте контрольных сумм для проверки арифметических операций ранних компьютеров. Ранее, в эпоху ручного счета, Фрэнсис ИсидорЭджуортпредложил использовать суммы 50 цифр, взятых из математических таблиц логарифмов, в качестве формы генерации случайных чисел; если предположить, что каждая цифра случайна, то по центральной предельной теореме эти цифровые суммы будут иметь случайное распределение, близкое к гауссову распределению.

Цифровая сумма двоичного представления числа известна как вес Хэмминга или численность населения. Алгоритмы выполнения этой операции были изучены, и она была включена в качестве встроенной операции в некоторые компьютерные архитектуры и некоторые языки программирования. Эти операции используются в вычислительных приложениях, включая криптографию, теорию кодирования и компьютерные шахматы.

Улучшение алгоритма вычисления цифрового корня

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

Модифицированный код:

def digitalRoot(number, base):    digitSum = 0    while number > 0:        digitSum += number % base         number //= base    digitSum %= base - 1    if digitSum == 0:        digitSum = base - 1    return digitSum

Свойства цифрового корня

Операция сложения

Сделаем небольшую таблицу, для того чтобы изучить закономерности, каким образом вычисляется цифровой корень суммы двух чисел:

Таблица для анализа операции цифрового корня суммы двух чисел.

Код для построения таблицы суммы:

firstTermRangeStart = 2firstTermRangeEnd = 8secondTermRangeStart = 1secondTermRangeEnd = 9base = 10for j in range(firstTermRangeStart, firstTermRangeEnd + 1):    print()    for i in range(secondTermRangeStart, secondTermRangeEnd + 1):        if i % (secondTermRangeEnd + 1) == 0:            print()        print('dr(',j,'+', i, ') =', digitalRoot(j + i, base), ' ', end='')

Как можно увидеть, цифровой корень суммы чисел равен цифровому корню суммы цифровых корней каждого отдельного числа:

$dr_{base}(a1 + a2) = dr_{base}(dr_{base}(a1) + dr_{base}(a2))$

Операция вычитания

Формула похожа на предыдущую, однако совпадает не полностью.

Приведемконтрпример: 455- 123 = 332.

$dr_{10}(455)=5; dr_{10}(123) = 6; dr_{10}(322) = 8$

Как можно отметить выражение 4 - 6 не даёт в результате 8, потому формулу сложения нужно модифицировать, чтобы она работала для операции вычитания:

$dr_{base}(a1 - a2) = dr_{base}(base - 1 + dr_{base}(a1) - dr_{base}(a2))$

Операция умножения

Выведем вариацию таблицы умножения, длятогочтобы исследовать эту операцию:

Расчет цифрового корня от двух множителей

Код для вывода таблицы умножения:

firstTermRangeStart = 1firstTermRangeEnd = 8secondTermRangeStart = 1secondTermRangeEnd = 9base = 10for i in range(secondTermRangeStart, secondTermRangeEnd + 1):    print()    for j in range(firstTermRangeStart, firstTermRangeEnd + 1):        print('dr(',j,'*', i, ') =', digitalRoot(i * j, base), ' ', end='')

Запишем значения для каждого множителя:

1) [1, 2, 3, 4, 5, 6, 7, 8, 9]

2) [2, 4, 6, 8, 1, 3, 5, 7, 9]

3) [3, 6, 9, 3, 6, 9, 3, 6, 9]

4) [4, 8, 3, 7, 2, 6, 1, 5, 9]

5) [5, 1, 6, 2, 7, 3, 8, 4, 9]

6) [6, 3, 9, 6, 3, 9, 6, 3, 9]

7) [7, 5, 3, 1, 8, 6, 4, 2, 9]

8) [8, 7, 6, 5, 4, 3, 2, 1, 9]

9) [9, 9, 9, 9, 9, 9, 9, 9, 9]

Можно видеть, что последовательности разбиваются на пары 1 и 8, 2 и 7, 3 и 6, 4 и 5. В каждой из пар сохраняется та же самая последовательность, но они представляют собой реверсированные копии друг друга, за исключением последнего элемента, который связан с множителем, равным основанию системы счисления - 1.

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

Визуализация последовательностей:

Последовательности для множителей 1, 2, 3, 4. Они же являются зеркальными для 8, 7, 6, 5.

Последовательностиможно рассмотреть, как множество всех возможных замкнутых фигур с количеством точек равным основанию системы счисления - 1, начиная с правильного n-угольника.Исключением является множитель который не является взаимно простым с основанием счисления - 1, в данном случае это 3 и 6.

Для нахождения последовательности любой линии можно записать формулу:

$multiplicationLine(firstFactor, secondFactor, base) = firstFactor * secondFactor \mod base.$

Если записать эти значения как множество пересечений всех множителей, мы получим в результате ведический квадрат.

Ведический квадрат для десятичной системы счисления.

Подмножество данного ведического квадрата формирует собой латинский квадрат. Чтобы получить его, нужно вычеркнуть элементы, равные основанию системы счисления - 1.

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

В результате мы получим:

Подмножество ведического квадрата составляющее ведический квадрат, в десятичной системе счисления.

Если переставить некоторые из его строчек местами, мы получим последовательность циклических чисел. О том, каким образом должны быть осуществлены перестановки строчек, будет описано ниже, при исследовании других операций вместе с цифровым корнем.

Ниже приведена ещё одна картинка ведических квадратов, для систем счисления 100 и 1000. Белым отмечены самые большие значения клеток соответствующие основанию системы счисления - 1, черным самые маленькие, соответствующие 1.

Ведические квадраты для систем счисления 100 и 1000.

Теперь вернемся к произведению. Цифровой корень произведения одиночных цифр, в заданной системе счисления, вычисляется при помощи соответствующего ведического квадрата.

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

$dr_{base}(a1 * a2) = dr_{base}(dr_{base}(a1) * dr_{base}(a2))$

Операция деления

Рассмотрим те числа, которые дают при делении непериодические дроби, это 2, 5, 4, 8.

Для того чтобы быть уверенными, что мы не допускаем ошибок, воспользуемся уже выведенными правилами и умножим результат деления на 1000; так как цифровой корень 1000 равен 1, то произведение будет иметь тот же самый цифровой корень.

Таблица деления для делителей, которые взаимно просты с десятичной системой счисления.

base = 10divisors = [2, 4, 5, 8]for j in divisors:     print()    for i in range(1, base):        value = (digitalRoot(int((i / j) * (base ** 3)), base))        print('dr(',i, '/', j, ') =', value, '  ', end='')

Тут бросаются в глаза несколько закономерностей.Число 9 не только при умножении, но и при делении приводит к значению цифрового корня, равному 9. Интересное происходит с числами 3 и 6, эти числа как при умножении, так и при делении дают абсолютно одинаковые значения цифрового корня.

Запишем в таблицу череду делений:

2) [5, 1, 6, 2, 7, 3, 8, 4, 9] - Эта последовательность встречалась в множителе 5

4) [7, 5, 3, 1, 8, 6, 4, 2, 9]- Эта последовательность встречалась в множителе 7

5) [2, 4, 6, 8, 1, 3, 5, 7, 9] - Эта последовательность встречалась в множителе 2

8) [8, 7, 6, 5, 4, 3, 2, 1, 9] - Эта последовательность встречалась в множителе 8, так же

Операция деления для цифрового корня определена только для делителей, которые не являются взаимно простыми с основанием системы счисления.

Операция возведения в степень

Таблица возведения в степень:

Таблица возведения в степень, в десятичной системе счисления.

base = 10.for i in range(2, base - 2):    print()    for j in range(1, base - 1):        print('dr(', j ,'^', i, ') =', digitalRoot(i ** j, base), ' ', end='')

Здесь мы можем наблюдать цикличность.

При внимательном рассмотрении других систем счисления можно сделать вывод, что эта череда связана с формированием остатков от деления, и таким образом она связалась с моим любимым классом простых чисел -fullreptendprime.

Для того чтобы пояснить это, рассмотрим операции возведения в степень в других системах счисления. Забегая вперед, скажу: наиболее интересными будут являться такие степени счисления, которые равныp^n+ 1, где p это простое число, а n - натуральное.

Рассмотрим систему счисления 8, череда его значений будет равна [1, 3, 2, 6, 4, 5]. Именно такие же остатки от деления мы получаем при делении числа в десятичной системе счисления.

Деление в столбик, 1 на 7. Здесь мы можем наблюдать остатки от деления [1, 3, 2, 6, 4, 5].

Последовательность полученная при возведении в степень, в восьмеричной системе счисления.

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

$dr_{base}(n) = n - (base - 1) * \lfloor\frac{n-1}{base-1}\rfloor$

Ещё визуализации

Приведём ниже визуализации для операции возведения в степень для разных систем счисления, все они будут связанны с паттернами образующимися в рациональных дробях 1/P, где P это full reptend prime.

Остатки от деления, найденные в 6 системе счисления, связанные с числом 5.

Остатки от деления, найденные в 10 системе счисления, связанные с квадратом числа 3.

Остатки от деления, найденные в 12 системе счисления, связанные с числом 11.

Остатки от деления, найденные в 14 системе счисления, связанные с числом 13.

Остатки от деления, найденные в 18 системе счисления, связанные с числом 17.

Остатки от деления, найденные в 20 системе счисления, связанные с числом 19.

Остатки от деления, найденные в 26 системе счисления, связанные с квадратом числа 5.

Остатки от деления, найденные в 28 системе счисления, связанные с кубом числа 3.

Теперь приведём несколько картинок из ведических квадратов, принцип их формирования очень прост, потому ограничимся небольшимколичеством:

Замкнутая фигура из 6ой системы счисления, связанна с числом 5.

Замкнутые фигуры из 8 системы счисления, связанны с числом 7.

Замкнутые фигуры из 12 системы счисления, связанные с числом 11.

Образование циклических чисел при помощи ведической площади и остатков от деления

После того как мы получили латинский квадрат из ведического квадрата, пронумеруем его строки последовательно:

Пронумерованный латинский квадрат.

Теперь мы можем переставить строки на основании череды остатков от деления, таким образом мы получим последовательность циклических чисел. Напомню остатки от деления были равны [1, 3, 2, 6, 4, 5]. В результате у нас получится следующая картина:

Перестановки в пронумерованном латинском квадрате, в результате мы получили циклические числа.

Как можно наблюдать - каждый столбец теперь представляет собой вариации циклического числа 142857.

Выводы

Несмотря на плохую репутацию нумерологии, операции суммы цифр и цифрового корня имеют пусть не широкое, но всё же практическое применение.

Например,с помощью цифрового корня можно сформировать множество замкнутых n-вершинных звезд, многие из которых очень любят современные рок\метал группы:)

Пентаграмма - в представлении не нуждается :) Ороборус тут не случайно, о нем в следующей статье!

Tool предпочитают 8 систему счисления, связанную с простым числом 7.

Slipknot тяготеют к десятеричной системе счисления, связанной с квадратом числа 3.

Как можно видеть, многие метал группы тоже любят теорию чисел!

Но лично я для свой метал группы решил выбрать анимированный логотип, составленный из одновременной визуализации периодических дробей, образованных из 90 рациональных дробей 1/91..90/91:

Почему я выбрал число 91, которое является произведением 7 и 13? Речь об этом пойдет в следующей статье :)

Если у кого-то есть дополнительная информация об описанных выше понятиях, пожалуйста присылайте её в комментарии, я буду очень благодарен!

Надеюсь, что вам было интересно, спасибо большое за внимание!

Подробнее..

Категории: Научно-популярное , Математика , Теория чисел , Простые числа , Циклические числа , Системы счисления , Full reptend prime , Нумерология , Цифровой корень

Число Рамсея R(5,5) 43

13.02.2021 16:10:43 |

Автор: admin

По моему глубокому убеждению, все задачи делятся на два типа: простые и сложные. У простых задач есть простые решения (пусть и требующие для их нахождения некоторого объёма специальных знаний), а сложных задач в математике нет. Чтобы проиллюстрировать это, я покажу вам удивительное в своей простоте доказательство вынесенного в заголовок поста утверждения. Одной картинкой.

Для начала, что изображено на картинке? Однозначного математического ответа на этот вопрос нет: с геометрической точки зрения это ортогональные проекции пятиячейника на плоскости Коксетера A₂ и A₄, а с точки зрения теории графов диаграммы K₄ и K₅.

Геометрия нагляднее, интуитивнее и потому гораздо проработаннее остальной математики, поэтому своё R(5,5) в ней давно нашли: этой публикацией доказано, что существует ровно 39 компактных арифметических групп треугольников общего вида и 4 паракомпактных группы прямоугольных треугольников, что в сумме даёт искомое 43 произвольный пятиячейник не может быть однозначно определён меньшим количеством групп, а необходимости в уточнении паракомпактных групп компактными нет. Собственно, на этом доказательство можно считать оконченным, так что дальше я буду лить воду на мельницу теории графов, брюзжать и рассказывать как до всего этого докатился.

С чего всё началось

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

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

Используемые определения:

(Простой неориентированный) граф это пара множеств (V, E) (множество вершин и множество рёбер), причём E {{v1, v2} | v1, v2 V, v v2}.

Диаграмма графа наглядное изображение графа, на котором вершины графа изображаются точками, а рёбра линиями, соединяющими между собой точки.

Регулярный граф граф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей. Например, если граф 10-регулярен, то каждая его вершина соединена ребром с 10 другими вершинами.

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

Полный граф K_g граф имеющий g вершин, в котором каждая пара различных вершин смежна, то есть соединена ребром.

Подграф граф, содержащий некое подмножество вершин исходного графа и некое подмножество инцидентных им рёбер.

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

Раскраска графа разбиение вершин или рёбер графа на множества (называемые цветами).

(Двухцветное) число Рамсея R(n,m) минимальное число вершин графа, двухцветная раскраска рёбер которого содержит либо полный подграф из n вершин одного цвета, либо полный подграф из m вершин другого цвета.

Таблица значений и оценок чисел Рамсея:

Формальное определение графа это математическая заумь и требует дополнительных разъяснений.

Понятнее всего граф с геометрической точки зрения: достаточно задать на плоскости наборы точек, например A,B,C,D и соединяющих их отрезков, например AB, AC, BC, CD это и будет граф.

Если отрезки будут соединять каждую точку с каждой получится полный граф. Несколько менее интуитивна численная интерпретация графа: для приведённого выше примера вершины это четыре простых числа, рёбра произведения соответствующих чисел. Теперь становится ясно почему задачи поиска чисел Рамсея стоят без движения: геометрически отрезок AB без дополнительной параметризации ничем не отличается от отрезка CD и приходится действовать полным перебором, а для численного подхода нужно сначала найти характеристические многочлены.

Ход решения

Числа Рамсея были записаны треугольником и сравнены треугольником Паскаля.

Стала видна область пересечения (красный треугольник на рисунке выше), а также то, что 36 (синий квадрат) это R(3,9), из чего родилась гипотеза: R(5,5)=45, R(4,6)=36, R(4,7)=49.

Предполагаемое решение основывалось на:

Хвостовой рекурсии, которая должна была съесть интервалы оценок до конкретного значения. Забегая вперёд, идея была верна. Ошибка в том, что съедать она может только в одном направлении сверху вниз.
10-регулярном гамильтоновом графе с 45 вершинами, из которого будет построен K₄₅. Промежуточный итог его построения:

Для рассмотрения мелких подробностей файл открывать здесь, голубые вершины графа имеют по 10 рёбер, серая 16. Для сравнения, насколько проще сделать аналогичное построение на 43 вершинах (ещё 150 рёбер должны попарно соединять фиолетовые вершины с оранжевыми, рисовать их не стал).

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

Happy end? Нет! За применение полученного 43 года назад результата награду скорее всего не дадут, значит необходимо двигаться дальше. На тот момент я понял природу чисел Рамсея настолько, что поиск алгоритма их нахождения занял всего два дня. Барабанная дробь!

Первый алгоритм нахождения чисел Рамсея

Предельно прост. Это сумма предыдущего числа, его квадрата и единицы: R(9,9)=43²+43+1=1893 и так далее, что нетрудно доказать через теорию бифуркаций (делать это я конечно же не буду) или через графы (квадрат это петля).Давайте лучше ещё раз взглянем на таблицу с числами Рамсея.

R(3,3) находится в центре квадрата с длиной стороны 5 ячеек, R(5,5) находится в его правой нижней точке, при этом 43=6²+6+1. Аналогично R(5,5) центр квадрата со стороной 9, R(9,9) его правая нижняя точка. Далее по индукции. К сожалению, алгоритм работает только в конкретном, описанном выше случае. К счастью, разложение R(9,9) на простые множители 631 и 3 явно указывает на то, что каждое неизвестное число Рамсея может быть вычислено алгоритмически.

Этих алгоритмов не более двенадцати, включая найденный.

Благодарю Михаила Ивановича Снегирёва за неоценимый вклад.

Использованные материалы:

TAKEUCHI, Kisao. Arithmetic triangle groups. J. Math. Soc. Japan 29 (1977), no. 1, 91--106.

Немного личного

Два года назад сэр Майкл Фрэнсис Атья, у которого заслуг и математических наград больше чем у Брежнева медалей, доказал гипотезу Римана, получив вместо заслуженной благодарности молчаливый скепсис математического сообщества и шквал оскорблений от физиков, самым мягким из которых было, пожалуй, выживший из ума старый маразматик, и ни один коллега не выступил в его защиту публично. Конечно, ведь у физики есть адронные коллайдеры, фотографии чёрных дыр и всякие другие токамаки, а у математики нет ничего. Даже цеховой солидарности и чувства собственного достоинства.

Примерно тогда же обстоятельства потребовали моего пребывания в Москве и я решил заглянуть в стекляшку с безобидным предложением: рассматривать центры чисел-близнецов как аттракторы. Дальше поста охраны меня конечно не пустили плебсу запрещено входить в храм мудрости, для этого нужен академический документ установленного образца, паспорт учёного, как любят называть его эти самые учёные. Ладно, я не гордый, подошёл к рядом стоящему телефону и начал набирать внутренние номера сотрудников кафедры теории чисел пусть санкционируют пропуск. Ни один телефон не отвечал. Может у них конференция, семинар, коллоквиум, библиотечные дни, преподавательская работа, оппонирование, заседание, обмен опытом, диссертационный совет, отпуска, выходные, больничные, научные встречи, форум или другая академическая чепуха? спросил я охранника. В ответ услышал, что все на своих рабочих местах, никто никогда не берёт трубки и ничего удивительного в этом нет. Согласен, если бы я в коротких перерывах между очередным симпозиумом и международным конгрессом писал научные работы, состоящие из заголовка Грант успешно и безрезультатно освоен, подробности ниже и стостраничного рерайта ранее изданных учебников, то тоже бы оглох и ослеп некогда, ctrl+c/ctrl+v само себя не нажмёт.

Так обстоят дела только в России? Нет, так везде. Большинство не желает видеть дальше собственного носа, все озабочены своими гомологиями, гомотетиями, самоцитированием и прочей ерундой. К примеру, кто систематически развивает идеи Джейкоба Лурье? Единицы. Остальные морщат носик: мы заслуженные специалисты, поэтому изучать что-то новое не можем займёт целый год, может пострадать карьера. Тусовка эгоистична настолько, что среди миллионов(!!!) не-англоязычных математиков до сего момента не нашлось ни одного человека, готового потратить час своего драгоценного времени на перевод статьи Википедии о центрах Морли фундаментальном результате планиметрии треугольника с английского на язык которым говорят его дети.

Резюмируя, единственное чувство которое должен испытывать адекватный человек по отношению к большинству математиков чувство глубочайшего презрения.

Ценный совет специалистам по теории Рамсея

Каждый из вас должен задать себе простой вопрос: чему равно количество независимых наборов рёбер графа K₈? В случае ответа двести тридцать два необходимо незамедлительно встать, начать лупить себя по затылку и делать это до того момента, пока из головы не вылупятся все стереотипы, предрассудки и заблуждения. Это количество равно сумме всех различных функций от набора из четырех элементов до надлежащего подмножества того же набора.

Резко поумнев, можно браться за самостоятельное доказательство R(5.5)=43 через графы:

Взять три копии K₄и раскрасить их вершины, например цветами CMYK, рёбра раскрасятся естественным образом.
Из 6 рёбер первой копии сделать соответственно раскрашенные вершины K₆, 15 рёбер которого снова раскрасятся естественным образом, из них сделать 15 вершин.
Вторую и третью копии исходного K₄объединить в K₈, получить раскраску 28 его рёбер, сделать из них 28 вершин.
На основе 15 предварительно раскрашенных вершин из п.2 и 28 вершин из п.3 построить K₄₃, все 903 ребра которого вновь окажутся раскрашены оттенками всего 4 исходных.
Немного поскрипеть мозгом на тему температуры цвета или пригласить какого-нибудь художника с лекцией о тёплых и холодных оттенках, на два множества которых (чёрное-белое) и нужно разбивать рёбра получившегося графа.
Profit!

Спасибо дочитавшим, на этом на сегодня всё. Всегда ваш, Мальчег-Зайчег.

Зайчик (осторожно, кровь)

Подробнее..

Категории: Математика , Графы , Теория чисел , Числа рамсея , Простые числа , Теория рамсея

Перевод Деликатные числа. Математики заявили о новом классе простых чисел

23.04.2021 20:10:29 |

Автор: admin

Ученые доказали, что существуют особые простые числа, настолько чувствительные, что изменение любой из ихцифр превращает такие числа в составные. Однако конкретных примеров исследователи пока не нашли.

Возьмем числа 294 001, 505 447 и 584 141. Заметили в них что-нибудь особенное? Можно догадаться, что все они простые (без остатка делятся только сами на себя и на единицу). Но указанные выше простые числа еще более необычны!

Если вы выберете любую цифру в каждом из этих чисел и измените ее, новое число будет составным и, следовательно, больше не будет являться простым. Изменим, например, цифру 1 в числе 294 001 на 7, и полученное число будет делиться на 7; изменим 1 на 9, и полученное число делится на 3.

Подобные простые числа получили название digitally delicate (чувствительные к замене цифр), это относительно недавнее математическое открытие. В 1978 году Мюррей Кламкин, математик, а также активный автор и редактор сложных математических задач, увлекся вопросом, существуют ли такие числа. На его вопрос быстро ответил странствующий математик Пал Эрдёш, один из самых сильных мастеров по решению задач. Эрдёш доказал, что чувствительные простые числа действительно существуют, а также он установил, что таких чисел множество. Полученный Палом результат будет справедлив не только для десятичной, но и для любой другой системы счисления.

С тех пор математики пошли дальше, развив идеи Эрдёша. Среди них и лауреат Филдсовской премии Теренс Тао: в статье 2011 года ученый доказал, что положительная пропорция (positive proportion) простых чисел digitally delicate , то есть чувствительна к замене цифр (для всех систем счисления). Это означает, что интервал между последовательными чувствительными простыми числами практически не меняется другими словами, простые числа, чувствительные к замене цифр, не будут встречаться реже с их увеличением.

В двух недавних статьях Майкл Филасета из Университета Южной Каролины развил идею дальше, предложив еще более разреженный класс простых чисел, чувствительных к замене цифр.

Это замечательный результат, отметил Пол Поллак из Университета Джорджии.

Вдохновленный работами Эрдёша и Тао, Филасета задумался, что произойдет, если добавить бесконечную последовательность нулей в качестве первой части простого числа. Значения чисел 53 и 0000000053 совпадают. Может ли замена любого из этих бесконечных нулей, добавленных к простому числу, автоматически сделать его составным?

Филасета решил назвать такие числа, предполагая, что они существуют, сильно чувствительными к замене цифр (widely digitally delicate), и исследовал их свойства в статье, вышедшей в ноябре 2020 года со своим бывшим аспирантом Джеремайей Саутвиком.

Неудивительно, что новое условие затрудняет поиск подобных чисел. 294 001 является чувствительным к замене цифр, но не будет сильно чувствительным, сказал Поллак, поскольку, если мы заменим 000 294 001 на 010 294 001, мы получим 10 294 001 еще одно простое число.

Фактически, Филасета и Саутвик не смогли найти ни одного примера простого числа, сильно чувствительного к замене цифр, в десятичной системе счисления, несмотря на проверку всех целых чисел вплоть до 1 000 000 000. Но это не помешало им сделать несколько убедительных заявлений о подобных, пусть гипотетических, числах.

Во-первых, они показали, что такие числа в десятичной системе счисления действительно возможны, и, более того, их существует бесконечное множество. Ученые пошли дальше и доказали, что положительная пропорция простых чисел сильно чувствительна к замене цифр, так же, как до этого Тао поступил в отношении простых чисел, чувствительных к замене цифр. В докторской диссертации Саутвик достиг тех же результатов для систем счисления, начиная с двоичной и до девятеричной, а также для одиннадцатиричной и тридцатиодноричной.

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

Майкл Филасета из Университета Южной Каролины помог доказать существование и высокую частоту встречаемости простых чисел, сильно чувствительных к замене цифр. Каждое из них настолько восприимчиво, что изменение любой из их цифр превращает такие числа из простых в составные. На толстовке Майкла Филасеты перечислены первые 20 простых чисел, чувствительных к замене цифр.Зак Уайт / Университет Южной Каролины

В основе доказательства лежат два инструмента. Первый, использующий понятие покрывающей системы, был изобретён Эрдёшем в 1950 году для решения другой проблемы теории чисел. Покрывающая система, говорит Саутвик, даёт нам большое количество сегментов, а также гарантирует, что каждое положительное целое число находится хотя бы в одном из этих сегментов. Если, например, вы разделите все положительные целые числа на 2, вы получите два сегмента: один содержит четные числа, в которых остаток равен 0, и другой, содержащий нечетные числа, в которых остаток равен 1. Таким образом, все положительные целые числа были покрыты, а числа, находящиеся в одном и том же сегменте, считаются конгруэнтными друг другу.

Ситуация с простыми числами, сильно чувствительными к замене цифр, конечно, более запутанная. Вам понадобится намного больше сегментов, около 10^{25 000}, и в одном из этих сегментов каждое простое число гарантированно станет составным, если какая-либо из его цифр, включая его начальные нули, будет увеличена.

Сильно чувствительное к замене цифр простое число также должно стать составным, если какая-либо из его цифр уменьшится. Здесь на помощь приходит второй инструмент, сито. Теория сита (кстати, появилась еще в Древней Греции) предлагает способ подсчета и оценки для целых чисел, удовлетворяющих определенным свойствам. Филасета и Саутвик использовали подход, аналогичный тому, который использовал Тао в 2011 году, чтобы показать: если вы возьмете простые числа в вышеупомянутом сегменте и уменьшите одну из цифр, положительная пропорция этих простых чисел станет составной. Другими словами, положительная пропорция этих простых чисел сильно чувствительна к замене цифр.

Теорема Филасеты-Саутвика, отмечает Поллак, является красивой и неожиданной иллюстрацией силы покрывающей системы.

В январской статье Филасета и его нынешний аспирант Джейкоб Жуйера сделали еще более поразительное заявление: существуют длинные последовательные ряды простых чисел, каждое из которых сильно чувствительно к замене цифр. Например, можно найти 10 последовательных простых чисел, которые сильно чувствительны к замене цифр. Но для этого вам придется исследовать столько простых чисел, сколько даже нет атомов во Вселенной, утверждает Филасета. Он сравнил этот процесс с выигрышем в лотерею 10 раз подряд: шансы на выигрыш чрезвычайно малы, но все же не нулевые.

Филасета и Жуйера доказали теорему в два этапа. Во-первых, они использовали покрывающие системы, чтобы доказать, что существует сегмент, содержащий бесконечно много простых чисел, все из которых сильно чувствительны к замене цифр.

На втором этапе они применили теорему, доказанную в 2000 году Даниэлем Шиу, чтобы показать, что где-то в списке всех простых чисел существует произвольное количество последовательных простых чисел, содержащихся в этом сегменте. Эти последовательные простые числа в силу того, что они находятся в этом сегменте, обязательно являются сильно чувствительными к замене цифр.

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

В то же время, как отметил Померанс, представление числа в виде его цифр в десятичной системе счисления может быть удобным, но это не имеет отношения к тому, что это за число на самом деле. Он заключает, что существуют более фундаментальные способы представления чисел, например, простые числе Мерсенна простые числа в виде 2^p - 1 для простого числа p.

Филасета согласился. Тем не менее последние статьи поднимают вопросы, которые нам еще предстоит изучить. Филасета интересуется, существуют ли в каждой системе счисления простые числа, сильно чувствительные к замене цифр. Жуйера, со своей стороны, задается вопросом, существует ли бесконечно много простых чисел, которые становятся составными, если вставить цифру между двумя цифрами, вместо того, чтобы просто заменить цифру.

Еще один мучительный вопрос от Померанса: все ли простые числа в конечном итоге становятся чувствительными к замене цифр либо сильно чувствительными по мере приближения к бесконечности? Ограничено ли количество простых чисел, которые чувствительны к замене цифр (или сильно чувствительны к замене цифр)? Померанс считает, что ответ на этот вопрос, как бы он ни был сформулирован, должен быть отрицательным. Но и Померанс и Филасета считают эти утверждения интригующей гипотезой, которую ни один из них не знает, как доказать, не полагаясь на другую недоказанную гипотезу.

История математических исследований такова, что нельзя знать заранее, сможете ли вы решить сложную задачу и приведет ли это к чему-то важному, сказал Померанс. Ты не можешь определить заранее: сегодня я собираюсь сделать что-то значимое. Хотя, конечно, здорово, когда все складывается именно так.

Подробнее..

Категории: Математика , Блог компании timeweb , Теория чисел , Простые числа

Новый класс простых чисел, который я открыл случайно

03.05.2021 12:05:25 |

Автор: admin

Всем привет! Это мой первый пост на Хабре, потому я представлюсь: меня зовут Костя, я разработчик C++, немного музыкант, начинающий ML инженер и любитель математики. Как не сложно догадаться этот пост будет о моём математическом хобби.

Предыстория: порядка 14 лет назад я столкнулся с феноменом циклических чисел, я был заворожен закономерностями которые в них образуются и пообещал себе объяснить их. Вначале я предпринимал наивные попытки анализа, которые принесли очень посредственные результаты, однако в 2016 году мне удалось самостоятельно увидеть что рациональная дробь 1/7 может быть представлена сходящейся геометрической прогрессией. Признаюсь честно в тот момент я даже не понял что это геометрическая прогрессия, но распознал её визуально. В 2018 году я решил приложить все свои навыки и старание чтобы найти как можно больше закономерностей циклических чисел. Я нашел очень много, но сейчас хочу поделиться тем, которое считаю самым важным, и по иронии - найденным мной случайно: новый класс простых чисел.

Я занимался исследованием full reptend prime, простых чисел, а если быть более точным - таких систем счисления для простых чисел, в которых 1/P, где P - простое число, будет давать периодическую дробь, период которой будет равен циклическому числу.

Здесь нужно пожалуй привести само определение циклического числа:

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

Самое известное циклическое число 142857, которое было популяризировано псевдонаучными концепциями "эннеаграммы" + вторая ссылка. Но я так же встречал его в научно популярных книгах, в частности в занимательной математике Перльмана. Не того гения, который доказал гипотезу Пуанкаре, а Якова Исидоровича Перьмана, жившего на век раньше и занимавшегося популяризацией науки. Это была несколько детская, но интересная книга "Занимательная арифметика. Загадки и диковинки в мире чисел".

Рассмотрим циклические перестановки этого числа:

142857 * 2 = 285714

142857 * 3 = 428571

142857 * 4 = 571428

142857 * 5 = 714285

142857 * 6 = 857142

Как можно увидеть, при умножении изначального числа 142857 на числа от 2 до 6, мы получаем циклические перестановки числа 142857. Когда я впервые это увидел мне это показалось настоящей магией.

Как я говорил выше, в один момент я заметил что 1/7 может быть представлена геометрической прогрессией. Позже я заметил что это не единственная сходящаяся геометрическая прогрессия для 1/7, я увидел ещё одну. Потом ещё одну.

Я наконец потом я заметил что у 1/7 была бесконечность сходящихся геометрических прогрессий. Окей формулы будут ниже! И вот вот я уже перейду к изложению математики, но эта преамбула была нужна чтобы объяснить, что исследуя эту формулу - я случайно нашёл тот самый класс простых чисел о которым я говорю, а потом мне посчастливилось найти в нем очень необычные закономерности.

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

Первое упоминание, связанное с циклическими числами и full reptend prime, встречается в книгеThe Philisophy of Arithmetic: Exhibiting a Progressive View on the Theory and Practice of Calculation.

Эта книга была опубликована за 200 лет до текущей работы, однако уже тогда была сформулирована возможность разложения периодической дроби в форме сходящейся геометрической прогрессии. Авторы книги не используют термин геометрическая прогрессия, однако они успешно показывают разложение дроби 1/7 на сумму уменьшающихся дробей.

В книге History of the Theory of Numbers встречается формулировка условия, при котором возникают full reptend prime.

В книге The Penguin Dictionary of Curious and Interesting Numbers можно найти упоминания о циклических числах и их связи с repunit.

В книге The Book of Numbers присутствует упоминание остатков от деления при образовании периодической дроби, которые впоследствии используются в формуле геометрических прогрессий.

Однако ни в этих книгах, ни в интернетах я не смог найти информацию, которую я открыл самостоятельно, чему был сильно удивлен, потому спешу поделиться ей в этой статье. И так дальше вас ждёт непосредственно математика.

Циклические простые числа

Первым циклическим простым числом, образованным от 142857, является 1428571, это число простое. Такое число можно записать по первой цифре изначального циклического числа и общему количеству цифр. Например, для 1428571 первая цифра это 1, и общее число цифр 7.

Приведем все простые числа, образованные от циклического числа 142857, и не превышающие титанические простые числа (до 10 тысяч цифр). Первые числа записаны целиком, более длинные описываются первой цифрой и количеством цифр.

Первые 7 циклических простых чисел, образованных от числа 142857: 1428571, 71428571, 7142857142857, 571428571428571, 1428571428571428571428571, 28571428571428571428571428571, 7142857142857142857142857142857.

Количество цифр в этих числах в десятичной системе счисления: 7, 8, 13, 15, 25, 29, 31.

Дальнейшие числа очень длинные и будут представлены только первой цифрой и количеством цифр.

Первая цифра	Число цифр
2	34
4	41
7	104
5	273
5	304
1	355
7	440
7	571
1	823
7	2215
5	2523
4	4379
2	4510
4	7553
4	7679
7	9536

Всего 23 простых числа, не превышающих 10¹⁰⁰⁰.

Свойства простых чисел в зависимости от системы счисления. Full reptend prime

Для того, чтобы рассмотреть, как возникают циклические простые числа, нам нужно также рассмотреть, как возникают циклические числа.

Существует класс простых чисел под названием full reptend prime или long prime. Соответствующего названия на русском языке нет. Данный класс простых чисел зависит от системы счисления, это значит, что каждое простое число является full reptend в некоторой системе счисления.

Простое определение full reptend и циклического числа

P простое число, если периодическая дробь, образованная в ходе вычисления рациональной дроби 1/P, в некоторой системе счисления N имеет период, равный P-1, то можно говорить, что простое число P в N системе счисления является full reptend.

Если число P является full reptend в некоторой системе счисления N, то все P-1 его цифр образуют циклическое число.

Более сложное определение

Если система счисления взаимно проста по отношению к числу P, то частное Ферма будет являться целым числом, на основании малой теоремы Ферма. Если система счисления является первообразным корнем мультипликативной группы кольца вычетов по модулю P, то тогда частное Ферма - циклическое число, а P - full reptend prime.

Рассмотрим простое число P = 7 в десятичной системе счисления. Число образованное от 1/P = 0,(142857). Период равен 6, что равно P-1. Рассмотрим остальные дроби из множества 1/P .. P-1/P:

2/P = 0,(285714)

3/P = 0,(428571)

4/P = 0,(571428)

5/P = 0,(714285)

6/P = 0,(857142)

Мы наблюдаем, что в данной дроби сохраняется свойство циклической перестановки. Ниже будет представлена одна из визуализаций. В этой таблице каждая строка представляет собой простое число, они указаны слева. Каждый столбец представляет собой систему счисления, они указаны сверху. Значение в ячейке - длина периода дроби 1/P. Зеленым цветом выделены ячейки которые являются full reptend.

Вначале разберем отдельные части этой таблицы:

Для каждого простого числа P есть последовательность из возможных длин периода дроби 1/P. Длина этой последовательности равна P. Для P = 2 длина цикла систем счисления равна 2, для P = 3 длина цикла систем счисления равна 3, и т.д.

Для расчета длины периода в некоторой системе счисления необходимо найти такое n:

(система счисленияⁿ) mod P = 1

Ниже приведена таблица для разных P в разных системах счисления:

В десятичной системе счисления мы видим, что первые простые числа, являющиеся full reptend, это 7, 17, 19, 23, 29. Числа 2 и 5 не имеют здесь периода, поскольку основание системы счисления делится на оба этих простых числа без остатка.

В случае P = 3 мы получаем периодическую дробь с единичной длиной периода в десятичной системе: 1/3 = 0,(3). В случае P = 11 мы получаем периодическую дробь с длиной периода, равной 2 в десятичной системе: 1/11 = 0,(09).

При P = 13 мы получим особый случай, длина периода равна 6, что не равно P-1. Однако длина периода равна (P-1)/2, когда соблюдается такая пропорция, образуется два набора циклических чисел. Такое число P называется 2nd reptend level prime. Приведем пример 2nd reptend level prime:

1/13 = 0,(076923)

2/13 = 0,(153846)

Все другие дроби от P = 13, вплоть до P-1/P, будут состоять из тех же цифр, что и 1/13 или 2/13, нос циклическими перестановками.

3/13 = 0,(230769) цикл 1

4/13 = 0,(307692) цикл 1

5/13 = 0,(384615) цикл 2

6/13 = 0,(461538) цикл 2

7/13 = 0,(538461) цикл 2

8/13 = 0,(615384) цикл 2

9/13 = 0,(692307) цикл 1

10/13 = 0,(769230) цикл 1

11/13 = 0,(846153) цикл 2

12/13 = 0,(923076) цикл 1

2nd reptend level prime тоже образуют циклические простые числа: от каждой из последовательностей цифр могут образовываться простые числа.

Т.е. существуют простые числа: 769230769, 769230769230769230769,769230769230769230769230769230769.

Но также и: 1538461.

Также в завершение этой темы интересно отметить, что системы счисления, в которых мы встречаем full reptend prime, тоже являются необычными. Для P = 7 первые 2 системы счисления, в которых оно является full reptend, это системы с основанием 3 и 5 простые числа близнецы.

Далее эти точки повторяются через каждые 7 систем счисления. Когда сумма оснований систем счисления делится без остатка на 12, мы встречаем снова простые числа близнецы. Например, 17 и 19, 59 и 61.

Представление периодической дроби в форме сходящейся геометрической прогрессии

Каждая из дробей, образованных full reptend или n-th repntend level может быть разложена на сходящиеся геометрические прогрессии. Для каждого простого числа P и заданной системы счисления N существует бесконечное количество таких геометрических прогрессий.

Формула для записи суммы геометрической прогрессии для 1/P:

$\begin{equation} \sum\limits_{n=0}^\infty\frac{s*r^n}{base^{length(n+1)}} = \frac{1}{P} \end{equation}$

Где s это целое число, полученное из дроби 1/P:

$\begin{equation} s=[\frac{1}{P}*base^{length}] \end{equation}$

Поскольку full reptend prime образуют бесконечную периодическую дробь, мы можем получить из нее числа с количеством цифр от 1 до бесконечности. Ну условно конечно :)

Параметр length означает количество символов, которые будут использованы в числе s, это число может варьироваться от единицы до бесконечности. При каждом новом параметре length мы будем получать новую геометрическую прогрессию.

Число r тоже является целым и представляет собой один из остатков от деления, образованны при вычислении 1/P. Как дробь 1/P будет иметь период P-1, в случае если простое число являетсяfull reptend в исследуемой системе счисления, точно так же количество остатков будет равно P-1.

Для того, чтобы понять, как образуются остатки от деления, рассмотрим их на примере. Возьмем P= 7, т.к. это первое full reptend в привычной нам десятичной системе счисления.

В итоге мы получили уникальные остатки: [3, 2, 6, 4, 5, 1]. Именно эти значения будут принимать участие в формуле. Первый остаток от деления будет равен base mod P. Каждый последующий остаток будет зависеть от предшествующего, функцию можно записать рекурсивно:

$\begin{equation} \begin{cases} r_0 = 1 \\ r_n = r_{n-1} * (base\mod P) \\ \end{cases} \end{equation}$

Переведем рекурсивную формулу в замкнутую форму:

$\begin{equation} r_{length}=base^{length}\mod P \end{equation}$

Запишем общую формулу геометрической прогрессии, используя только следующие параметры: P простое число; base исследуемая система счисления; length параметр, определяющий номер геометрической прогрессии для данного простого числа и данной системы счисления.

$\begin{equation} \frac{1}{P} = \sum\limits_{n=0}^\infty\frac{[\frac{1}{P}*base^{length}]*(base^{length}\mod P)^n}{base^{length(n+1)}} \end{equation}$

Приведем формулы для P = 7 c использованием разных s, начиная с самых коротких:

$\begin{equation} \frac{1}{7} = \sum\limits_{n=0}^\infty\frac{1*3^n}{10^{n+1}} \end{equation}$

В данной формуле s = 1, это первая цифра из дроби 0,(142857), т.е. параметр length = 1.При этом остаток r = 3, это самый первый остаток, что соответствует параметру length = 1.

$\begin{equation} \frac{1}{7} = 0.1 + 0.03 + 0.009 + 0.0027 + 0.00081 + .. \end{equation}$

Каждый следующий член прогрессии получается посредством умножения на 3 и деления на 10. Теперь рассмотрим следующую прогрессию:

$\begin{equation} \frac{1}{7} = \sum\limits_{n=0}^\infty\frac{14*2^n}{10^{2(n+1)}} \end{equation}$ $\begin{equation} \frac{1}{7} = 0.14 + 0.0028 + 0.000056 + 0.00000112 + .. \end{equation}$

В данной формуле каждый следующий член прогрессии получается посредством умножения на 2 и деления на 100. Здесь s = 14, это первые две цифры из дроби 0,(142857), т.е. параметр length = 2. При этом остаток r = 2, это второй остаток, что соответствует параметру length = 2. Есть интересные закономерности, которые можно исследовать связанные с этим, но я приберег это для отдельной статьи, которую я так же обязательно опубликую в том числе на Хабре.

Дальнейшие формулы по аналогии с предшествующими будут получены просто последовательным увеличением значения length на 1:

$\begin{equation} \frac{1}{7} = \sum\limits_{n=0}^\infty\frac{142*6^n}{10^{3(n+1)}} \end{equation}$ $\begin{equation} \frac{1}{7} = \sum\limits_{n=0}^\infty\frac{1428*4^n}{10^{4(n+1)}} \end{equation}$ $\begin{equation} \frac{1}{7} = \sum\limits_{n=0}^\infty\frac{14285*5^n}{10^{5(n+1)}} \end{equation}$ $\begin{equation} \frac{1}{7} = \sum\limits_{n=0}^\infty\frac{142857*1^n}{10^{6(n+1)}} \end{equation}$

И наконец мы получаем последовательность, в которой s представляет собой простое число:

$\begin{equation} \frac{1}{7} = \sum\limits_{n=0}^\infty\frac{1428571*3^n}{10^{7(n+1)}} \end{equation}$

Собственно когда я факторизировал все возможные s - что к слову представляло для меня интерес по другой причине, я нашел что некоторые из них сами по себе простые. Так собственное я и совершил это небольшое открытие. Но это не всё что мне удалось найти про эти простые числа.

На этом можно отложить рассмотрение дальнейших геометрических прогрессий, однако важно заметить, что их может быть бесконечное множество, так как чисел s для каждого числа P в некоторой системе счисления N бесконечное множество.

Приведем также в пример несколько сходящихся геометрических прогрессий для P = 17:

$\begin{equation} \frac{1}{17} = \sum\limits_{n=0}^\infty\frac{5*15^n}{10^{2(n+1)}} \end{equation}$ $\begin{equation} \frac{1}{17} = \sum\limits_{n=0}^\infty\frac{58*14^n}{10^{3(n+1)}} \end{equation}$ $\begin{equation} \frac{1}{17} = \sum\limits_{n=0}^\infty\frac{588*4^n}{10^{4(n+1)}} \end{equation}$

Интересно рассмотреть разложение числа 89 на геометрические прогрессии. 1/89 = 0,0112359.. можно увидеть, как в первых цифрах дроби наблюдаются числа Фибоначчи. И действительно эту дробь можно разложить не только на сходящуюся геометрическую прогрессию, но и описать формулой с числами Фиббоначи:

$\begin{equation} \frac{1}{89} = \sum\limits_{n=0}^\infty\frac{1*11^n}{10^{2(n+1)}} \end{equation}$ $\begin{equation} \frac{1}{89} = \sum\limits_{n=0}^\infty\frac{Fibonacci(n)}{10^{n+1}} \end{equation}$

Интересно, что схожее явление можно встретить в другом простом числе 109.

Формула для этого числа отличается от формулы 1/89 только множителем: 2*(n%2) - 1. Этот множитель приводит к тому, что происходит не только суммирование, а чередование суммирования и вычитания разных элементов прогрессии.

$\begin{equation} \frac{1}{109} = \sum\limits_{n=0}^\infty\frac{9*17^n}{10^{3(n+1)}} \end{equation}$ $\begin{equation} \frac{1}{109} = \sum\limits_{n=0}^\infty\frac{Fibonacci(n)*(2(n\mod2)-1))}{10^{n+1}} \end{equation}$

Возможно, существуют и другие разложения периодической дроби, помимо сходящихся геометрических прогрессий и суммирование чисел Фибоначчи.

Образование циклических и суб-циклических простых чисел

Когда мы будем рассматривать разные значения s из формулы геометрической прогрессии, мы заметим, что среди них будут встречаться простые числа.

Например, для простого числа P = 7, образующего циклическое число 142857, первым простым числом будет 1428571. Далее будет возникать большое количество подобных чисел, для того чтобы рассмотреть все возможное их множество, нужно рассматривать не только геометрические прогрессии 1/P, но и все другие прогрессии из множества 1/P .. P-1/P. Иначе мы могли бы пропустить, например, простое число 71428571.

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

На самом деле, если мы внимательно рассмотрим параметр s, мы встретим в нем простые числа,которые будут меньше, чем циклическое число, однако будут содержать последовательность цифр из циклического числа. Такие числа можно назвать простыми суб-циклическими числами.

Рассмотрим их на примере P = 7. Если мы будем одновременно рассматривать не только 1/P, но и все другие дроби вплоть до P-1/P, то мы увидим, что среди параметров s встречается множество других простых чисел: 2, 5, 7, 71, 571, 2857, 28571.

В отличие от циклических простых чисел, множество суб-циклических простых чисел всегда ограничено.

Циклические и суб-циклические простые числа могут быть образованы от любого простого числа P в некоторой системе счисления N. Это является следствием того, что каждое простое число может быть full reptend prime в некоторой системе счисления.

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

Как было сказано ранее, циклическое простое число может быть получено от любого простого числа в некоторых системах счисления. Для каждого конкретного циклического простого числа есть простое число P и система счисления N, с помощью которых было образовано циклическое простое число. Однако циклические простые числа, образованные от одного P, но в разных системах счисления, могут проявлять свойства позволяющие их группировать.

Наконец десерт - это то что мне нравится больше всего:

Однако циклические простые числа, образованные от одного P, но в разных системах счисления, могут проявлять свойства позволяющие их объединять в группы. Например, в десятичной системе счисления мы получаем простые числа из циклического числа 142857. А в 40 системе счисления мы получаем простые числа из циклического числа 5SMYBH (что соответствует последовательности цифр 5, 28, 22, 34, 11, 17).

Однако, если мы возьмем простое число, которое оригинально выглядит как H5SMYBH в 40 системе счисления, и переведем его в десятичную систему счисления, мы увидим некоторую закономерность: 70217142857.

Младшие разряды будут соответствовать процессу образования циклических простых чисел, но в старших разрядах будут отклонения. Если написанное выше было непонятно, я приведу несколько чисел образованных в десятичной системе счисления, и представленных как в десятичной, так и в сороковой.

Вот простые числа в десятичной системе счисления образованные от P=7 N=10:

1) 1428571

2) 71428571

3) 7142857142857

4) 571428571428571

5) 1428571428571428571428571

6) 28571428571428571428571428571

7) 7142857142857142857142857142857

8) 2857142857142857142857142857142857

9) 42857142857142857142857142857142857142857

Те же самые числа представленные в 40 системе счисления:

1) MCYB

2) Ra2YB

3) 13NYIMYBH

4) 277Sb5SMYB

5) 1D8TJS2CYBH5SMYB

6) GP98QAT0SMYBH5SMYB

7) 2NbRO471EIMYBH5SMYBH

8) PdGa11UDOPSMYBH5SMYBH

9) 3WAEQ3OR61AQVH5SMYBH5SMYBH

Пример чисел образованных от P=7 N=10 в сороковой системе счисления:

1) H5SMYBH

2) Следующее число днинное - 77 цифры длиной, оно начинается с 5SMYBH, и повторяется до B:

5SMYBH5SMYBH5SMYBH5SMYBH5SMYBH5SMYBH5SMYBH5SMYBH5SMYBH5SMYBH5SMYBH5SMYBH5SMYB

А вот те же самые числа в десятичной системе счисления:

1) 70217142857

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

2) 3262280440470765442418939358741703168874849426...

...28571428571428571428571428571428571428571428571428571428571428571428571428571

Следующие числа я не привожу из-за их чрезмерной длины, однако закономерности в них сохраняются так же.

Формула для вычисления систем счисления, образующих связи с оригинальной системой счисления для заданного простого числа

Выше мы рассмотрели простое число P = 7 и систему счисления N = 10. Обобщенно формулу для нахождения связанных систем счисления можно записать так:

Ns(i) = N + 3*N*i + (i + 1 % 2) * i*N*4

Где i это натуральное число. И i = 0 соответствует первой системе, в которой простое число является full reptend prime. Однако эта формула подходит исключительно для десятичной системы счисления.

Если мы попробуем выписать подобные формулы хотя бы для нескольких других систем счисления, окажется, что их не так легко обобщить.

Формула для N = 3, 10, 17, 31, 38, 59:

Ns(i) = N + 3*N*i + (i + 1 % 2) * i*N

Формула для N = 5, 19, 26, 33, 47, 61:

Ns(i) = N + N*i + (i + 1 % 2) * i*5*N

Формула для N = 12:

Ns(i) = N + N*i + (i + 1 % 2) * i*5*N

N = 40 относится к группе, образованной от N = 10.

Схожее справедливо и для N = 24, она так же образована от N = 12.

Отличие образованных групп заключается в том, что связанные циклические числа начинают образовываться в системах счисления ниже, чем изначальная исследуемая N.

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

Схожее верно и для 12 и 24 систем счисления. Несмотря на то, что многие системы счисления образуют одинаковые формулы, другие все же отличаются, например 12.

Итак, есть сами по себе циклические простые числа, они образуются в любой системе счисления,где изначальное простое число является full reptend.

Они могут быть взаимосвязаны с циклическими простыми числами в других системах счисления, при этом некоторые числа имеют связь только с системами счисления выше, другие же имеют и связь с системами счисления ниже, как в случае с 40 и 10 системами счисления.

Можно наблюдать схожую конструкцию для P = 5, есть повторяющиеся коэффициенты относительно первой системы счисления в группе. А в случае с P = 17 все становится намного сложней, видно, что шаги всегда равны base, base*2, base*4, однако их чередование меняется.

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

Перечень наблюдений, требующих доказательства или опровержения

Возможно у вас создалась иллюзия что я профессиональный математик, имеющий математическое образование. На самом деле это не так. К моему сожалению мои познания в математике и в частности в Теории Чисел не так и глубоки, однако это не мешает мне испытывать большой трепет к этой дисциплине.

Я уверен что среди читателей Хабра есть профессиональные, настоящие математики. Я был бы безумно раз, если бы они помогли бы мне доказать мои наблюдения и оформить их в качестве теорем.

Разложение периодической дроби на бесконечное количество геометрических прогрессий
Наличие циклических простых чисел в каждой системе счисления, и то, что их потенциально бесконечное множество

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

Возможность доказать или опровергнуть любые из моих гипотез крайне приветствуется!

Также интересна любая информация, касающаяся full reptend prime или циклических чисел.

Большая часть вычислений и визуализаций была сделана при помощи небольшого самодельного приложения. Его код далек от идеальности, но он помогает изучить закономерности визуально, все доступно на github. Там же можно найти английскую версию статьи.

Светлое будущее

У меня осталось несколько неосвещенных тем, связанных с full reptend prime. Однако их освещение требует дополнительного исследования и написания нового кода для визуализации.

Я надеюсь, что я смогу встретить хотя бы одного человека, кто серьезно заинтересован в этой теме, и тогда я продолжу это исследование с более серьезным отношением.

Большинство из описанных закономерностей, и в частности сами циклические простые и связи между ними в разных системах счисления были открыты мной в марте 2019 года, но работа\семья и другие исследования не позволяли добраться до публикации долгое время.

Недавно я закончил редактирование английской версии статьи, и теперь испытываю некоторое затруднение в том, чтобы опубликовать её на arxiv.org мне нужно найти эндорсера. Я уже написал парочке потенциальных, однако они не отвечают. И одна из причин публикации этой статьи возможность задать вопрос:

Дорогие Хабравчане, среди вас есть те кто публиковались на arxiv в категории Теории Чисел? Можете мне дать пожалуйста эндорсмент? Это потребует просто ввести 6-ти значный код при подачи моей публикации, я бы очень хотел поделиться этим открытием с миром.

Всем огромное спасибо за внимание! Надеюсь моя первая статья была не утомительной, впереди ещё несколько и не все о них будут о математике.

Подробнее..

Категории: Математика , Теория чисел , Простые числа , Числа фибоначчи , Циклические числа , Системы счисления , Full reptend prime

	Русский
	English

Теория чисел

Перевод Математики открыли новый фронт в битве с древней числовой задачей

Сжимающаяся сеть

Разбираемся в совершенных числах

Новые соблазнительные промахи

Имитации нечётных совершенных чисел

Просеивая возможности

Путь вперёд?

Закономерности в распределении простых чисел

Введение

Распределение простых чисел

Проблемы Ландау

1. Гипотеза Гольдбаха

2. Гипотеза о числах-близнецах

3. Гипотеза Лежандра

4. Почти квадратные простые числа

Заключение

Нумерология никакого гадания, только теория чисел

Введение

Сумма цифр и цифровой корень

Применение цифровой суммы

Улучшение алгоритма вычисления цифрового корня

Свойства цифрового корня

Операция сложения

Операция вычитания

Операция умножения

Операция возведения в степень

Ещё визуализации

Образование циклических чисел при помощи ведической площади и остатков от деления

Число Рамсея R(5,5) 43

С чего всё началось

Ход решения

Первый алгоритм нахождения чисел Рамсея

Немного личного

Ценный совет специалистам по теории Рамсея

Перевод Деликатные числа. Математики заявили о новом классе простых чисел

Новый класс простых чисел, который я открыл случайно

Циклические простые числа

Свойства простых чисел в зависимости от системы счисления. Full reptend prime

Простое определение full reptend и циклического числа

Более сложное определение

Представление периодической дроби в форме сходящейся геометрической прогрессии

Образование циклических и суб-циклических простых чисел

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

Формула для вычисления систем счисления, образующих связи с оригинальной системой счисления для заданного простого числа

Перечень наблюдений, требующих доказательства или опровержения

Светлое будущее

Категории

Последние комментарии