Project Euler Problema 27 in F #

Question

Ho cercato di lavorare il mio modo attraverso Problema 27 di project Euler, ma questo sembra essere me stumping. In primo luogo, il codice sta prendendo troppo tempo per l'esecuzione (un paio di minuti, forse, sulla mia macchina, ma ancora più importante, è il ritorno la risposta sbagliata anche se davvero non riesco a individuare qualcosa di sbagliato con l'algoritmo dopo aver guardato attraverso di esso per un po ' .

Ecco il mio codice corrente per la soluzione.

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

Qualche consiglio su come a) ottenere questo algoritmo in realtà tornare la risposta giusta (penso che sto almeno un approccio praticabile) e b) migliorare le prestazioni, in quanto supera chiaramente la "sola regola minuto" di cui nelle FAQ Project Euler. Sono un po 'di un novizio di programmazione funzionale, in modo che qualsiasi consiglio su come potrei prendere in considerazione il problema con una soluzione più funzionale in mente sarebbe anche apprezzato.

Answer 1

Due osservazioni:

1. Si può approfittare del fatto che b deve essere primo . Ciò deriva dal fatto che il problema richiede la più lunga sequenza di numeri primi per n = 0, 1, 2, ... Così, formula(0) deve essere privilegiata per cominciare, ma formula(0) = b, di conseguenza, b deve essere privilegiata.

2. Io non sono un programmatore # F, ma mi sembra che il codice non cerca n = 0 a tutti . Questo, naturalmente, non soddisfa il requisito del problema che n deve partire da 0, quindi non ci sono possibilità trascurabile di una risposta corretta potrebbe essere prodotto.

Answer 2

A destra, dopo un sacco di controllare che tutte le funzioni di supporto stavano facendo quello che dovrebbero, ho finalmente raggiunto una soluzione di lavoro (ragionevolmente efficiente e).

In primo luogo, il is_prime funzione era completamente sbagliato (grazie a Dimitre Novatchev per avermi fatto guardo quella). Non sono sicuro del tutto come sono arrivato alla funzione che ho postato nella domanda originale, ma avevo pensato che stava lavorando da quando avevo usato nei problemi precedenti. (Molto probabilmente, avevo appena ottimizzato e spezzato da quando.) In ogni caso, la versione di lavoro di questa funzione (che restituisce cruciale falsa per tutti gli interi a meno di 2) è questa:

/// 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 funzione principale è stato cambiato in quanto segue:

/// 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 chiave qui per aumentare la velocità era di generare solo l'insieme dei primi tra 1 e 1000 per i valori di b (utilizzando i primi funzione, la mia implementazione della crivello di Eratostene metodo). Sono anche riuscito a rendere questo codice un po 'più conciso eliminando la Seq.map inutile.

Quindi, sono abbastanza felice con la soluzione che ho adesso (ci vuole poco meno di un secondo), anche se naturalmente eventuali ulteriori suggerimenti sarebbe comunque il benvenuto ...

Answer 3

Si potrebbe accelerare la funzione "is_prime" utilizzando un algoritmo probabilistico. Uno dei più facili algoritmi rapidi per questo è il Miller-Rabin algoritmo.

Answer 4

per sbarazzarsi di metà dei tuoi calcoli si potrebbe anche fare la gamma di possibili a's contenere solo numeri dispari

Answer 5

la mia soluzione python superveloce: 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()