Clojure and Project Euler, Part 1

Foreword

I recently started learning the Clojure language. He interested me because it is a lisp dialect running on jvm. I myself program in java, and lisp surprised me with its brackets. And here such a mixture is interesting. And I also wanted to get acquainted with functional programming. But then a problem arose: how to learn clojure? It is necessary to write something on it ... But what? And I came to the conclusion that it’s very convenient to solve some simple mathematical problems when learning the language: you’ll get used to the syntax and get to know the functionality a bit. Project Euler is very suitable for this.. Here I will try to show how to start working with clojure and solve a couple of problems on it. I am new to functional programming and lisp, so I will be very happy to see solutions that are closer and more beautiful from the point of view of functional and lisp.

Training

First, of course, you need to configure everything so that there is where to work.
Clojure is distributed as a jar archive, how to connect it is described here .
A good tutorial, in my opinion, can be found here .
For clojure I use emacs, how to make them friends .
That's basically it. Now you can begin to solve this very Euler.

Task 1

Task
Find the sum of all numbers from 1 to 1000 999, which are divided by 3 or 5.

Algorithm
1. Create a sequence of numbers from 1 to 1000 999 inclusive.
2. Filter it, leaving only the numbers we need.
3. Sum all numbers.

The code

(reduce +
       (filter # (or (zero? (rem% 3))
                        (zero? (rem% 5)))
               (range 1000)))

(range 1000) - a sequence of numbers from 0 to 999
(#or (zero? (rem% 3)) (zero? (rem% 5))) - an anonymous function that checks whether the argument% is divided by 3 or 5. If argument 1, then it is denoted by%, otherwise% 1,% 2,% 3 ...
(filter ...) - filters our message using our anonymous function.
(reduce + ...) is a function that in our case adds up the numbers of a sequence.
In general, it is worth looking at the description of reduce separately , as she is often used.
Also, documentation for any function can be viewed using (doc functionName) directly in repl.

Task 2

Task
Find the sum of all even Fibonacci numbers less than 4 million.

Algorithm
1. We build the Fibonacci sequence fib-seq (infinite, thanks to lazy initialization).
2. We construct the second sequence of Fibonacci numbers less than 4 million.
3. We select only the even ones.
3. Summarize.

The code

(def fib-seq 
       (lazy-cat [1 2] (map + fib-seq (rest fib-seq))))
 
(reduce + 
            (filter even? 
                     (take-while # (<% 4000000) fib-seq))

For me, the most difficult thing here was to realize how the fib-seq is set in this version.
It is obtained by “gluing” the vector [1 2] and by the way, which is calculated using fib-seq. Something like this:

fib-seq = (1 2) + (3 5 8 13 ...)
                       =
         fib-seq: (1 2 3 5 ...)
                       +
  (rest fib-seq): (2 3 5 8 ...)

And then it’s already easier, using take-while we take elements from the beginning, while they are less than 4,000,000, we filter and summarize. Here it is worth paying special attention to the map function .

Intermediate task

Task
Build a sequence of primes (infinite).
It will come in handy in more than one task from Euler.

Algorithm
The idea and the implementation itself is taken from here .
It is based on the sieve of Eratosthenes. Sieve - this will be a map in which the number will act as the key, and the value will be the divisor of the number. Immediately we will work only with odd numbers.
At each step, we will take the next candidate p, see if he is in the sieve. If not, it means simple, otherwise composite. Then we will update the sieve, i.e. p is prime, then we add to the sieve the following number divisible by p, which is not in the sieve. If p is composite, then we get it out of the sieve, take out its divisor, and add the next number, which is divided by a divisor and is not in the sieve.

Code

For implementation, we will write several functions:

(defn enqueue [sieve candidate step]
      (let [m (+ candidate step)]
            (if (sieve m)
                 (recur sieve m step)
                 (assoc sieve m step))))

This function adds to the sieve the next number after the candidate, which is divided by step and which is not yet in the sieve.

(defn next-sieve [sieve candidate]
        (if-let [step (sieve candidate))
                (-> (dissoc sieve candidate)
                      (enqueue candidate step))
                (enqueue sieve candidate (+ candidate candidate))))

This f-tion is looked at by a simple or compound candidate and, depending on this, either removes it from the sieve or not. And then he adds the next one, which is not yet in the sieve.

(defn next-primes [sieve candidate]
         (if (sieve candidate)
              (next-primes (next-sieve sieve candidate) (+ 2 candidate))
              (cons candidate 
                       (lazy-seq (next-primes (next-sieve sieve candidate)) (+ 2 candidate))))))

This function is the main one; it returns the number of primes. And she, besides, if I understand correctly, recursive. At its entrance, a sieve and a candidate are given. She checks for the simplicity of the candidate, and if he is simple, then adds it to the output, and calls herself recursively with the changed sieve and the next candidate. It should be noted that it is precisely the lazy post (lazy-seq) that returns here.

And now the last function is to create a global sequence of primes:

(def primes (concat [2] (next-primes {} 3)))

Task 3

Task
Find the maximum prime divisor of 600851475143.

Algorithm
We will have 2 functions.
One auxiliary, which divides the number by the maximum degree of its divisor, to "get rid" of the divisor in the number.
The second main one, which alternately runs through all prime numbers and tries to divide our number into them. And accordingly, that prime number, after which we got 1 and will be the desired one.

The code

(defn divide-all [x divisor]
         (if (zero? (rem x divisor))
             (recur (/ x divisor) divisor)
             x))
 
(defn max-prime-divisor [x ind]
          (let [m (divide- all x (nth primes ind))]
                (if (== m 1)
                    (nth primes ind)
                    (recur m (inc ind)))))

Here we used our primes.

That's all for now. I would really like to see any comments, instructions on the true path from the point of view of the language itself and functional programming.