Czy kod się kończy?


92

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.


2
Witamy w PPCG!
Luis Mendo

3
Kod można golfed do 50 bajtów: n=3 while sum(k*(n%k<1)for k in range(1,n))-n:n+=2.
xnor

13
To naprawdę świetna koncepcja. Miło jest widzieć takie oryginalne pomysły.
Nathan Merrill,

7
@Mego Myślę, że to wyzwanie działa tylko wtedy, gdy przyjmiesz nieskończone typy danych, które automatycznie przyjmą nieskończoną pamięć.
Martin Rosenau,

52
Kiedy przeczytałem tytuł, pomyślałem, że chcesz, abyśmy rozwiązali problem z zatrzymaniem ORAZ rozwiązanie golfa.
MrPaulch

Odpowiedzi:


29

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.

3
Muszę nauczyć się galaretki ...
noɥʇʎԀʎzɐɹƆ

19

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.

16

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                   

11

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ę.


1
Byłoby -~n**.5nie pracować w miejscu (n+1)**.5?
ETHproductions

@ETHproductions Pierwszeństwo potęgowania jest większe niż pierwszeństwo ~, więc wywołałoby to błąd TypeError za próbę bitowej negacji liczby zmiennoprzecinkowej.
Dennis

11

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)-$_.


3
Ponieważ istnieje skończona liczba możliwych zwykłych liczb perla, mogę faktycznie ustalić, czy ten program się zakończy, czy nie. Aby to zadziałało (lub zaimplementuj), musisz załadować pakiet bigint
Ton Hospel,

Zrób to. Wyzywam cię. :-)
Veky

11

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

8

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

8

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


Czy na pewno nawiasy są poprawnie umieszczone? Wygląda na to, że sprawdzasz, czy 2 ^ (n-1)! ≡ 1 (mod n ^ 3), a nie 2 ^ n ≡ 1 (mod n ^ 3). To prawda, że ​​nie znam tak dobrze priorytetu operatora Pythona.
Gabriel Benamy

Ups, kod jest poprawny, ale moje wyjaśnienie nie. Naprawię to.
Julian Rosen

2
można zastąpić (n-1)z~-n
Sriotchilism O'Zaic

7

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.


6

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.


6

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.


5

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.


Mam nadzieję, że ten problem i problem Sierpińskiego zostaną rozwiązane w najbliższej przyszłości, tylko z większą liczbą obliczeń.
qwr

4
Ten kod z pewnością się kończy, ponieważ po prostu wymieniasz dwa lambda, tak naprawdę nic nie wołasz . :-P
Veky,

4
W rzeczywistości nie. Twój kod wciąż się kończy, ponieważ semantyka języka Python2 jest zamrożona (PEP 404) i zawiera twardy limit rekurencyjnych wywołań fiat BDFL ( neopythonic.blogspot.hr/2009/04/final-words-on-tail-calls.html ). ;-P
Veky

2
@ Veky Musiałem głosować za komentarzem.
Qwerp-Derp,

1
Zaledwie kilka dni po napisaniu tego, prima 10223*2^31172165 + 1 została odkryta . Od tego 21181czasu jest najmniejszą liczbą, dla której nie wiadomo, czy to Sierpiński, czy nie.
Jeppe Stig Nielsen

4

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.


3
Nie będąc w stanie go odczytać, wątpię, by Twój kod działał dokładnie tak, jak twierdzisz. Czy szukasz pierwszej liczby, która przechodzi do pętli innej niż 4-2-1? Myślę, że nie znajdziesz go, jeśli istnieje mniejsza liczba, która nie kończy się żadną pętlą. W każdym razie, jeśli tak robi Twój kod, to wystarczy, aby nie wiedzieć, czy się skończy.
Christian Sievers

1
Szukam pierwszej liczby całkowitej> = 1, która idzie do pętli i nigdzie w obrębie przejścia do tej pętli nie ma 1.
Steven H.

3
Tego się spodziewałem. Ale to nie jedyny możliwy sposób, aby liczba nie spełniała hipotezy collatz.
Christian Sievers

W rzeczywistości udowodniono, że każda liczba albo odchyla się w nieskończoność, albo obejmuje 1-2-4 pod mapą Collatz. Twój kod nigdy się nie skończy. Chodzi o to, że sekwencja kroków tworząca pętlę tworzy równanie, którego jedynymi rozwiązaniami są 1-2-4, wartości ujemne i racjonalne wartości niecałkowite.
John Dvorak

3
@JanDvorak Nie wierzę, że to prawda. Czy możesz podać źródło?
KSFT,

4

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

4

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


3

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)

3

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!


Myślę, że możesz zaoszczędzić 6 bajtów g=lambda n:[p(b)*p(n-b)for b in range(n)]and g(n+2). Myślę też, że powinno to brzmieć: „zakończy się, jeśli hipoteza Goldbacha się nie utrzyma”.
Jonathan Allan

2

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óż.


Chociaż jest długi, jest sprytnie golfowy, więc daje +1.
wizzwizz4


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

@trichoplax Ah, „funkcja” tabulacji / spacji uderza ponownie ...
wizzwizz4,

1
Jeśli ktokolwiek również uzna konwersję tabulatorów za nieprzydatną,
odbędzie

1

Galaretka , 7 bajtów

*+3Ẓµ4#

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

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

0

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ć.


0

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


0

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 .

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

0

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.


Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.