Today’s Programming Praxis exercise comes from the same challenge as the longest palindrome exercise from two weeks ago. The goal is to write a function that calculates the sum of the factors of 1 plus the first prime fibonacci number higher than the input number. Let’s get started, shall we?
To generate the fibonacci numbers, we use the well-known one-liner.
fibs :: [Integer] fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
Getting the factors of a number is done via simple trial division. Unlike the Scheme solution, we don’t repeat factors, since the original challenge says not to.
factors :: Integer -> [Integer] factors = f 2 where f d n | n < d = [] | mod n d == 0 = d : f (d + 1) (div n d) | otherwise = f (d + 1) n
We could write some fancy algorithm to check primality, but since we already have a function to calculate factors, why bother? Since the only factor of a prime number will be itself, we can just use that as a check. Initally I just used the isPrime function from Data.Numbers.Primes for this, but looking through the source code I realized I could replace it with this version. Obviously this won’t work too well on large numbers, but for our test case it’s fast enough.
isPrime :: Integer -> Bool isPrime n = factors n == [n]
The top-level function does what it says on the tin: look through the fibonacci numbers to find one that’s greater than n and prime, add one and return the sum of the factors.
greplin :: Integer -> Integer greplin n = head [sum $ factors (f + 1) | f <- fibs, f > n, isPrime f]
All that’s left is to apply it to the test number:
main :: IO () main = print $ greplin 227000
As expected, we get 352 as a result. And, in the spirit of the contest, which is to do these challenges quickly, I think this one took me about 20 minutes.
Tags: bonsai, code, fibonacci, greplin, Haskell, kata, praxis, prime, programming
