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.
n=3
while sum(k*(n%k<1)for k in range(1,n))-n:n+=2
.Odpowiedzi:
Galaretka , 7 bajtów
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
źródło
Galaretka ,
119 bajtówZakończy się, gdy zostanie znaleziona szósta liczba pierwsza Fermata .
Wypróbuj online!
Jak to działa
źródło
Pyth, 10 bajtów
Wykorzystuje przypuszczenie, że wszystkie liczby Fermata
2^(2^n)+1
są złożonen>4
.źródło
Python, 36 bajtów
Wykorzystuje problem Brocarda :
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ę.
źródło
-~n**.5
nie pracować w miejscu(n+1)**.5
?~
, więc wywołałoby to błąd TypeError za próbę bitowej negacji liczby zmiennoprzecinkowej.Perl,
5038363433 bajtówObjaś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.
co nie jest poprawne.
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
$n
z$_
zaoszczędzić 2 bajty dla domniemanych argumentreverse
. 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)-$_
.źródło
MATL, 11 bajtów
Kończy się, jeśli hipoteza Goldbacha jest fałszywa. Oznacza to, że program zatrzymuje się, jeśli znajdzie liczbę parzystą większą niż
2
ta, której nie można wyrazić jako sumę dwóch liczb pierwszych.źródło
05AB1E , 8 bajtów
Zakończy się, gdy zostanie znaleziona szósta liczba pierwsza Fermata .
Wyjaśnienie
źródło
Python,
3028 bajtówTen 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).
źródło
(n-1)
z~-n
Haskell, 47 bajtów
Przeszukanie pierwszego quasiperfect numer , który jest liczbą,
n
której suma dzielników jest2*n+1
. Zamiast dodawać 1, wykluczam 1 z listy dzielników.źródło
Brain-Flak,
212208204 bajtówTen 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.
źródło
Brachylog (v2), 3 bajty w kodowaniu Brachylog
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
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:
Wypróbuj online!
Zostałoby to wydrukowane
true.
jako pełny program, ale wrzuciłemZ
argument wiersza poleceń, aby faktycznie wydrukować dany numer, dając lepszą demonstrację, że to ogólne podejście działa.źródło
Python 2, 88 bajtów
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,
k
w której wszystkie liczby postaci(k * 2^n) + 1
są złożone.źródło
10223*2^31172165 + 1
została odkryta . Od tego21181
czasu jest najmniejszą liczbą, dla której nie wiadomo, czy to Sierpiński, czy nie.Pyth, 16 bajtów
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.
źródło
Właściwie 16 bajtów
Wypróbuj online!
Ten kod kończy się, jeśli istnieje pewna liczba złożona
n
, któratotient(n)
dzielin-1
( problem totalny Lehmera ).Wyjaśnienie:
źródło
Galaretka ,
98 bajtów-1 bajt dzięki @Dennis! (użyj potęgowania zamiast mnożenia, aby uniknąć
Æṣ(0)
)Zwraca listę zero i najmniejszą nieparzystą liczbę doskonałą , jeśli taka istnieje.
W jaki sposób?
źródło
Haskell, 46 bajtów
Kończy się, jeśli znajdzie czwarte rozwiązanie problemu brocarda .
źródło
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.
źródło
Python 2,
1239892 bajtyTen 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!
źródło
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”.JavaScript (ES6),
104101 bajtówUż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óż.
źródło
Python, 80 bajtów
Kończy się, jeśli hipoteza Collatza okaże się fałszywa. Zobacz to pytanie .
źródło
Python 2, 64 bajty
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.
źródło
Galaretka , 7 bajtów
Wypróbuj online! (drukuje dwa elementy, a nie 4, dzięki czemu można zobaczyć, jak się zatrzymał)
Wyjaśnienie
źródło
R, 30 bajtów, można argumentować, czy jest deterministyczny
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ć.
źródło
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łkowitejA^6+B^6+C^6+D^6+E^6==F^6
), dla której nie znaleziono kontrprzykładu.W Pythonie 2 (104 bajty):
Mniej golfa:
Wersja Mathy bez ewaluacji:
Alternatywne odniesienie: Euler's Sum of Powers Conjecture - MathWorld
źródło
Python, 68 bajtów
Wypróbuj online
Próbuje odpowiedzieć na jedno z pytań Gelfanda .
źródło
Clojure, 154 bajtów
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
,1
i82,000
. Nie ma więcej liczb zgodnych z tą zasadą, które są mniejsze niż w przybliżeniu3*10^19723
.źródło
Pyt , 14 bajtów
Port odpowiedzi mbomb007 .
źródło