It is nice to see the different angles of attack for this problem. Here is a variation, where the inner loop iterates over primes. If next-prime uses a precomputed prime table, then potentially this could save some calls to prime?. But whether this kicks in this example where n is relatively small, is another question.
/soegaard
The problem:
Find first odd, composite n where
n = p + 2 x^2 , p prime,
doesn't have a solution.
Note: If p<n is prime , then:
n = p + 2 x^2 has a solution
<=> (n-p)/2 is a square
(require (planet "math.ss" ("soegaard" "math.plt")))
(define (perfect-square? n)
(let ([sqrt-n (integer-sqrt n)])
(zero? (- n (* sqrt-n sqrt-n)))))
(let n-loop ([n 3])
(if (prime? n)
(n-loop (+ n 2))
(let p-loop ([p 2])
(cond [(> p n)
n]
[(perfect-square? (quotient (- n p) 2))
(n-loop (+ n 2))]
[else
(p-loop (next-prime p))]))))
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Yet another solution
Date: 2008-03-17 10:55 am (UTC)Here is a variation, where the inner loop iterates over primes.
If next-prime uses a precomputed prime table, then potentially
this could save some calls to prime?. But whether this kicks
in this example where n is relatively small, is another question.
/soegaard
The problem: Find first odd, composite n where n = p + 2 x^2 , p prime, doesn't have a solution. Note: If p<n is prime , then: n = p + 2 x^2 has a solution <=> (n-p)/2 is a square (require (planet "math.ss" ("soegaard" "math.plt"))) (define (perfect-square? n) (let ([sqrt-n (integer-sqrt n)]) (zero? (- n (* sqrt-n sqrt-n))))) (let n-loop ([n 3]) (if (prime? n) (n-loop (+ n 2)) (let p-loop ([p 2]) (cond [(> p n) n] [(perfect-square? (quotient (- n p) 2)) (n-loop (+ n 2))] [else (p-loop (next-prime p))]))))