We solve Project Euler on F #: Tasks 3, 7, 10

Well, let's continue our acquaintance with F #, and at the same time solving 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 first ten of these are three pieces, so we'll take a look at them.
In these examples, we will continue to use only the functional aspects of the language, for the final, so to speak, consolidation. And how to use F # in the imperative and object-oriented paradigm, I probably will 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 the 13195 are 5, 7, 13 and 29. What is the largest factor of the number of 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 run out, we are not gathered for this, but we will solve with the usual sieve of Eratosthenes . As a 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 these, an empty list, is needed solely so that the compiler does not swear at incomplete pattern matches. In fact, our function will never fall here, and the second comparison is terminal for it.
In this template, in addition to the standard for working with lists of division into head and tail ( n :: tail ), an additional condition is used, which is written after the keyword when . In this case, it checks if our number is not large enough (sqrt max), that the screening procedure could be stopped, and if so, it gives out the remaining list to it. In the last pattern, the screening itself is specified, given by lambda.
Since the sum of all primes can be quite impressive (and it is, answer 142913828922), we use 64-bit int64 in the code, and we hint about this to the compiler by writing “L” constants.
In one case, it was not possible to manage with hints, since I had to cast the square root to int64. By the way, before that, we had to bring our number to a floating point with the float function, since I did not want to take sqrt from the whole. For C # programmers, this looks pretty weird. The function does not work very quickly, but it fits into 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, the kettle method.

If someone accidentally accidentally knows something, the method is described by the following anecdote:
The mathematician asks the physicist: “You have an empty kettle, a faucet with water, and a stove. How to warm the kettle? ”“ It is necessary to pour water from the tap into the kettle, light the fire and put the kettle on it, ”the physicist replies. "Fine! - says the mathematician, - and now imagine that there is water in the kettle, and the fire is lit. ” “Well, then it's very simple,” says the physicist, “we put the kettle on the stove.” “That's not it,” says the mathematician, “we must pour out the 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 those that divide the given number and find the maximum among them. The only valuable thought is that you should look for primes not up to the number itself, but before 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 appreciate the full power of Pipeline. (How can you translate into Russian? The “pipeline” somehow does not sound very much ...) Surely there are ways and quickly decide, without a “teapot”, can anyone suggest?

The third task, of course, can also be solved with the help of the same kitchen appliance, for example, by empirically checking that the primes <2M we found are much more than 10001 (yes, there are more of them in a million), so simply without fear to take the 10001st element of the list. But you must agree, such a decision somehow sickened our programming sense of beauty. I'd like to solve the problem in general.

As a result of the reflections, I decided to simply implement the naive method - filtering the full list of numbers according to the simplicity test, applied small optimizations, and, surprisingly, worked perfectly, and for 10001 it turned out disproportionately faster than the first proposed method.
In my interpretation it looks like this:

#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 curious example of all three.
The Seq.init_infinite method sets, as the name implies, an infinite sequence. Well, yes, it is infinite. It is given by the lambda indicated in brackets, which is identical in our case. This infinity is, of course, virtual, because in fact the sequence at the moment of determination does not exist yet, and it will be created only when it becomes necessary, just as operations on it will be done only when their results are required for further work. In short, F # supports lazy evaluation (by adding the keyword lazy before the function), and the class Seq has this ability a priori. The topic of lazy calculations is quite extensive and complex to at least a little to fully illuminate 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 adepts may of course find fault with my self-defined definitions, but I, in turn, do not understand what could be so interesting for Haskell adepts in this article to read to this point.

Well, the rest of the actions in the program are unlikely to cause questions. Using the first two filters, we leave only those elements that we need (big two and not divisible into two), and the last filter applies the test for simplicity.
Something like that.