Project Euler : Considering natural numbers of the form, ab, finding the maximum digital sum.

Problem 56

A googol (10¹⁰⁰) is a massive number: one followed by one-hundred zeros; 100¹⁰⁰ is almost unimaginably large: one followed by two-hundred zeros. Despite their size, the sum of the digits in each number is only 1.
Considering natural numbers of the form, a^b, where a, b < 100, what is the maximum digital sum?

Solution (in Ruby)

Nothing much to discuss about the solution, I've implemented it directly as given in the problem statement.

Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : Evaluate the sum of all amicable pairs under 10000.

Problem 21

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a b, then a and b are an amicable pair and each of a and b are called amicable numbers.
For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.
Evaluate the sum of all the amicable numbers under 10000.

Solution (in Ruby)

For this problem, it is vital to write an efficient method to find the sum of divisors of a number. The divisor finding logic is same as the one stated in Problem 12. Rest is an as-is implementation of the problem statement.

Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : How many letters would be needed to write all the numbers in words from 1 to 1000?

Problem 17

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.
If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of "and" when writing out numbers is in compliance with British usage.

Solution (in Ruby)

We will have to first try to come out with the unique words that are present in the numbers. We start with the ones which are one, two upto nine. Then the elevens starting from eleven to nineteen. Then the tens, twenties upto nineties. We should also define a hundred and thousand. After that the logic is directly readable from the ruby code given below.


Hover here to see the solution

Cheers!!
Bragaadeesh.

Project Euler : Discover all the fractions with an unorthodox cancelling method.

Problem 33

The fraction ⁴⁹/₉₈ is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that ⁴⁹/₉₈ = ⁴/₈, which is correct, is obtained by cancelling the 9s.
We shall consider fractions like, ³⁰/₅₀ = ³/₅, to be trivial examples.
There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.
If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

Solution (in Ruby)

This problem unlike the other problems does not ask us to go to millions and trillions and the scope is such that this can be solved in the least running time. All this problem demands careful inspection of the problem statement itself. Its clear we need to iterate through numbers from 1 to 99. For the outer loop (numerator), its enough we run from 12 since its the first double digit number which does not end with a 0 or their digits being equal. We run upto 97 since the numerator cannot be greater than equal to denominator since the fraction should be less than 1
Same is the case for the inner loop. We should always continue to the next iteration if the last number of either numerator or denominator is 0, or if both digits or equal or if the numerator is greater than or equal to denominator. Rest of the solution is just a language specific implementation of finding whether the two different fractions are indeed equal.

Hover here to see the solution

Cheers!!
Bragaadeesh.

Project Euler : What is the value of the first triangle number to have over five hundred divisors?

Problem 12

The sequence of triangle numbers is generated by adding the natural numbers. So the 7^th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

 1: 1
 3: 1,3
 6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.
What is the value of the first triangle number to have over five hundred divisors?

Solution (in Ruby)

The main aspect about this solution is finding an efficient way to calculate the number of divisors. Lets take a simple example. The number 6 has 4 divisors namely 1,2,3,6. For this number its enough we run upto the Square root of 6 which is integer floored value to be 2. 1 is divisible by 6 by 6 times, so 1 and 6 are divisors. 2 is divisble by 6 3 times, so 2 and 3 are divisors. So totally we have 4 divisors.
There is one more point to be noted here. For a square number such as 16, if we apply this formula, we will end up getting 6 divisors --> 1, 2, 4, 4, 8, 16. You may see we may calculate 4 twice. But it occurs only once for a square number. This special case is handled in the solution given below. The rest is an as-is implementation of the problem statement.

Hover here to see the solution

Cheers!!
Bragaadeesh.

Project Euler : How many Lychrel numbers are there below ten-thousand?

Problem 55

If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.
Not all numbers produce palindromes so quickly. For example,

349 + 943 = 1292,
1292 + 2921 = 4213
4213 + 3124 = 7337

That is, 349 took three iterations to arrive at a palindrome.
Although no one has proved it yet, it is thought that some numbers, like 196, never produce a palindrome. A number that never forms a palindrome through the reverse and add process is called a Lychrel number. Due to the theoretical nature of these numbers, and for the purpose of this problem, we shall assume that a number is Lychrel until proven otherwise. In addition you are given that for every number below ten-thousand, it will either (i) become a palindrome in less than fifty iterations, or, (ii) no one, with all the computing power that exists, has managed so far to map it to a palindrome. In fact, 10677 is the first number to be shown to require over fifty iterations before producing a palindrome: 4668731596684224866951378664 (53 iterations, 28-digits).
Surprisingly, there are palindromic numbers that are themselves Lychrel numbers; the first example is 4994.
How many Lychrel numbers are there below ten-thousand?

