Random Code Patterns

SOPA Blackout

2012-01-19T02:00:00.000-05:00

Well, the blackout on January 18 worked to get the SOPA and PIPA bills noticed on national media. However, coverage is about what you would expect considering most TV networks are owned by the very media conglomerates that want to shut down the Internet as we know it.

Just check out this report from Media Matters on FOX News' coverage.

More SOPA and PIPA news

2012-01-17T11:42:00.001-05:00

A couple more links on the SOPA front.

The White House has declared it’s opposition to SOPA.
A great explanation of how PIPA will break the Internet.
Congress shelves SOPA indefinitely. (Don’t be confused, though, PIPA is still alive in the Senate.)
Wikipedia is doing a great job covering the status of these two bills.

Haven’t heard of these bills before:

SOPA – Stop Online Piracy Act
Proposes to stop online piracy by barring sites that post, link to, or otherwise make available copyright content. However, this bill would also allow your site to be shut down if someone simply posts a copyrighted image in the comments section of the site. The full text of the bill can be found here.
PIPA – PROTECT IP Act (Preventing Real Online Threats to Economic Creativity and Theft of Intellectual Property)
This bill would give the government the ability to completely block sites that corporations don’t like. Again, this is ostensibly to allow them to block piracy, except that it doesn’t since downloaders will still be able to access these sites via their IP addresses. The full text of the bill can be found here.

We need everybody’s support to make sure these bills don’t happen. Write your Senator and your Congressman. Or you can fill out one of the many joint letters being compiled online, such as the one at Fight for the Future.

More SOPA in the news, or not...

2012-01-07T05:00:00.000-05:00

Is it just me, or is SOPA not getting very much coverage despite its horrendous implications. Oh, guess it isn't just me...

REPORT: News Networks Ignore Controversial SOPA Legislation

Controversial legislation that the co-founder of Google has warned "would put us on a par with the most oppressive nations in the world" has received virtually no coverage from major American television news outlets during their evening newscasts and opinion programming. The parent companies of most of these networks, as well as two of the networks themselves, are listed as official "supporters" of this legislation on the U.S. House of Representatives' website.

Congress vs. The Internet

2011-12-20T05:00:00.000-05:00

It is just sad that in this day and age, our elected officials have no idea how the internet works nor do they wish to speak to people who do.

Dear Congress, It's No Longer OK To Not Know How The Internet Works

Project Euler-Problem 21

2011-05-13T12:00:00.001-04:00

Description

From Project Euler:

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

This problem is best broken down into steps. The first thing we need is an easy way to get the proper divisors of a number.

def divisors(n)
  return [] if n <=1
  limit = Math.sqrt(n).floor
  (2..limit).select { |d| n % d == 0 }.inject([1]) do |result,d|
    result << n << n / d
  end.uniq
end

This method is fairly complex for a change, so we’ll break it down. First, we exit fast with an empty set if the number is less than or equal to one. Notice that since a proper divisor must be less than the number, one has no proper divisors.

Next, we figure out what the square root of the number n is. This gives us a good cutoff, since if we add the divisors in pairs, by the time we reach limit we will already have added all the values greater than limit. With this number in hand, we can iterate through the entire range from 2 to limit and select only the numbers that divide evenly into n.

We will create an array by beginning with [1] (remember, n is not a proper divisor of itself, so 1 has no pair and must be added manually). We then proceed to add each divisor to result in pairs, the current divisor and it’s matching dividend above limit.

There is one more thing we have to take into account. If n is a perfect square, then it will have a divisor equal to limit. This divisor will actually be added twice (once as a divisor and once as a dividend). There is a number of ways we could correct this, but I found it easiest to just ask Ruby to return the unique results.

The next method we will need is to test if a number is amicable or not. For this, I've decided to implement a method that will return the other amicable number in a pair, or nil if no such number exists.

# extracted summing proper divisors
def dsum(n)
  divisors(n).reduce(0, :+)
end

def amicable_pair(n)
  pair = dsum(n)
  pair if dsum(pair) == n and pair != n
end

The last thing to do is find all of the amicable numbers from 1 to 10,000. We can use the fact that select will treat nil as false when querying an Enumerable and just call amicable_pair on each value. Then just sum up the results and we are done.

(1..10_000).select { |n| amicable_pair(n) }.reduce(0, :+)

The full source and specifications can be seen on github. Next time, what is the total of all the name scores in a given file of first names?

Project Euler-Problem 20

2011-05-11T12:00:00.000-04:00

Description

From Project Euler:

n! means n x (n - 1) x ... x 3 x 2 x 1

For example, 10! = 10 x 9 x ... x 3 x 2 x 1 = 3628800,
and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.

Find the sum of the digits in the number 100!

Solution

The first thing that we need to solve this problem is a quick method for computing factorials. Since Ruby supports arbitrary precision integers, computing 100! will not be too big of a task.

class ::Integer
  def fact
    (1..self).reduce(1, :*)
  end
end

We will also need our digits method from back in Problem 8. With these two things together, we can put together a fairly trivial solution.

100.fact.digits.reduce(0, :+)

The full source and specifications can be seen on github. Next time, evaluating the sum of all amicable pairs under 10,000.

Project Euler-Problem 19

2011-05-08T22:49:00.001-04:00

Description

From Project Euler:

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

Most modern languages (Ruby included) have decent basic date support baked in. In our case, Ruby makes it easy to check what day of the week a given date falls on through the use of the sunday? through saturday? methods. So all we really have to do here is iterate through the 1,200 months (12 months/year * 100 years) and check the first of each month:

(1..12).to_a.product((1901..2000).to_a).count { |month,year| Time.new(year,month,1).sunday? }

