Euler Solution 108

From ProgSoc Wiki

Jump to: navigation, search

Solutions for Problem 108

Given the equation (1/x)+(1/y)=n where x,y,n are integers, find the first n with more than 1000 distinct solutions.

Haskell by SanguineV

Runtime: 956.868 ms

{- Prime numbers as usual -}
primes :: [Integer]
primes = 2:3:primes'
  where
    1:p:candidates  = [6*k+r | k <- [0..], r <- [1,5]]
    primes'         = p : filter isPrime candidates
    isPrime n       = all (not . divides n) $ takeWhile (\p -> p*p <= n) primes'
    divides n p     = n `mod` p == 0

{- Primorials as usual -}
primorials = map (\x -> product (take x primes)) [1..]

{- Numbers to check.
 - Note that the primorials (and miltiples of) have the most solutions. -}
pots = inner 1 2 (tail primorials)
  where
    inner m cp pps@(p:ps)
      | mp < p = mp : inner (m + 1) cp pps
      | otherwise = inner 1 p ps
        where
          mp = m * cp

{- The number of solutions for a given "n" -}
solns n = length (filter (\x -> mod (n * x) (x - n) == 0) [n+1..2*n])

{- Find the first "n" with over 1000 solutions. -}
main = print (head (filter (\x -> solns x > 1000) pots))
Personal tools