March 3, 2009 at 14:59Solving Project Euler on F #: Problems 3, 7, 10
Well, let's continue our acquaintance with F #, and at the same time solve problems from the Euler Project, which I started in a previous post . Today I will consider several tasks from this project related to prime numbers. In the top ten there are three pieces, so let's look at them.
In these examples, we will, as before, use only the functional aspects of the language, for the final, so to speak, consolidation. And about how to use F # in an imperative and object-oriented paradigm, I will probably tell you separately, next time.
So, we have three tasks:
10. The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. Find the sum of all the primes below two million.
3. The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143?
7. By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6 ^ (th) prime is 13. What is the 10001 ^ (st) prime number?
In the first task, we will not be cast out, not for that we have actually gathered, but we will decide for ourselves what the ordinary sieve of Eratosthenes is . As homework, you can try to implement the Atkin sieve .
After several cleanings and improvements, I got the following code:
The internal recursive function next, which takes a list, compares it with three possible patterns. The first of them, an empty list, is needed exclusively so that the compiler does not swear on incomplete pattern matches. In fact, our function will never get here, and the second comparison is terminal for it.
In this template, in addition to the standard for working with head and tail separation lists (n :: tail), an additional condition is used, which is written after the when keyword. In this case, it checks if our number has not become large enough (sqrt max), that the screening procedure could be stopped, and if so, it gives out the list that remains with it. In the last template, the screening specified by the lambda actually occurs.
Since the sum of all primes can be quite an impressive number (and the way it is, the answer is 142913828922), then we use 64-bit integers int64 in the code, and we kind of hint about this to the compiler, appending “L” after the constants.
In one case, the truth could not be avoided with hints, since it was necessary to cast the square root to int64. By the way, before that, we had to cast our number to a floating point with the float function, since sqrt did not want to take an integer. For C # programmers, this looks pretty weird. The function does not work very quickly, but it fits within the framework outlined by the rules of the project with a margin.
We will solve the second of the list of problems by the greatest mathematical method of all times and peoples, namely, by the teapot method.
If suddenly by accident someone does not know, the method is described by the following joke: The
mathematician asks the physicist: “You have an empty kettle, a tap with water, and a stove. How to warm the kettle? ”“ It is necessary to pour water from the tap into the kettle, light a fire and put the kettle on it, ”the physicist replies. "Excellent! - the mathematician says, - and now imagine that there is water in the kettle and the fire is lit. ” “Well then, it’s quite simple,” the physicist says, “we put the kettle on the stove.” “No,” says the mathematician, “you need to pour out water, put out the fire and the task will be reduced to the previous one.”
So we are reducing the problem to the previous one, build a list of all primes, filter out those into which the given number is divided and find the maximum among them. The only valuable idea is to look for prime numbers not up to the number itself, but to its square root. Thus, we have the code:
With this example, you can once again evaluate the full power of Pipeline. (How can I translate something into Russian? The “pipeline” somehow doesn’t sound very good ...) Surely there are ways and quicker to solve, without a “teapot”, can anyone suggest something?
The third problem, of course, can also be solved using the same kitchen appliance, for example, by empirically checking that the primes found by us <2M are much more than 10001 (yes there, there are a million more), so it's quite simple without fear, take the 10001st element of the resulting list. But you must admit, such a solution somehow disgusts our programmer's sense of beauty. I'd like to solve the problem in a general way.
As a result of my thoughts, I decided to simply implement the naive method - filtering the full list of numbers in accordance with the simplicity test, applied small optimizations, and, surprisingly, it worked fine, and for the 10001th it turned out incomparably faster than the first proposed method.
It looks like in my interpretation:
Perhaps this is the most interesting example of all three.
The Seq.init_infinite method sets, as the name implies, an infinite sequence. Well, yes, it is endless. It is specified by the lambda indicated in parentheses, in our case, identical. This infinity, of course, is virtual, because in fact the sequence at the time of determination does not yet exist, and will only be created when it becomes necessary, just like operations on it will be done only when their results are required for further work. In short, F # supports lazy computing(by adding the lazy keyword before the function), and the Seq class has this ability a priori. The topic of lazy computing is extensive and complex enough to at least somehow fully cover it here, so I will not even try to do it. I think Google is able to provide the necessary amount of information on this topic. Haskell adherents may of course find fault with my self-made definitions, but I, in turn, do not understand what could interest Haskell adherents in this article to read to this point.
Well, the remaining actions in the program are unlikely to raise questions. With the first two filters, we leave only those elements that we need (large two and not divisible by two), and the last filter applies a simplicity test.
Something like that.
In these examples, we will, as before, use only the functional aspects of the language, for the final, so to speak, consolidation. And about how to use F # in an imperative and object-oriented paradigm, I will probably tell you separately, next time.
So, we have three tasks:
10. The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. Find the sum of all the primes below two million.
3. The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143?
7. By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6 ^ (th) prime is 13. What is the 10001 ^ (st) prime number?
In the first task, we will not be cast out, not for that we have actually gathered, but we will decide for ourselves what the ordinary sieve of Eratosthenes is . As homework, you can try to implement the Atkin sieve .
After several cleanings and improvements, I got the following code:
#light
let primes max =
let rec next potentialPrimes =
match potentialPrimes with
|[] -> []
|n::tail when n > int64 (sqrt (float max)) -> n::tail
|n::tail -> n :: next (List.filter (fun x -> x % n <> 0L) tail)
next [2L .. max]
primes 2000000L |> List.fold_left (+) 0L |> printfn "%d"
The internal recursive function next, which takes a list, compares it with three possible patterns. The first of them, an empty list, is needed exclusively so that the compiler does not swear on incomplete pattern matches. In fact, our function will never get here, and the second comparison is terminal for it.
In this template, in addition to the standard for working with head and tail separation lists (n :: tail), an additional condition is used, which is written after the when keyword. In this case, it checks if our number has not become large enough (sqrt max), that the screening procedure could be stopped, and if so, it gives out the list that remains with it. In the last template, the screening specified by the lambda actually occurs.
Since the sum of all primes can be quite an impressive number (and the way it is, the answer is 142913828922), then we use 64-bit integers int64 in the code, and we kind of hint about this to the compiler, appending “L” after the constants.
In one case, the truth could not be avoided with hints, since it was necessary to cast the square root to int64. By the way, before that, we had to cast our number to a floating point with the float function, since sqrt did not want to take an integer. For C # programmers, this looks pretty weird. The function does not work very quickly, but it fits within the framework outlined by the rules of the project with a margin.
We will solve the second of the list of problems by the greatest mathematical method of all times and peoples, namely, by the teapot method.
If suddenly by accident someone does not know, the method is described by the following joke: The
mathematician asks the physicist: “You have an empty kettle, a tap with water, and a stove. How to warm the kettle? ”“ It is necessary to pour water from the tap into the kettle, light a fire and put the kettle on it, ”the physicist replies. "Excellent! - the mathematician says, - and now imagine that there is water in the kettle and the fire is lit. ” “Well then, it’s quite simple,” the physicist says, “we put the kettle on the stove.” “No,” says the mathematician, “you need to pour out water, put out the fire and the task will be reduced to the previous one.”
So we are reducing the problem to the previous one, build a list of all primes, filter out those into which the given number is divided and find the maximum among them. The only valuable idea is to look for prime numbers not up to the number itself, but to its square root. Thus, we have the code:
#light
let num = 600851475143L
let primes max =
let rec next potentialPrimes =
match potentialPrimes with
|[] -> []
|n::tail when n > int64 (sqrt (float max)) -> n::tail
|n::tail -> n :: next (List.filter (fun x -> x % n <> 0L) tail)
next [2L .. max]
num |> float |> sqrt |> int64 |> primes
|> List.filter (fun x -> num % x = 0L) |> List.max |> printfn "%d"
With this example, you can once again evaluate the full power of Pipeline. (How can I translate something into Russian? The “pipeline” somehow doesn’t sound very good ...) Surely there are ways and quicker to solve, without a “teapot”, can anyone suggest something?
The third problem, of course, can also be solved using the same kitchen appliance, for example, by empirically checking that the primes found by us <2M are much more than 10001 (yes there, there are a million more), so it's quite simple without fear, take the 10001st element of the resulting list. But you must admit, such a solution somehow disgusts our programmer's sense of beauty. I'd like to solve the problem in a general way.
As a result of my thoughts, I decided to simply implement the naive method - filtering the full list of numbers in accordance with the simplicity test, applied small optimizations, and, surprisingly, it worked fine, and for the 10001th it turned out incomparably faster than the first proposed method.
It looks like in my interpretation:
#light
let isPrime n =
let limit n = int(sqrt (float n)) in
{ 2..limit n } |> Seq.for_all (fun x -> n%x <> 0)
let primes = Seq.init_infinite (fun i -> i)
|> Seq.filter (fun i -> i >= 2)
|> Seq.filter (fun i -> i%2 <> 0)
|> Seq.filter isPrime
primes |> Seq.nth 10000 |> printfn "%d"
Perhaps this is the most interesting example of all three.
The Seq.init_infinite method sets, as the name implies, an infinite sequence. Well, yes, it is endless. It is specified by the lambda indicated in parentheses, in our case, identical. This infinity, of course, is virtual, because in fact the sequence at the time of determination does not yet exist, and will only be created when it becomes necessary, just like operations on it will be done only when their results are required for further work. In short, F # supports lazy computing(by adding the lazy keyword before the function), and the Seq class has this ability a priori. The topic of lazy computing is extensive and complex enough to at least somehow fully cover it here, so I will not even try to do it. I think Google is able to provide the necessary amount of information on this topic. Haskell adherents may of course find fault with my self-made definitions, but I, in turn, do not understand what could interest Haskell adherents in this article to read to this point.
Well, the remaining actions in the program are unlikely to raise questions. With the first two filters, we leave only those elements that we need (large two and not divisible by two), and the last filter applies a simplicity test.
Something like that.