Another simple solution provided by the power of Ruby. One thing I would have liked to see, though, was the product method on the Range class. Or even better, having the * operator as an alias to the product method. This can be achieved easily enough, though:

class ::Range
  def product(other)
    self.to_a.product(other.to_a)
  end
  alias :* :product
end

((1..12) * (1901..2000)).count { |month,year| Time.new(year,month,1).sunday?}

The full source and specifications can be seen on github. Next time, finding the sum of digits in 100!

Project Euler-Problems 18 & 67

2011-03-31T11:35:00.001-04:00

Description

From Project Euler:

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 of the triangle below:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

Solution

As the note in the problem statement mentions, this problem is pretty easy to brute force by simply adding together every possible path. We will assume the triangle is stored as an array of arrays, like so:

class Problem018 
  TRIANGLE = [ [75],
               [95,64],
               [17,47,82],
               [18,35,87,10],

               # additional rows

               [4,62,98,27,23,9,70,98,73,93,38,53,60,4,23]
             ]
end

Now we can build a method that recursively evaluates the “top” of the triangle, plus the two smaller sub-triangles underneath it:

module TriangleSolver
  def add_triangle(triangle, row = 0, col = 0)
    return 0 if row >= triangle.length
    return triangle[row][col] if row == triangle.length - 1
    
    left = add_triangle(triangle, row + 1, col)  # compute the maximal sum of the left sub-triangle
    right = add_triangle(triangle, row + 1, col + 1) # compute the maximal sum of the right sub-triangle

    triangle[row][col] + (left + right ? left : right)
  end
end

Notice that here I’ve used a module because we will be making use of this solution for problem 67 as well. This works well for this problem since there are relatively few paths to compute. But as the triangle gets larger this will become too slow to be able to solve. However, we can greatly improve the number of paths that have to actually be computed.

The first step towards this goal is to realize that each sub-triangle (except the ones on the very edge) get reused. How? Take a look at the original (smaller) example triangle. The triangle 4-5-9 is both the right sub-triangle of the 7 in the second row and it is the left sub-triangle of the 4 in the second row. In our current implementation, we would compute the maximal sum of this sub-triangle both times, but we really only need to compute it once and then reuse that result. So, with some judicious use of memoization, we can actually reduce the number of triangle computations by a large degree!

module TriangleSolver
  def initialize
    @cache = {}
  end

  def add_triangle(triangle, row = 0, col = 0)
    return 0 if row >= triangle.length
    return triangle[row][col] if row == triangle.length - 1
    return @cache[row][col] if @cache.include? row and @cache[row].include? col
    
    left = add_triangle(triangle, row + 1, col)  # compute the maximal sum of the left sub-triangle
    right = add_triangle(triangle, row + 1, col + 1) # compute the maximal sum of the right sub-triangle

    @cache[row] ||= {}
    @cache[row][col] = triangle[row][col] + (left + right ? left : right)
  end
end

With this change, our solution is much more efficient for larger triangles. How can we test that fact? Well, problem 67 is the same exact problem, just a much larger triangle. Here is the description of from Project Euler:

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.

NOTE: This is a much more difficult version of Problem 18. It is not possible to try every route to solve this problem, as there are 2⁹⁹ altogether! If you could check one trillion (10¹²) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)

So to test our solution against this much larger triangle, all we need is a method to load the triangle from disk.

class Problem067
  include TriangleSolver

  def load_file
    File.open('triangle.txt') do |file|
      file.readlines.map { |line| line.split(' ').map { |num| num.to_i } }
    end
  end
end

And now when we run problem 67, we can see that indeed, our memoization technique is a success. We can find the maximal sum of a triangle with 100 rows in less than one second. I dare say that is a lot better than twenty billion years!

The full source and specifications for problem 18 can be seen on github. You can also see the source and specs for the TriangleSolver as well as problem 67. Next time, how many Sundays fell on the first of the month during the twentieth century?

Project Euler-Problem 17

2011-03-28T23:35:00.001-04:00

Description

From Project Euler:

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

Disclaimer: This problem is one of several that went through several iterations, and I’m still not completely happy with it.However, it works, and produces a result in less than one second, so good enough I guess.

This problem is fairly straight-forward. Simply iterate through all the numbers from one to one thousand and count up the letters. The only real trick is how you figure out how many letters are in each word. So for this problem, lets do something a little different and look at what the end result will be:

(1..1000).reduce(0) { |sum, n| sum + letters_for(n) }

Pretty simple stuff. All we need to do now is define the letters_for method and we're done.

There are only a few actual words used in generating the text representations of the number from one to one thousand. Namely, each of the numbers from one to twenty has its own name. From there each group of ten numbers is just a new word by itself or hyphenated with one of the numbers from one to nine. This keeps going until we get to one hundred, which introduces another new word. And finally, one thousand introduces one more word.

Now that we know we only have a few actual words we need to keep track of, I just stuffed all of those lengths into a hash for easy lookup.

class Problem017
  LETTERS = {
    1 => 3, 2 => 3, 3 => 5, 4 => 4, 5 => 4, 6 => 3, 7 => 5, 8 => 5, 9 => 4, 10 => 3,
    11 => 6, 12 => 6, 13 => 8, 14 => 8, 15 => 7, 16 => 7, 17 => 9, 18 => 8, 19 => 8,
    20 => 6, 30 => 6, 40 => 5, 50 => 5, 60 => 5, 70 => 7, 80 => 6, 90 => 6, 
    100 => 7, 1000 => 8, 0 => 0
  }
end

The last piece is to implement our letters_for method by just adding up the pieces of the text by looking them up in the hash. This is the part I am not very happy with and may change in the future. It just seems very procedural and not very Ruby-esque.

