Monthly Archives: May 2012

Euler Problem 123 – Remainder of Primes

Here is another prime number problem. Again, I re-used my prime number sieve, which I called whenever a remainder was to be calculated. I suppose I could have sped things up a bit by pre-calculating the primes, but this routine still runs in only a few minutes and does the trick.

Haskell’s list manipulation capabilities are simply amazing. The one thing I wasn’t sure about was if asking for the list head in main was sufficient to end the routine. Note that the list comprehension is based on [1,3..] which is open ended. Obviously, it did end, otherwise you wouldn’t be reading this and I’d still be staring at the prompt.

import Data.List.Ordered

pri :: [Integer]
pri = 2 : sieve [3,5..] where
    sieve [] = []
    sieve (p:xs) = p : sieve (xs `minus` [p*p, p*p+2*p..])

calcRem :: Integer -> Integer
calcRem n = (((pri!!(x-1))-1)^x + ((pri!!(x-1))+1)^x) `rem` (pri!!(x-1))^2
	where x = fromIntegral n
	
main = print $ head [x | x <- [1,3..], calcRem x > 10^10]

Euler Problem 124 – Prime Factors

When I was looking for a picture to represent Prime Number Factorization, I had no idea what to use. So I Googled images on the topic and discovered there was a Star Trek: Voyager episode called Prime Factors. The above picture is a scene from it — exciting I know! 😉 Too bad its not a picture of Seven of Nine.

So my solution consist of two parts. A prime number generator. I re-used the code from my solution of Euler Problem 131. The other part is a factorization routine that matches against the list of prime numbers. I found some concise Haskell code here.

This routine runs in less than 4 seconds on a single core 3 Ghz system.

import Data.List
import Data.List.Ordered

primes :: Integer -> [Integer]
primes m = 2 : sieve [3,5..m] where
    sieve [] = []
    sieve (p:xs) = p : sieve (xs `minus` [p*p, p*p+2*p..m])

primeFactors :: Integer -> [Integer]
primeFactors x = 
	unfoldr findFactor x where
		first (a,b,c) = a
		findFactor 1 = Nothing
		findFactor b = (\(_,d,p)-> Just (p, d))
			$ head $ filter ((==0).first) 
			$ map (\p -> (b `mod` p, b `div` p, p)) $ primes 100000

rad :: Integer -> Integer
rad n = product $ Data.List.nub $ primeFactors n

main = print $ snd $ sort [(rad x, x) | x <- [1..100000]] !! (9999)

Ah, what the heck — Why not?

Euler 142 – Rearrange the variables

This is is just a bunch of algebraic relationships. One could use brute force, but it would take several hours.
Instead, reassign these variables:

a = x + y
b = x – y
c = x + z
d = x – z
e = y + z
f = y – z

Then playing around with them, we get:

x = (a+b)/2 = (c+d)/2 because b = c – e and e = a – d
y = (e+f)/2 = (2a-d-c)/2 because e = a – d and f = a – c
z = (c-d)/2
x + y + z = (2a-d+c)/2

So now we just iterate on a,c,d over a list of squares testing for:
a > c > d;
c-d is even;
b,e,f are squares;
and x > y > z > 1

Routine runs in about 120 seconds on a single core 3Ghz system.

import Data.List

isSqr :: Int -> Bool
isSqr n = sq * sq == n
    where sq = floor $ sqrt $ (fromIntegral n::Double)
	
slist :: [Int]
slist = [x | x <- [2..1000000], isSqr x]

test :: Int -> Int -> Int -> Bool
test a c d =
	a > c && c > d && even (c-d) && isSqr(c-a+d) && isSqr(a-d) && isSqr(a-c) && x > y && y > z && z > 1
	where
		x = (c+d) `div` (fromIntegral 2)
		y = ((2*a)-d-c) `div` (fromIntegral 2)
		z = (c-d) `div` (fromIntegral 2)

main = print $ head $ sort [((2*a)-d+c) `div` (fromIntegral 2)| a<-slist,c<-slist,d<-slist,test a c d]