Clojure with Project Euler, part 1

Preface

I recently started to learn Clojure. I was interested in it because it's a Lisp dialect running on the jvm. I myself program in java, lisp and surprised me with their brackets. And there is such a mix of interesting. And with functional programming, too, wanted to meet you. But then came the problem: how to learn clojure? Should it have something to write... But what? And came to the conclusion, which is very convenient when learning a language to solve some simple mathematical puzzles: and to get used to the syntax and functionality a bit to meet you. This fits very well Project Euler. Here I will try to show you how to start working with clojure to solve a couple of problems on it. I'm new to functional programming and Lisp, so I would be very happy to see solutions more close and beautiful from the point of view of functional and Lisp.

Preparation

Of course first you have to configure everything to where it was working.
Clojure is distributed as a jar archive, it works as described here.
Good, in my opinion, the tutorial can be found here.
For clojure, I use emacs, how to make friends.
That is, in principle, that's all. You can now proceed to the solution of this Euler.

Task 1

Job
Find the sum of all numbers from 1 to 1000 999 that are divisible by 3 or 5.

Algorithm
1. To create a sequence of numbers from 1 to 1000 999, inclusive.
2. Filter it, leaving only the desired number.
3. The sum of all the numbers.

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))) — anonymous f-tion, the verifier does the argument % 3 or 5. If the argument is 1, it is denoted by a %, otherwise %1, %2, %3...
(filter ...) — filters our POS-th through our anonymous f-tsii.
(reduce + ...) — f-tion, which in our case adds up the numbers in the sequence.
In General, we should also see the description of reduce as it is often used.
As the documentation for any function can be accessed using (doc functionName) repl'.

Task 2

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

Algorithm
1. Build the Fibonacci sequence fib-seq (infinite, due to lazy initialization).
2. Building a second sequence of Fibonacci numbers less 4 million.
3. Select only the even-numbered.
3. To sum up.

Code

(def fib-seq
(lazy cat. [1 2] (map + fib-seq (rest fib-seq))))

(reduce +
(take-while #(< % 4000000) fib-seq))

For me the most difficult was to understand how to set the POS-th fib-seq in this performance.
It is obtained by "gluing" vector [1 2] and POS-ti, which is calculated by using the fib-seq. Somehow like this:

the

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

And then easier by using take-while taking elements from the beginning, while they are less than 4000000, filtered and summarize. Here it is necessary to pay special attention to f-related map.

intermediate Objective

Job
To build a sequence of Prime numbers (endless).
It is useful more than in a problem of Euler.

Algorithm
The idea and implementation itself is taken here.
It is based on the sieve of Eratosthenes. Sieve — this is the map, where the key will be number and the value is a divisor of number. Once we work only with odd numbers.
At every step we pick the next candidate p, see if it's in a sieve. If no — means simple, otherwise composite. Then we update the sieve, i.e. p is Prime, then add into a sieve the next number divisible by p, which is not in the sieve. If p is composite, then we a sieve we'll get, we'll get him the divisor, and add the next number that is divisible by the divisor, and is not in the sieve.

Code

For realizie will write some f-functions:

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

This f-tion adds to the sieve next the number of the candidate, which is divided into step and which is not yet in a sieve.

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

This f-tsiya looks simple or compound candidate and depending on that either gets it from the sieve or not. And then adds the following, which is not yet in a 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 f-tion is the main, it returns the POS-th Prime numbers. And also, if I understand correctly, recursive. On entrance it is given to the sieve and the candidate. It checks for ease of the candidate, and if it is simple, it adds it to the output pic-and calls itself recursively with a modified sieve and the next candidate. It is worth noting that here the back is a lazy POS-th (lazy-seq).
And now the latest should — to create a global sequence of Prime numbers:

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

Task 3

Job
Find the maximum Prime divisor of 600851475143.

Algorithm
We will have 2 functions.
One subsidiary, which divides the number by maximum degree of the divisor to "get rid" of the divisor from the number.
The second main, which in turn runs through all Prime numbers and trying our number on them to share. And accordingly it is a Prime number, after which we got 1 and will be sought.

Code

(defn divide-all [x divisor]
(if (zero? (rem x divisor))
(recur (/ x divisor) divisor)
x))

(defn max-prime-divisor [ind x]
(let [m (divide-all x (nth primes ind))]
(if (== m 1)
(nth primes ind)
(sets m (inc ind)))))

Here we used our primes.

That's all for now. I would love to see any comments, guidance to the right path, in terms of the language itself and functional programming.

Article based on information from habrahabr.ru