Это проблема кода в гольф, о которой я подумал с математическим уклоном. Задача состоит в том, чтобы написать максимально короткий код, так что остается открытым вопрос, заканчивается ли код. Примером того, что я имею в виду, может быть следующий фрагмент кода на Python, адаптированный от anwser к этому вопросу cs stackexchange.
def is_perfect(n):
return sum(i for i in range(1, n) if n % i == 0) == n
n = 3
while not is_perfect(n):
n = n + 2
Математики предполагают, что не существует нечетных совершенных чисел, но это никогда не было доказано, поэтому никто не знает, закончится ли когда-нибудь этот фрагмент кода. Можете ли вы придумать другие фрагменты кода (возможно, опираясь на другие открытые проблемы, такие как гипотеза Коллатца или гипотеза двойных простых чисел), которые короче, но для которых неизвестно, заканчиваются ли они или нет?
Редактировать: Некоторые люди выдвинули хорошее дополнительное правило - решение вопроса должно быть детерминированным. Хотя было бы еще интереснее, если бы вы могли найти более короткие решения, используя недетерминизм. В этом случае правилом будет поиск фрагмента, для которого вероятность завершения неизвестна.
n=3
while sum(k*(n%k<1)for k in range(1,n))-n:n+=2
.Ответы:
Желе , 7 байт
Попробуйте онлайн!
Фон
Это закончится, как только он найдет четвертое решение проблемы Брокара , то есть решение n! + 1 = м² с (n, m) ≠ (4, 5), (5, 11), (7, 71) над положительными целыми числами. Реализация не использует арифметику с плавающей запятой, поэтому она прекратит работу, только если найдет четвертое решение или если n! больше не может быть представлен в памяти.
Проблема Брокара была впервые использована в этом ответе @xnor.
Как это устроено
источник
Желе ,
119 байтЭто закончится, как только будет найдено шестое простое число Ферма .
Попробуйте онлайн!
Как это устроено
источник
Pyth, 10 байт
Использует гипотезу, что все числа Ферма
2^(2^n)+1
составны дляn>4
.источник
Python, 36 байт
Использует проблему Брокара :
Вычисляет последовательные факториалы и проверяет, являются ли они квадратами и имеют ли они
k>7
. Спасибо Деннису за 2 байта!Это предполагает, что Python продолжает иметь точную арифметику для сколь угодно больших чисел. В фактической реализации это заканчивается.
источник
-~n**.5
будет работать на месте(n+1)**.5
?~
, так что это просто вызовет ошибку TypeError для попытки побитового вычисления с плавающей запятой.Perl,
5038363433 байтаПояснение: 196 - это возможное число Лихрелы - число, которое не образует палиндром при многократном добавлении его обратного к себе. Цикл продолжается до тех пор, пока $ n не станет равным его обратному, что пока неизвестно для начального значения 196.
который не действителен.
поэтому ни одно из чисел в этой последовательности не является действительным.
Редактировать: ударить его, используя цикл до вместо цикла (как-то). Кроме того, у меня было меньше байтов, чем я думал (вероятно, в будущем мне следует более внимательно посмотреть на мой счет байтов).
Редактировать: Заменено
$n
на,$_
чтобы сохранить 2 байта для подразумеваемого аргумента вreverse
. Я думаю, что это так же хорошо, как эта реализация.Редактировать: я был неправ. Вместо использования
until($%=reverse)==$_
я могу пойти в то время как разность равна нулю (т.е. истинно)while($%=reverse)-$_
.источник
MATL, 11 байт
Завершается, если гипотеза Гольдбаха неверна. Таким образом, программа останавливается, если находит четное число, большее, чем
2
это, которое не может быть выражено как сумма двух простых чисел.источник
05AB1E , 8 байтов
Завершится, когда будет найдено 6-е простое число Ферма .
объяснение
источник
Python,
3028 байтЭта программа остановится тогда и только тогда, когда существует целое число n, большее 1, такое, что 2 ^ (n-1) -1 делится на n ^ 3. Насколько мне известно, неизвестно, существует ли какое-либо число с этим свойством (если число, удовлетворяющее этому свойству, является простым, оно называется простым числом Вифериха порядка 3 к основанию 2 и открыто, существует ли какое-либо такое простое число).
источник
(n-1)
на~-n
Haskell, 47 байтов
Поиск первого квазиперфектного числа , представляющего собой число
n
, сумма делителей которого равна2*n+1
. Вместо добавления 1 я исключаю 1 из списка делителей.источник
Brain-Flak,
212208204 байтаЭта программа использует алгоритм умножения, написанный MegaTom, и неквадратную проверку, написанную 1000000000
Попробуйте онлайн
Эта программа начинается с 8 и проверяет каждое число, чтобы увидеть, является ли n! +1 квадратным числом. Он выходит, когда находит. Это известно как проблема Брокара, и это открытая проблема в математике.
источник
Brachylog (v2), 3 байта в кодировке Brachylog
Попробуйте онлайн! (истечет время, не делая ничего видимого по очевидным причинам)
Полная программа; если выполняется без ввода, ищет первое простое число Smarandache и выводит,
true.
если и когда оно находит. Это открытый вопрос относительно того, существуют ли какие-либо простые числа Smarandache. (Обратите внимание, что алгоритм простого тестирования Brachylog, хотя он теоретически работает на произвольно больших числах, имеет тенденцию работать на них медленно; поэтому, если вы заинтересованы в поиске простых чисел Smarandache, я рекомендую использовать другой язык.)объяснение
Брахилог работает с десятичными цифрами числа всякий раз, когда вы пытаетесь рассматривать его как список, поэтому «диапазон», за которым следует «конкатенация», - это очень краткий способ генерации последовательности чисел Смарандаша (а затем мы фильтруем ее по простоте; полное поведение программы по умолчанию заставит первый элемент полученного генератора). Диапазон имеет ведущий ноль, но, к счастью, при такой схеме потока, Brachylog удаляет ноль, а не сбой.
Вот пример, который находит первое число Smarandache, равное 6 (мод 11), как демонстрацию аналогичной программы, которая завершается в течение 60 секунд, а не имеет неизвестный статус остановки:
Попробуйте онлайн!
Это напечатало бы
true.
как полную программу, но я добавилZ
аргумент командной строки, чтобы фактически напечатать рассматриваемое число, давая лучшую демонстрацию, что этот общий подход работает.источник
Python 2, 88 байт
Этот код прекратит работу, если 10223 является числом Серпинского. 10223 в настоящее время является самым маленьким кандидатом, который может или не может быть числом Серпинского по состоянию на декабрь 2013 года.
Число Серпинского - это число,
k
в котором все числа формы(k * 2^n) + 1
составные.источник
10223*2^31172165 + 1
был обнаружен . С тех21181
пор было наименьшее число, для которого неизвестно, является ли он Серпиньским или нет.Pyth, 16 байт
Возвращает первое значение, для которого гипотеза Коллатца не выполняется. Поскольку неизвестно, верна ли гипотеза для всех чисел, неизвестно, завершится ли этот код.
источник
На самом деле , 16 байтов
Попробуйте онлайн!
Этот код завершается, если существует какое-то составное число,
n
такое, чтоtotient(n)
делитn-1
( общая проблема Лемера ).Объяснение:
источник
Желе ,
98 байт-1 байт благодаря @Dennis! (используйте возведение в степень вместо умножения, чтобы избежать
Æṣ(0)
)Вернет список с нулем и наименьшим нечетным совершенным числом , если оно существует.
Как?
источник
Haskell, 46 байтов
Завершает работу, если находит 4-е решение проблемы Брокара .
источник
Python, 92 байта
Это не победа в каких-либо соревнованиях по коду с кодом, и требует бесконечной памяти и глубины рекурсии, но это почти идеальная возможность решить интересную проблему, которую я задал на математическом стеке два года назад, что никакое число Фибоначчи больше 8 не является суммой из двух положительных кубов . Как ни странно, это началось как идея для игры в гольф, так что я думаю, что прошел полный круг.
источник
Python 2,
1239892 байтаЭтот код завершится, если гипотеза Гольдбаха не верна для всех четных чисел (т. Е. Если все четные числа могут быть выражены как сумма двух простых чисел). В настоящее время он был проверен на числа до 4 * 10 ^ 18.
Огромное спасибо @Pietu1998 за то, что сильно сократили мой код!
РЕДАКТИРОВАТЬ: Спасибо @JonathanAllan за сокращение 6 байт от моего кода!
источник
g=lambda n:[p(b)*p(n-b)for b in range(n)]and g(n+2)
. Я также думаю , что это должно быть «будет прекращено , если гипотеза Гольдбаха вовсе не держать».JavaScript (ES6),
104101 байтИспользует тот же метод, что и в ответе Perl: устанавливает n равным 196, затем многократно добавляет n к своему обратному основанию 10, пока он не станет палиндромом в базовом 10. Это было бы короче, если бы JS поддерживал числа с произвольной точностью, ну да ладно.
источник
Python, 80 байт
Завершается, если гипотеза Коллатца оказывается ложной. Смотрите этот вопрос .
источник
Python 2, 64 байта
Нет число Lychrel не было доказано , что существует в базе десяти. 196 - наименьший базовый десятый кандидат чисел Лихрел. Было показано, что если бы существовал палиндром (в котором 196 не число Лихрела), он имел бы по меньшей мере миллиард (10 ^ 9) цифр, потому что люди так долго запускали алгоритм.
источник
Желе , 7 байт
Попробуйте онлайн! (печатает два элемента, а не 4, чтобы вы могли увидеть его остановку)
объяснение
источник
R, 30 байт, спорно ли детерминированный
По умолчанию генератор случайных чисел R имеет равнораспределение в 653 последовательных измерениях, но в 654 измерениях он неизвестен. Таким образом, может быть или не быть последовательность псевдослучайных чисел, которые выбирают самый низкий элемент из данного вектора 654 раза подряд (здесь вектор
1:2
).Поскольку RNG R является периодическим (хотя и с очень длительным периодом), я утверждаю, что это является детерминированным, так как он в конечном итоге будет циклически возвращаться к началу. Ваши мнения могут отличаться, конечно.
источник
Python 3, 101 байт
Я знаю, что это дольше, чем у многих, но я потратил много времени, чтобы увидеть, как быстро я смогу сыграть в гольф.
Это попытка опровергнуть гипотезу Эйлера о сумме полномочий для
k=6
(не существует положительного целочисленного решения диофантова уравненияA^6+B^6+C^6+D^6+E^6==F^6
), для которой не найдено никакого контрпримера.В Python 2 (104 байта):
Менее гольф:
Мати версия без оценки:
Альтернативная ссылка: гипотеза Эйлера о сумме полномочий - MathWorld
источник
Python, 68 байт
Попробуйте онлайн
Пытается ответить на один из вопросов Гельфанда .
источник
Clojure, 154 байта
Проверяет, существует ли число выше 82 000, которое содержит только 0 и 1 для основания 2 вплоть до основания 5. Другими словами, оно проверяет, есть ли другое число в этой последовательности .
В этой специальной группе, есть только три цифры:
0
,1
и82,000
. Нет больше чисел, которые следуют этому правилу, которые меньше чем приблизительно3*10^19723
.источник
Пыть , 14 байт
Порт ответа mbomb007 .
источник