Гипотеза Била имеет приз в миллион долларов, если вы докажете / опровергнете его.
В нем говорится, что если A, B, C, x, y и z являются натуральными числами с x, y, z> 2, то A, B и C имеют общий простой множитель.
Задача состоит в том, чтобы написать программу, которая ищет контрпример, чтобы опровергнуть это!
правила
- Напишите программу, которая ищет контр-пример гипотезы Била
- Вы можете выполнить исчерпывающий поиск (т. Е. Все возможные комбинации чисел, которые соответствуют этой форме) или использовать некоторые оптимизации (например, A и B симметричны).
- Вы должны использовать целые числа произвольной точности.
Примечания
- Это конкурс популярности, будь креативным!
- Скорость не нужна, но делает ее более интересной. Оптимизировать!
- Я также заинтересован в том, чтобы увидеть самый короткий код. Вы получите +1 от меня!
- Я запусту программу-победитель на суперкомпьютере, к которому у меня есть доступ!
- Эта гипотеза считается верной, но это не значит, что мы не можем попробовать!
- Питер Норвиг из Google тоже попытался решить эту проблему. Вы можете использовать его страницу в качестве руководства. У него есть небольшая программа на Python, которую вы можете использовать в качестве примера.
- Какой-то другой парень (который также работает в Google) значительно улучшил подход Norvig, его страницу (с исходным кодом) можно найти здесь .
- Мой вопрос SO, связанный с этим два года назад, также может быть полезным: найти все A ^ x в заданном диапазоне .
popularity-contest
math
Остин Хенли
источник
источник
Ответы:
Я пафосно ленивый (каламбур), но почему бы и нет ... кажется, выполняет правила.
Хаскелл, 204
Это печатает 1 все комбинации, которые удовлетворяют свойству контрпримеров. Я использовал пакет control-monad -omega для диагонализации ℕ 6 ... можно было бы считать читерство библиотекой. Но, увидев, что кто-то позже опубликует ответ APL, где все это встроено в язык (или нет?), Я не слишком много об этом говорю ...
Конечно, программа слишком медленная (наивное исчерпание ресурсов и связанные списки как структура данных), чтобы можно было ожидать контрпример, но сам Haskell действительно может добиться достойной производительности.
1 Так как он печатает кортежи в формате списка, то есть в одной строке, вам нужно отключить буферизацию вашего терминала, иначе вы не увидите, когда будет получен результат. В качестве альтернативы вы можете заменить
print
на,mapM_ print
чтобы после каждого результата получать новую строку, очистка терминала с линейной буферизацией.Чтобы протестировать программу, измените
each[3..]
наeach[2..]
, тогда вы просто получите все не взаимно простые пифагорейские кортежи в результате.источник
C #, без петель
Хорошо, я просмотрел несколько этих ссылок, но, честно говоря, они были немного скучными. Я не заинтересован в том, чтобы оптимизировать его с помощью хеш-таблиц и еще много чего. Зачем мне это нужно? У тебя чертов суперкомпьютер!
Черт, я даже не хочу возиться с петлями! Это решение будет следовать правилу без циклов .
Обратите внимание, что код, который я собираюсь написать, не является хорошим кодом или кодом, который я написал бы в реальной жизни (на случай, если кто-нибудь из потенциальных работодателей прочитает это). Этот кодекс подчеркивает краткость и умение работать в повествовании, а также подчеркивает надлежащие условности, ритуалы, циклы и так далее.
Чтобы продемонстрировать, о чем я говорю, начнем с шокирующего класса с открытыми полями для хранения операндов уравнения:
Хорошо, мы начнем с того, что, вероятно, самая сложная задача. Нам нужно найти способ перестановки каждой комбинации этих операндов. Несомненно, есть способы сделать это более эффективно, чем проверка каждой перестановки, но я не могу быть обеспокоен, выясняя их. А зачем мне? У нас есть чертов суперкомпьютер!
Вот алгоритм, который я придумал. Это невероятно неэффективно и повторяет одни и те же операнды снова и снова, но кого это волнует? Суперкомпьютер!
Как сделать все это без петель? Легко! Просто реализовать
IEnumerable
и связанноеIEnumerator
с откачкой перестановок. Позже мы будем использовать LINQ для запроса.Теперь мы в деле! Все, что нам нужно сделать, это перечислить экземпляр
BealOperandGenerator
и найти контрпример к гипотезе Била.Наша следующая большая проблема заключается в том, что не существует встроенного способа поднять a
BigInteger
до степени aBigInteger
. ЕстьBigInteger.Pow(BigInteger value, int exponent)
, иBigInteger.ModPow(BigInteger value, BigInteger exponent, BigInteger modulus)
, но нет способа поднятьBigInteger
, к власти другогоBigInteger
, по модулю бесконечности.Какой блестящий гвоздь проблемы! Похоже, это было решено с помощью нашего
IEnumerable
/IEnumerator
молотка!Теперь у нас есть метод расширения
Pow
, который можно вызывать для aBigInteger
и который принимаетBigInteger
показатель степени без модуля.Хорошо, давайте отступим. Как мы можем определить, является ли конкретный
BealOperands
контрпример гипотезы Била? Ну, две вещи должны быть правдой:У нас есть то, что нам нужно, чтобы проверить первое условие. И оказывается, что второе условие гораздо проще проверить, чем кажется.
BigInteger
предоставляет прекрасныйGreatestCommonDivisor
метод, который позволяет нам удобно обходить весь кошмар, пытаясь реализовать это без циклов.Итак, мы готовы написать метод, чтобы проверить,
BealOperands
является ли контрпример. Вот оно...И, наконец, мы можем объединить все это с помощью этого довольно изящного
Main
метода:источник
Нет контрпримеров с C ^ Z <= 1.0E27.
По состоянию на февраль 2019 года я проверяю до C ^ Z <= 1.0E29 в предположении, что показатель степени «X» и / или «Y» должен быть> = 5.
Текущая версия этой программы («X» и / или «Y»> = 5) занимает меньше 1 секунды на AMD 2920X, чтобы найти все решения для C ^ Z <= 1.0E15. (Но все gcd (A, B, C)> = 2)
Подробности на http://www.durangobill.com/BealsConjecture.html
Я могу изменить текущий код (использует «C» и OpenMP) за эти пределы, но для его запуска потребуется более 128 ГБ ОЗУ. (Сотни процессоров также помогут. Тысячи процессоров будут еще лучше.) (Если у вас есть свободный доступ к чему-то подобному, пожалуйста, свяжитесь со мной.)
Мой адрес электронной почты находится на моей домашней странице http://www.durangobill.com
источник
Второй вариант поисковой программы Била завершен. Результаты:
Подробности на: http://www.durangobill.com/BealsConjecture.html
Следующие два вопроса: 1) Может ли суперкомпьютер расширить поиск? 2) Если бы суперкомпьютер мог расширить поиск, будет ли это практичным?
1) Чтобы расширить любой из вышеперечисленных поисков до 1.0E30, потребуется 300 ГБ ОЗУ на ядро, если ядра не могут совместно использовать 300 ГБ. Для каждого дополнительного дополнительного приращения экспоненциальной мощности, превышающей 1.0E30, объем требуемой оперативной памяти увеличивается как минимум в 2,2 раза.
2) Количество вычислительной мощности, необходимой для каждого последующего инкрементального увеличения показателя степени до 1,0E30 и более, умножает объединенное время ЦП примерно на 3,8. Поиск до 1.0E29 занял 2 недели с использованием 12 ядер. Время на суперкомпьютерах, как правило, не является «бесплатным», и вероятность того, что существуют какие-либо контрпримеры, очень мала.
В качестве руководства по эффективности кода на сайте durangobill.com/BealE29code.txt каждое из 12 ядер в среднем выполняло 220 миллионов итераций цикла в секунду для внутреннего цикла. (Среднее значение для двухнедельного прогона.) (Увеличение оперативной памяти сверх того, что было у меня, увеличило бы эту среднюю скорость почти в 2 раза.)
Я позволю Остину ответить 1) и 2), поскольку у него есть доступ к суперкомпьютеру, а у меня нет. (Если по какому-то удаленному случаю оба «1» и «2» являются «go», я могу предоставить код «C» с предупреждением о том, что я не знаком с многопоточными инструкциями для больших кластеров суперкомпьютеров.)
источник
Пришлось поместить это в 2 комментария, чтобы заставить это соответствовать.
Основные массивы распределяются следующим образом:
(Вам понадобится 128 ГБ ОЗУ для этих массивов)
с:
«Base» на самом деле нужно 33 бита (
cbrt(1.0E29)
) - дополнительный бит вставляется в «Power» (который требует только 7 бит).Массивы работают аналогично хеш-таблице. Однако, поскольку они отсортированы по PRIME1 и используются только как справочные таблицы, вам не нужны связанные списки для доступа к ним. Таким образом, результатом является очень быстрый линейный поиск по времени, чтобы увидеть, является ли пробный A ^ X + B ^ Y = любым C ^ Z.
Таким образом, операторы в самом внутреннем цикле имеют только два цикла.
Операторы «Pragma» контролируют количество используемых процессорных ядер (в данном случае 12) - все могут получить доступ к единственной копии массивов.
Вот «основной» код (в «C») (Надеюсь, что комментарии соответствуют длине опубликованной строки. Если нет, скопируйте их и вставьте код в какой-то документ с более длинной длиной строки.)
источник