Jest to wyzwanie golfa kodu, o którym myślałem z matematyki. Wyzwanie polega na napisaniu możliwie najkrótszego kodu, tak aby było otwarte pytanie, czy kod się kończy. Przykładem tego, co mam na myśli mógłby być następujący fragment kodu Pythona, dostosowany od anwser do tego cs Stack Exchange Network pytanie.

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

Matematycy przypuszczają, że nie ma nieparzystych liczb doskonałych, ale nigdy nie zostało to udowodnione, więc nikt nie wie, czy ten fragment kodu kiedykolwiek się skończy. Czy możesz wymyślić inne fragmenty kodu (być może polegające na innych otwartych problemach, takich jak hipoteza Collatza lub hipoteza podwójnych liczb pierwszych), które są krótsze, ale dla których nie wiadomo, czy się kończą?

Edycja: Niektóre osoby wprowadziły dobrą dodatkową zasadę - Rozwiązania tego pytania powinny być deterministyczne. Chociaż może być jeszcze bardziej interesujące, jeśli można znaleźć krótsze rozwiązania wykorzystujące niedeterminizm. W takim przypadku regułą byłoby znalezienie fragmentu, dla którego prawdopodobieństwo zakończenia nie jest znane.

Galaretka , 7 bajtów

!‘Ʋµ4#

Wypróbuj online!

tło

Zakończy się, gdy znajdzie czwarte rozwiązanie problemu Brocarda , tj. Rozwiązanie n! + 1 = m² z (n, m) ≠ (4, 5), (5, 11), (7, 71) ponad dodatnimi liczbami całkowitymi. Implementacja nie używa arytmetyki zmiennoprzecinkowej, więc zakończy się tylko, jeśli znajdzie czwarte rozwiązanie lub jeśli n! nie może być już reprezentowany w pamięci.

Problem Brocarda został po raz pierwszy użyty w tej odpowiedzi przez @xnor.

Jak to działa

!‘Ʋµ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.

Galaretka , 11 9 bajtów

ÆẸ⁺‘ÆPµ6#

Zakończy się, gdy zostanie znaleziona szósta liczba pierwsza Fermata .

Wypróbuj online!

Jak to działa

ÆẸ⁺‘Æ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.

Pyth, 10 bajtów

fP_h^2^2T5

Wykorzystuje przypuszczenie, że wszystkie liczby Fermata 2^(2^n)+1 są złożone n>4.

f        5   Find the first number T>=5 for which
   h^2^2T    2^(2^T)+1
 P_          is prime                   

Python, 36 bajtów

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

Wykorzystuje problem Brocarda :

Czy n! +1 to idealny kwadrat dla dowolnego n≥8?

Oblicza kolejne silnie i sprawdza, czy są kwadratami i mają k>7. Dzięki Dennis za 2 bajty!

Zakłada się, że Python nadal ma dokładną arytmetykę dla dowolnie dużych liczb. W rzeczywistej realizacji kończy się.

Perl, 50 38 36 34 33 bajtów

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

Objaśnienie: 196 jest możliwą liczbą Lychrel - liczbą, która nie tworzy palindromu poprzez wielokrotne dodawanie do siebie swojej odwrotności. Pętla trwa do momentu, gdy $ n będzie równa jej odwrotności, która jest jeszcze nieznana dla wartości początkowej 196.

25 + 52 = 77

co nie jest poprawne.

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

więc żadna z liczb w tej sekwencji nie jest poprawna.

Edycja: Grałem w golfa za pomocą pętli till zamiast pętli for (jakoś). Ponadto miałem mniej bajtów, niż myślałem (prawdopodobnie powinienem bardziej uważnie przyjrzeć się mojej liczbie bajtów w przyszłości).

Edit: Wymieniłem $nz $_zaoszczędzić 2 bajty dla domniemanych argument reverse. Myślę, że jest to tak skomplikowane, jak to wdrożenie.

Edycja: Myliłem się. Zamiast używania until($%=reverse)==$_mogę iść, gdy różnica jest niezerowe (czyli prawda) while($%=reverse)-$_.

MATL, 11 bajtów

`@QEtZq&+=z

Kończy się, jeśli hipoteza Goldbacha jest fałszywa. Oznacza to, że program zatrzymuje się, jeśli znajdzie liczbę parzystą większą niż 2ta, której nie można wyrazić jako sumę dwóch liczb pierwszych.

`        % 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

05AB1E , 8 bajtów

Zakończy się, gdy zostanie znaleziona szósta liczba pierwsza Fermata .

5µNoo>p½

Wyjaśnienie

5µ          # loop over increasing N (starting at 1) until counter reaches 5
  Noo       # 2^2^N
     >      # + 1
      p½    # if prime, increase counter

