Saturday, March 12, 2011

Project Euler 12

I coach the ACM programming contest team for CNU, and last meeting we could not get on the Online Judge site. To give us a problem to solve I thought we would try out problem 12 on Project Euler.
The problem is to find the first triangle number with more than 500 divisors.
The nth triangle number is the sum from 1 to n, or n*(n+1)/2. To get from the nth triangle number to the n+1th just add n+1 to the nth number.

We were successful with a brute force approach in Java in about 24 lines of code. For comparison here is my Haskell solution.

answer = head $ dropWhile small [tri n | n <- [1..]] where
divisors n = succ $ sum $ [if n `mod` i == 0 then 1 else 0 | i <- [1..n `div` 2]]
small n = divisors n <= 500
tri n = ((n*n) + n) `div` 2

No comments:

Post a Comment