Код заканчивается?

92

Это проблема кода в гольф, о которой я подумал с математическим уклоном. Задача состоит в том, чтобы написать максимально короткий код, так что остается открытым вопрос, заканчивается ли код. Примером того, что я имею в виду, может быть следующий фрагмент кода на 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

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

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

Болтон Бейли
источник
2
Добро пожаловать в PPCG!
Луис Мендо
3
Ваш код может быть golfed до 50 байт: n=3 while sum(k*(n%k<1)for k in range(1,n))-n:n+=2.
xnor
13
Это действительно отличная концепция. Приятно видеть такие оригинальные идеи.
Натан Меррилл
7
@Mego Я думаю, что эта задача работает, только если вы предполагаете бесконечные типы данных, которые автоматически предполагают бесконечную память
Мартин Розенау
52
Когда я прочитал заголовок, я подумал, что вы хотите, чтобы мы решили проблему остановки и нашли решение.
MrPaulch

Ответы:

29

Желе , 7 байт

!‘Ʋµ4#

Попробуйте онлайн!

Фон

Это закончится, как только он найдет четвертое решение проблемы Брокара , то есть решение n! + 1 = м² с (n, m) ≠ (4, 5), (5, 11), (7, 71) над положительными целыми числами. Реализация не использует арифметику с плавающей запятой, поэтому она прекратит работу, только если найдет четвертое решение или если n! больше не может быть представлен в памяти.

Проблема Брокара была впервые использована в этом ответе @xnor.

Как это устроено

!‘Ʋµ4#  Main link. No arguments. Implicit argument: 0

    µ4#  Convert the links to the left into a monadic chain and call it with
         arguments k = 0, 1, 2, ... until 4 of them return 1.
!        Factorial; yield k!.
 ‘       Increment; yield k! + 1.
  Ʋ     Squareness; return 1 if k! + 1 is a perfect square, 0 if not.
Деннис
источник
3
Мне нужно научиться желе ...
noɥʇʎԀʎzɐɹƆ
19

Желе , 11 9 байт

ÆẸ⁺‘ÆPµ6#

Это закончится, как только будет найдено шестое простое число Ферма .

Попробуйте онлайн!

Как это устроено

ÆẸ⁺‘ÆPµ6#  Main link. No arguments. Implicit argument: 0

      µ6#  Convert the links to the left into a monadic chain and call it with
           arguments k = 0, 1, 2, ... until 6 of them return 1.
ÆẸ         Convert [k] to the integer with that prime exponent factorization, i.e.,
           into 2 ** k.
  ⁺        Repeat.
   ‘       Increment.
           We've now calculated 2 ** 2 ** k + 1.
    ÆP     Test the result for primality.
Деннис
источник
16

Pyth, 10 байт

fP_h^2^2T5

Использует гипотезу, что все числа Ферма 2^(2^n)+1 составны для n>4.

f        5   Find the first number T>=5 for which
   h^2^2T    2^(2^T)+1
 P_          is prime                   
XNOR
источник
11

Python, 36 байт

k=n=1
while(n+1)**.5%1+7/k:k+=1;n*=k

Использует проблему Брокара :

Является ли n! +1 идеальным квадратом для любого n≥8?

Вычисляет последовательные факториалы и проверяет, являются ли они квадратами и имеют ли они k>7. Спасибо Деннису за 2 байта!

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

XNOR
источник
1
Не -~n**.5будет работать на месте (n+1)**.5?
ETHproductions
@ETHproductions Приоритет возведения в степень выше, чем приоритет ~, так что это просто вызовет ошибку TypeError для попытки побитового вычисления с плавающей запятой.
Денис
11

Perl, 50 38 36 34 33 байта

$_=196;$_+=$%while($%=reverse)-$_

Пояснение: 196 - это возможное число Лихрелы - число, которое не образует палиндром при многократном добавлении его обратного к себе. Цикл продолжается до тех пор, пока $ n не станет равным его обратному, что пока неизвестно для начального значения 196.

25 + 52 = 77

который не действителен.

96 + 69 = 165
165 + 561 = 726
726 + 627 = 1353
1353 + 3531 = 4884

поэтому ни одно из чисел в этой последовательности не является действительным.

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

Редактировать: Заменено $nна, $_чтобы сохранить 2 байта для подразумеваемого аргумента в reverse. Я думаю, что это так же хорошо, как эта реализация.

Редактировать: я был неправ. Вместо использования until($%=reverse)==$_я могу пойти в то время как разность равна нулю (т.е. истинно) while($%=reverse)-$_.

Габриэль Бенами
источник
3
Поскольку существует конечное число возможных простых чисел perl, я могу фактически определить, завершается ли эта программа или нет. Вам нужно загрузить пакет bigint, чтобы сделать эту работу (или внедрить ее)
Тон Хоспел
Сделай это. Попробуй. :-)
Veky
11

