Project Euler 44: Ruby

In my attempt to learn Ruby out in the open, here’s my solution for Project Euler Problem 44. 

So much for my brute-force-only-just-get-the-answer-in-less-than-one-minute approach. I worked through this problem four different ways — each time holding x number of pentagonal numbers in a various data structure for quick comparison. That was a bad move as each attempt took forever to complete. Instead I tried calculating each pentagonal on the fly and Wikipedia clued me into the pentagonal? check. Premature optimization. Still bad most of the time.

Other than the newly discovered math, there are a few bits I’d like to point out. There’s the natural number check found within the pentagonal? method and I guess there’s no concept of Integer::Max in Ruby so I stole someone else’s implementation. Should I be surprised that Integer::Max doesn’t exist?

As always, any feedback is welcome.

# Euler 44
# http://projecteuler.net/index.php?section=problems&id=44
# Pentagonal numbers are generated by the formula,
# Pn=n(3n1)/2. The first ten pentagonal numbers are:
#
# 1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...
#
# It can be seen that P4 + P7 = 22 + 70 = 92 = P8. However,
# their difference, 70 - 22 = 48, is not pentagonal.
#
# Find the pair of pentagonal numbers, Pj and Pk, for which
# their sum and difference is pentagonal and D = |Pk - Pj|
# is minimised; what is the value of D?
timer_start = Time.now

class Integer
  def pentagonal
    return self*(3*self-1)/2
  end

  # http://en.wikipedia.org/wiki/Pentagonal_number
  # If n is a natural number, then x is the nth pentagonal
  # number. If result is not a natural number,
  # then self is not pentagonal.
  def pentagonal?
    return ((Math.sqrt(24*self + 1) + 1) / 6) % 1.0 == 0.0;
  end

  # http://drawohara.com/post/117643208/
  # ruby-integer-max-and-integer-min
  N_BYTES = [42].pack('i').size
  N_BITS = N_BYTES * 8
  MAX = 2 ** (N_BITS - 2) - 1
  MIN = -MAX - 1
end

# Another upper bound guess
upper_bound = 5000
answer = Integer::MAX

1.upto(upper_bound) do |j|
  (j+1).upto(upper_bound) do |k|
    pk, pj = k.pentagonal, j.pentagonal
    d = pk - pj

    break if d > answer
    next if !d.pentagonal?

    s = pj + pk
    if s.pentagonal? then
      answer = d
    end
  end
end

puts answer
puts "Elapsed Time: #{(Time.now - timer_start)*1000} milliseconds"