Proyecto Euler problema 27 en Fa #

Question

He estado tratando de trabajar mi camino a través de problema 27 de proyecto Euler, pero éste parece que estar haciendo campaña. En primer lugar, el código está tomando demasiado tiempo para funcionar (un par de minutos, tal vez, en mi máquina, pero lo más importante, es devolver la respuesta equivocada a pesar de que realmente no puedo detectar algo malo con el algoritmo después de mirar a través de él por un tiempo .

Aquí está mi código actual para la solución.

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

¿Algún consejo sobre cómo a) obtener este algoritmo en realidad devolver la respuesta correcta (Creo que estoy teniendo, al menos, un enfoque viable) y b) mejorar el rendimiento, ya que supera claramente la "regla de un solo minuto" establecido en el FAQ Proyecto Euler. Soy un poco de un novato en la programación funcional, por lo que cualquier consejo sobre cómo podría considerar el problema con una solución más funcional en cuenta también sería apreciada.

Answer 1

Dos observaciones:

1. Es posible aprovechar el hecho de que b debe ser primer . Esto se deduce del hecho de que el problema pide la secuencia más larga de números primos para n = 0, 1, 2, ... Así, formula(0) debe ser primordial para empezar, pero formula(0) = b, por lo tanto, debe ser primer b.

2. No soy un programador # F, pero me parece que el código no intenta n = 0 en todos los . Esto, por supuesto, no cumple con el requisito de que el problema debe partir de n 0, por lo tanto, hay posibilidades despreciables una respuesta correcta podría ser producido.

Answer 2

derecho, después de un montón de comprobar que todas las funciones de ayuda estaban haciendo lo que debe, por fin he alcanzado un trabajo (y razonablemente eficiente) solución.

En primer lugar, el is_prime función era totalmente erróneo (gracias a Dimitre Novatchev por hacerme ver, por cierto). No estoy muy seguro de cómo llegué a la función que he publicado en la pregunta original, pero había asumido que estaba trabajando desde que había utilizado en los problemas anteriores. (Lo más probable es que acababa de pellizcado y roto desde entonces.) De todos modos, la versión de trabajo de esta función (que devuelve falso crucial para todos los enteros menores de 2) es la siguiente:

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

La función principal se cambió a la siguiente:

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

La clave aquí para aumentar la velocidad era sólo para generar el conjunto de los números primos entre 1 y 1000 para los valores de b (usando los primos función, mi implementación de la criba de Eratóstenes método). También logré hacer que el código un poco más concisa mediante la eliminación de la Seq.map innecesaria.

Por lo tanto, estoy bastante contento con la solución que tengo ahora (se tarda menos de un segundo), aunque, por supuesto, cualquier otra sugerencia todavía serían bienvenidos ...

Answer 3

Se podría acelerar su función "is_prime" mediante el uso de un algoritmo probabilístico. Uno de los algoritmos rápidos más fáciles de esto es la algoritmo de Miller-Rabin .

Answer 4

para deshacerse de la mitad de sus cálculos también se puede hacer que el conjunto de posibles excelentes calificaciones sólo contienen números impares

Answer 5

mi solución pitón ultrarrápido: 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()