Need Hint for ProjectEuler Problem

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.

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.

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?

If you look at it, it seems to be a list filtering operation. List of infinite numbers, to be filtered based on case the whether number is divisible by all numbers from 1 to 20.

So what we got is we need a function which takes a integer and a list of integer and tells whether it is divisible by all those numbers in the list

isDivisible :: [Int] -> Int -> Bool

and then use this in List filter as

filter (isDivisible [1..20]) [1..]

Now as Haskell is a lazy language, you just need to take the required number of items (in your case you need just one hence List.head method sounds good) from the above filter result.

I hope this helps you. This is a simple solution and there will be many other single line solutions for this too :)

Alternative answer: You can just take advantage of the lcm function provided in the Prelude.

For efficiently solving this, go with Don Roby's answer. If you just want a little hint on the brute force approach, translate what you wrote back into english and see how it differs from the problem description.

You wrote something like "filter the product of the positive naturals and the positive naturals from 1 to 20"

what you want is more like "filter the positive naturals by some function of the positive naturals from 1 to 20"

You have to get Mathy in this case. You are gonna do a foldl through [1..20], starting with an accumulator n = 1. For each number p of that list, you only proceed if p is a prime. Now for the previous prime p, you want to find the largest integer q such that p^q <= 20. Multiply n *= (p^q). Once the foldl finishes, n is the number you want.

A possible brute force implementation would be

head [n|n <- [1..], all ((==0).(n `mod`)) [1..20]]

but in this case it would take way too long. The all function tests if a predicate holds for all elements of a list. The lambda is short for (\d -> mod n d == 0).

So how could you speed up the calculation? Let's factorize our divisors in prime factors, and search for the highest power of every prime factor:

2  = 2
3  =     3
4  = 2^2
5  =         5
6  = 2 * 3
7  =           7
8  = 2^3
9  =     3^2
10 = 2     * 5
11 =             11
12 = 2^2*3
13 =                13
14 = 2        *7
15 =     3 * 5
16 = 2^4
17 =                   17
18 = 2 * 3^2
19 =                      19
20 = 2^2   * 5
--------------------------------
max= 2^4*3^2*5*7*11*13*17*19     

Using this number we have:

all ((==0).(2^4*3^2*5*7*11*13*17*19 `mod`)) [1..20]
--True

Hey, it is divisible by all numbers from 1 to 20. Not very surprising. E.g. it is divisible by 15 because it "contains" the factors 3 and 5, and it is divisible by 16, because it "contains" the factor 2^4. But is it the smallest possible number? Think about it...