NOTE: Wording was modified slightly on 24 April 2007 to emphasise the theoretical nature of Lychrel numbers.

Solution (in Ruby)

This problem had a higher difficulty rating in project euler problems. But it was one of the straightforward ones that I solved it with Ruby. Nothing to say about the solution, its an as-is implementation of the problem statement.


Hover here to see the solution

Cheers!!
Bragaadeesh.

Project Euler : Concealed Square

Problem 206

Find the unique positive integer whose square has the form 1_2_3_4_5_6_7_8_9_0,
where each “_” is a single digit.

Solution (in Ruby)

Before we look at the optimal solution, lets look at what brute force has to offer us. There are nine slots in the number which leaves us to iterate on 1000000000 times (1 trillion times). This is simply not doable, it will take years to run through this loop. So brute force is out of the equation. We need to find a digit or two to reduce the loop count.

So its wiser to look at some of the property of square numbers. Square number ending with zero, has to have the previous digit also 0, which leaves us with only 8 slots now. One more property is that the square root for this particular number has to start with 1. The reason is in finding the square root, we need pair numbers from the back and need to find the square root of the first hanging digit/pair. In this case its 1. Square root 1 is 1 and its enough to inspect only one digit. This leaves us 1 more slot less in our problem. And one final property is the ending digit. Here its 9. Only numbers that end with 3 and 7 produces 9. This leaves our permutation reduce by one more digit (since its enough for us to step 10 times every time in the loop). We need to find the lower bound of the number which is 10203040506070809. The square root of this number is 101010101. We shall end with either 3 or 7. And start with the maximum digit in that sequence which is 199999999. Thats it!! Now we've shortened the problem to be solved within seconds!!


Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : How many circular primes are there below one million?

Problem 35

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.
There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.
How many circular primes are there below one million?

Solution (in Ruby)

The solution to this problem invovles one performance enhancement in finding the prime numbers. If you want to check whether the same number is prime more than once in your program, it is highly important to have a look on the running time. That is why I am using an array to store the number as the index itself. This would make sure that the number given is found to be prime or not in O(1) time. Rest of the solution did what the problem statement demands


Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : Find the sum of all numbers less than one million, which are palindromic in base 10 and base 2.

Problem 36

The decimal number, 585 = 1001001001₂ (binary), is palindromic in both bases.
Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)

Solution (in Ruby)

The solution is one the simplest and straightforward when implemented in Ruby.

sum = 0
1.upto(1000000) do |num|
  sum+=num if num.to_s == num.to_s.reverse && num.to_s(base=2) == num.to_s(base=2).reverse
end
puts "Sum is #{sum}"

Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : How many triangle words does the list of common English words contain?

Problem 42

The n^th term of the sequence of triangle numbers is given by, t_n = ½n(n+1); so the first ten triangle numbers are:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t₁₀. If the word value is a triangle number then we shall call the word a triangle word.
Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, how many are triangle words?

Solution (in Ruby)

The main place where we need to attack this problem involves in finding the roots of the quadratic equation. We know the roots of the quadratic equation

If you apply this equation to the simple formula to find the triangle numbers, we will find out that a = 1 and b = 1 and c will be twice the triangle number. There will be two roots possible, one will be positive and other will be negative. It is enough to find the positive root. If that root is a whole number, then that will be a proper triangle number.

names = File.new("/words.txt","r").gets.split(/,/)
count = 0
names.each do |n|
  value = n.gsub!(/^"(.*?)"$/,'\1').split(//).inject(0){|b,i| b+i[0]-64}
  positive_root = (-1+Math.sqrt(1+8*value))/2
  count+=1 if positive_root == positive_root.ceil
end
puts "The total number of words is #{count}"

Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : Using an efficient algorithm find the maximal sum in the triangle?

Problem 67

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.
Find the maximum total from top to bottom in triangle.txt (right click and 'Save Link/Target As...'), a 15K text file containing a triangle with one-hundred rows.

Solution (in Ruby)

To attack this problem, we should think in the reverse order as exploring all the possible routes would take 20 billion years to solve this problem!! We should start at the bottom but before level. For each number in that level, replace with the sum of that number and the maximum of the below two numbers. Do this for each level and bingo! we will arrive at the solution. So easy now isnt it? :) Thats 'after' you know it. Ruby code is presented below. There is another problem (Problem 18) (the minor input version) which also is the same one like the one above.

input = ''

f = File.new("/triangle.txt","r")
while (line = f.gets)
  input += line
end

class Row
  attr_accessor :index, :data
end

