sierpinski.rb

# Calculate number of triangles (that don't contain triangles) inside a
# Sierpinski triangle
module Sierpinski
  # @param [Integer] n - number of iterations
  # @return [Integer] the number of triangles that don't contain triangles
  #
  # f(n) = 4(f(n - 1) - f(n - 2)) + f(n - 2)
  # T(n) in O(n)
  def self.triangles(n)
    raise 'must be nonnegative' if n < 0

    case n
    when 0
      1
    when 1
      4
    else
      spk0 = 1
      spk1 = 4

      (2..n).each do
        spk1, spk0 = 4 * (spk1 - spk0) + spk0, spk1
      end

      spk1
    end
  end
end