MATL, 11 байт

`@QEtZq&+=z

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

`        % Do...while
  @      %   Push iteration index k. Gives 1, 2, 3, ...
  QE     %   Add 1 and multiply by 2. Gives 4, 6, 8, ...
  tZq    %   Duplicate. Push all primes up to current k
  &+     %   Matrix with all pairwise additions of those primes
  =z     %   Number of entries of that matrix that equal k. This is used as loop
         %   condition. That is, the loop continues if this number is nonzero
         % Implicit end
Луис Мендо
источник
8

05AB1E , 8 байтов

Завершится, когда будет найдено 6-е простое число Ферма .

5µNoo>p½

объяснение

5µ          # loop over increasing N (starting at 1) until counter reaches 5
  Noo       # 2^2^N
     >      # + 1
      p½    # if prime, increase counter
Emigna
источник
8

Python, 30 28 байт

n=2
while 2**~-n%n**3-1:n+=1

Эта программа остановится тогда и только тогда, когда существует целое число n, большее 1, такое, что 2 ^ (n-1) -1 делится на n ^ 3. Насколько мне известно, неизвестно, существует ли какое-либо число с этим свойством (если число, удовлетворяющее этому свойству, является простым, оно называется простым числом Вифериха порядка 3 к основанию 2 и открыто, существует ли какое-либо такое простое число).

Джулиан Розен
источник
Вы уверены, что круглые скобки размещены правильно? Похоже, вы тестируете, чтобы увидеть, если 2 ^ (n-1)! ≡ 1 (мод n ^ 3), а не 2 ^ n ≡ 1 (мод n ^ 3). Конечно, я не очень хорошо знаю приоритет оператора Python.
Габриэль Бенами
Ой, код правильный, но мое объяснение не так. Я исправлю это.
Джулиан Розен
2
Вы можете заменить (n-1)на~-n
Wheat Wizard
7

Haskell, 47 байтов

[n|n<-[1..],2*n==sum[d|d<-[2..n],n`mod`d<1]]!!0

Поиск первого квазиперфектного числа , представляющего собой число n, сумма делителей которого равна 2*n+1. Вместо добавления 1 я исключаю 1 из списка делителей.

Кристиан Сиверс
источник
6

Brain-Flak, 212 208 204 байта

Эта программа использует алгоритм умножения, написанный MegaTom, и неквадратную проверку, написанную 1000000000

Попробуйте онлайн

(((()()()()){})){{}((({}()))<{(({})[()])}{}>[()]){({}<({}<>)({<({}[()])><>({})<>}{}<><{}>)>[()])}{}(({}())){(({}[()]<>)<>)(({({})({}[()])}{}[({})]<>)){{}{}({}<>)(<([()])>)}{}({}()){(((<{}{}<>{}>)))}{}}{}}

Эта программа начинается с 8 и проверяет каждое число, чтобы увидеть, является ли n! +1 квадратным числом. Он выходит, когда находит. Это известно как проблема Брокара, и это открытая проблема в математике.

Мастер пшеницы
источник
6

Brachylog (v2), 3 байта в кодировке Brachylog

⟦cṗ

Попробуйте онлайн! (истечет время, не делая ничего видимого по очевидным причинам)

Полная программа; если выполняется без ввода, ищет первое простое число Smarandache и выводит, true.если и когда оно находит. Это открытый вопрос относительно того, существуют ли какие-либо простые числа Smarandache. (Обратите внимание, что алгоритм простого тестирования Brachylog, хотя он теоретически работает на произвольно больших числах, имеет тенденцию работать на них медленно; поэтому, если вы заинтересованы в поиске простых чисел Smarandache, я рекомендую использовать другой язык.)

объяснение

⟦cṗ
⟦     Form an increasing range from 0 to {the smallest number with no assertion failure} 
 c    Concatenate all the numbers that make up that range, in decimal
  ṗ   Assert that the result is prime

Брахилог работает с десятичными цифрами числа всякий раз, когда вы пытаетесь рассматривать его как список, поэтому «диапазон», за которым следует «конкатенация», - это очень краткий способ генерации последовательности чисел Смарандаша (а затем мы фильтруем ее по простоте; полное поведение программы по умолчанию заставит первый элемент полученного генератора). Диапазон имеет ведущий ноль, но, к счастью, при такой схеме потока, Brachylog удаляет ноль, а не сбой.

Вот пример, который находит первое число Smarandache, равное 6 (мод 11), как демонстрацию аналогичной программы, которая завершается в течение 60 секунд, а не имеет неизвестный статус остановки:

⟦c{-₆~×₁₁&}

Попробуйте онлайн!

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

ais523
источник
5

Python 2, 88 байт