Python, 30 28 bajtów

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

Ten program zostanie zatrzymany tylko wtedy, gdy istnieje liczba całkowita n większa od 1, taka że 2 ^ (n-1) -1 jest podzielna przez n ^ 3. Według mojej wiedzy nie wiadomo, czy istnieje jakaś liczba z tą właściwością (jeśli liczba spełniająca tę właściwość jest liczbą pierwszą, nazywa się ją liczbą pierwszą Wiefericha rzędu 3 do podstawy 2 i jest otwarte, czy taka liczba pierwsza istnieje).

Haskell, 47 bajtów

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

Przeszukanie pierwszego quasiperfect numer , który jest liczbą, nktórej suma dzielników jest 2*n+1. Zamiast dodawać 1, wykluczam 1 z listy dzielników.

Brain-Flak, 212 208 204 bajtów

Ten program wykorzystuje algorytm mnożenia napisany przez MegaTom i moduł sprawdzania niekwadratowego napisany przez 1000000000

Wypróbuj online

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

Ten program rozpoczyna się od 8 i sprawdza każdą liczbę, aby sprawdzić, czy n! +1 jest liczbą kwadratową. Wyjdzie, gdy go znajdzie. Jest to znane jako problem Brocarda i jest otwartym problemem w matematyce.

Brachylog (v2), 3 bajty w kodowaniu Brachylog

⟦cṗ

Wypróbuj online! (z oczywistych powodów upłynie limit czasu bez robienia niczego widocznego)

Pełny program; jeśli działa bez danych wejściowych, wyszukuje pierwszą liczbę pierwszą Smarandache i wyświetla dane wyjściowe, true.jeśli ją znajdzie. Pytanie otwarte, czy istnieją liczby pierwsze Smarandache. (Zauważ, że algorytm testowania liczb pierwszych Brachylog, chociaż działa teoretycznie na dowolnie duże liczby, zwykle działa na nich powoli; dlatego jeśli jesteś zainteresowany samodzielnym znalezieniem liczb pierwszych Smarandache, zalecam użycie innego języka).

Wyjaśnienie

⟦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 działa na cyfrach dziesiętnych liczby za każdym razem, gdy próbujesz traktować ją jak listę, więc „zakres”, po którym następuje „konkatenat”, jest bardzo zwięzłym sposobem generowania sekwencji liczb Smarandache (a następnie filtrujemy ją według pierwotności; Brachylog's domyślne zachowanie pełnego programu wymusi wtedy pierwszy element generatora wynikowego). Zakres ma wiodące zero, ale na szczęście przy tym schemacie przepływu Brachylog usuwa zero, a nie zawodzi.

Oto przykład, w którym pierwsza liczba Smarandache jest równa 6 (mod 11), jako demonstracja podobnego programu, który kończy się w ciągu 60 sekund, a nie ma nieznanego stanu zatrzymania:

⟦c{-₆~×₁₁&}

Wypróbuj online!

Zostałoby to wydrukowane true.jako pełny program, ale wrzuciłem Zargument wiersza poleceń, aby faktycznie wydrukować dany numer, dając lepszą demonstrację, że to ogólne podejście działa.

Python 2, 88 bajtów

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)

Ten kod wygasa, jeśli 10223 to numer Sierpińskiego. 10223 jest obecnie najmniejszym kandydatem, który może, ale nie musi być numerem Sierpińskiego, od grudnia 2013 r.

Liczba Sierpińskiego to liczba, kw której wszystkie liczby postaci (k * 2^n) + 1są złożone.

Pyth, 16 bajtów

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

Zwraca pierwszą wartość, dla której nie istnieje hipoteza Collatza. Ponieważ nie wiadomo, czy domniemanie obowiązuje dla wszystkich liczb, nie wiadomo, czy ten kod się zakończy.

Właściwie 16 bajtów

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

Wypróbuj online!

Ten kod kończy się, jeśli istnieje pewna liczba złożona n, która totient(n)dzieli n-1( problem totalny Lehmera ).

Wyjaśnienie:

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

Galaretka , 9 8 bajtów

-1 bajt dzięki @Dennis! (użyj potęgowania zamiast mnożenia, aby uniknąć Æṣ(0))

*ḂÆṣ=µ2#

Zwraca listę zero i najmniejszą nieparzystą liczbę doskonałą , jeśli taka istnieje.

W jaki sposób?

*ḂÆṣ=µ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

Haskell, 46 bajtów

[n|m<-[1..],n<-[1..m],product[1..n]+1==m^2]!!3

Kończy się, jeśli znajdzie czwarte rozwiązanie problemu brocarda .

Python, 92 bajty

