[プロジェクト・オイラー]
下に示す直方体は寸法が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を求めよ.
素数の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乗の和で表される数は何個あるか?
|
+
|
解答
|
|
|
- 考えたこと
- エラトステネスの篩を使って素数テーブルを求める
- 条件に合う整数の集合は意外に少ないので、集合を求めた後総当りでなんとかなる
\[ \begin{aligned} \text{let MAX} &= 50,000,000 \\ n2 &:= \{x \in \mathbb{P}\ |\ x^2 < \text{MAX}\} \\ \#n2 &= 908 \\ n3 &:= \{x \in \mathbb{P}\ |\ x^3 < \text{MAX}\} \\ \#n3 &= 73 \\ n4 &:= \{x \in \mathbb{P}\ |\ x^4 < \text{MAX}\} \\ \#n4 &= 23 \end{aligned}\]
# 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
|
少なくとも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 に対する全ての最小積和数の和は何か?
ローマ数字の記法は一つの数について沢山ある場合が存在する (FAQを見よ).
しかし, ある数については最良の記法が必ず存在する.例えば, 16の正しい記法を全て並べてみる.
IIIIIIIIIIIIIIII
VIIIIIIIIIII
VVIIIIII
XIIIIII
VVVI
XVI最後の例は, 最小の文字数で表せるという意味で, 最も効率が良い.11Kのテキストファイルroman.txt は1000個のローマ記法で書かれた数を含んでいる. これらは, 正しい記法に従っている.
即ち, 大きい数から順に書かれていて, 引き算ペアのルールにも従っている(このルールについてはFAQを見よ) 但し, 最小の文字数で表されているとは限らない.
最小形で書いたときに, 何文字節約できるかを求めよ.注: ファイル中の全てのローマ数字には, 5つ以上の同じ文字が連続して含まれることはない.
(訳者:概略のみ与える)全ての文字はサイズの降順に並ぶ引き算ペアについて.X (10) + IX (9) として19=XIXと表せる. ただし, 8をIIXと二文字以上を引くことは許されない.
立方体の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つの立方体の異なる配列の組はいくつあるか.