class Problem017
  def letters_for(n)
    sum = 0
    sum += LETTERS[n / 1000] + LETTERS[1000] and n %= 1000 if n >= 1000
    sum += LETTERS[n / 100] + LETTERS[100] and n %= 100 if n >= 100
    sum += AND if sum > 0 and n > 0
    sum += LETTERS[n - n%10] + LETTERS[n%10] and n = 0 if n >= 20
    sum += LETTERS[n]
  end
end

As you can see, we just add however many “thousands” there are, plus the word “thousand”. Then we do the same for “hundred”. Then there is a small piece that adds the “and” between the hundreds and the tens/ones if both are present.¹ Finally, we add in a possibly hyphenated word for the numbers twenty to ninety-nine, or if the number is less then twenty, we add the proper word.

Notice that I’ve included zero as having no letters here. This is so that the addition for the hyphenated words works out correctly. For instance:

# The last two lines for 30
sum += 30 + 0 and n = 0 
sum += 0

# The last two lines for 31
sum += 30 + 1 and n = 0
sum += 0

The full source and specifications can be seen on github. Next time, finding the maximum sum travelling from the top of the triangle to the base.

¹This part is a little weird since in the United States, it is incorrect to include the and, but in certain European countries it is required. As the problem states it is looking for the British version, we need to add this in.

Project Euler-Problem 16

2011-03-14T01:00:00.001-04:00

Description

From Project Euler:

2¹⁵ = 32,768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2¹⁰⁰⁰?

Solution

This is another one of those problems that Ruby makes so easy by having a built-in arbitrary precision integer. Also, remember that back in problem 8 we created a method on Integer that will return an array with the digits of an integer. Putting these two elements together, we come to the very simple solution:

(2**1000).digits.reduce(:+)

The full source and specifications can be seen on github. Next time, how many letters would be needed to write all the numbers in words from 1 to 1000?

Project Euler-Problem 15

2011-03-13T12:15:00.001-04:00

Description

From Project Euler:

Starting in the top left corner of a 2x2 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 20x20 grid?

Solution

In order find the number of paths that can be taken, we must first observe that we are going to move right 20 times and down 20 times in any valid solution. So our initial answer might be that we simply have to find how many ways we can rearrange 20 rights and 20 downs. Well, the number of possible orderings of 40 elements is 40!. So we might write something like:

class Problem015
  class ::Integer
    def fact
      (1..self).reduce(1, :*)
    end
  end
end

40.fact

There is a problem with this solution, however. What happens if we swap a move down with a move down? We get the exact same ordering of moves. Now, since there are 20 moves down, there are 20! possible ways you can swap a down move with another down move. Similarly there are 20! ways we can swap a right move with another right move. So we need to remove these possibilities from the total number of orderings. So we get:

40.fact / (20.fact * 20.fact)

Now we can generalize this a little bit for any grid mxn.

class Problem015
  def paths_for_grid(m,n)
    (m+n).fact / (m.fact * n.fact)
  end
end

Problem015.new.paths_for_grid(20,20)

The full source and specifications can be seen on github. Next time, what is the sum of the digits of the number 2¹⁰⁰⁰?

Project Euler-Problem 14

2011-03-10T22:40:00.001-05:00

Description

From Project Euler:

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

The relatively straight-forward solution to this problem is to simply create an Enumerator that will generate the appropriate sequence from a given starting point. We can then generate all of the sequences that start with numbers up to one million and find the longest one.

class Problem014
  def sequence(start)
    Enumerator.new do |yielder|
      n = start
      (yielder << n) && (n = n.even ? n / 2 : 3*n + 1) while n > 1
      yielder << 1
    end
  end

  def chain_lengths
    Enumerator.new do |yielder|
      start
      yielder << [start, sequence(start).count] && start += 1 while start < 1_000_000
    end
  end
end

Problem014.new.chain_lengths.max_by { |start,length| length }[0]

There is one glaring problem with this solution though. We are computing sequences hundreds of times over. Take for example a sequence starting with the number 26:

26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

Notice that this contains the entire sequence that starts with 13. Therefore, the length of the sequence is just the length of the sequence for 13 plus one. Similarly, the length of sequence 13 is just the length of sequence 40 plus one. And so on and so forth. So with a little memoization, we can actually reuse the sequence lengths we have already computed.

class Problem014
  def initialize
    @known_lengths = { 1 => 1 }
  end

  def sequence(n)
    n.even? ? n / 2 : 3*n + 1
  end

  def chain_length(start)
    return @known_lengths[start] if @known_lengths.include? start
    @known_lengths[start] = chain_length(sequence(start)) + 1
  end

  def chain_lengths
    Enumerator.new do |yielder|
      start = 2
      yielder << [start, chain_length(start)] && start += 1 while start < 1_000_000
    end
  end
end

Notice that now the sequence method only returns the next value in the chain. That is all that is necessary for us to look up and see if we already know that length. The chain_length method will then return a pre-computed length if we already know it, or the chain_length of the next value in the chain plus one. In addition, we will also store this length in case it is needed again for another sequence. Does all of this complication actually help? Well on my system I was able to go from 83s for the original algorithm down to 12s for the memoized version. Well worth the effort I think.

The full source and specifications can be seen on github. Next time, starting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner?

Project Euler-Problem 13

2011-03-10T15:52:00.001-05:00

Description

From Project Euler:

Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.

