DmitrySpb79 19 окт 2018 в 23:37

Численная проверка abc-гипотезы (да, той самой)

8 мин

16K

Программирование*C++*Алгоритмы*Математика*

+31

Комментарии 30

mphys 19 окт 2018 в 23:58

Ну на самом деле час это не так уж и долго :)

DmitrySpb79 20 окт 2018 в 09:22

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

Sdima1357 20 окт 2018 в 00:04

Статья конечно забавная, но ничего и не доказывает. То что 2020 года еще никогда не было, не доказывает что его и не будет…

DmitrySpb79 20 окт 2018 в 00:06

Я на «доказательство» и не претендовал :) Просто было интересно проверить, что получается…

Sdima1357 20 окт 2018 в 00:09

Я предполагаю, что она и была выдвинута после подобной проверки.

qw1 20 окт 2018 в 16:06

В науке независимая перепроверка экспериментов очень важна.

artyomtch 20 окт 2018 в 00:31

Наверное, стоит еще раз подчеркнуть, что «rad(a*b*c) = rad(a)*rad(b)*rad(с)» справедливо лишь для взаимнопростых (a,b,c), а не для любой тройки. Я когда прочитал эту строку, то первой мыслью было: «Это неверно!», и лишь второй мыслью было «Ах, да, мы же о взаимнопростых числах...» (но о том было написано двумя абзацами выше).

Но вообще забавно :)

DmitrySpb79 20 окт 2018 в 09:22

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

Refridgerator 20 окт 2018 в 05:54

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

Это ничего не значит. Логарифм числа тоже растёт медленнее, однако его предел в бесконечности равен бесконечности.

maximw 20 окт 2018 в 12:03

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

Refridgerator 22 окт 2018 в 11:05

Но если функция возрастает как гипербола, то предел будет. Если посмотреть на их производные
(log(x))′=1/x
(1/x)′=-1/x²
то можно предположить, что для наличия предела производная функции должна затухать быстрее, чем 1/х.

DmitrySpb79 22 окт 2018 в 12:34

Тут тема интересная. Как говорит теорема, множество «троек» должно быть ограничено, но как подсказали в комментариях, в Википедии уже есть результаты — пока проверили до 10^18 и «конца» пока не нашли. С другой стороны, может «конец» лежит где-то в районе чисел типа 10^1000, хз.

Так что вопрос открытый, и интрига остается.

Refridgerator 20 окт 2018 в 06:03

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

Imposeren 20 окт 2018 в 06:23

Это же математики. Конечно же такая мысль много кому приходила в голову:
www.coolissues.com/mathematics/disprovingtheabcconjecture.html
arxiv.org/pdf/math/0503401.pdf
forums.xkcd.com/viewtopic.php?t=125159

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

DmitrySpb79 20 окт 2018 в 09:27

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

И даже странно, что за 5 лет обсуждения на довольно большом ИТ-ресурсе как хабр, никто не решил проверить. Ни у кого случайно суперкомпьютер не простаивает? ;)

-2

mtivkov 20 окт 2018 в 09:41

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

DmitrySpb79 20 окт 2018 в 11:16

Идея интересная, да. Но разложение на множители у меня и так кешируется, и считается только 1 раз на каждое число. Самое медленное в рассчете, это расчет пересечения трех множеств для каждого a,b,c.

Deosis 22 окт 2018 в 10:16

Если условие a+b=c выполняется, то достаточно проверить на взаимную простоту только одну пару чисел.

DmitrySpb79 22 окт 2018 в 11:20

Да, это интересный момент, спасибо.

НЛО прилетело и опубликовало эту надпись здесь

DmitrySpb79 20 окт 2018 в 11:45

Спасибо за идею.

Радикалы не проблема, они вычисляются быстро (меньше 1% от всего времени).
Попробовал в Python-прототипе заменить пересечение множеств на условие gcd(a,b) == gcd(b,c) == gcd(a,c) == 1 — быстрее не стало, время примерно то же. Хотя тут есть один плюс — таблицу для gcd(a,b) закешировать можно.

НЛО прилетело и опубликовало эту надпись здесь

DmitrySpb79 20 окт 2018 в 12:42

Так сложно получается. Во-первых, число может раскладываться на несколько повторяющихся простых чисел, например 2*2*2*3*7, значит надо перебирать все такие варианты. Во-вторых, имея А мы можем сгенерировать только взаимно-простое B, а результат С мы все равно должны вычислять и проверять на пересечение с А, В.

В итоге хз будет ли это быстрее, проще таблицу GCD 1 раз вычислить и в памяти держать, тогда вычисление будет линейно О(1).

НЛО прилетело и опубликовало эту надпись здесь

MikailBag 20 окт 2018 в 12:55

Существует быстрый алгориьм поиска нод, делающий только вычитание и деление на 2. Вы писали его?

MikailBag 31 окт 2018 в 22:34

Вот ссылка, если что.

Разница во времени работы имхо — несколько раз.

ripatti 20 окт 2018 в 15:36

Немного пооптимиздил:
10^6 22сек — 102 тройки
10^7 30мин — 212 троек
Это все в 1 поток на ноутбуке.
Есть еще несколько идей как ускорить, надеюсь 10^8 затащу. Ну и я еще подумаю код сюда сразу скинуть или статью написать — а то много довольно интересных идей всплыло.

Еще у Вас, кстати, на 10^7 переполнение тут:

valRads[a]*valRads[b]*valRads[c]

DmitrySpb79 20 окт 2018 в 15:41

Спасибо за правку, да, для больших чисел тип в typedef нужно будет поменять.

В виде отдельной статьи будет даже интереснее :)

PS: 212 — интересный результат, пока неясно, уменьшается скорость роста количества троек от N или нет.