I’ve taken ill for the last two days, so I’ve been working on a couple Project Euler problems in between trips to the bathroom.

Problem #27

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.

Since you start with n = 0, you know that b always has to be prime in order to satisfy n = 0.

Next, if b must be prime, and all primes greater than 2 are odd, and we don’t care about expressions resulting in less than 3 consecutive primes (example expression has 40), then we know that all values of a must be odd in order to satisfy n = 1!

I also suspect that for the number of consecutive primes we need to ‘win’, that we only need to look at negative values of a, but I’m having a heck of a time trying to prove it.

027.rb

require 'prime_generator'

# pre-calculate primes
MAX     = 1_000
primer  = Prime_Generator.new MAX
primes  = primer.stack
product = 0
highest = 0

# a must be odd
(0..MAX).each do |i| 
  next if i & 1 == 0

  # b must be prime
  primes.each do |b|
    
    # a can be positive or negative
    [i,-i].each do |a|
      n = 0
      while n += 1 do
        break unless primer.is_prime?(n ** 2 + a * n + b)
      end

      if highest < n
        highest = n
        product = a * b
      end

    end
  end
end

puts product

And here’s the prime generator I’m using:

prime_generator.rb

class Prime_Generator

  attr_reader :stack

  def initialize max = 3
    @stack  = [1,2,3]
    fill_to max
  end

  def fill_to max	
    n = 1
    while true do
      n += 4
      return @stack if n > max
      @stack << n if is_prime? n
  
      n += 2
      return @stack if n > max
      @stack << n if is_prime? n          
    end
  end
  
  def is_prime? n
    return false if n <= 0
    max = Math.sqrt(n).floor
    fill_to(max + 1) if max > @stack.last
  
    @stack.each do |i|
      next if i == 1
      return true if i > max
      return false if n % i == 0
    end
  
    true
  end

end

You can find more Project Euler solutions here: https://svn2.assembla.com/svn/joe-zack-personal/projects/euler/ruby/

I realize this isn’t the fast solution, but the more I optimized, the uglier it got so I’m done playing with it. The hardest part was figuring out what the upper bound limit was.

Problem 30

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

power, total = 5, 0

(power * 9**power).times do |i|
  total += i if i == i.to_s.split('').inject(0) {
    |sum, n|
    sum + n.to_i**power
  }
end

puts total - 1

I knew I’d be implementing my own division algorithm for this problem, but I had a hard time figuring out a good way to detect the repeating sequence.

That’s all I have to say about that.

Problem #26

Find the value of d 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

def divide n, d, repo = []
  return repo.size - repo.index(n) if repo.include? n
  divide 10 * (n - (n / d) * d), d, repo << n
end

highest = {"d" => 1, "count" => 1}

(1..499).each do |i|
  x     = i * 2 + 1
  count = divide 1, x
  if count > highest['count']
    highest = {"d" => x, "count" => count}
  end
end

puts highest["d"]

Looks like I took a pretty common approach on this one. First I calculated all the abundant numbers and dropped the sums in a hash. Then I just summed up to the given upper bound of 28,124 excluding those abundant sums.

Ruby1.9 solves it on my computer in about 15 seconds. After reading through the forums, some people were using a much lower upper limit of 20,200 which brought my run time down to a much respectable 6 seconds.

Problem #23

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

def sum_proper_divisors n
  sum = 1
  (2..Math.sqrt(n)).each do |i|
    if n % i == 0
      result = n / i
      sum += result unless result == i
      sum += i
    end
  end
  sum
end

def next_abundant repo
  i = repo.last + 1
  while( sum_proper_divisors(i) <= i)
    i += 1
  end
  i
end

max   = 20_200
repo  = [12]
sums  = {24 => nil}
total = 0

while repo.last < max do
  repo << next_abundant(repo)
  repo.each do |i|
    sum = repo.last + i
    if sum > max
      break
    end
    sums.store sum, nil
  end
end

max.times do |i|
  total += i unless sums.include? i
end

puts total

Although it felt dirty, I used Ruby’s baked-in date class. I’d written some day-of-week code when I first started coding, before I knew better, and it’s annoying. Besides, this was my last problem to do before level 1. That’s right…

LEVEL 1!!!!

Bravo, thejoezack! Now that you have solved 25 problems you have achieved what 79.52% of members have failed to do and have advanced to level 1. Good luck as you continue.”

I’m proud. I found a few of the problems to be really hard and it feels really good to have finally hit a milestone. I’ve actually had a much easier time with the problems as I’ve gone on, as I’ve learned a lot about solving these problems and perhaps even problem solving in general. Kudos and thanks, Project Euler!

Oh yeah…and here’s my solution:

Problem #19

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

require 'date'

start = Date.new 1901, 1, 1
total = 0

(100 * 12 - 1).times do |i|
  total += 1 if (start >> i).wday == 0
end

puts total

Cake. I really hate hard-coding that ascii value in there, but it made it easier for me to get it working in different versions of Ruby.

Problem #22

What is the total of all the name scores in the file?

def convert word
  total = 0
  word.each_byte do |i|
    total += i - 64
  end
  total
end

file  = File.new("files/names.txt", "r")
names = eval("[" + file.gets + "]").sort
total = 0

file.close

names.each_with_index do |name, i|
  total += convert(name) * (i + 1)
end

puts total

Pretty standard Project Euler solution. You only need to check up to the square of each number, and you can cache each calculation as you go along.

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.

Evaluate the sum of all the amicable numbers under 10000.

def d(n)
  total = 1
  (2..Math.sqrt(n)).each do |i|
    if n % i == 0
      total += n / i + i
    end
  end
  total
end

def amicable?(a, repo)
  repo[a] = b = d(a)
  a != b and a == repo[b]
end

repo  = {}
total = 0

10_000.times do |i|
  if amicable?(i, repo)
    total += (i + repo[i])
  end
end

puts total

I realized the other day, that you can sort the Project Euler problems by difficulty. For the most part it sticks pretty closely to the problem number, but this one was an outlier. Most of the solutions didn’t actually trim out the extraneous characters, but I thought that was the “hardest” part of this problem since I actually had to check the docs.

Problem #48

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

sum = 0

(1..1_000).each do |i|
  sum += i**i
end

puts (sum % 10**10).to_s[-10, 10]

I cheesed out on this one, pretty much just did what the problem called for. No magic. Looking through the forums, however, it was pretty much par for the course.

Problem #20

Find the sum of the digits in the number 100!

product, sum = 1, 0

100.times do |i|
  product *= i + 1
end

while product > 0
  sum += (product /= 10) % 10
end

puts sum