プロジェクトオイラー

また、Project Eulerの問題をぽつぽつ解いてみた。そこそこやる気になるし、いい練習だしでいいんだけど、一部の問題は、「これってRubyを使うのは反則じゃないか」という感じ。Ruby1.9＋mathnライブラリを使ってしまうと、最初のほうの問題はかなりトリビアルになってしまう。

Problem 48

The series, 1^(1) + 2^(2) + 3^(3) + ... + 10^(10) = 10405071317.
Find the last ten digits of the series, 1^(1) + 2^(2) + 3^(3) + ... + 1000^(1000).

とか、

1.upto(1000).inject(0){|t, i| t += i**i}.to_s[-10..-1] => "9110846700"

とワンライナーでいける。もう少し面倒なもの、例えば、こんなのでも、

Problem 47

The first two consecutive numbers to have two distinct prime factors are:

14 = 2 × 7
15 = 3 × 5

The first three consecutive numbers to have three distinct prime factors are:

644 = 2^2 × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19.

Find the first four consecutive integers to have four distinct primes factors. What is the first of these numbers?

素因数分解がprime_divisionで一撃なので、簡単。

require "mathn"

2.upto(1000000) do |i|

  if ((i.prime_division.to_a.size >= 4) &&
      ((i+1).prime_division.to_a.size >= 4) &&
      ((i+2).prime_division.to_a.size >= 4) &&
      ((i+3).prime_division.to_a.size >= 4))
    print i, ",", i + 1, ",", i + 2, ",", i + 3, "\n"
    break
  end
end

強力すぎる。

とはいえ、問題の難易度なのか飽きの問題なのか分からないけど、問題IDが後ろの方に行くと極端に正答者が少なくなってるみたいなので、そんなに自明も問題ばかりじゃないのかも。計算時間が増えるとRubyは厳しくなるとかもあるかしら。

そういえば、使ったことないけど遅延評価って以下のような問題にはやっぱり便利なんじゃないだろうかと思った。

Problem 12

The sequence of triangle numbers is generated by adding the natural numbers. So the 7^(th) triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

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

require "mathn"

class Triangle
  attr_reader :n, :t

  def initialize(n=1)
    @n = n
    @t = @n
  end

  def succ
    @n += 1
    @t += @n
  end
end

t = Triangle.new

while true
  t.succ
  k = t.t.prime_division.map{|p|p.last+1}.inject(&:*)
  if k > 500 then
    puts k, t.t
    exit
  end
end

いや、遅延評価といってもtakeとかで取り出すんだとしたら、どっちみち同じことなのかな。