p=lambda n:all(n%x for x in range(2,n))
s=lambda n:0if p((10223*2**n)+1)else s(n+1)
s(0)

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

Число Серпинского - это число, kв котором все числа формы (k * 2^n) + 1составные.

Qwerp-Derp
источник
Я надеюсь, что эта проблема и проблема Серпинского будут решены в ближайшем будущем, просто с большим количеством вычислений.
QWR
4
Этот код обязательно завершается, так как вы просто называете две лямбды, на самом деле вы ничего не вызываете . :-P
Veky
4
На самом деле вы этого не сделали. Ваш код по-прежнему всегда завершается, так как семантика Python2 заморожена (PEP 404) и включает жесткое ограничение на рекурсивные вызовы по указу BDFL ( neopythonic.blogspot.hr/2009/04/final-words-on-tail-calls.html). ). ;-P
Веки
2
@Veky Должен был поднять ваш комментарий.
Qwerp-Derp
1
Спустя несколько дней после того, как это было написано, премьер 10223*2^31172165 + 1 был обнаружен . С тех 21181пор было наименьшее число, для которого неизвестно, является ли он Серпиньским или нет.
Джеппе Стиг Нильсен
4

Pyth, 16 байт

f!}1.u@,/G2h*3GG

Возвращает первое значение, для которого гипотеза Коллатца не выполняется. Поскольку неизвестно, верна ли гипотеза для всех чисел, неизвестно, завершится ли этот код.

Стивен Х.
источник
3
Не имея возможности прочитать его, я сомневаюсь, что ваш код делает именно то, что вы утверждаете. Вы ищете первое число, которое идет в петлю, отличную от 4-2-1? Я думаю, вы не найдете его, если есть меньшее число, которое не заканчивается ни в одном цикле. Во всяком случае, если это то, что делает ваш код, этого достаточно, чтобы не знать, закончится ли он.
Кристиан Сиверс
1
Я ищу первое целое число> = 1, которое идет в цикл, и нигде в обходе этого цикла не содержится 1.
Стивен Х.
3
Это то, что я ожидал. Но это не единственный мыслимый способ для числа не удовлетворить гипотезу Коллатца.
Кристиан Сиверс
Фактически, было доказано, что каждое число либо расходится до бесконечности, либо укрывается до 1-2-4 по карте Коллатца. Ваш код никогда не прекратит работу. Идея состоит в том, что последовательность шагов, образующих цикл, устанавливает уравнение, единственными решениями которого являются 1-2-4, отрицательные значения и нецелые рациональные числа.
Джон Дворак
3
@JanDvorak Я не верю, что это правда. Можете ли вы привести источник?
KSFT
4

На самом деле , 16 байтов

1`;;pY)▒@D÷íu*`╓

Попробуйте онлайн!

Этот код завершается, если существует какое-то составное число, nтакое, что totient(n)делит n-1( общая проблема Лемера ).

Объяснение:

1`;;pY)▒@D÷íu*`╓
1`            `╓  first integer, starting with 0, where the following function leaves a truthy value on top of the stack:
    pY       *      composite (not prime) and
   ;  )▒            totient(n)
  ;     @D֒u       is in the list of divisors of n-1
Мего
источник
4

Желе , 9 8 байт

-1 байт благодаря @Dennis! (используйте возведение в степень вместо умножения, чтобы избежать Æṣ(0))

*ḂÆṣ=µ2#

Вернет список с нулем и наименьшим нечетным совершенным числом , если оно существует.

Как?

*ḂÆṣ=µ2# - Main link: no arguments
     µ   - monadic chain separation
      2# - count up from implicit `n=0` and return the first 2 truthy results of
 Ḃ       -     mod 2        -> n%2
*        -     exponentiate -> n**(n%2)  (1 when n is even, n when n is odd)
  Æṣ     -     sum of proper divisors of n**(n%2)
    =    -     equals n?    -> 1 if n is zero or both perfect and odd, else 0
Джонатан Аллан
источник
3

Python, 92 байта

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

def f(i,j):
 r=range(i)
 for a in r:
  for b in r:
   if a**3+b**3==i:1/0
 f(j,i+j)
f(13,21)
qwr
источник
3

Python 2, 123 98 92 байта

p=lambda n,k=2:n<=k or n%k*p(n,k+1)
g=lambda n:[p(b)*p(n-b)for b in range(n)]and g(n+2)
g(4)

Этот код завершится, если гипотеза Гольдбаха не верна для всех четных чисел (т. Е. Если все четные числа могут быть выражены как сумма двух простых чисел). В настоящее время он был проверен на числа до 4 * 10 ^ 18.

Огромное спасибо @Pietu1998 за то, что сильно сократили мой код!

РЕДАКТИРОВАТЬ: Спасибо @JonathanAllan за сокращение 6 байт от моего кода!

