# Euler Solution 108

### From ProgSoc Wiki

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