Need a hint for ProjectEuler problem

Question

What is the smallest positive number evenly divided by all numbers from 1 to 20?

---

I could easily go overboard in an imperative programming language with loops. But I want to do it in Haskell, and the lack of loops makes it a lot more complicated. I was thinking of doing something like this:

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

But I know that this will not work, because "d" will make the condition equal True with d = 1. I need a hint on how to make n mod d be calculated for [1..20] and can be checked for all 20 numbers.

Again, please do not give me a solution. Thank you

Answer 1

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

So, we got a function that takes an integer and a list of integers and tells if it shares all of these numbers in a list

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

and then use this in the Filter list as

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

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

Hope this helps you. This is a simple solution, and there will be many other single-line solutions for this :)

Answer 2

As with many of the problems of Project Euler, this is at least about the same as mathematics, like programming.

What you are looking for is the least common multiple of a set of numbers that are in a sequence starting with 1.

Probable tactics in a functional language try to make it recursive by clarifying the relationship between the smallest number divisible by all [1..n] and the smallest number divisible by all [1..n+1] . Play with this with a smaller number than 20, and try to understand the mathematical relation or, perhaps, to distinguish a pattern.

Answer 3

Instead of searching until you find such a number, consider a constructive algorithm instead, where, given the set of numbers, you create the smallest (or least) positive number that is evenly divided by (aka "common multiple") of all these numbers. Look at the algorithms there and think about how the Euclidean algorithm (which they mention) can be applied.

Can you imagine any connection between the two numbers in terms of their greatest common divisor and their smallest common multiple? What about the number of numbers?

Answer 4

Alternative answer: you can simply use the lcm function provided in the prelude.

Answer 5

For an effective solution to this, respond with don Rob. If you just want to give a little hint at the brute force approach, translate what you wrote in English and see how it differs from the description of the problem.

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

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

Answer 6

In this case, you should get Mati. You are about to make foldl in [1..20] , starting with battery n = 1 . For each p number of this list, you will continue only if p is prime. Now for the previous prime p you want to find the largest integer q such that p^q <= 20 . Multiply n *= (p^q) . When foldl ends, n is the number you want.

Answer 7

A possible realization of brute force will be

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

but in this case it will take too much time. The all function checks if a predicate exists for all elements of the list. Lambda is short for (\d -> mod nd == 0) .

So, how could you speed up the calculation? Let our divisors factor in prime factors and look for the highest degree of each 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 divides into all numbers from 1 to 20. Not very surprising. For instance. it is divided by 15 because it “contains” factors 3 and 5, and it is divided by 16 because it “contains” a factor of 2 ^ 4. But is this the smallest possible number? Think about it...