Qwerp-Derp
источник
Я думаю, что вы можете сэкономить 6 байтов с g=lambda n:[p(b)*p(n-b)for b in range(n)]and g(n+2). Я также думаю , что это должно быть «будет прекращено , если гипотеза Гольдбаха вовсе не держать».
Джонатан Аллан
2

JavaScript (ES6), 104 101 байт

for(n=[6,9,p=1];!p;n=n.map((x,i)=>(q=n[n.length+~i],p|=x^q,c=q+x+c/10|0)%10).concat(c/10|0||[]))c=p=0

Использует тот же метод, что и в ответе Perl: устанавливает n равным 196, затем многократно добавляет n к своему обратному основанию 10, пока он не станет палиндромом в базовом 10. Это было бы короче, если бы JS поддерживал числа с произвольной точностью, ну да ладно.

ETHproductions
источник
Хотя это долго, это ловко в гольф, так что +1.
wizzwizz4
2

Python, 80 байт

Завершается, если гипотеза Коллатца оказывается ложной. Смотрите этот вопрос .

n=2
while 1:
 L=[];x=n
 while~-n:1/(n not in L);L+=[n];n=(n/2,n*3+1)[n%2]
 n=x+1
mbomb007
источник
Это отвратительно, но и красиво.
Джеймс Мерфи
1

Python 2, 64 байта

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

Нет число Lychrel не было доказано , что существует в базе десяти. 196 - наименьший базовый десятый кандидат чисел Лихрел. Было показано, что если бы существовал палиндром (в котором 196 не число Лихрела), он имел бы по меньшей мере миллиард (10 ^ 9) цифр, потому что люди так долго запускали алгоритм.

n=196
while 1:
    x=str(n);r=x[::-1]
    if x!=r:n=n+int(r)
    else:1/0
mbomb007
источник
@trichoplax Ах, "особенность" вкладок / пробелов снова
появляется
1
Если кто-то еще находит преобразование вкладок бесполезным, есть обсуждение мета ...
trichoplax
1

Желе , 7 байт

*+3Ẓµ4#

Попробуйте онлайн! (печатает два элемента, а не 4, чтобы вы могли увидеть его остановку)

NNN+3

объяснение

*+3Ẓµ4#
     4#  Find the first four numbers with the following property:
    µ      (bracketing/grouping: place everything to the left inside the loop)
*          {The number} to the power of {itself}
 +3        plus 3
   Ẓ       is prime
ais523
источник
0

R, 30 байт, спорно ли детерминированный

while(any(sample(2,654,T)>1))1

По умолчанию генератор случайных чисел R имеет равнораспределение в 653 последовательных измерениях, но в 654 измерениях он неизвестен. Таким образом, может быть или не быть последовательность псевдослучайных чисел, которые выбирают самый низкий элемент из данного вектора 654 раза подряд (здесь вектор 1:2).

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

JDL
источник
0

Python 3, 101 байт

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

Это попытка опровергнуть гипотезу Эйлера о сумме полномочий для k=6(не существует положительного целочисленного решения диофантова уравнения A^6+B^6+C^6+D^6+E^6==F^6), для которой не найдено никакого контрпримера.

R=[1]
while 1:R+=[R[-1]+1];eval(("[1/("+"+%s**6"*5+"!=%%s**6)%s]"%("for %s in R "*6))%(*"ABCDEF"*2,))

В Python 2 (104 байта):

R=[1]
while 1:R+=[R[-1]+1];eval(("[1/("+"+%s**6"*5+"!=%%s**6)%s]"%("for %s in R "*6))%tuple("ABCDEF"*2))

Менее гольф:

x=2
while 1:
    R=range(1,x)
    [1/(A**6+B**6+C**6+D**6+E**6!=F**6)for F in R for E in R for D in R for C in R for B in R for A in R]
    x+=1

Мати версия без оценки:

R=range
x=2
while 1:
    for i in R(x**6):1/(sum(map(lambda x:x**6,[1+(i%x**-~j/x**j)for j in R(6)]))-i%x-1)
    x+=1

Альтернативная ссылка: гипотеза Эйлера о сумме полномочий - MathWorld

mbomb007
источник
0

Clojure, 154 байта

(loop[x 82001](if(= 0(reduce +(map{true 1 false 0}(for[y(range 3 6)](true?(for[z(str(range 2 y))](.indexOf z(Integer/toString x y))))))))x(recur(inc x))))

Проверяет, существует ли число выше 82 000, которое содержит только 0 и 1 для основания 2 вплоть до основания 5. Другими словами, оно проверяет, есть ли другое число в этой последовательности .

В этой специальной группе, есть только три цифры: 0, 1и 82,000. Нет больше чисел, которые следуют этому правилу, которые меньше чем приблизительно 3*10^19723.

Qwerp-Derp
источник