37107287533902102798797998220837590246510135740250
46376937677490009712648124896970078050417018260538
74324986199524741059474233309513058123726617309629
91942213363574161572522430563301811072406154908250
23067588207539346171171980310421047513778063246676
89261670696623633820136378418383684178734361726757
28112879812849979408065481931592621691275889832738
44274228917432520321923589422876796487670272189318
47451445736001306439091167216856844588711603153276
70386486105843025439939619828917593665686757934951
62176457141856560629502157223196586755079324193331
64906352462741904929101432445813822663347944758178
92575867718337217661963751590579239728245598838407
58203565325359399008402633568948830189458628227828
80181199384826282014278194139940567587151170094390
35398664372827112653829987240784473053190104293586
86515506006295864861532075273371959191420517255829
71693888707715466499115593487603532921714970056938
54370070576826684624621495650076471787294438377604
53282654108756828443191190634694037855217779295145
36123272525000296071075082563815656710885258350721
45876576172410976447339110607218265236877223636045
17423706905851860660448207621209813287860733969412
81142660418086830619328460811191061556940512689692
51934325451728388641918047049293215058642563049483
62467221648435076201727918039944693004732956340691
15732444386908125794514089057706229429197107928209
55037687525678773091862540744969844508330393682126
18336384825330154686196124348767681297534375946515
80386287592878490201521685554828717201219257766954
78182833757993103614740356856449095527097864797581
16726320100436897842553539920931837441497806860984
48403098129077791799088218795327364475675590848030
87086987551392711854517078544161852424320693150332
59959406895756536782107074926966537676326235447210
69793950679652694742597709739166693763042633987085
41052684708299085211399427365734116182760315001271
65378607361501080857009149939512557028198746004375
35829035317434717326932123578154982629742552737307
94953759765105305946966067683156574377167401875275
88902802571733229619176668713819931811048770190271
25267680276078003013678680992525463401061632866526
36270218540497705585629946580636237993140746255962
24074486908231174977792365466257246923322810917141
91430288197103288597806669760892938638285025333403
34413065578016127815921815005561868836468420090470
23053081172816430487623791969842487255036638784583
11487696932154902810424020138335124462181441773470
63783299490636259666498587618221225225512486764533
67720186971698544312419572409913959008952310058822
95548255300263520781532296796249481641953868218774
76085327132285723110424803456124867697064507995236
37774242535411291684276865538926205024910326572967
23701913275725675285653248258265463092207058596522
29798860272258331913126375147341994889534765745501
18495701454879288984856827726077713721403798879715
38298203783031473527721580348144513491373226651381
34829543829199918180278916522431027392251122869539
40957953066405232632538044100059654939159879593635
29746152185502371307642255121183693803580388584903
41698116222072977186158236678424689157993532961922
62467957194401269043877107275048102390895523597457
23189706772547915061505504953922979530901129967519
86188088225875314529584099251203829009407770775672
11306739708304724483816533873502340845647058077308
82959174767140363198008187129011875491310547126581
97623331044818386269515456334926366572897563400500
42846280183517070527831839425882145521227251250327
55121603546981200581762165212827652751691296897789
32238195734329339946437501907836945765883352399886
75506164965184775180738168837861091527357929701337
62177842752192623401942399639168044983993173312731
32924185707147349566916674687634660915035914677504
99518671430235219628894890102423325116913619626622
73267460800591547471830798392868535206946944540724
76841822524674417161514036427982273348055556214818
97142617910342598647204516893989422179826088076852
87783646182799346313767754307809363333018982642090
10848802521674670883215120185883543223812876952786
71329612474782464538636993009049310363619763878039
62184073572399794223406235393808339651327408011116
66627891981488087797941876876144230030984490851411
60661826293682836764744779239180335110989069790714
85786944089552990653640447425576083659976645795096
66024396409905389607120198219976047599490197230297
64913982680032973156037120041377903785566085089252
16730939319872750275468906903707539413042652315011
94809377245048795150954100921645863754710598436791
78639167021187492431995700641917969777599028300699
15368713711936614952811305876380278410754449733078
40789923115535562561142322423255033685442488917353
44889911501440648020369068063960672322193204149535
41503128880339536053299340368006977710650566631954
81234880673210146739058568557934581403627822703280
82616570773948327592232845941706525094512325230608
22918802058777319719839450180888072429661980811197
77158542502016545090413245809786882778948721859617
72107838435069186155435662884062257473692284509516
20849603980134001723930671666823555245252804609722
53503534226472524250874054075591789781264330331690

Solution

This problem is actually exceptionally easy in Ruby because of the Bignum built-in type. Because Bignum allows arithmetic on arbitrary precision integers, we can simply add the numbers together and pull off the first ten digits:

class Problem013
  
  NUMBERS = [37107287533902102798797998220837590246510135740250,
             46376937677490009712648124896970078050417018260538,
             74324986199524741059474233309513058123726617309629,
             91942213363574161572522430563301811072406154908250,
             ...
             77158542502016545090413245809786882778948721859617,
             72107838435069186155435662884062257473692284509516,
             20849603980134001723930671666823555245252804609722,
             53503534226472524250874054075591789781264330331690]
end

Problem013::NUMBERS.reduce(:+).to_s.slice(0..9).to_i

The full source and specifications can be seen on github. Next time, find the longest sequence using a starting number under one million..

Project Euler-Problem 12

2011-03-09T18:08:00.001-05:00

Description

From Project Euler:

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

There are two basic parts of this problem that we need to be concerned with. The first is generating the sequence of triangle numbers, and the second is counting how many divisors a given number has.

The first part is relatively trivial. We will just create an Enumerable that returns the proper sequence of numbers:

class Problem012
  include Enumerable

  def each
    counter = 1; result = 1
    while true
      yield result
      result += (counter += 1)
    end
  end
end

