Monthly Archives: April 2012

Euler Problem 131 – Prime Numbers

Now that I’m on a Haskell kick, I opted to solve this one because of the need for calculating prime numbers. I found tons of resources online that detail different ways to calculate it. I settled on a modified Sieve of Eratosthenes that also takes into account squares, making it faster. Calculating the 78K prime numbers under a million, only takes a few seconds.

The other part of the solution comes from the fact that by playing with the values of the relationship from the problem, we see that n^2 and (n+p) have to be cubes. This makes the prime number a difference of cubes such that prime = (a+1)^3–a^3. This new value stays under a million when a is less than 600. So we just test over this smaller series and count the number of resulting primes. This solution runs in less than 10 secs.

Oh by the way, just for kicks the above image represents the distribution of prime numbers. The source code can be found here.

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

testEquation :: Integer -> Bool
testEquation a = (((a+1)^3)-(a^3)) `elem` (primes 1000000)

main = print $ length [(((a+1)^3)-(a^3))| a <- [1..600], testEquation a ]

Euler Problem 197 – Convergent Functions

I solved this one kind of by accident. Its a short program (most things in Haskell are) and I coded it in just a few minutes. Then I plugged in a starting series of 10^6 numbers. Thought that would be a good start. Got the result in a few seconds, and figured that I would need to do the full 10^9 digits. Left it to work over the weekend. Of course, it never finished.

After analysing the function a little more, I discovered that its an oscillating convergent function. Interestingly, after only a few thousand numbers, the varience is smaller than 10^-9. So by using 10^6, it was already overkill.

f :: Double -> Double
f x = 
	let a = 30.403243784-(x**2)
	in fromIntegral (floor (2**a)) * 10**(-9)

u :: Double -> Double
u 0 = -1
u n = f ( u (n-1)) 

main =
	let n = 10^6
	in print $ (u n) + u(n+1)

Euler Problem 104 – Hello Fibonacci

Fibonacci sequences are the “Hello World” of Haskell. So of course I thought that Euler 104 might be a nice, simple problem to tackle. NOT. I found lots of examples online, but I still have a steep learning curve to follow. I ended up piecing together a bunch of disconnected routines that make sense to me.

The only reason why this runs in less than a minute is due to Haskell’s laziness. Specifically, the second expression for the && isn’t executed unless the first passes. Calculating the lower order numbers is much faster than the higher order numbers.

Euler Problem 145 – Haskell Revisit

Oh my head. Is that toast I smell? I’m actually getting headaches from trying to understand Haskell. Functional programming is totally different fron Imperative. But its also very powerful, especially for mathematically inclined Euler problems. That being said, what the hell is a Monad?

Admittedly I found much of the following code online, but I changed it a bit for my purposes. I compiled it using GHC on a dual-core 6-year old PC and it ran in 13 minutes, 11 seconds! For those of you playing at home, that’s a 819% speed improvement over Python! (see previous post). Where’s the Advil?

import Data.Time

oddDigits :: Integer -> Bool
oddDigits n
	| n < 10 = mod n 2 == 1
	| otherwise = (mod (mod n 10) 2) == 1 && oddDigits (div n 10)

rev :: Integer -> Integer -> Integer
rev n acc
	| n < 10 = n + (10 * acc)
	| otherwise = rev (div n 10) ((mod n 10) + (10 * acc))

isReverse :: Integer -> Bool
isReverse n
	| mod n 10 == 0 = False
	| otherwise = oddDigits (n + (rev n 0))

main = do
	start <- getCurrentTime
	print (length (filter isReverse [1..10^9]))
	stop <- getCurrentTime
	print $ diffUTCTime stop start

Euler 145 – Brute Force Solution

Testing for reversible properties of a billion numbers sounds like a simple premise. And it is. But it takes time. There are a number of shortcuts you can find on the Internet, like if a number is reversible then its reverse is also reversible. But after messing around with whether or not a number and its reverse are part of a set with certain starting or ending numbers etc, so as to avoid even numbers, I came to the conclusion that good old-fashioned brute force gets the job done best.

The routine below runs in about 1.8 hours on a 6-year old dual-core machine. Not blazingly fast. Python is SLOOOOW. I have a need for speed, but hate C/C++. Hmmm, being a sucker for punishment, I’m going to translate the same code into Haskell and see what happens. Haskell compiler speeds have a reputation of being epic. We shall see…

import time
if __name__=="__main__":
    t0 = time.time()
    c = 0
    i = 1
    while i < 10**9:
        if i % 10**6 == 0:
            print "i:"+str(i)+" -> c:"+str(c)
        if i % 10 == 0:
            i += 1
        rev = str(int(str(i))+int(str(i)[::-1]))
        if '0' in rev or '2' in rev or '4' in rev or '6' in rev or '8' in rev:
            i += 1
        c += 1
        i += 1
    print "Answer = "+str(c)
    print time.time() - t0, "seconds"