index = 0
triangle =  input.lines.map{|each_line| r = Row.new; r.index = index; r.data=[]; index+=1; sub_index = 0
  each_line.split.map{|n| r.data[sub_index] = n.to_i; sub_index+=1}; r}

(triangle.size - 2).downto(0) do |n|
  0.upto(triangle[n].data.size-1) do |sub_index|
    triangle[n].data[sub_index] += [ triangle[n+1].data[sub_index+1] , triangle[n+1].data[sub_index] ].max
  end
end

puts "The maximum value is #{triangle[0].data}"

Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : Find a quadratic formula that produces the maximum number of primes for consecutive values of n.

Problem 27

Euler published the remarkable quadratic formula:

n² + n + 41

It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 40² + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.
Using computers, the incredible formula  n² - 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, -79 and 1601, is -126479.
Considering quadratics of the form:

n² + an + b, where |a| < 1000 and |b| < 1000

where |n| is the modulus/absolute value of n
e.g. |11| = 11 and |-4| = 4

Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.

Solution (in Ruby)

Normally we would want to run through 1000 numbers in the outer loop and 1000 numbers in the inner loop to attack this problem. But we can significantly reduce that by just running 168 x 168 times by calculating the number of primes below 1000 first. This would reduce our running time. The rest of the solution is an as-is implementation of the problem statement.

def is_prime(n)
  return false if n <= 1
  2.upto(Math.sqrt(n).to_i) do |x|
    return false if n%x == 0
  end
  true
end

max_primes = []; a_s = []; b_s = []
INFINITY = 1.0/0.0

primes_upto_1000 = []
1.upto(999) do |each_num|
  primes_upto_1000 << each_num if is_prime(each_num)
end

primes_upto_1000.each do |a|
  primes_upto_1000.each do |b|
    each_prime = 0
    0.upto(INFINITY) do |n|
      break unless is_prime(n**2 - a*n + b)
      each_prime+=1 
    end
    max_primes<<< -a ; b_s << b
  end
end

puts "Product of a and b is #{a_s[max_primes.index(max_primes.max)] * b_s[max_primes.index(max_primes.max)]}" 

Hover here to see the solution

Cheers!!
Bragaadeesh.

Project Euler : What is the total of all the name scores in the file of first names?

Problem 22

Using names.txt (right click and 'Save Link/Target As...'), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.
For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 53 = 49714.
What is the total of all the name scores in the file?

Solution (in Ruby)

All we had to do is read the file convert all the values into an array and sort it. Then for each word we need to apply the rule as stated in the problem. If you could look at the code inside the loop, i would be ripping the starting and trailing quotes '"' and then converting them to index numbers. ie A for 1, B for 2 upto Z for 26. Rest is self explanatory.

