Clojure and Project Euler, part 1

Foreword

I recently started learning Clojure. He interested me because it is a lisp'a dialect running on jvm. I myself program in java, and lisp surprised me with my brackets. And here such a mixture is interesting. And I also wanted to get acquainted with functional programming. But then the problem arose: how to study clojure? We need to write something on it ... Why? And I came to the conclusion that when learning a language it is very convenient to solve some simple mathematical problems: you will get used to the syntax, and you will get acquainted with the functionality a bit. Project Euler is very well suited for this. Here I will try to show how to start working with clojure and solve a couple of tasks on it. I am new to functional programming and lisp, so I will be very happy to see solutions closer and more beautiful in terms of functional and lisp.

Training

First of all, of course, you need to set everything up so that you have where to work.
Clojure is distributed as a jar archive, how to connect it is described here .
Good, in my opinion, tutorial can be found here .
For clojure, I use emacs as a friend .
That's basically it. Now you can begin to solve this very Euler.

Task 1

The 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 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 ) ) ) is an anonymous function that checks whether the argument% is divisible by 3 or 5. If the argument is 1, then it is denoted%, otherwise% 1 ,% 2,% 3 ...
( filter ... ) - filters our pos-t with the help of our anonymous function.
( reduce + ... ) is a function, which in our case adds up the numbers of a sequence.
In general, it is worth looking separately at the description of reduce , since it is often used.
Also, documentation for any function can be viewed using (doc functionName) directly in the repl.

Task 2

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

Algorithm
1. Build a fib-seq fibonacci sequence (infinite, thanks to lazy initialization).
2. Build a second sequence of Fibonacci numbers less than 4 million.
3. We select only even ones.
3. We summarize.

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 Fib-seq is assigned in this version.
It is obtained by “gluing” the vector [1 2] and all 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 further it is already easier, with the help of 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

The task
Build a sequence of prime numbers (infinite).
It is useful to more than one problem from Euler.

Algorithm
The idea and the implementation itself is taken from here .
At the heart lies the sieve of Eratosthenes. Sieve - we will have a map in which the key will be a number, and the value is a divisor of a number. We will immediately work only with odd numbers.
At every step we will take the next candidate p, see if he is in the sieve. If not, then simple, otherwise composite. Then we will update the sieve, i.e. p is a simple one, then add the following number to the sieve, dividing by p, which is not in the sieve. If p is composite, then we will get it from the sieve, we will also get its divisor, and add the following number, which is divisible by a divisor and absent in the sieve.

Code

For implementation, we will write a few functions:

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

This function adds the following number to the sieve for the candidate, which is divisible 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 looks simple or compound candidate and, depending on this, either gets him out of the sieve or not. And then 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 f-tion is the main, it returns after-primes. And she, besides, if I correctly understand, recursive. At the entrance it is given a sieve and a candidate. She checks for the simplicity of the candidate, and if he is simple, she adds him to the exit, and calls herself recursively with a modified sieve and the next candidate. It is worth noting that the lazy post-t (lazy-seq) returns here.

And now the last function - the creation of a global sequence of prime numbers:

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

Task 3

The task
Find the maximum prime divisor of the number 600851475143.

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

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 prime numbers.

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