Projeto Euler problema 27 em F #

Question

Eu tenho tentado trabalhar o meu caminho através Problema 27 de projeto Euler, mas este parece ser me stumping. Em primeiro lugar, o código está levando muito tempo para executar (um par de minutos, talvez, na minha máquina, mas mais importante, ele está retornando a resposta errada, embora eu realmente não pode manchar errado nada com o algoritmo depois de olhar através dele por um tempo .

Aqui está o meu código atual para a solução.

/// Checks number for primality.
let is_prime n = 
    [|1 .. 2 .. sqrt_int n|] |> Array.for_all (fun x -> n % x <> 0)

/// Memoizes a function.
let memoize f = 
    let cache = Dictionary<_, _>()
    fun x -> 
        let found, res = cache.TryGetValue(x)
        if found then
            res
        else
            let res = f x
            cache.[x] <- res
            res

/// Problem 27
/// Find a quadratic formula that produces the maximum number of primes for consecutive values of n.
let problem27 n =
    let is_prime_mem = memoize is_prime
    let range = [|-(n - 1) .. n - 1|]
    let natural_nums = Seq.init_infinite (fun i -> i)
    range |> Array.map (fun a -> (range |> Array.map (fun b ->
        let formula n = n * n + a * n + b
        let num_conseq_primes = natural_nums |> Seq.map (fun n -> (n, formula n))
                                |> Seq.find (fun (n, f) -> not (is_prime_mem f)) |> fst
        (a * b, num_conseq_primes)) |> Array.max_by snd)) |> Array.max_by snd |> fst

printn_any (problem27 1000)

Todas as dicas sobre como a) obter este algoritmo realmente retornar a resposta certa (eu acho que sou, pelo menos, tendo uma abordagem viável) e b) melhorar o desempenho, uma vez que excede claramente a "regra de uma hora" estabelecido no Projeto Euler FAQ. Eu sou um pouco de um novato à programação funcional, de modo algum conselho sobre como eu poderia considerar o problema com uma solução mais funcional em mente também seria apreciada.

Answer 1

Duas observações:

1. Você pode tirar proveito do fato de que b deve ser primo . Esta situação resulta do facto de que o problema pede a sequência mais longa de números primos para n = 0, 1, 2, ... Então, formula(0) deve ser privilegiada para começar, mas formula(0) = b, portanto, b deve ser privilegiada.

2. Eu não sou um F # programador, mas parece-me que o código não tenta n = 0 em todos . Isto, naturalmente, não atende a exigência do problema que n deve começar a partir 0, portanto, há chances negligenciável poderiam ser produzidos a resposta correta.

Answer 2

direito, depois de um monte de verificação de que todas as funções auxiliares estavam fazendo o que deveria, eu finalmente chegou a um trabalho (e razoavelmente eficiente) solução.

Em primeiro lugar, o is_prime função era completamente errada (graças a Dimitre Novatchev por me fazer olhar para isso). Não tenho certeza exatamente como eu cheguei na função que eu postei na pergunta original, mas eu tinha assumido que estava trabalhando desde que eu tinha usado em problemas anteriores. (Provavelmente, eu tinha acabado de tweaked-lo e quebrado desde então.) De qualquer forma, a versão de trabalho desta função (que crucialmente retorna false para todos os inteiros inferior a 2) é o seguinte:

/// Checks number for primality.
let is_prime n = 
    if n < 2 then false
    else [|2 .. sqrt_int n|] |> Array.for_all (fun x -> n % x <> 0)

A função principal foi alterado para o seguinte:

/// Problem 27
/// Find a quadratic formula that produces the maximum number of primes for consecutive values of n.
let problem27 n =
    let is_prime_mem = memoize is_prime
    let set_b = primes (int64 (n - 1)) |> List.to_array |> Array.map int
    let set_a = [|-(n - 1) .. n - 1|]
    let set_n = Seq.init_infinite (fun i -> i)
    set_b |> Array.map (fun b -> (set_a |> Array.map (fun a ->
        let formula n = n * n + a * n + b
        let num_conseq_primes = set_n |> Seq.find (fun n -> not (is_prime_mem (formula n)))
        (a * b, num_conseq_primes))
    |> Array.max_by snd)) |> Array.max_by snd |> fst

A chave aqui para aumentar a velocidade era apenas para gerar o conjunto de números primos entre 1 e 1000 para os valores de b (usando o primos função, minha implementação do crivo de método Eratóstenes). Eu também conseguiu fazer com que este código ligeiramente mais concisa, eliminando a Seq.map desnecessário.

Então, eu estou muito feliz com a solução que eu tenho agora (leva pouco menos de um segundo), embora, naturalmente, quaisquer outras sugestões ainda seria bem-vindo ...

Answer 3

Você poderia acelerar a sua função "is_prime" usando um algoritmo probabilístico. Um dos mais fáceis algoritmos rápidos para isso é o algoritmo Miller-Rabin .

Answer 4

para se livrar de metade dos seus cálculos, você também pode fazer a matriz de possíveis a's contêm apenas números ímpares

Answer 5

minha solução python super rápida: P

flag = [0]*204
primes = []

def ifc(n): return flag[n>>6]&(1<<((n>>1)&31))

def isc(n): flag[n>>6]|=(1<<((n>>1)&31))

def sieve():
    for i in xrange(3, 114, 2):
        if ifc(i) == 0:
            for j in xrange(i*i, 12996, i<<1): isc(j)

def store():
    primes.append(2)
    for i in xrange(3, 1000, 2):
        if ifc(i) == 0: primes.append(i)

def isprime(n):
    if n < 2: return 0
    if n == 2: return 1
    if n & 1 == 0: return 0
    if ifc(n) == 0: return 1
    return 0    

def main():
    sieve()
    store()
    mmax, ret = 0, 0
    for b in primes:
        for a in xrange(-999, 1000, 2):
            n = 1
            while isprime(n*n + a*n + b): n += 1
            if n > mmax: mmax, ret = n, a * b
    print ret

main()