09-Oct-2013 by Allison McMillan

Read Time: Approx. 3 minutes

Eulers Continued: Problems 2 and 3

Continuing with the Project Euler problems, here's my solution for numbers 2 and 3.

Problem 2

Each new term in the Fibonacci sequence is generated by adding 
the previous two terms.
By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose
values do not exceed four million, find the sum of the even-valued terms.


First, here are the tests that I wrote:
 
require 'problem2/problem2'

describe 'solution' do

it "sums the first two terms to generate the third term" do
expect(Problem2.fib(2)).to eq 1
end

it "sums the even-valued terms up to the limit" do
expect(Problem2.fib(4000000)).to eq 4613732
end
end

Similar to the tests written for the first problem, we want to check the answer and put the actual numbers in the test and then write the code so that it doesn't need a number, it just needs the argument to be noted and the argument in the code pulls the fixed number arguments from the test in order to run and pass. The Problem2 is the module and fib is the method.

So, onto the code:
module Problem2

def self.fib(limit)
arr = []
a,b = 0,1

while a < limit
arr << a
a, b = b, a + b
end

sum = arr.select { |i| i.even? }.reduce(:+)

end

fib(4000000) #sets the limit
end
 
To solve this problem, first, I decided to create an empty array, then I needed to put stuff in the array (that's the second line). The question gives a certain number as the limit (4000000) so while the number is under the limit, we want to push the new number onto the end of the array (arr << a). So that create the action of what will happen. Then we need to create the formula that will produce the number (the recursion formula). And that's that part of the problem. Next, once we have the Fibonacci sequence in the array, we need to solve the second part of the problem where we find the sum of the even-valued terms. In order to find the sum, we take the array and use the select method, passing the array through a block that looks for which numbers are even, selecting those numbers and then using the reduce :+ method to add those numbers together. Finally, fib(4000000) sets the limit of what we are looking for to put the result. One note about solving these problems. I've started outlining each step at the top of the problem to give myself a short roadmap to work from and then once I have the problem clarified in my mind and a roadmap worked out, I can work through each part until I find the solution and get working code.  

Problem 3

I include both problems in this entry because my solution to problem 3 is a bit of a cheat. But before we go there, here's the problem:

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

Here are the tests I wrote:

require 'problem3/problem3'

describe 'answer' do

it 'will have the largest prime factor for 13195' do
expect(Problem3.prime(13195)).to eq 29
end

it 'will have a largest prime factor for 600851475143' do
expect(Problem3.prime(600851475143)).to eq 6857
end
end
 
And here's the code:

require 'prime'

module Problem3

def self.prime(num)
primes = Prime.prime_division(num)
primes.last[0]
end
end

So, there's a Ruby library called Prime which makes doing anything with prime numbers really simple. First, I required that library. The I just defined primes and used prime_division which divides the number to determine which the prime numbers are. Finally, I took the last number in the list which would be the largest number. Really simple and straight forward.

Ready to chat?

Join my mailing list

* indicates required

Set up a free call

phone icon