Otrzymujesz funkcje: h1 (f, * args) i h2 (f, * args)

Obie są metodami, które są już dla Ciebie zdefiniowane (tutaj gwiazdka wskazuje zmienną liczbę argumentów)

f jest funkcją, * args to lista parametrów, które należy przekazać tej funkcji

h1 zwraca wartość logiczną: Prawda, jeśli funkcja f kiedykolwiek się zatrzymuje po wywołaniu * args, a False, jeśli nie (zakładając, że uruchomiona maszyna ma nieskończony czas i pamięć oraz że interpreter / kompilator języka, w którym piszesz umie obsługiwać nieskończony czas i pamięć).

Jeśli f (* args) kiedykolwiek wykona wywołanie do h1 lub h2, h1 zgłasza wyjątek

h2 zachowuje się dokładnie tak, jak h1, z wyjątkiem tego, że jeśli f wywoła h1, wówczas h2 nie zgłosi wyjątku

W jak najmniejszej liczbie znaków napisz program, który nie pobiera danych wejściowych i powinien wypisać:

The Collatz Conjecture is {True/False}
Goldbach's Conjecture is {True/False}
The Twin Primes Conjecture is {True/False}

na podstawie ważności każdej z tych przypuszczeń.

Oto linki do Wikipedii wyjaśniające każdą z przypuszczeń:

http://en.wikipedia.org/wiki/Collatz_conjecture

http://en.wikipedia.org/wiki/Goldbach%27s_conjecture

http://en.wikipedia.org/wiki/Twin_prime

Możesz założyć, że dowolna duża biblioteka liczb całkowitych w dowolnym języku, który wybierzesz, z powodzeniem reprezentuje dowolne duże liczby całkowite. Innymi słowy, założymy, że każdy język / biblioteka, która jest zdolna do wyrażania, 3**(3**10)jest również zdolna do wyrażania 3**(3**(3**10))na wystarczająco mocnej maszynie.

Oczywiście, ponieważ nie można uruchomić programu, proszę wyjaśnić, jak działa on wraz z kodem

J, 207