The next part of the problem is to count the number of divisors for a given number. Note that we don't actually need to compute the divisors, just count how many there are. The first observation that we can make is that the number of divisors will always be even except for the case of a perfect square. Why? Because if the number n is evenly divisible by a number d (and hence it is a divisor), then it is also divisible by n/d. So in finding divisor d, we have also found n/d. For perfect squares, however, this rule works until you reach the square root of n. In that case d = n/d, so there is only one divisor. In addition, we also know that every number greater than one will have at least two divisors - one and itself. Given all of this, we come up with:

class Integer
  def divisor_count
    return 1 if self == 1
    limit = Math.sqrt(self)
    (2..limit).inject(limit == limit.floor ? 1 : 2) do |count,d|
      count + (self % d == 0 ? 2 : 0)
    end
  end
end

We are now in a position to find the first triangle number with greater than 500 divisors:

Problem012.new.find { |n| n.divisor_count > 500 }

The full source and specifications can be seen on github. Next time, finding the first ten digits of the sum of one-hundred 50-digit numbers.

Project Euler-Problem 11

2011-03-08T08:36:00.002-05:00

Description

From Project Euler:

In the 20x20 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 = 1,788,696.

What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 20x20 grid?

Solution

This is another one of those problems that is just very easy to brute force. We simply create a two dimensional array that will represent our grid.

class Problem011
  GRID = [[ 8, 2,22,97,38,15, 0,40, 0,75, 4, 5, 7,78,52,12,50,77,91, 8],
          [49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48, 4,56,62, 0],
          [81,49,31,73,55,79,14,29,93,71,40,67,53,88,30, 3,49,13,36,65],
          [52,70,95,23, 4,60,11,42,69,24,68,56, 1,32,56,71,37, 2,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, 3,45, 2,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, 2,62,12,20,95,63,94,39,63, 8,40,91,66,49,94,21],
          [24,55,58, 5,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72],
          [21,36,23, 9,75, 0,76,44,20,45,35,14, 0,61,33,97,34,31,33,95],
          [78,17,53,28,22,75,31,67,15,94, 3,80, 4,62,16,14, 9,53,56,92],
          [16,39, 5,42,96,35,31,47,55,58,88,24, 0,17,54,24,36,29,85,57],
          [86,56, 0,48,35,71,89, 7, 5,44,44,37,44,60,21,58,51,54,17,58],
          [19,80,81,68, 5,94,47,69,28,73,92,13,86,52,17,77, 4,89,55,40],
          [ 4,52, 8,83,97,35,99,16, 7,97,57,32,16,26,26,79,33,27,98,66],
          [88,36,68,87,57,62,20,72, 3,46,33,67,46,55,12,32,63,93,53,69],
          [ 4,42,16,73,38,25,39,11,24,94,72,18, 8,46,29,32,40,62,76,36],
          [20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74, 4,36,16],
          [20,73,35,29,78,31,90, 1,74,31,49,71,48,86,81,16,23,57, 5,54],
          [ 1,70,54,71,83,51,54,69,16,92,33,48,61,43,52, 1,89,19,67,48]]
end

We then generate all of the vertical, horizontal, and diagonal lines containing four numbers from the grid.

class Problem011
  def get_lines
    result = []

    GRID.length.times do |i|
      (GRID.length - 3).times do |j|
        result << [GRID[i][j + 0],
                   GRID[i][j + 1],
                   GRID[i][j + 2],
                   GRID[i][j + 3]]
        result << [GRID[j + 0][i],
                   GRID[j + 1][i],
                   GRID[j + 2][i],
                   GRID[j + 3][i]]
      end
    end

    (GRID.length - 3).times do |i|
      (GRID.length - 3).times do |j|
        result << [GRID[i + 0][j + 0],
                   GRID[i + 1][j + 1],
                   GRID[i + 2][j + 2],
                   GRID[i + 3][j + 3]]
        result << [GRID[i + 0][GRID.length - j - 1],
                   GRID[i + 1][GRID.length - j - 2],
                   GRID[i + 2][GRID.length - j - 3],
                   GRID[i + 3][GRID.length - j - 4]]
      end
    end

    return result
  end
end

Finally we find the products of each of those four number combinations and get the largest one.

Problem011.new.get_lines.map { |ary| ary.reduce(1, :*) }.max

The full source and specifications can be seen on github. Next time, finding the first triangle number with over five hundred divisors.

Project Euler-Problem 10

2011-03-05T13:00:00.015-05:00

Description

From Project Euler:

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

Solution

As you'll recall, back in problem 7 we created a general purpose prime number generator. That is going to come in extremely handy for this problem. Why? Well, the solution is as easy as:

PrimeGenerator.new.take_while { |p| p < 2_000_000 }.reduce(:+)

And that is all there is to it. Now wasn't that simple?

The full source and specifications can be seen on github. Next time, finding the greatest product of four numbers on the same line in a 20x20 grid.

Project Euler-Problem 9

2011-03-05T00:01:00.105-05:00

Description

From Project Euler:

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

a² + b² = c²
For example, 3² + 4² = 9 + 16 = 25 = 5².
There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

Solution

Creating all of the Pythagorean triplets can be done in one of two ways. The first is to simply pick arbitrary values for a and b and then compute the value of c. Using this tactic we can see that the following would hold true:

