Você recebe as funções: h1 (f, * args) e h2 (f, * args)

Ambos são métodos já definidos para você (aqui o asterisco indica um número variável de argumentos)

f é uma função, * args é uma lista de parâmetros a serem passados ​​para essa função

h1 retorna um valor booleano: True se a função f for interrompida quando chamada * args e False, se não existir (supondo que a máquina esteja com tempo e memória infinitos e que o intérprete / compilador do idioma em que está escrevendo) sabe como lidar com tempo e memória infinitos).

Se f (* args) telefonar para h1 ou h2, h1 lançará uma exceção

h2 se comporta exatamente como h1, exceto que se f fizer chamadas para h1, então h2 não emitirá uma exceção

Com o menor número de caracteres possível, escreva um programa que não aceita entrada e deve gerar:

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

com base na validade de cada uma dessas conjecturas.

Aqui estão os links da Wikipedia explicando cada uma das conjecturas:

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

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

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

Você pode assumir que qualquer grande biblioteca de números inteiros, independentemente do idioma que escolher, representará com êxito números inteiros grandes arbitrários. Em outras palavras, assumiremos que qualquer linguagem / biblioteca capaz de expressar 3**(3**10)também é capaz de expressar 3**(3**(3**10))em uma máquina suficientemente robusta.

Obviamente, como é impossível executar seu programa, forneça uma explicação de como ele funciona junto com o código

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

Eu escolhi usar fe gno lugar de h1e h2, conforme a recompensa; duas linhas adicionais com 10 caracteres no total anteriores são suficientes para alternar: f=:h1, g=:h2.

E a lógica real:

Collatz

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