(('The Collatz';'Goldbach''s';'The Twin Primes'),.<'Conjecture is'),.((>:^:((((-:`>:@*&3)^:(~:&1))^:_)&f)^:_ g 2)((+&2)^:(+./@1&p:@(-p:@_1&p:))^:_ f 4)(>:^:((4&p:)^:(2&~:&(-~4&p:))&f)^:_ g 3){'True':'False')

Zdecydowałem się użyć fi gzamiast h1i h2, zgodnie z nagrodą; wystarczą dwie dodatkowe linie z 10 znakami wcześniej: f=:h1, g=:h2.

I rzeczywista logika:

Collatz

>:^:((((-:`>:@*&3)^:(~:&1))^:_)&f)^:_ g 2

((-:`>:@*&3)^:(~:&1))^:_jest jego mięsem; jest to w zasadzie pętla while (x != 1) x = collatz(x). Jeśli nazwiemy to zdanie reduce:

>:^:(reduce&f)^:_ g 2

reduce&fma być czasownikiem monadycznym (patrz koniec), gdzie reduce&f njest prawdziwe, gdy reduce(n)zatrzymuje się. Pozostałe bity pętli y >:^:()^:_są w zasadzie nieskończoną pętlą ( >:jest to przyrost, ^:może być używany jako warunek i iterator), który pęka po napotkaniu redukcji Collatza, która się nie zatrzymuje. W końcu gwywoływane jest, aby sprawdzić, czy nieskończona pętla kiedykolwiek się zakończy.

Goldbach

(+&2)^:(+./@1&p:@(-p:@_1&p:))^:_ f 4

Ta sama logika w przeważającej części, oczywistą różnicą jest teraz obliczenie rdzenia +./@1&p:@(-p:@_1&p:). -p:@_1&p:oblicza różnicę między liczbą a wszystkimi liczbami pierwszymi mniejszymi od tej liczby, 1&p:jest isPrimefunkcją i +./jest logicznym OR. Zatem jeśli różnica między liczbą a dowolną liczbą pierwszą mniejszą od tej liczby jest również liczbą pierwszą, wówczas hipoteza Goldbacha jest spełniona, a pętla nieskończona trwa dalej. Znów fjest stosowany w końcowym teście, czy wspomniana nieskończona pętla jest naprawdę nieskończona.

Twin Primes

>:^:((4&p:)^:(2&~:@(-~4&p:))&f)^:_ g 3

Taki sam jak powyżej, z wyjątkiem tego, że (4&p:)^:(2&~:@(-~4&p:)). 4&p:zwraca następną największą liczbę pierwszą po podanej liczbie. -~4&p:zwraca różnicę między liczbą a następną największą liczbą pierwszą po niej. 2&~:jest != 2. Zatem najbardziej wewnętrzna pętla jest analogiczna do while (nextPrimeAfter(p) - p != 2) p = nextPrimeAfter(p).

Notatki

Nie mogą być błędy składniowe, bo nie testowałem z manekina fi gjeszcze. Przyjąłem to fi gprzybierze formę, którą można skomponować z czasownikiem po lewej stronie i rzeczownikiem po prawej stronie, co nie jestem całkowicie pewien, że w jakikolwiek sposób przestrzega gramatyki J. Są one z natury funkcjami wyższego rzędu, a ja jestem zbyt zmęczony, by szukać odpowiedniej konstrukcji jako przysłówków / spójników / what-have-you w tej chwili, jeśli istnieje nawet taka odpowiednia konstrukcja.

Tak naprawdę nie użyłem właściwej konkatenacji ciągów, a zamiast tego zdecydowałem się pozostawić pojedyncze ciągi w pudełku. Dane wyjściowe (zakładając, że wszystko inne jest poprawne) byłyby zatem tabelą z trzema kolumnami, przy czym lewa kolumna to „The Collatz” itp., Środkowa kolumna to „Conjecture is”, a prawa kolumna „True” / „False” .

Jestem też całkiem pewien, że J domyślnie nie konwertuje liczb całkowitych na dowolną dokładność, a kluczowa funkcja użyteczności liczb pierwszych p:nie ma arbitralnie dużej domeny. Z drugiej strony, biorąc pod uwagę, że J obsługuje standardowy typ liczb o dowolnej dokładności, nie jestem pewien, ile wysiłku wymagałoby doprowadzenie tego kodu do wartości nominalnej.

Haskell, 242

p n=and[rem n r>0|r<-[2..n-1]]
c 1=1
c n|odd n=c$3*n+1|0<1=c$div n 2
s!f=putStr(s++" Conjecture is ")>>print(not$h2$all(h1.f)[4..])
main=do"The Collatz"!c;"Goldbach's"! \n->or[p$n-r|r<-[2..n-2],p r];"The Twin Primes"! \n->or[p$r+2|r<-[n..],p r]

ponieważ w Haskell zmienne mogą zawierać nie tylko wartości, ale także obliczenia (to się nazywa lenistwo), pozwalam sobie h1, h2wziąć jeden argument i powrócić, czy nie, jego ocena się zatrzyma.

nieco nieznany kod:

h1 = undefined
h2 = undefined

prime n=and[rem n r>0|r<-[2..n-1]]
collatz 1=1
collatz n
    |odd n=collatz (3*n+1)
    |0<1  =collatz (div n 2)

s!f=do
    putStr (s++" Conjecture is ")
    print$not$h2$all(h1.f)[4..]

main=do
    "The Collatz"!c                                         --collatz
    "Goldbach's"! \n->or[prime (n-r)|r<-[2..n-2],prime r]   --goldbach
    "The Twin Primes"! \n->or[prime (r+2)|r<-[n..],prime r] --twin primes

trochę wyjaśnienia:

gdy alljest stosowana do listy nieskończonym, to powstrzymanie IFF jeden z elementów listy jestFalse powodu lenistwa (zwarcie, dla wszystkich osób spoza Haskell). używamy tego do obliczenia hipotezy collatz i hipotezy bliźniaczych liczb pierwszych.

!pakuje to oszustwo wraz z drukowaniem. wynikiem jest, Truegdy fkończy się na wszystkich liczbach4.. . (nie ma to znaczenia dla hipotezy collatz lub hipotezy podwójnych liczb pierwszych, ponieważ wiemy już, że są prawdziwe dla tak małych liczb).

kod dla przypuszczenia collatz to "The Collatz"!c. wypisuje „The Collatz Conjecture is”, a wynik, którym jest pogoda, ckończy się na wszystkich liczbach4.. .

kod hipotezy Goldbacha to "Goldbach's"! \n->or[p$n-r|r<-[2..n-2],p r]. \n->or[p$n-r|r<-[2..],p r,r<n+1]jest funkcją, która n, jeśli jest sumą dwóch liczb pierwszych, zwraca True, ale poza tym zapętla się w nieskończoność. więc jeśli zatrzyma się na każdym4.. hipotezy Goldbacha, jest to prawdą.

kodem domniemania podwójnych liczb pierwszych jest "The Twin Primes"! \n->or[p$r+2|r<-[n..],p r]. \n->or[p$r+2|r<-[n..],p r]jest funkcją, która biorąc pod uwagę n, że jeśli są dwie liczby pierwsze większe niż n, zwraca True, ale poza tym pętle są nieograniczone. zatem jeśli zatrzyma się dla każdej 4..podwójnej pierwotnej hipotezy, to prawda.

Python (965 znaków)

Ponieważ moje pytanie nie ma miłości. Zamieszczam moje (niekodowane w golfa) rozwiązanie w Pythonie:

def numCollatzSteps(n):
    numSteps=0
    while n>1:
        if n%2==0:
            n//=2
        else:
            n=3*n+1
        numSteps+=1
    return numSteps

def findNonHaltingN():
    for n in count(1):
        if not h1(numCollatzSteps,n):
            return n

print "The Collatz Conjecture is "+str(not h2(findNonHaltingN))

def isPrime(n):
    for i in range(2,n):
        if n%i==0:
            return False
    else:
        return True

def isSumOf2Primes(n):
    for i in range(2,n-2):
        if isPrime(i) and isPrime(n-i):
            return True
    else:
        return False

def findNonSum():
    for i in count(4,2):
        if not isSumOf2Primes(i):
            return i

print "Goldbach's Conjecture is "+str(not h1(findNonSum))

def isSmallTwinPrime(n):
    return isPrime(n) and isPrime(n+2)

def nextSmallTwinPrime(n):
    for i in count(n):
        if isSmallTwinPrime(i):
            return i

def largestTwinPrimes():
    for n in count(2):
        if not h1(nextSmallTwinPrime,n):
            return n-1,n+1

print "The Twin Primes Conjecture is "+str(not h2(largestTwinPrimes))

To dość proste.

numCollatzSteps (n) mówi, ile kroków wykonuje sekwencja Collatz dla określonego n. Działa nieskończenie, jeśli wspomniana sekwencja Collatz się nie kończy.

findNonHaltingN () liczy w górę, sprawdzając, czy numCollatzSteps kończy się dla każdego n. findNonHaltingN kończy się wtedy i tylko wtedy, gdy istnieje n, dla którego numCollatzSteps się nie kończy.

Możemy więc sprawdzić, czy hipoteza Collatza jest prawdziwa, sprawdzając, czy findNonHaltingN () nie zatrzymuje się

isPrime (n) sprawdza, czy liczba jest liczbą pierwszą, widząc, że żadna dodatnia liczba całkowita od 1 do n-1 nie dzieli

isSumOf2Primes (n) iteruje po wszystkich liczbach całkowitych dodatnich od 2 do n-2 i sprawdza, czy co najmniej jedna jest liczbą pierwszą wraz z dopełniaczem

findNonSum () liczy liczby parzyste w górę od 4, aż osiągnie pierwszą liczbę, która nie jest sumą 2 liczb pierwszych, a następnie ją zwróci. Jeśli taka liczba nie istnieje, będzie ona kontynuowana w nieskończoność.

Możemy sprawdzić, czy hipoteza Goldbacha jest prawdziwa, widząc, że findNonSum się nie zatrzymuje.

isSmallTwinPrime (n) zwraca wartość true tylko wtedy, gdy n i n + 2 są liczbami pierwszymi

nextSmallTwinPrime (n) zwraca następny numer> = n, dla którego parametr isSmallTwinPrime ma wartość true

największyTwinPrimes () liczy w górę od 2, sprawdzając, czy nextSmallTwinPrime zatrzymuje się dla wszystkich n. Jeśli kiedykolwiek nextSmallTwinPrime nie zatrzyma się na jakieś n, oznacza to, że największymi liczbami podwójnymi są n-1 i n + 1, i na tym się zatrzymujemy

Następnie możemy sprawdzić poprawność hipotezy o dwóch liczbach pierwszych, sprawdzając, czy największaTwinPrimes nigdy się nie zatrzymuje.

APL (234)

Jest to oczywiście niesprawdzone, ale logika wydaje się rozsądna. Uwzględniono wszystkie polecenia drukowania, dane wyjściowe to 104znaki, a rzeczywista logika to 130.

Z←' Conjecture is '∘,¨'True' 'False'
⎕←'The Collatz',Z[1+{~{1=⍵:⍬⋄2|⍵:∇1+3×⍵⋄∇⍵÷2}h1⍵:⍬⋄∇⍵+1}h2 1]
⎕←'Goldbach''s',Z[1+{~⍵∊∘.+⍨N/⍨~N∊∘.×⍨N←1+⍳⍵:⍬⋄∇⍵+2}h1 2]
⎕←'The Twin Primes',Z[1+{~(T←{∧/{2=+/(⌈=⌊)⍵÷⍳⍵}¨N←⍵+1:N⋄∇N})h1⍵:⍬⋄∇T⍵}h2 4 2]

Nie golfowany:

⍝ Environment assumptions: ⎕IO=1 ⎕ML=1
⍝ I've also assumed h1 and h2 are APL operators
⍝ i.e. x F y = f(x,y); x (F h1) y = h1(F,x,y)

⍝ 'Conjecture is True', 'Conjecture is False'
Z←' Conjecture is '∘,¨'True' 'False'

⍝⍝⍝ Collatz Conjecture
⍝ halts iff 1 is reached from given ⍵
collatzLoop←{
   1=⍵:⍬       ⍝ ⍵=1: halt
   2|⍵:∇1+3×⍵  ⍝ ⍵ uneven: loop with new val
   ∇⍵÷2        ⍝ ⍵ even: loop with new val
}

⍝ halts iff 1 is *not* reached from a value ≥ ⍵ (collatz false)
collatzHalt←{~collatzLoop h1 ⍵:⍬⋄∇⍵+1}

⍝ does it halt?
⎕←'The Collatz',Z[1+ collatzHalt h2 1]


⍝⍝⍝ Goldbach's Conjecture

⍝ Can ⍵ be expressed as a sum of two primes?
sumprimes←{
    N←1+⍳⍵         ⍝ N=[2..⍵+1]
    P←(~N∊N∘.×N)/N ⍝ P=primes up to ⍵+1×⍵+1
    ⍵∊P∘.+P        ⍝ can two P be summed to ⍵?
}

⍝ halts iff Goldbach is false
goldbachHalt←{
    ~sumprimes ⍵:⍬ ⍝ not a sum of primes: halt
    ∇⍵+2           ⍝ try next even number
}

⍝ does it halt?
⎕←'Goldbach''s',Z[1+ goldbachHalt h1 2]

⍝⍝⍝ Twin Primes

⍝ is it a prime?
isPrime←{
   2=+/(⌊=⌈)⍵÷⍳⍵    ⍝ ⍵ is a prime if ⍵ is divisible by exactly two
                   ⍝ numbers in [1..⍵] (i.e. 1 and ⍵)
}

⍝ find next twin
nextTwin←{
   N←⍵+1            ⍝ next possible twin
   ∧/ isPrime¨ N:N  ⍝ return it if twin
   ∇N               ⍝ not a twin, search on
}       

⍝ halts iff no next twin for ⍵
twinPrimeHalt←{
   ~nextTwin h1 ⍵: ⍬  ⍝ if no next twin for ⍵, halt
   ∇nextTwin ⍵        ⍝ otherwise try next twin
}

⍝ does it halt?
⎕←'The Twin Primes',Z[1+ twinPrimeHalt h2 4 2]