CODEWITHSUNDEEP
algorithmhaskellmath
Deven.W
Deven.W

Reputation: 59

Help me find the problem with my solution to Project Euler #12 in Haskell

I'm a total newbie to Haskell, and programming in general, but I'm trying to work through some Project Euler problems because I do like problem solving. However, I have a problem with problem #12.

I devised a solution I thought would work, but alas, it does not.

Can you help me by opening my eyes to the problem with my code, and maybe push me in the right direction towards fixing it? Thank you.

Here is the code:

triangleNumber = scanl1 (+) [1..]

factors n = [x | x <- [1..n], n `mod` x == 0]

numFactors = length . factors

eulerTwelve = find ((>500) . numFactors) triangleNumber

Thank you very much! :)

Upvotes: 5

Views: 899

Answers (4)

Tom Crockett
Tom Crockett

Reputation: 31579

I assume the problem you're alluding to is that eulerTwelve takes way too long to terminate; your code is correct, it's just inefficient. The bottleneck is your factors function, which is trying every number between 1 and n to see if it's a divisor of n. Here's a faster way to find the divisors of a number, using efficient prime factorization and a nifty implementation of the power set:

import Data.Numbers.Primes (primeFactors)

powerSet = filterM (const [True, False])

factors = map product . nub . powerSet . primeFactors

Even this is pretty inefficient; you can instead calculate numFactors directly from primeFactors like so:

numFactors = product . map ((+1) . length) . group . primeFactors

When I replace your numFactors with this one I obtain the result instantly.

Upvotes: 1

Gareth Rees
Gareth Rees

Reputation: 65854

The Project Euler questions are designed so that it's a bad idea to try solve them by "brute force", that is, by programming the obvious search and just leaving it to run. (Some of the earlier questions can be solved like that, but it's a good idea not to exploit that, but to use them as practice.) Instead, you have to think about the mathematical content of the question so as to make the computer search tractable.

I don't want to give away too much, but here are some hints:

  • There's a formula for the nth triangular number. Find it, so you don't have to compute it by summation.

  • Given this formula for the nth triangular number, what numbers can possibly be its divisors?

  • Given what you know about these divisors, what's an easy way to figure out how many of them are there? (Without having to enumerate them.)

Upvotes: 3

hspim
hspim

Reputation: 47

IIRC when checking for factors you don't need to test every integer between 1 and n - only the numbers between 1 and n^0.5 (squareroot of n), since at this number you will already have obtained all the factors available.

Upvotes: 0

Santiago Alessandri
Santiago Alessandri

Reputation: 6855

I copied it and what it threw me was an error that find couldn't be found. That is because you need to import the module List where find is in:

import Data.List

By the way, you should optimize your factors function.

Upvotes: 2

Related Questions