[プロジェクト・オイラー]
三角数, 四角数, 五角数, 六角数, 七角数, 八角数は多角数であり, それぞれ以下の式で生成される.
多角数 |
式 |
例 |
三角数 |
P3,n=n(n+1)/2 |
1, 3, 6, 10, 15, ... |
四角数 |
P4,n=n^2 |
1, 4, 9, 16, 25, ... |
五角数 |
P5,n=n(3n-1)/2 |
1, 5, 12, 22, 35, ... |
六角数 |
P6,n=n(2n-1) |
1, 6, 15, 28, 45, ... |
七角数 |
P7,n=n(5n-3)/2 |
1, 7, 18, 34, 55, ... |
八角数 |
P8,n=n(3n-2) |
1, 8, 21, 40, 65, ... |
3つの4桁の数の順番付きの集合 (8128, 2882, 8281) は以下の面白い性質を持つ.
- この集合は巡回的である. 最後の数も含めて, 各数の後半2桁は次の数の前半2桁と一致する
- それぞれ多角数である: 三角数 (P3,127=8128), 四角数 (P4,91=8281), 五角数 (P5,44=2882) がそれぞれ別の数字で集合に含まれている
- 4桁の数の組で上の2つの性質をもつはこの組だけである.
三角数, 四角数, 五角数, 六角数, 七角数, 八角数が全て表れる6つの巡回する4桁の数からなる唯一の順序集合の和を求めよ.
+
|
解答
|
|
|
- 考えたこと
- それぞれの数の前半2桁、後半2桁をグラフの始点終点と考えれば、答えの順序集合はその全域木となる
|
立方数 41063625 (3453) は, 桁の順番を入れ替えると2つの立方数になる: 56623104 (3843) と 66430125 (4053) である.
41063625は, 立方数になるような桁の置換をちょうど3つもつ最小の立方数である.立方数になるような桁の置換をちょうど5つもつ最小の立方数を求めよ.
5桁の数 16807 = 7^5は自然数を5乗した数である. 同様に9桁の数 134217728 = 8^9も自然数を9乗した数である.自然数を n 乗して得られる n 桁の正整数は何個あるか?
+
|
解答
|
|
|
- 考えたこと
- べき乗の指数に対してべき乗される自然数を洗い出すプログラムを考えると意外と簡単に解ける
- 自然数の総数はたくさんあるが、べき乗の桁数はべき乗が少し大きくなると天元突破するのでそれほどたくさん数はない
def pow_eql_exp(exp)
count = 0
n = 1
loop {
pow = n**exp
if pow.to_s.length == exp
count += 1
elsif pow.to_s.length > exp
break
end
n += 1
}
count
end
ans = (1..200).to_a.map do |n|
pow_eql_exp(n)
end.inject(&:+)
puts ans
|
平方根は連分数の形で表したときに周期的であり, 以下の形で書ける:√N = a0 + 1 / (a1 + 1 / (a2 + 1 / (a3 + ...)))例えば, √23を考えよう.√23 = 4 + √23 - 4 = 4 + 1 / (1 / (√23 - 4)) = 4 + 1 / (1 + (√23 - 3) / 7)となる.この操作を続けていくと,√23 = 4 + 1 / (1 + 1 / (3 + 1 / (1 + 1 / (8 + ...))))を得る.操作を纏めると以下になる:よって, この操作は繰り返しになることが分かる. 表記を簡潔にするために, √23 = [4;(1,3,1,8)]と表す. (1,3,1,8)のブロックは無限に繰り返される項を表している.最初の10個の無理数である平方根を連分数で表すと以下になる.N ≤ 13で奇数の周期をもつ平方根は丁度4つある.N ≤ 10000 について奇数の周期をもつ平方根が何個あるか答えよ.
2の平方根は無限連分数として書くことができる.無限連分数である √2 = [1;(2)] と書くことができるが, (2) は2が無限に繰り返されることを示す. 同様に, √23 = [4;(1,3,1,8)].平方根の部分的な連分数の数列から良い有理近似が得られることが分かる.√2の近似分数について考えよう.従って, √2の近似分数からなる数列の最初の10項は:1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985, 3363/2378, ...もっとも驚くべきことに, 数学的に重要な定数,
e = [2; 1,2,1, 1,4,1, 1,6,1 , ... , 1,2k,1, ...].e の近似分数からなる数列の最初の10項は:2, 3, 8/3, 11/4, 19/7, 87/32, 106/39, 193/71, 1264/465, 1457/536, ...10項目の近似分数の分子の桁を合計すると1+4+5+7=17である.e についての連分数である近似分数の100項目の分子の桁の合計を求めよ.