Nie wygrywa to żadnych zawodów golfowych i wymaga nieskończonej pamięci i głębokości rekurencji, ale jest to prawie idealna okazja, aby podłączyć interesujący problem, który zadałem podczas wymiany stosów matematycznych dwa lata temu, że żadna liczba Fibonacciego większa niż 8 nie jest sumą dwóch dodatnich kostek . Zabawne, że zaczęło się od pomysłu na golfa, więc chyba zatoczyłem koło.

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)

Python 2, 123 98 92 bajty

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)

Ten kod wygasa, jeśli hipoteza Goldbacha nie obowiązuje dla wszystkich liczb parzystych (tj. Jeśli wszystkie liczby parzyste można wyrazić jako sumę dwóch liczb pierwszych). Obecnie jest testowany na liczby do 4 * 10 ^ 18.

Ogromne podziękowania dla @ Pietu1998 za znaczne skrócenie mojego kodu!

EDYCJA: Dzięki @JonathanAllan za zgolenie 6 bajtów mojego kodu!

JavaScript (ES6), 104 101 bajtów

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

Używa tej samej metody, co odpowiedź Perla: ustawia n na 196, a następnie kilkakrotnie dodaje n do swojej odwrotnej podstawy 10, aż stanie się palindromem w podstawie 10. Byłoby to krótsze, gdyby JS obsługiwał liczby o dowolnej dokładności, ale no cóż.

Python, 80 bajtów

Kończy się, jeśli hipoteza Collatza okaże się fałszywa. Zobacz to pytanie .

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

Python 2, 64 bajty

Liczba Lychrel jest liczbą naturalną, która nie może utworzyć palindromu poprzez iteracyjny proces wielokrotnego odwracania cyfr i dodawania liczb wynikowych.

Nie udowodniono, że w bazie dziesiątej istnieją liczby Lychrel . 196 jest najmniejszym kandydatem dziesiątej liczby Lychrel. Wykazano, że jeśli istnieje palindrom (co powoduje, że 196 nie jest liczbą Lychrela), miałby co najmniej miliard (10 ^ 9) cyfr, ponieważ ludzie tak długo posługują się algorytmem.

n=196
while 1:
    x=str(n);r=x[::-1]
    if x!=r:n=n+int(r)
    else:1/0

Galaretka , 7 bajtów

*+3Ẓµ4#

Wypróbuj online! (drukuje dwa elementy, a nie 4, dzięki czemu można zobaczyć, jak się zatrzymał)

$n$$n^n+3$

Wyjaśnienie

*+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

R, 30 bajtów, można argumentować, czy jest deterministyczny

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

Domyślny generator liczb losowych R ma równomierny rozkład w 653 kolejnych wymiarach, ale nie jest znany w 654 wymiarach. Zatem może występować ciąg liczb pseudolosowych lub nie, które próbkują najniższy element z danego wektora 654 razy z rzędu (tutaj wektor 1:2).

Ponieważ RNG R jest okresowy (choć z bardzo długim okresem), twierdzę, że jest to deterministyczne, ponieważ ostatecznie zapętli się do początku. Twoje opinie mogą się oczywiście różnić.

Python 3, 101 bajtów

Wiem, że jest dłuższy niż wiele innych, ale spędziłem dużo czasu, obserwując, jak krótko mogę w to grać.

Próba obalenia hipotezy Sumy Mocy Eulera dla k=6(brak równania diofantyńskiego o dodatniej liczbie całkowitej A^6+B^6+C^6+D^6+E^6==F^6), dla której nie znaleziono kontrprzykładu.

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

W Pythonie 2 (104 bajty):

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

Mniej golfa:

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

Wersja Mathy bez ewaluacji:

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

Alternatywne odniesienie: Euler's Sum of Powers Conjecture - MathWorld

Python, 68 bajtów

n=2
while"".join(str((i+2)**n)[0]for i in range(8))!="23456789":n+=1

Wypróbuj online

Próbuje odpowiedzieć na jedno z pytań Gelfanda .

2. Czy wiersz „23456789” pojawi się kiedykolwiek dla n> 1? Żadne nie działa dla n <= 10 ^ 5. ...

Clojure, 154 bajtów

(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))))

Sprawdza, czy liczba powyżej 82 000 zawiera tylko 0 i 1 dla podstawy 2 aż do podstawy 5. Innymi słowy, sprawdza, czy w tej sekwencji jest inna liczba .

W tej szczególnej grupie, są tylko 3 numery: 0, 1i 82,000. Nie ma więcej liczb zgodnych z tą zasadą, które są mniejsze niż w przybliżeniu 3*10^19723.

Pyt , 14 bajtów

27*²0`ŕĐ₫+Đ₽¬ł

Port odpowiedzi mbomb007 .