((-:`>:@*&3)^:(~:&1))^:_é a carne disso; é essencialmente um loop que faz while (x != 1) x = collatz(x). Se chamarmos essa frase reduce:

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

reduce&fdeve ser um verbo monádico (ver final), onde reduce&f né verdadeiro se se reduce(n)parar. Os outros bits de loop-y,, >:^:()^:_são essencialmente um loop infinito ( >:é incremento,^: pode ser usado como condicional e como iterador) que interrompe ao encontrar uma redução de Collatz que não é interrompida. Finalmente, o gé chamado para ver se o loop infinito termina.

Goldbach

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

A mesma lógica, na maior parte, a diferença óbvia sendo o cálculo principal é agora +./@1&p:@(-p:@_1&p:). -p:@_1&p:calcula a diferença entre um número e todos os números primos menores que esse número, 1&p:é uma isPrimefunção e +./é OR lógico. Portanto, se a diferença entre um número e qualquer primo menor que esse número também for um primo, a conjectura de Goldbach é satisfeita e o loop infinito continua. Novamente, fé usado em um teste final para determinar se o referido loop infinito é realmente infinito.

Twin Primes

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

O mesmo que acima, exceto (4&p:)^:(2&~:@(-~4&p:)). 4&p:retorna o próximo maior número primo após um determinado número. -~4&p:retorna a diferença entre um número e o próximo maior número primo depois dele. 2&~:é != 2. Portanto, o loop mais interno é análogo a while (nextPrimeAfter(p) - p != 2) p = nextPrimeAfter(p).

Notas

Pode haver erros sintáticos, desde que eu não testei com manequim fe gainda. Além disso, eu assumi isso fe gassumiria algum tipo de forma que pode ser composta com um verbo à esquerda e um substantivo à direita, que não tenho certeza absoluta de que adere à gramática J de forma alguma. São funções inerentemente de ordem superior, e estou cansado demais para procurar uma construção adequada como advérbios / conjunções / o que você tem no momento, se houver uma construção tão apropriada.

Eu realmente não usei a concatenação adequada de strings e, em vez disso, optei por deixar as strings individuais em caixas. A saída (supondo que tudo o mais esteja correto) seria, portanto, uma tabela de 3 colunas, com a coluna da esquerda sendo "The Collatz" etc., a coluna do meio sendo "A conjectura é" e a coluna da direita "True" / "False" .

Também tenho certeza de que J não converte números inteiros em precisão arbitrária por padrão, e a função crucial do utilitário número primo p:não possui um domínio arbitrariamente grande. Por outro lado, dado que J suporta um tipo de número de precisão arbitrário padrão, não tenho certeza de quanto esforço seria necessário para obter esse código no mesmo nível.

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]

porque, em Haskell, as variáveis ​​podem conter não apenas valores, mas também cálculos (isso é chamado de preguiça). Eu me permito usar h1, h2um único argumento e retornar o clima, ou a avaliação será interrompida.

código um pouco não destruído:

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

um pouco de explicação:

quando allaplicado a uma lista infinita, ele será interrompido se um dos elementos da lista for Falsedevido à preguiça (curto-circuito, para todos os que não pertencem a Haskell por aí). usamos isso para calcular a conjectura de collatz e a conjectura de primos gêmeos.

!empacota esse truque junto com a impressão. o resultado é Truequando ftermina em todos os números 4... (isso não importa para a conjectura de collatz ou a conjectura de primos gêmeos, porque já sabemos que elas são verdadeiras para números tão pequenos).

o código para a conjectura de collatz é "The Collatz"!c. imprime "A conjectura de Collatz é" e o resultado, que é o clima, ctermina em todos os números 4...

o código para a conjectura de goldbach é "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]é uma função que n, se for uma soma de dois números primos, retorna True, mas faz um loop indefinidamente. assim, se 4..parar para cada conjectura de goldbach é verdadeiro.

o código para a conjectura de primos gêmeos é "The Twin Primes"! \n->or[p$r+2|r<-[n..],p r]. \n->or[p$r+2|r<-[n..],p r]é uma função que n, se houver primos gêmeos maiores que n, retorna True, mas, de outra forma, faz um loop indefinidamente. assim, se parar para todas 4..as conjecturas primárias gêmeas é verdade.

Python (965 caracteres)

Desde que minha pergunta está ficando sem amor. Estou postando minha solução (sem código de golfe) em Python:

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

É bem simples.

numCollatzSteps (n) diz quantas etapas a sequência Collatz para um n específico leva. Ele roda infinitamente se a sequência Collatz não terminar.

findNonHaltingN () conta para cima, verificando se numCollatzSteps termina para cada n. findNonHaltingN termina se, e somente se, existe um n para o qual numCollatzSteps não termina.

Portanto, podemos verificar se a conjectura de Collatz é verdadeira, verificando se findNonHaltingN () não interrompe

isPrime (n) verifica se um número é primo, observando que nenhum número inteiro positivo de 1 a n-1 o divide

isSumOf2Primes (n) itera sobre todos os números inteiros positivos entre 2 e n-2 e verifica se pelo menos um é primo junto com seu complemento

findNonSum () conta números pares acima de 4 até atingir o primeiro número que não é uma soma de 2 números primos e depois o retorna. Se esse número não existir, ele continuará infinitamente.

Podemos verificar se a conjectura de Goldbach é verdadeira ao ver que findNonSum não pára.

isSmallTwinPrime (n) retorna true se e somente se n e n + 2 forem primos

nextSmallTwinPrime (n) retorna o próximo número> = n para o qual isSmallTwinPrime é verdadeiro

largestTwinPrimes () conta mais de 2, verificando se nextSmallTwinPrime pára para todos os n. Se alguma vez nextSmallTwinPrime não parar por algum n, então os maiores números primos gêmeos são n-1 e n + 1 e paramos por aí

Então, podemos verificar a validade da conjectura dos primos gêmeos, verificando se o maiorTwinPrimes nunca pára.

APL (234)

Obviamente, não foi testado, mas a lógica parece sólida. Os comandos de impressão estão todos incluídos, a saída são 104caracteres e a lógica real é 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]

Ungolfed:

⍝ 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]