Pure functional (or monadic?) solution to Euler#10..?

[jang]

In an attempt to become less rusty, I was looking at some of the Euler challenge problems. #10 has me scratching my head. The problem statement is pretty simple: sum the primes < 2,000,000. A trivial (imperative, array-based) sieve in (your (other) language of choice) calculates this in no time flat.

The reason I _know_ that the imperative sieve runs so quickly is because I had plenty of time to write one whilst I was waiting for the Haskell one to run to conclusion; which, incidentally, it never did. Admittedly I used the "my first Haskell program" approach for sieving out primes, which runs candidate integers through an ever-increasing cascade of filters, one per prime:

> primes [] = []

> primes (n:ns) = n : primes [ n' | n' <- ns, n' `mod` n /= 0 ]

It's a neat expression of primality and showcases Haskell's lazy approach; but I'm hunting around for better (by which I mean, faster) ways to do this: ideally with derivations that are amenable to study. The Haskell wiki has some pointers (see? I _do_ google first) but if anyone with more Haskell chops fancies spending five minutes running through alternatives (especially in this case, where the upper bound is known well in advance, so a fixed array is a plausible approach) at the next meeting I'd be really appreciative.

Cheers,

jan

[jang]

Yikes!

To answer my own question, the paper pointed at here:

http://hackage.haskell.org/packages/archive/primes/0.2.1.0/doc/html/Data-Numbers-Primes.html

(that is: http://www.cs.york.ac.uk/ftpdir/pub/colin/jfp97lw.ps.gz ) leads me sufficiently by the nose to be useful.

I'd still be curious to see alternative approaches.

[status203]

You might also find http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf of interest.

Otherwise, if you want to see how not to do it ;) , you can see my very messy (probably non-idiomatic) version of an iterative sieve (without a wheel) near the top of https://github.com/status203/euler-clj/blob/master/src/euler/numbers.clj . I was exploring the idea of filtering/transforming down from an initial lazy sequence that contained every step of the sieve.

[Arwyn]

Hi Jan,

Here's my first attempt:

-- euler problem #10

e10 = sum (takeWhile (< 2000000) primes)

   where primes = 2 : [x | x <- [3..], prime x]

         prime y = testFactors y $ takeWhile (<= intSqrt y) primes

         testFactors z = all ((/=0).mod z)

         intSqrt = truncate.sqrt.fromIntegral

Now I can go and read those papers...

Cheers,

Arwyn

[Shiyaz Rasheed]

Hi Jan/Arwyn,

I would suggest a filter with the Chinese primality test (which will
catch most of the composites) before doing the more expensive sieve. I
have no Haskell chops to speak of, so I won't do a demonstration of my
ignorance :|

The Chinese test is (2^n - 2) mod n == 0, then n is probably prime.

(2^2 - 2) mod 2 == 2 mod 2 == 0
(2^3 - 2) mod 3 == 6 mod 3 == 0
(2^4 - 2) mod 4 == 14 mod 4 == 2
(2^5 - 2) mod 5 == 30 mod 5 == 0
(2^6 - 2) mod 6 == 62 mod 6 == 2
.
.
.

I assume Haskell has a highly optimised exponentiation operator/function?

Cheers,

Shiyaz