Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 30
Ну на самом деле час это не так уж и долго :)
Статья конечно забавная, но ничего и не доказывает. То что 2020 года еще никогда не было, не доказывает что его и не будет…
Наверное, стоит еще раз подчеркнуть, что «rad(a*b*c) = rad(a)*rad(b)*rad(с)» справедливо лишь для взаимнопростых (a,b,c), а не для любой тройки. Я когда прочитал эту строку, то первой мыслью было: «Это неверно!», и лишь второй мыслью было «Ах, да, мы же о взаимнопростых числах...» (но о том было написано двумя абзацами выше).
Но вообще забавно :)
Но вообще забавно :)
В принципе, вполне очевидно, что зависимость количества возможных троек от N растет заметно медленнее самого N, и вполне вероятно, что результат будет сходиться к какому-то конкретному числу для каждого εЭто ничего не значит. Логарифм числа тоже растёт медленнее, однако его предел в бесконечности равен бесконечности.
Именно, на графике монотонно возрастающая функция. И вывод на основе только этого графика, что функция неограниченна, был бы более интуитивно логичен (хотя был бы так же необоснован).
Но если функция возрастает как гипербола, то предел будет. Если посмотреть на их производные
(log(x))′=1/x
(1/x)′=-1/x²
то можно предположить, что для наличия предела производная функции должна затухать быстрее, чем 1/х.
(log(x))′=1/x
(1/x)′=-1/x²
то можно предположить, что для наличия предела производная функции должна затухать быстрее, чем 1/х.
Тут тема интересная. Как говорит теорема, множество «троек» должно быть ограничено, но как подсказали в комментариях, в Википедии уже есть результаты — пока проверили до 10^18 и «конца» пока не нашли. С другой стороны, может «конец» лежит где-то в районе чисел типа 10^1000, хз.
Так что вопрос открытый, и интрига остается.
Так что вопрос открытый, и интрига остается.
Мало кому приходит в голову, что abc-гипотеза может быть и ошибочной. Не все гипотезы от великих математиков подтверждаются.
Это же математики. Конечно же такая мысль много кому приходила в голову:
www.coolissues.com/mathematics/disprovingtheabcconjecture.html
arxiv.org/pdf/math/0503401.pdf
forums.xkcd.com/viewtopic.php?t=125159
И в целом опровергнуть гипотезу было бы не менее престижно и ценно. Но существующие «опровержения» пока принимаются не лучше, чем «доказательства».
www.coolissues.com/mathematics/disprovingtheabcconjecture.html
arxiv.org/pdf/math/0503401.pdf
forums.xkcd.com/viewtopic.php?t=125159
И в целом опровергнуть гипотезу было бы не менее престижно и ценно. Но существующие «опровержения» пока принимаются не лучше, чем «доказательства».
Кстати странно, но я так и не нашел (а может плохо искал) каких-либо результатов численной проверки гипотезы — дошли до конца множества-то в итоге или нет, хз.
И даже странно, что за 5 лет обсуждения на довольно большом ИТ-ресурсе как хабр, никто не решил проверить. Ни у кого случайно суперкомпьютер не простаивает? ;)
И даже странно, что за 5 лет обсуждения на довольно большом ИТ-ресурсе как хабр, никто не решил проверить. Ни у кого случайно суперкомпьютер не простаивает? ;)
А не лучше ли было бы не раскладывать a и b на множители, а формировать их из заранее известных простых множителей?
Ну, т.е. понятно, что это лучше для скорости, но немного сложнее алгоритм.
Спасибо за идею.
Радикалы не проблема, они вычисляются быстро (меньше 1% от всего времени).
Попробовал в Python-прототипе заменить пересечение множеств на условие gcd(a,b) == gcd(b,c) == gcd(a,c) == 1 — быстрее не стало, время примерно то же. Хотя тут есть один плюс — таблицу для gcd(a,b) закешировать можно.
Радикалы не проблема, они вычисляются быстро (меньше 1% от всего времени).
Попробовал в Python-прототипе заменить пересечение множеств на условие gcd(a,b) == gcd(b,c) == gcd(a,c) == 1 — быстрее не стало, время примерно то же. Хотя тут есть один плюс — таблицу для gcd(a,b) закешировать можно.
Так сложно получается. Во-первых, число может раскладываться на несколько повторяющихся простых чисел, например 2*2*2*3*7, значит надо перебирать все такие варианты. Во-вторых, имея А мы можем сгенерировать только взаимно-простое B, а результат С мы все равно должны вычислять и проверять на пересечение с А, В.
В итоге хз будет ли это быстрее, проще таблицу GCD 1 раз вычислить и в памяти держать, тогда вычисление будет линейно О(1).
В итоге хз будет ли это быстрее, проще таблицу GCD 1 раз вычислить и в памяти держать, тогда вычисление будет линейно О(1).
Существует быстрый алгориьм поиска нод, делающий только вычитание и деление на 2. Вы писали его?
Немного пооптимиздил:
10^6 22сек — 102 тройки
10^7 30мин — 212 троек
Это все в 1 поток на ноутбуке.
Есть еще несколько идей как ускорить, надеюсь 10^8 затащу. Ну и я еще подумаю код сюда сразу скинуть или статью написать — а то много довольно интересных идей всплыло.
Еще у Вас, кстати, на 10^7 переполнение тут:
10^6 22сек — 102 тройки
10^7 30мин — 212 троек
Это все в 1 поток на ноутбуке.
Есть еще несколько идей как ускорить, надеюсь 10^8 затащу. Ну и я еще подумаю код сюда сразу скинуть или статью написать — а то много довольно интересных идей всплыло.
Еще у Вас, кстати, на 10^7 переполнение тут:
valRads[a]*valRads[b]*valRads[c]Спасибо за правку, да, для больших чисел тип в typedef нужно будет поменять.
В виде отдельной статьи будет даже интереснее :)
PS: 212 — интересный результат, пока неясно, уменьшается скорость роста количества троек от N или нет.
В виде отдельной статьи будет даже интереснее :)
PS: 212 — интересный результат, пока неясно, уменьшается скорость роста количества троек от N или нет.
Там есть табличка. en.wikipedia.org/wiki/Abc_conjecture
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Численная проверка abc-гипотезы (да, той самой)