プロジェクト・オイラー(086-090)

[プロジェクト・オイラー]

プロジェクト・オイラー(086-090)

  Problem 86

Probem 「直方体のルート」

 下に示す直方体は寸法が6×5×3である. この直方体の1つの頂点Sにクモがいる. また反対の頂点Fにはハエがいる.

 SからFまでの壁に沿って直線移動する最短ルートは図に示す通りで, この長さは10である.
 この最短ルートの候補は3本あるが, 最短のものがいつも整数長さとは限らない.
 さて, M×M×M以下の寸法の直方体について, 最短ルートが整数である直方体の数を考える.
 M=100のとき, 条件を満たす直方体は2060個ある. このM=100は個数が2000を超える最小のMである. 
 なお, M=99のときは1975個である.100万個を超える最小のMを求めよ.

Answer

  Problem 87

Probem 「3つの素数のべき乗」

 素数の2乗と素数の3乗と素数の4乗の和で表される最小の数は28である. 50未満のこのような数は丁度4つある.
 28 = 22 + 23 + 24
 33 = 32 + 23 + 24
 49 = 52 + 23 + 24
 47 = 22 + 33 + 24
 では, 50,000,000未満の数で, 素数の2乗と素数の3乗と素数の4乗の和で表される数は何個あるか?

Answer

# n1**2 + n2**3 + n3**4
require 'set'

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

MAX = 50_000_000
PN = erastosthenes(10**5)

N2 = PN.map{|n| n**2}.select{|n| n < MAX}
N3 = PN.map{|n| n**3}.select{|n| n < MAX}
N4 = PN.map{|n| n**4}.select{|n| n < MAX}
p N2.count
p N3.count
p N4.count

ans = Set[]
for n2 in N2
  for n3 in N3
    for n4 in N4
      sum = n2 + n3 + n4
      if sum > MAX
        next
      else
        ans << sum
      end
    end
  end
end

p ans.length

  Problem 88

Probem 「積和数」

 少なくとも2つの自然数 {a1, a2, ... , ak} の集合の和かつ積として表せる自然数Nを積和数と呼ぶ：
   N = a1 + a2 + ... + ak = a1 × a2 × ... × ak.
 例えば, 6 = 1 + 2 + 3 = 1 × 2 × 3.ある集合の大きさ k に対して,この性質を持つ最小の N を最小積和数と呼ぼう. 
 集合の大きさ k = 2, 3, 4, 5, 6 に対する最小積和数は次のとおりである.
 
 k=2: 4 = 2 × 2 = 2 + 2
 k=3: 6 = 1 × 2 × 3 = 1 + 2 + 3
 k=4: 8 = 1 × 1 × 2 × 4 = 1 + 1 + 2 + 4
 k=5: 8 = 1 × 1 × 2 × 2 × 2 = 1 + 1 + 2 + 2 + 2
 k=6: 12 = 1 × 1 × 1 × 1 × 2 × 6 = 1 + 1 + 1 + 1 + 2 + 6
 
 したがって 2 ≤ k ≤ 6 に対して,全ての最小積和数の和は 4+6+8+12 = 30 である. 
 8 は和に一度だけカウントされていることに気をつけよう.
 実際, 2 ≤ k ≤ 12 に対する最小積和数の完全な集合は {4, 6, 8, 12, 15, 16} なので,その和は 61 である.
 2 ≤ k ≤ 12000 に対する全ての最小積和数の和は何か?

Answer

  Problem 89

Probem 「ローマ数字」

 ローマ数字の記法は一つの数について沢山ある場合が存在する (FAQを見よ).
 しかし, ある数については最良の記法が必ず存在する.例えば, 16の正しい記法を全て並べてみる.
 IIIIIIIIIIIIIIII
 VIIIIIIIIIII
 VVIIIIII
 XIIIIII
 VVVI
 XVI最後の例は, 最小の文字数で表せるという意味で, 最も効率が良い.11Kのテキストファイルroman.txt は1000個のローマ記法で書かれた数を含んでいる. これらは, 正しい記法に従っている. 
 即ち, 大きい数から順に書かれていて, 引き算ペアのルールにも従っている(このルールについてはFAQを見よ) 但し, 最小の文字数で表されているとは限らない.
 最小形で書いたときに, 何文字節約できるかを求めよ.注: ファイル中の全てのローマ数字には, 5つ以上の同じ文字が連続して含まれることはない.
 (訳者:概略のみ与える)全ての文字はサイズの降順に並ぶ引き算ペアについて.X (10) + IX (9) として19=XIXと表せる. ただし, 8をIIXと二文字以上を引くことは許されない.

Answer

  Problem 90

Probem 「2つの立方体の数字」

 立方体の6面それぞれに異なる数字(0から9)が書かれている;2番目の立方体も同様になっている. 異なる位置に2つの立方体を隣り合わせることで様々な2桁の数を作ることができる.例えば, 平方数である64も作ることができる:事実, 両方の立方体の数字を注意深く選ぶと100以下のすべての平方数を示すことが可能である:01, 04, 09, 16, 25, 36, 49, 64, そして 81.例えば, これを実現する一つの方法としては {0, 5, 6, 7, 8, 9} を一方の立方体に, そして {1, 2, 3, 4, 8, 9} を他方の立方体に配置すればよい.しかし, 6と9を逆さまに回転することを許すと {0, 5, 6, 7, 8, 9} と {1, 2, 3, 4, 6, 7} のような配列で9つすべての平方数を示す事ができる;
 そうでなければ09を得ることができない.順番ではなくそれぞれの立方体の数字に着目して配列を区別する.
 {1, 2, 3, 4, 5, 6} は {3, 6, 4, 1, 2, 5} と同じものとし
 {1, 2, 3, 4, 5, 6} は {1, 2, 3, 4, 5, 9} と異なるものとする.しかし6と9を逆さにすることを許すために, 最後の例で区別された両方の配列のかわりに, {1, 2, 3, 4, 5, 6, 9} という(要素数が７つに)拡張された配列を使用して2桁の数をつくることにする.すべての平方数を表示し得る2つの立方体の異なる配列の組はいくつあるか.

Answer