names = File.new("/names.txt","r").gets.split(/,/).sort
sum = 0
index = 1
names.each do |n|
  sum += n.gsub!(/^"(.*?)"$/,'\1').split(//).inject(0){|b,i| b+i[0]-64} * index
  index+=1
end
puts "The total of all the name scores is #{sum}"

Hover here to see the solution

Cheers!!
Bragaadeesh.

Project Euler : How many Sundays fell on the first of the month during the twentieth century?

Problem 19

You are given the following information, but you may prefer to do some research for yourself.

• 1 Jan 1900 was a Monday.
• Thirty days has September,
  April, June and November.
  All the rest have thirty-one,
  Saving February alone,
  Which has twenty-eight, rain or shine.
  And on leap years, twenty-nine.
• A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

Solution (in Ruby)

This particular solution does not involve any hard calculations, just run through the dates starting from the first sunday step by 7 days and check if the sunday lies on the first day of the month.

require 'date'
d1, d2, total_sundays = [Date::civil(1901, 1, 1), Date::civil(2000, 12, 31), 0]
d1 +=1 while (d1.wday != 0)
d1.step(d2, 7){|date| total_sundays+=1 if date.day == 1}
puts "Total number of Sundays : #{total_sundays}"

Hover here to see the solution

Project Euler : Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits in some order.

Problem 52

It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, but in a different order.
Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.

Solution(in Ruby)

The solution to this problem is simple and straight forward as shown below. Just convert the problem statement into code with tweaks here and there, we should arrive at the solution smoothly. Do not get scared by the catch statement, its just to break nested loops. Moreover, it is enough to inspect numbers that start with 1. The obvious reason being numbers that begin with 2 get more digits when multiplied by 6 which would defeat our purpose.

INFINITY = 1.0 / 0.0
catch (:done) do
  1.upto(INFINITY) do |i|
    ((10**i)...(2*10**i)).each do |x|
      y = x.to_s.split(//)
      if ( y - (x*2).to_s.split(//) ).size == 0 && y.size == (x*2).to_s.split(//).size &&
         ( y - (x*3).to_s.split(//) ).size == 0 && y.size == (x*3).to_s.split(//).size &&
         ( y - (x*4).to_s.split(//) ).size == 0 && y.size == (x*4).to_s.split(//).size &&
         ( y - (x*5).to_s.split(//) ).size == 0 && y.size == (x*5).to_s.split(//).size &&
         ( y - (x*6).to_s.split(//) ).size == 0 && y.size == (x*6).to_s.split(//).size
        puts "The minimum unique number is #{x}"
        throw :done
      end
    end
  end
end

Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : Find the minimal path sum from the left column to the right column.

Problem 82
The minimal path sum in the 5 by 5 matrix below, by starting in any cell in the left column and finishing in any cell in the right column, and only moving up, down, and right, is indicated in red and bold; the sum is equal to 994.

131 673 234 103 18 201 96 342 965 150 630 803 746 422 111 537 699 497 121 956 805 732 524 37 331

Find the minimal path sum, in matrix.txt (right click and 'Save Link/Target As...'), a 31K text file containing a 80 by 80 matrix, from the left column to the right column.

Solution(in Ruby)

This problem has to be attacked in the reverse order ie starting from the right to left. Lets take the last but before column. For each cell in that column, find the minimum possible sum for that cell. To find the minimum possible sum, you will have to find all the 'L' paths explored, their sum has be calculated and stored and the minimum sum has to be stored in that cell. After traversing that entire column, replace that particular column value with the minimal sum. Repeat this process for the immediate left column until you exhaust all the columns reaching the left most column. The minimal value of the leftmost column is the minimal sum which is exactly what we look for.

require 'matrix'

input = ''
file = File.new("/matrix.txt","r")
while (line = file.gets) 
  input += line
end

class Cell
  attr_accessor :min_sum, :value
end

x = Matrix.rows(input.lines.map{|each_line| each_line.split(/,/).map{
      |n|
      c = Cell.new
      c.min_sum = c.value = n.to_i
      c
    }})

MAX = x.row_size

(MAX-2).downto(0) do |column|
  0.upto(MAX-1) do |row|
    val_array = []
    aggregate = x[row,column].value
    val_array << aggregate + x[row,column+1].value
    (row+1).upto(MAX-1) do |down_traverse|
      aggregate += x[down_traverse,column].value
      val_array << aggregate + x[down_traverse,column+1].value
    end
    aggregate = x[row,column].value
    (row-1).downto(0) do |up_traverse|
      aggregate += x[up_traverse,column].value
      val_array << aggregate + x[up_traverse,column+1].value
    end
    x[row,column].min_sum = val_array.min
  end
  0.upto(MAX-1) do |each_row|
    x[each_row,column].value = x[each_row,column].min_sum
  end
end
val_array = []
0.upto(MAX-1) do |val|
  val_array << x[val,0].value
end

puts "The minimum sum is #{val_array.min}"

Hover here to see the solution

Cheers!!
Bragaadeesh.

Project Euler : Find the longest sequence using a starting number under one million.

Problem 14

The following iterative sequence is defined for the set of positive integers:

n --> n/2 (n is even)
n --> 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 --> 40 --> 20 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

Solution (in Ruby)

In order to solve this problem, we first need to find a pattern by attacking in the reverse order. If you could see if the number gotten is a power of two, it will diminish all the way upto 1. So its wiser to store their frequency (power of 2 numbers) first in the array. The next interesting property is that if you find the chain count for a number you do not want to find that again. Combining these two properties, we can very well get a linear solution for the input count of 1 million solving the problem within seconds.

MAX_NUM = 1000000
n = Array.new(MAX_NUM)
n[0] = 0
n[1] = 1
counter = 1
index = 1
while (counter < MAX_NUM)
  n[counter] = index
  index+=1
  counter*=2
end
(MAX_NUM-1).downto(2) do |num|
  if n[num]
    next
  end
  rolling = num
  sequence = 0
  while !n[rolling]
    if rolling % 2 == 0
      rolling = rolling/2
    else
      rolling = 3*rolling + 1
    end
    sequence+=1
  end
  n[num] = sequence + n[rolling]
end
puts "The maximum chained number is #{n.index(n.max)}"

Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : Calculate the sum of all the primes below two million.

Problem 10
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.


Solution(in Ruby)
The solution to this problem involves the tricky implementation of prime number functionality. Rest is just a matter of programming.

def is_prime(n)
  return false if n <= 1
  2.upto(Math.sqrt(n).to_i) do |x|
    return false if n%x == 0
  end
  true
end
sum = 0
2.upto(2000000) do |num|
  x+=num if is_prime(num)
end
puts "Sum is #{sum}"

Hover here to see the solution

Cheers!
Bragaadeesh

Project Euler : Find the greatest product of five consecutive digits in the 1000-digit number.

Problem 8

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 (in Ruby)

The solution to this problem can be solved by just naked eyes. Anyway, I have presented the code in Ruby.

num = '73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450'
f = ''
num.lines{|x| f += x.chop}
y = f.split(//)
arr = []
0.upto(995) do |index|
  arr << y[index].to_i * y[index+1].to_i * y[index+2].to_i * y[index+3].to_i * y[index+4].to_i
end
puts arr.max

Hover here to see the solution

Cheers!!
Bragaadeesh.

Project Euler : Find the largest palindrome made from the product of two 3-digit numbers.

Problem 4

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 x 99.
Find the largest palindrome made from the product of two 3-digit numbers.

Solution (in Ruby)

The solution to this problem is pretty straight forward. All we had to do is run from 101 to 999 and multiply all the combination and push them into an array and find the maximum value.

arr = []
101.upto(999) do |i|
  101.upto(999) do |j|
    prod = i*j
    arr << prod if prod.to_s == prod.to_s.reverse
  end
end
puts "The largest palindromic number is #{arr.max}"

Hover here to see the solution

Cheers!!
Bragaadeesh.

Project Euler : Finding maximum prime factor

Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

Solution (in Ruby)

The solution to this problem is simple. But the main problem here is to construct a rock solid method that returns whether a given number is prime or not. A prime number is a number which divisible by itself and 1 only. Example of prime numbers are 2,3,11,4999. The following is the ruby code to find whether or not a number is prime or not. You may see that I have used a square root of the number as the upper bound, the simple reason being, there cannot be a number greater than the square root of that number being prime (you can get it if you think deep)

Now that we have written a method that returns whether or not a number is prime, the rest of the problem is fairly simple. Again, we have to use the square root property. It is enough if we run the prime number validation from the square root of the number. We will have to traverse all the way to 2 for this. The first occurring prime factor is ofcourse the solution to our problem.

Hover here to see the solution.

Cheers!!
Bragaadeesh.

Project Euler : Finding maximum product in a matrix

Problem 11

In the 20 x 20 grid below, four numbers along a diagonal line have been marked in red.

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

The product of these numbers is 26 x 63 x 78 x 14 = 1788696.
What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 20 x 20 grid?

Solution (In Ruby)

The solution to this particular problem is simple and by simple naked eye viewing we can get what we want. But then, if the numbers are almost in the same range and if the matrix size is more then it will become real difficult to identify the maximum number. The following ruby code will find the maximum number. All we are doing here is finding the product of the numbers in the fashion we are supposed to. There is no trick shortcut here. We 'will' have to traverse the entire matrix for finding the product.

require 'matrix'
input =
 '08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
  49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
  81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
  52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
  22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
  24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
  32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
  67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
  24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
  21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
  78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
  16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
  86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
  19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
  04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
  88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
  04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
  20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
  20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
  01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48'

x =  Matrix.rows(input.lines.map{|line| line.split.map{|n| n.to_i}})
val = []
0.upto(19) do |r|
  0.upto(19) do |c|
    val << x[r,c] * x[r,c+1] * x[r,c+2] * x[r,c+3] if c<=16
    val << x[r,c] * x[r+1,c] * x[r+2,c] * x[r+3,c] if r<=16
    val << x[r,c] * x[r+1,c+1] * x[r+2, c+2] * x[r+3, c+3] if c<=16 && r<=16
    val << x[r,c] * x[r+1,c-1] * x[r+2, c-2] * x[r+3, c-3] if c>=3 && r<=16
  end
end
puts puts "Maximum product is #{val.max}"

Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : Find the last ten digits of the series, 1^(1) + 2^(2) + 3^(3) + ... + 1000^(1000).

Problem 48

The series, 1¹ + 2² + 3³ + ... + 10¹⁰ = 10405071317.
Find the last ten digits of the series, 1¹ + 2² + 3³ + ... + 1000¹⁰⁰⁰.

Solution (In Ruby)

The solution to this problem becomes simple if we just directly implement with the brute force technique. It just costs two lines in Ruby and the source code is given below.

sum = (1..1000).to_a.inject(0) {|b,i| b+= i**i}.to_s
puts sum.to_s[(sum.size-10)..(sum.size)]

Hover here to see the solution.

Cheers!!
Bragaadeesh