if a = 0 (which will maximize b in this equation, then
a² + b² = c²
b² = c²
b = c

and

a + b + c = 1000
2b = 1000
b = 500

Since a must be greater than 0, we can deduce that b must be less than 500. This means we need to search all of the pairs such that 1 <= a <= b < 500. Thankfully, there is a much easier solution. The astute reader may have noticed that a large number of the triplets (the vast majority in fact) will generate values of c that are irrational. Since we are only concerned with values of c that are natural numbers, there is an easy way to cut down the problem space.

The answer here is Euclid's formula for Pythagorean triples. This formula states that given an arbitrary pair of positive integers m and n such that m > n, a Pythagorean triple exists given by the equations:

a = m² - n² b = 2mn c = m² + n²

Given these equations, we can easily work out what the range of m and n are that we need to search to find our answer.

a + b + c = 1000
m² - n² + 2mn + m² + n² = 1000
2m² + 2mn = 1000
if n = 0 (which will maximize m in this equation), then
2m² = 1000
m² = 500
m = 22.360...

Since m and n must be positive integers, we know that the range we need to search is 1 <= n < m < 23. This is a much smaller search space than our first attempt.
With all of this theory out of the way, lets take a look at some code.

class Problem009
  def find_triplet
    max = Math.sqrt(500).floor
    2.upto(max) do |m|
      1.upto(m-1) do |n|
        a = m**2 - n**2
        b = 2*m*n
        c = m**2 + n**2
        return [a, b, c] if a + b + c == 1000
      end
    end
  end
end
Problem009.new.find_triplet.reduce(1, :*)

The full source and specifications can be seen on github. Next time, computing the sum of all prime numbers less than 2 million.

Project Euler–Problem 8

2011-02-23T12:18:00.003-05:00

Description

From Project Euler:

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

This problem is another one that is very easy to brute force, especially since Ruby has some nice built-in methods that make it a no brainer. One thing we will need is an easy way to take a number and break it up into it’s digits. For that a simple method added to the Integer class will do.

class Integer
 def digits
  self.to_s.split('').map { |s| s.to_i }
 end
end

This method doesn’t do much, it converts the number to a string, splits it into individual characters, then converts the characters back into integers. Again, simple, but this method will come in handy for this problem as well as several in the future.
The first thing we need to find is all the combinations of 5 consecutive digits. We can make use of the Enumerable#each_cons method to accomplish this.

class Problem008
 def partition(number)
  number.digits.each_cons(5)
 end
end

This will give us an enumerator that contains arrays of 5 consecutive digits. We can now map each of these arrays to the product of their values.

class Problem008
 def products(number)
  partition(number).map { |a| a.reduce(1, :*) }
 end
end

And the final step, just find the largest product.

THOUSAND_DIGIT_NUM = # number from problem statement
products(THOUSAND_DIGIT_NUM).max

# This could have been written all in one line as
THOUSAND_DIGIT_NUM.digits.each_cons(5).map { |a| a.reduce(1, :*) }.max

The full source and specifications can be seen on github. Next time, finding the only Pythagorean triplet, {a, b, c} for which a + b + c = 1000.

Project Euler–Problem 7

2011-02-22T12:33:00.002-05:00

Description

From Project Euler:

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

Finding primes is an interesting problem. There are a number of ways that we can go about doing so, and it is something we will need to do several times throughout the Project Euler problems. So we will want to develop a solution that is not only accurate, but also fairly efficient.
A fairly efficient method for finding all of the prime numbers below a given value is the Sieve of Eratosthenes. The way it works is simple:

Create a list of consecutive integers from two to n: (2, 3, 4, …, n)
Start with p = 2, the first prime number.
Remove from the list all multiples of p less than or equal to n.
Find the smallest number remaining on the list greater than p. This is the next prime number. Set p equal to this number.
Repeat this process until p² is greater than n.
All remaining numbers on the list are prime.

This works extremely well if you know what your upper bound is going to be. While we could take a guess and generate all the primes up to some arbitrarily large number, we would like a way of using this method to generate any arbitrary number of primes. This can still be done if we take into account the following facts:

If we want an arbitrary limit, there is no n value, so we cannot stop striking composite numbers as in step 5 above.
Since we have no upper bound, striking all of the multiples of p would be impossible (there are infinitely many). So we will only strike the next multiple and worry about the larger ones when we get to them.
There is insufficient memory to store a list of all numbers (obviously), so we will ignore all primes that have already been yielded and all composites that have already been stricken. Thus we will only store a list of composites that will need to be stricken when we reach them.

This last observation is the real trick. Instead of keeping a list of prime candidates, we’ll keep a list of known composites to strike. We’ll also need to know what primes that composite is a multiple of in order to know what the next multiples of each will be. For instance, 12 is a multiple of both 2 and 3. This means that it would be stricken by both in the original sieve algorithm. We would need to know this so that we can see that the next multiple of 2 will be 14 and the next multiple of 3 will be 15.
One final note before we start implementing our algorithm. When we reach a prime number p, we do not need to strike the first p-1 multiples of p. This is because those multiples will be a multiple of another prime as well. This can easily be seen with an example:

Given the prime number p = 11
2p = 22 which is a multiple of 2
3p = 33 which is a multiple of 3
4p = 2*2p = 44 which is a multiple of 2
5p = 55 which is a multiple of 5
6p = 2*3p = 66 which is a multiple of both 2 and 3
7p = 77 which is a multiple of 7
8p = 2*2*2p = 88 which is a multiple of 2
9p = 3*3p = 99which is a multiple of 3
10p = 5*2p = 110 which is a multiple of both 2 and 5
11p = 121 which is only a multiple of 11.

Therefore, when we find a prime p, the first composite we need to concern ourselves with is p².

class PrimeGenerator
 include Enumerable

 def each
  composites = {}
  n = 2
  while true
   if composites.has_key?(n)
    factors = composites.delete(n)
    factors.each { |factor| composites.merge!(n + factor => [factor]) { |key,left,right| left + right } }
   else
    composites.merge!(n**2 => [n]) { |key,left,right| left + right }
    yield n
   end
   n += 1
  end
 end
end

With this class in place, finding the 10,001st prime is as simple as:

PrimeGenerator.new.take(10001).drop(10000).first

The full source and specifications can be seen on github. Next time, discovering the largest product of five consecutive digits in a 1000-digit number.

Project Euler–Problem 6

2011-02-19T23:52:00.003-05:00

Description

From Project Euler:

The sum of the squares of the first ten natural numbers is,
1² + 2² + ... + 10² = 385
The square of the sum of the first ten natural numbers is,
(1 + 2 + ... + 10)² = 55² = 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

The straight forward solution to this problem is just to loop through the numbers from 1 to 100 and compute both the square of the sum and the sum of the squares.

class Problem006
 def sum_of_squares(n)
  (1..n).map { |n| n**2 }.reduce(:+)
 end

 def square_of_sum(n)
  (1..n).reduce(:+) ** 2
 end

 def difference(n)
  sum_of_squares(n) - square_of_sum(n)
 end
end

Problem006.new.difference(100)

Of course, this iterative solution works fine on such a small range, but starts to break down as the range gets larger. Fortunately, there is a simple formula for computing the sum of numbers 1 to n.
sum(n) = n x (n + 1) / 2
Using this information we can now calculate the square of the sum in constant time.

class Problem006
 def square_of_sum(n)
  (n * (n + 1) / 2) ** 2
 end
end

Similarly, there is a formula for calculating the sum of squares from 1 to n. The derivation of which can be found here.
sum²(n) = (n x (n + 1) x (2n + 1)) / 6
So finally, we can optimize the sum of squares to also work in constant time. This gives us a fast solution regardless of the size of n.

class Problem006
 def sum_of_squares(n)
  ((2*n+1) * (n+1) * n) / 6
 end
end

The full source and specifications can be seen on github. Next time, finding the 10,001st prime number.

Project Euler–Problem 5

2011-02-18T08:33:00.003-05:00

Description

From Project Euler:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Solution

Another name for the smallest number that is evenly divisible by two or more numbers is the least common multiple (LCM). In general, finding the least common multiple is an easy task if we make the following observation. All numbers greater than 1 can be expressed uniquely as the product of its prime factors.
10 => 2, 5 => 2 x 5
In addition, each prime factor may have an exponent greater than one.
90 => 2, 3, 3, 5 => 2¹ x 3² x 5¹
To find the least common multiple of two or more numbers, you take the prime factorization of each number, than multiply the highest exponent of each prime together. This gives the least common multiple. (For more information on how this works, see this Wikipedia article).
8 => 2, 2, 2 => 2³
18 => 2, 3, 3 => 2¹ x 3² 84 => 2, 2, 3, 7 => 2² x 3¹ x 7¹
lcm(8, 9, 21) => 2³ x 3² x 7¹ => 504
We already created a method that can compute the prime factors for us in problem 3. However, now, we don’t want to simply list them, we want to list the factors exactly once with their associated exponent. To do this, we’ll change the prime_factors method to instead return a hash. The keys of the hash will be the prime factors, and the values will be the exponent.

class Integer
 def prime_factors
  prime = 2
  result = {}
  value = self
  while value >= prime ** 2
   if value % prime == 0
    result.merge!(prime => 0) if not result.has_key?(prime)
    result[prime] += 1
    value /= prime
   else
    prime += 1
   end
  end
  result.merge!(value => 0) if not result.has_key?(value)
  result[value] += 1
  return result
 end
end

Note that this does force us to change the solution to problem 3:

600_851_475_143.prime_factors.keys.max

Only a minor change, we are now calling keys on prime_factors before calling max.
Now the method for computing the least common multiple becomes trivial:

class Problem005
 def lcm(*numbers)
  factors = {}
  numbers.each do |n|
   factors.merge!(n.prime_factors) do |key,x,y|
    x > y : x : y
   end
  end
  factors.inject(1) { |product,pair| product * (pair[0] ** pair[1]) }
 end
end
Problem005.new.lcm 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

The only thing to note here is that we are overriding the merge! methods logic. Instead of overwriting the current value of the hash with the new one, we always add the larger number to the hash. Thus, { 5 => 2}.merge( 5 => 1) would result in { 5 => 2 } instead of { 5 => 1 }.
The full source and specifications can be seen on github. Next time, the difference between the sum of squares and the square of sums.

Project Euler–Problem 4

2011-02-17T11:06:00.003-05:00

Description

From Project Euler:

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

There are two parts to the solution to problem 4. The first part is to generate all the multiples of 3-digit numbers. This is relatively trivial. All we need to do multiple all the combinations of numbers from 100 to 999. The only obvious optimization here is to recognize that 100 * 999 is the same as 999 * 100. So we really only have to compute one of the two.

class Problem004
 def multiples(range)
  Enumerator.new do |yielder|
   range.each do |i|
    (range.first..i).each do |j|
     yielder << i * j
    end
   end
  end
 end
end

Here I’ve used an Enumerator. It simply loops through all the numbers in a range and multiplies those values by all the numbers in the range less than that number. Each time, it yields these values.
The second part of the problem is to determine whether a number is a palindrome or not. This too is straight forward. All we need to do is compare whether the number is equal to its reverse. Since numbers do not have a reverse method, we’ll have to convert it to a string first.

class Integer
 def palindrome?
  text = self.to_s
  text == text.reverse
 end
end

With all of this in place, finding the largest palindrome is as easy as:

Problem004.new.multiples(100..999).select { |x| x.palindrome? }.max

The full source and specifications can be seen on github. Next time, finding the smallest number divisible by each of the number 1 through 20.

Project Euler–Problem 3

2011-02-16T19:46:00.003-05:00

Description

From Project Euler:

The prime factors of 13,195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600,851,475,143?

Solution

The solution to this problem actually involves solving another problem that we’ll need later. Namely: computing the prime factors of a number. For this we’ll actual extend the Integer class to include a prime_factors method. This method will return an array that contains all of the prime factors for the current number. The solution will then be to simply find the largest value in the array.

class Integer
 def prime_factors
  prime = 2
  result = []
  value = self
  while value >= prime ** 2
   if value % prime == 0
    result << prime
    value /= prime
   else
    prime += 1
   end
  end
  result << value
 end
end
600_851_475_143.prime_factors.max

There are a number of optimizations that we can eventually make to this method, but we’ll hold off until we actually need the pieces necessary to improve it. One such piece will come in problem five.
The full source and specifications can be seen on github. Next time, finding the largest palindrome made from the product of two 3-digit numbers.

Project Euler–Problem 2

2011-02-16T14:37:00.003-05:00

Description

From Project Euler:

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.

Solution

The solution to this problem again has a trivial solution and a slight optimization. The trivial solution simply involves creating a method to calculate the Fibonacci sequence up to 4 million and a second method to add the even terms together.

class Problem002
 include Enumerable

 def each
  last = 1; current = 2
  yield last; yield current
  while true
   last, current = current, last + current
   yield current
  end
 end

 def sum_to(maximum)
  take_while { |n| n < maximum }.select { |n| n.even? }.inject { |sum,n| sum + n}
 end
end

Problem002.new.sum_to(4_000_000)

Notice that here I’ve used a mix-in to make the problem itself an enumerable collection of Fibonacci terms. However, we have a slight optimization we can make by observing two things.
First is that we don’t actually need to yield all of the terms of the Fibonacci sequence, only the even terms. Notice that the only way to get an even term is if the previous two terms are both even or both odd. If we start with 1 and 2 our next term will be odd because an odd plus an even is odd. The next term will be odd as well because we now have an even followed by an odd. The third term will be even since an odd plus an odd is even. For the fourth term we are back to an odd followed by an even. So we see that if we start with the second term (2), we only need to yield every third term in the sequence^.
Our second observation is regarding calculating the terms themselves. we can see that each term is specified by the previous two terms in the sequence:

n = (n-1) + (n-2)
n-1 = (n-2) + (n-3)

However, this means that we can also express each term by any previous two terms in the sequence. Reversing this, it means we can specify any future term by the current two terms. So we can come up with the following:

Given n and m (the term before n)
n+1 = n + m
n+2 = (n+1) + n = (n + m) + n = 2n + m
n+3 = (n+2) + (n+1) = (2n + m) + (n + m) = 3n + 2m

As you can see, term n+1 doesn’t ever need to be computed since we can express n+2 and n+3 in terms of n and m. This saves us computed 1/3 of all the values. So our new more optimal solution looks like this:

class Problem002
 include Enumerable

 def each
  current = 2
  last = 1
  while true
   yield current
   last, current = 2*current + last, 3*current + 2*last
  end
 end

 def sum_to(maximum)
  take_while { |n| n < maximum }.inject { |sum,n| sum + n }
 end
end
Problem002.new.sum_to(4_000_000)

As always, the source is available on github, both the full source and specifications. Next time, finding the largest prime factor of a composite number.

Project Euler–Problem 1

2011-02-02T10:18:00.003-05:00

In my constant effort to learn more, I’ve run into a number of road blocks with my progression with YABE. Why? Because I’m trying to write my blog engine in Ruby on Rails, while I have little real experience with Ruby, Rails, RSpec, Gems, etc. etc. So I am trying to rectify this by at least getting the basics of the “Ruby way” down. My solution? Well simple really. I am going to go through and start implementing the problems from Project Euler in Ruby and testing my solutions using RSpec. I’ve already completed a few of the problems, which you can see here.

Basic Structure

The project has a very simple structure. There is a batch file in the \bin folder that allows you to run a simple console with all of the problems I have completed. Selecting a problem will give the result and how many seconds it took to generate that result. Every problem will have a corresponding specification, and possibly a number of utility classes (which will have their own specifications in turn).

Problem #1

From the Project Euler website:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.

The trivial solution for this problem is actually quite easy. Simply loop through all of the number from 1 to 1000 (exclusive) and add all of the numbers that are divisible by 3 or 5. It might look something like this:

def sum
 (3...1000).inject do |sum,value|
  if value % 3 == 0 or value % 5 == 0
   sum + value
  else
   sum
  end
 end
end

Of course, I wasn’t satisfied with this solution, as there are two divisions going on for every value tested. And we are testing every value conceivable, even ones we can easily see will not be used. What if instead we were to only iterate through the multiples of 3 and 5, skipping all the other integers. We could then eliminate the division and the extra iterations.
How do we iterate over only the multiples of 3 and 5 though? Well, the first step is to notice that the multiples are spaced in a cyclical pattern. Take a look at this:

3	5	6	9	10	12	15	18
18	20	21	24	25	27	30	33
33	35	36	39	40	42	45	48
	+2	+1	+3	+1	+2	+3	+3

The cycle repeats itself every 6 values. So we can simply use this sequence to iterate over all of the multiples and just add all of the values less than 1000 together! Here is were it gets fun, we can use an Enumerable to handle the iteration of these values, and then use the standard Enumerable mixin methods to solve the problem, like so:

class Problem001
 include Enumerable
 ADD_VALUES = [2,1,3,1,2,3,3]  
 def each    
  n = 3    
  i = 0    
  while (true) do      
   yield n      
   n += ADD_VALUES[i]      
   i = (i + 1) % ADD_VALUES.length    
  end  
 end
 def sum(maximum)
  inject { |sum,value| break if value > maximum; sum + value; }
 end
end

You can see the full source and specification on github. Next time, we’ll take a look at problem #2: summing the even values of a Fibonacci sequence less than four million.