mercoledì 10 novembre 2010

Problem 12

The sequence of triangle numbers is generated by adding the natural numbers. So the 7^(th) triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
Let us list the factors of the first seven triangle numbers:
 1: 1
 3: 1,3
 6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
We can see that 28 is the first triangle number to have over five divisors.
What is the value of the first triangle number to have over five hundred divisors?

solution = findResult $ halveEvens [1..]
    where findResult (x:y:xs)
            | (divisors x * divisors y) > 500 = triangleAt x
            | otherwise = findResult (y:xs)
          halveEvens (x:y:xs) = x : (div y 2) : halveEvens xs

triangleAt x = div (x * (x + 1)) 2

divisors :: Int -> Int
divisors x = product $ map ((+1).primePowers x)
                     $ filter (isDivisorOf x)
                     $ takeWhile (<=(div x 2)) primes
    where isDivisorOf v = (==0).(mod v)
          primePowers v p
              | mod v p /= 0 = 0
              | otherwise = 1 + primePowers (div v p) p

primes :: Integral a => [a]
primes = 2 : iterate nextPrime 3
    where nextPrime x = head $ filter isPrime[(x+1)..]

isPrime :: Integral a => a -> Bool
isPrime x = and $ [mod x p /= 0 | p <- takeWhile lowerThanSqrtX primes]
    where lowerThanSqrtX candidate = candidate <= (round $ sqrt $ fromIntegral x)



This time I avoided brute force, since I've got some useful math insights.

I remember from primary school that "the sum of all numbers from 1 to n is equal to n (n + 1) / 2". Later I learned that the such numbers are named Triangular numbers.

From such definition I derived the function triangleAt.

Looking at the function I got an insight: the factors of a triangular number should be equal to the product of the factors of its root and the factors of the root + 1.

After some google search I found a wikipedia page about the Divisor function that gave me the info I required.

First the divisors function definition:
Moreover I read that actually the divisor function is multiplicative: for any coprime pair a b it is true that d(a*b) = d(a) * d(b).

Since for all integer numbers are coprime with the succeeding one we can state that the
  • d(triangularAt(x)) = d(x/2) * d(x + 1) when x is even
  • d(triangularAt(x)) = d(x) * d((x + 1)/2) when x is odd
So to get the solution I simply had to halveEvens in the sequence of natural numbers and findResult between each number and the succeeding one.

Nessun commento:

Posta un commento