Need Hint for ProjectEuler Problem

Question

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

---

I could easily brute force the solution in an imperative programming language with loops. But I want to do this in Haskell and not having loops makes it much harder. I was thinking of doing something like this:

[n | n <- [1..], d <- [1..20], n `mod` d == 0] !! 0

But I know that won't work because "d" will make the condition equal True at d = 1. I need a hint on how to make it so that n mod d is calculated for [1..20] and can be verified for all 20 numbers.

Again, please don't give me a solution. Thanks.

Answer 1

As with many of the Project Euler problems, this is at least as much about math as it is about programming.

What you're looking for is the least common multiple of a set of numbers, which happen to be in a sequence starting at 1.

A likely tactic in a functional language is trying to make it recursive based on figuring out the relation between the smallest number divisible by all of [1..n] and the smallest number divisible by all of [1..n+1]. Play with this with some smaller numbers than 20 and try to understand the mathematical relation or perhaps discern a pattern.

Answer 2

Instead of a search until you find such a number, consider instead a constructive algorithm, where, given a set of numbers, you construct the smallest (or least) positive number that is evenly divisible by (aka "is a common multiple of") all those numbers. Look at the algorithms there, and consider how Euclid's algorithm (which they mention) might apply.

Can you think of any relationship between two numbers in terms of their greatest common divisor and their least common multiple? How about among a set of numbers?