Cake.

Problem #16

What is the sum of the digits of the number 2^(1000)?

n = 0

(2 ** 1000).to_s.scan(/./).each do |i|
  n += i.to_i
end

puts n

I spent a lot of time drawing this on paper trying to figure out an equation behind it before I gave up and went the recursive route. There was an obvious pattern behind it…but I’m not a mathematician. I could see from the traces that I could store information about exhausted routes to save a lot of cycles, so I’m happy with my solution.

Problem #15

How many routes are there through a 20 x 20 grid? (no backtracking)

def move grid, x, y
  size = grid.size - 1

  if x > size or y > size
    return 0
  end

  if x == size and y == size
    return 1
  end

  if grid[x][y] != nil
    return grid[x][y]
  end

  grid[x][y] = move(grid, x + 1, y) + move(grid, x, y + 1)
  
end

size = ARGV[0].to_i
grid = Array.new(size + 1) do |i|
  i = Array.new(size + 1)
end

puts move(grid, 0, 0)

Straight up brute force was too slow, so I would store the sequence counts for numbers I’d already seen in a hash table.

Problem #14

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

Which starting number, under one million, produces the longest chain?

def advance heap, n, count

  if heap.has_key? n
    return heap[n] + count
  end

  if (n & 1) == 0
    return advance(heap, n / 2, count + 1)
  end

  advance(heap, 3 * n + 1, count + 1)

end

heap = Hash[0,0,1,1]
answer, max = 1, 1

1_000_000.times do |i|

  heap[i] = advance(heap, i, 1)

  if heap[i] > max
    max = heap[i]
    answer = i
  end
  
end

puts answer 

Just finished up Problem #13. Straight up brute force ran really well, but I figured I could save some cycles by only adding up the last 11 digits.

I ran this and #25 through ruby 1.8.6 and 1.9.1 and was suprised to see that it ran much slower in the newer version. Everything else I’ve tried has run much better.

Here are some numbers I found to be pretty indicative. Bummer.

$ time ruby 13.rb

real	0m0.009s
user	0m0.008s
sys	0m0.000s

$ time ruby1.9 13.rb

real	0m0.026s
user	0m0.020s
sys	0m0.004s

Problem 13

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

input = File.new("files/13.txt", "r")
total = 0

input.each do |i|
  total += i.slice(0..10).to_i
end

puts total.to_s.slice(0,10)

Skipping around a bit, I saw that #25 looked pretty easy. It was. I saw in the forums that someone had used binary search and a calculator which I thought was pretty clever, but mine was just brute force.

Problem #25

What is the first term in the Fibonacci sequence to contain 1000 digits?

Solution

max  = 10 ** 999
a, b, i = 1, 1, 2

while b < max
  i += 1
  a, b = b, b + a
end

puts i

I took a couple swings at problem #12 before I finally got it. I’m definitely over my head mathematically, but that’s part of the fun and I’m certainly learning a lot along the way. Big thanks to Dr. Math for his excellent explanation of how to find a number’s number of factors.

Problem #12

What is the value of the first triangle number to have over five hundred divisors?

Surely it’s not the perfect solution, but it ran in under 4 seconds on ruby 1.9, so I’m happy with it. Looking at it now, it all seems obvious but I must have started over at least a dozen times. Here are a few recurring Project Euler themes I’ve picked up on, as applied to this problem.

1. Like every other Project Euler problem, don’t repeat your calculations, cache it! Prime number computation is heavy.
2. If you don’t have to store something don’t. In this case it’s enough to count the distinct factors, you don’t have to store them.
3. Cut down your data set. Since we’re looking for a number that has over 500 factors then we don’t need to start looking until after the 500th triangle.

Enough talk, here’s the code:

require 'mathn'

primer  = Prime.new
primes  = [ primer.next ]
seed    = 500
n       = (seed * (seed + 1)) / 2
i       = seed + 1

def count_prime_factors primer, primes, n
  total = 1
  max   = Math.sqrt(n).to_i

  while primes.last < max
    primes << primer.next
  end
  
  primes.each do |i|
    count = 0
    while n % i == 0
      n = n / i
      count += 1
    end
    if count > 0
      total *= count + 1
    end
  end

  total
end

while(count_prime_factors(primer, primes, n) < seed)
  n += i
  i += 1
end

puts n