This post originated from an RSS feed registered with Ruby Buzz by Rick DeNatale. Original Post: Solving the Final Google Treasure Hunt Problem in Ruby Feed Title: Talk Like A Duck Feed URL: http://talklikeaduck.denhaven2.com/articles.atom Feed Description: Musings on Ruby, Rails, and other topics by an experienced object technologist. Latest Ruby Buzz Posts Latest Ruby Buzz Posts by Rick DeNatale Latest Posts From Talk Like A Duck

For each of the four questions, I wrote a Ruby program to find the answer.

The final question was probably the hardest, and although it’s still ‘alive’, the spoilers have already started to appear on the internets. Peter Krumins has posted a solution using unix shell commands, so I figured I’d show my Ruby solution

The Problem

As Peter describes the problem is to find the smallest prime number which can be expressed as a sum of several different numbers of consecutive primes. Here’s the question as Google posed it to me:

the sum of 3 consecutive prime numbers,

the sum of 5 consecutive prime numbers,

the sum of 275 consecutive prime numbers,

the sum of 1161 consecutive prime numbers,

and is itself a prime number.

For example, 41 is the smallest prime number that can be expressed as the sum of 3 consecutive primes (11 + 13 + 17 = 41) and the sum of 6 consecutive primes (2 + 3 + 5 + 7 + 11 + 13 = 41).

Note that I’ve got a different set of four numbers of consecutive primes than Peter’s

The Approach

I always try to do ‘the simplest thing that could possibly work.’ Like Peter I had no desire to write a prime number generator. A little googling found me the same source of prime numbers. I figured as a first guess that the answer would probably lie somewhere within the first million prime numbers, so I downloaded that list, and examined the list in Textmate.

As Peter notes, the file has two lines of header, and then several primes in sequence on each line. I just deleted the header lines in Textmate and then wrote a class which would read the file and return each prime number in sequence:

class PrimeReader
  def initialize(file)
    @file = file
    read_line
    yield self
  end

  def next
    read_line if @numbers.empty?
    @numbers.shift.to_i
  end

  def read_line
    @numbers = @file.readline.split(' ')
  end
end

This should be fairly explanatory. PrimeReader reads the file as necessary and hands out each prime number.

Now that I had a source of consecutive primes it was time to write the code to search for the answer. Here’s the outer loop:

processor = Processor.new

File.open("#{File.dirname(__FILE__)}/primes1.txt") do |f|
  PrimeReader.new(f) do | primes |
    until processor.test(primes.next)
    end
  end
end

The real work is done, in the unimaginatively named Processor. The loop reads lines from the PrimeReader until the processor finds the desired prime or end of file generates an exception.

And here’s the Processor class:

class Processor
  def initialize
    @counts = [3, 5, 275, 1167].reverse
    # @counts = [3,6]
    @sums = @counts.inject({}) { |hash, count| hash[count] = []; hash}
    @processed = []
  end

  def test(prime)
    puts "testing #{1+@processed.length}: #{prime} "
    qualifies(prime) || process(prime)
  end

  def qualifies(prime)
    @sums.each_value do | sums |
      return false unless sums.include?(prime)
    end
    report(prime)
    true
  end

  def process(prime)
    @processed << prime
    @counts.each do |count|
      calc_sum(count)
    end
    false
  end

  def calc_sum(count)
    if @processed.length >= count
      @sums[count] << @processed[-count,count].inject(0) { |sum, p| sum + p}
    end
  end

  def report(found)
    puts "Found #{found}"
    @counts.each do | count|
      report_sum(count, found)
    end
  end

  def report_sum(count, found)
    sums = @sums[count]
    sum_start = sums.index(found)
    puts "#{found} = #{@processed[sum_start, count].join(" + ")}"
  end
end

The approach I took was to compute the sums and save them in arrays which in turn are the values for each count used as a key in the hash @sums. I keep each prime in the array @processed which is used to calculate the sums.

I hard coded the parameters in the initialize method, note the commented out assignment to counts, by changing the commenting I could test the code against the example given and show that my code found 41 as the lowest prime expressible by both 3 and 6 consecutive primes.

The test method reports the number and value of each prime it examines, purely as a ‘progress indicator.’ The statment “qualifies(prime) || process(prime)” will return true if qualifies returns a truthy value, otherwise it will invoke process which always returns false.

The qualifies method returns true only if the array for each count contains the current prime, which is the essence of what we are seeking. Otherwise it returns false.

The process method first appends the new prime to @processed, then calculates the sum for each count using the calc_sum method. This method determines if we have enough primes in @processed to calculate the particular sum, and if so calculates the sum and appends it to the array for the count.

Once the answer has been found, the report method prints it and the sums which total to it. The sums are calculated in the report_sum method. This method takes a slice out of the @processed array, consisting of the count elements starting at the index where the answer is found in the particular sums array. A bit of reflection will reveal that this is precisely the primes which add to the answer.

In the case of my parameters, the answer, in case you are wondering is 5,181,901, which was confirmed by Google when I gave my answer. This is the 360,245th prime number by the way.

Performance

Although this might be a bit of a brute force approach, the performance was acceptable.

The biggest feature of Ruby which makes this approach feasible is the copy-on-write nature of Ruby arrays. In Ruby Array#slice (a.k.a. Array#[]) doesn’t copy the elements of the array, it just creates a new Array with an offset from the beginning of the original array and the length of the result. As long as neither Array is changed to affect one of the shared elements, nothing is copied, but when a shared element in the source or result array is changed, Ruby first does the copy to preserve the semantics.

My code does a lot of slicing of the @processed array, but other than appending to the end of the @processed array, the accesses to that array and the slices are read-only, so nothing needs to be copied.