Project Euler
For any of you who do not know about Project Euler, here is a description lifted off of projecteuler.net:
"Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems."
I have a passion for finding efficient and elegant algorithms for solving complex mathematical problems. At the time of writing this I have solved 45 out of 208 problems of Project Euler and I would like to share with you a snippet of code written to solve problem 104. The question is as follows: "Given that F(k) is the first Fibonacci number for which the first nine digits AND the last nine digits are 1-9 pandigital, find k."
Writing the solutions in Ruby was a bit of a challenge for me since when compared to languages like C++ or Perl, Ruby comes last in terms of speed. This made the quest for efficient algorithms more difficult. That being said, here is the solution I came up with in Ruby that runs in approximately 100 seconds.
class String
def pandigital?
"123456789" == self.to_s.split(//).sort.join
end
end
older,old = 1, 1
counter = 3
while true
fib = older+old
if (fib % 1_000_000_000).to_s.pandigital?
if fib.to_s.slice(0,9).pandigital?
break
end
end
counter,older,old = counter+1, old, fib
end
puts "k = #{counter}"
Another snippet of code I would like to share is for problem 45 from Project Euler. The first hexagonal number that is also triangular and pentagonal is 40755, the question asked in problem 45 is to find the next one.
Solution written in Ruby:
require 'mathn'
class Integer
def hexagonal
self*(2*self-1)
end
def pentagonal?
n = (Math.sqrt(24*self+1)+1)/6
n == n.ceil
end
def triagonal?
n = (Math.sqrt(8*self+1)-1)/2
n == n.ceil
end
end
count = 144
while true
num = count.hexagonal
break if num.pentagonal? && num.triagonal?
count+=1
end
puts "result: #{num}"