Solving Project Euler Problem #16 in Clojure

Problem Statement :

2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2^1000?


Solution :
The easiest way to multiply a number by 2 is to perform a left bit shift.
Get the number, convert it to string, put the indices in a map and apply a "+" function on it.

(println (apply + (map #(Integer/parseInt (str %1)) (str (bit-shift-left 2 999)))))

Solving Project Euler Problem #10 in Ruby

Problem Statement :-

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

Solution :-

require "mathn"
require "benchmark"
module Enumerable
  def lazy_select
    Enumerator.new do |yielder|
      each do |obj|
        yielder.yield(obj) if yield(obj)
      end
    end
  end
end

p 5+((5..2000000).lazy_select {|v| (v%6 == 1 || v%6 ==5) && v.prime?}.take(2000000)).inject(0) {|s,v| s+=v}
#Benchmark.bm(12) { |b| b.report('Report:') {5+((5..2000000).lazy_select {|v| (v%6 == 1 || v%6 ==5) && v.prime?}.take(2000000)).inject(0) {|s,v| s+=v}}  }

Solving Project Euler Problem #9 No code Required

Problem Statement :-

A Pythagorean triplet is a set of three natural numbers, a b c, for which,

a^2 + b^2 = c^2
For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

Solution :-
Lets have a look on the first Pythagorean triplet 3, 4 and 5.

All their multiples, would also be a Pythagorean triplet (e.g. 6, 8 and 10 or 9, 12 and 15 , and so on..)

Also, any odd number can be represented as x^2 - y^2
For e.g.
3 = 2^2 - 1^2
5 = 3^2 - 2^2
7 = 4^2 - 3^2

Since, (x^2 - y^2)^2 + (2xy)^2 = (x^2 + y^2)^2, we can always generate a triplet for any odd number x^2 - y^2.

So, using this any triplet is of the form :
k*(x^2-y^2), k*2xy and k*(x^2+y^2), where k is any number (1, 2, ...n).

Well, now let us solve the current problem.

a = k*(x^2-y^2)
b = k*2xy
c = k*(x^2+y^2)
Since a+b+c = 1000, and they are the sides of a triangle,

a,b,c < 500
=> k*(x^2+y^2) < 500
=> x,y < 500^(1/2) < 23

Now, given a+b+c = 1000
=> k(x^2-y^2+2xy+x^2+y^2) = 1000
=> 2kx(x+y) = 1000
=> k*x(x+y) = 500 (Factors of 500 is , 2,2,5,5,5)
=> k*x(x+y) = 20*(20+5) (This is the only value, which satisfies x,y < 23)
=> for k =1 , x = 20, y = 5

So, a = 20^2 - 5^2 = 375
b = 2*20*5 = 200
c = 20^2 + 5 ^2 = 425

So, the product is : 375*200*425 = 31875000

Solving Project Euler Problem #8 No code Required

Problem Statement :-
Find the greatest product of five consecutive digits in the 1000-digit number.
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450


Solution :

One way to solve is :-
starting from the beginning 5 numbers (strating from the 1st), multiplying them, storing it in as max, continuing the process for the next 5 numbers(starting from the 2nd), replacing the max value if the current product is more than the max stored earlier and so on till we reach the last 5 elements.
We may minimize the number of iterations based on the fact that for every zero found we don't need to calculate the product.


Lucky Solution :-
I started looking for 99999 using "ctrl+F" (as I knew if I find this any where), this would be the max no matter what the other numbers are.
Since it was not there, I started looking for the combination of for 9's and one 8 (it was also not there) and so on, and eventually found 99879. Definitely, i was lucky to get the number in a minute or so (The data set for the problem was friendly, otherwise I would have probably coded it.

You may use another fact to code your logic. If you know the sum of n numbers x1+x2+..xn, the maximum value of their product is when x1=x2=..=xn.

For e.g. sum of 9,9,8,8,8 and 9,9,8,7,9 is equal, the product of 9,9,8,8,8 would be
larger (8+7+9 = 24 = 8+8+8).

Solving Project Euler Problem #7 in Ruby, Clojure

Problem Statement :
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

Solution :

This works on Ruby 1.9+. Here we have taken advantage of the method discusses here to create Lazy enumerator in Ruby. I started looking for the ruby equivalent as the clojure code becomes so easy to deal with using the lazy sequences.

require "mathn"
infinity = 1.0/0.0
module Enumerable
  def lazy_select
    Enumerator.new do |yielder|
      each do |obj|
        yielder.yield(obj) if yield(obj)
      end
    end
  end
end

p (1..infinity).lazy_select { |v| v.prime? }.take(10001).last

The clojure code is as follows :
Here we have added one optimization (Any prime number after 2 and 3, when divided by 6, leaves the remainder 5 or 1).

(defn sqrt [x]
  (int (Math/sqrt x)))

(defn get-smallest-prime-factor [n]
  (loop [n n d 2]
    (cond (> d (sqrt n)) n
      (= n d) n
      (= 0 (rem n d)) d
      true (recur n (inc d)))))

(def get-nth-prime
  (lazy-cat '(2 3)
    (filter
      #(= % (get-smallest-prime-factor %))
      (filter
        #(or (= 1 (rem % 6)) (= 5 (rem % 6)))
        (take-nth 2 (iterate inc 3))))))

(println (nth get-nth-prime 10000))

Here is another cheat, if you have installed the clojure contrib library.

(use 'clojure.contrib.lazy-seqs)
(println (nth primes 10000))

Solving Project Euler Problem #6

Problem Statement :
The sum of the squares of the first ten natural numbers is,
1**2 + 2**2 + ... + 10**2 = 385
The square of the sum of the first ten natural numbers is,(1 + 2 + ... + 10)**2 = 55*2 = 3025
Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 385 = 2640.
Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Solution is -> (n(n+1)/2)**2 - (n*(n+1)*(2n+1))/6

(defn euler6 [n] (- (* (/ (* n (+ n 1)) 2) (/ (* n (+ n 1)) 2)) (/ (* n (+ n 1) (+ 1 (* n 2))) 6)))
(println (euler6 100))

Dual Pivot Quicksort in Java

This is from the paper published by Vladimir Yaroslavskiy (Read it for more details : here

Sorting data is one of the most fundamental problems in Computer Science, especially if the arranging objects are primitive ones, such as integers, bytes, floats, etc. Since sorting methods play an important role in the operation of computers and other data processing systems, there has been an interest in seeking new algorithms better than the existing ones. We compare sorting methods by the number of the most "expensive" operations, which influence on effectiveness of the sorting techniques, — comparisons and swaps. Quicksort algorithm is an effective and wide-spread sorting procedure with C*n *ln(n) operations, where n is the size of the arranged array. The problem is to find an algorithm with the least coefficient C. There were many attempts to improve the classical variant of the Quicksort algorithm:

1. Pick an element, called a pivot, from the array.
2. Reorder the array so that all elements, which are less than the pivot, come before the pivot and all elements greater than the pivot come after it (equal values can go
either way). After this partitioning, the pivot element is in its final position.
3. Recursively sort the sub-array of lesser elements and the sub-array of greater elements.

We can show that using two pivot elements (or partitioning to three parts) is
more effective, especially on large arrays. We suggest the new Dual-Pivot Quicksort
scheme, faster than the known implementations, which improves this situation. The
implementation of the Dual-Pivot Quicksort algorithm has been investigated on different inputs and primitive data types. Its advantages in comparison with one of the most effective known implementations of the classical Quicksort algorithm [1], [2], and implementation of Quicksort in JDK™ 6.0 platform [3] have been shown.

It is proved that for the Dual-Pivot Quicksort the average number of
comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n),
whereas classical Quicksort algorithm has 2*n*ln(n) and 1*n*ln(n)
respectively.



Here is the source code for the implementation : Code by Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch.


Comparision between Current JDK Quicksort vs Dual Pivot Quick sort : comparision