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))