プロジェクト・オイラー(006-010)

• 総当たりでも解けるが、数列の和を漸化式で解いたほうが速い
  • 数列の和の公式(Σ公式)と基本的なΣ計算

• 総当たり

def sum_of_sequare(n)
  array = (1..n).to_a
  array = array.map{|e| e**2}
  ans   = array.inject(&:+)
  ans
end

def sequare_of_sum(n)
  array = (1..n).to_a
  ans   = array.inject(&:+)
  ans   = ans**2
  ans
end

puts sequare_of_sum(100) - sum_of_sequare(100)

• 数列の和の公式

def sum_of_sequare(n)
  ans = n * (n+1) * (2*n+1) / 6
  ans
end

def sequare_of_sum(n)
  ans = n * (n+1) / 2
  ans = ans**2
  ans
end

puts sequare_of_sum(100) - sum_of_sequare(100)

• エラトステネスのふるいを使った
  • エラトステネスのふるい

def erastosthenes(n)
  array = (2..n).to_a
  threshold = Math.sqrt(n)
  count = 2
  while threshold > count
    array.reject!{|n| n != count and n % count == 0}
    count += 1
  end
  array
end

PN = erastosthenes(1000000)

puts PN.length
puts PN[10000]

模範解答を見ると、エラトステネスのふるいを使うまでもないようだ

• 愚直にいってみた
  • #each_cons で華麗に解く

lines = <<'EOS'
   73167176531330624919225119674426574742355349194934
   96983520312774506326239578318016984801869478851843
   85861560789112949495459501737958331952853208805511
   12540698747158523863050715693290963295227443043557
   66896648950445244523161731856403098711121722383113
   62229893423380308135336276614282806444486645238749
   30358907296290491560440772390713810515859307960866
   70172427121883998797908792274921901699720888093776
   65727333001053367881220235421809751254540594752243
   52584907711670556013604839586446706324415722155397
   53697817977846174064955149290862569321978468622482
   83972241375657056057490261407972968652414535100474
   82166370484403199890008895243450658541227588666881
   16427171479924442928230863465674813919123162824586
   17866458359124566529476545682848912883142607690042
   24219022671055626321111109370544217506941658960408
   07198403850962455444362981230987879927244284909188
   84580156166097919133875499200524063689912560717606
   05886116467109405077541002256983155200055935729725
   71636269561882670428252483600823257530420752963450
EOS

#lines = $stdin.read
array = lines.split("\n")

big_numbers = array.map{|str| str.strip }.join

max_four_digit = ""
max_number     = 0

big_numbers.split("").each_cons(13) do |digit|
    s = digit.map(&:to_i).inject(:*)
    if s > max_number
        max_number = s
        max_four_digit = digit.join
    end
end

puts max_four_digit
puts max_four_digit.split("").map(&:to_i).inject(&:*)

• 総当りなのだが、変数の置き方がポイント。結構悩んだ。

for a in 1..1000
  for b in 2..1000
    c = 1000 - a - b
    if (a+b+c == 1000) and (a**2 + b**2 == c**2) and (a < b and b < c)
      puts "a = #{a}, b = #{b}, c = #{c}"
      puts "  a*b*c = #{a*b*c}"
    end
  end
end

• もう一度エラトステネスのふるいを使った
  • エラトステネスのふるい

def erastosthenes(n)
  array = (2..n).to_a
  threshold = Math.sqrt(n)
  count = 2
  while threshold > count
    array.reject!{|n| n != count and n % count == 0}
    count += 1
  end
  array
end

PN = erastosthenes(2000000)

puts PN.length
puts PN.inject(:+)