[プロジェクト・オイラー]
三角数, 四角数, 五角数, 六角数, 七角数, 八角数は多角数であり, それぞれ以下の式で生成される.
多角数 |
式 |
例 |
三角数 |
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桁の数からなる唯一の順序集合の和を求めよ.
+
|
解答
|
|
|
- 考えたこと
- 対象の数値が4桁の数限定なので元となる数の集合は少なく、全探索できそうな雰囲気がある
- 再帰的な関数を定義して数え上げることで実装できた
- 各種集合を重複無く数え上げるためにハッシュマップの値に配列をもたせてみた
- 後で見たときのため、処理内容を以下に示す
- 三角数〜八角数までをp3,p4,p5,p6,p7,p8で定義しておく
- 答えとなる巡回数列は、どの数値から始めてもいいので三角数からはじめるものとして、三角数の全ての要素でループを開始
- ループ内部で再帰関数に三角数の1要素をスタックの形で渡す
- 再帰関数内部で三角数〜八角数までをループして、スタックの最後の要素の下二桁が上二桁と一致する数値があれば取得する
- 取得した数値をスタックにpushし再帰関数に渡すことを繰り返す、その際に使用したN角数の配列は削除しておく
- 再帰関数内で三角数〜八角数の配列が空であれば答えとなる巡回数列が揃ったことになるので記録する
p3,p4,p5,p6,p7,p8 = [],[],[],[],[],[]
(1..10**5).each do |n|
_p3 = n*(n+1)/2
p3 << _p3 if 999 < _p3 and _p3 < 10000
_p4 = n**2
p4 << _p4 if 999 < _p4 and _p4 < 10000
_p5 = n*(3*n-1)/2
p5 << _p5 if 999 < _p5 and _p5 < 10000
_p6 = n*(2*n-1)
p6 << _p6 if 999 < _p6 and _p6 < 10000
_p7 = n*(5*n-3)/2
p7 << _p7 if 999 < _p7 and _p7 < 10000
_p8 = n*(3*n-2)
p8 << _p8 if 999 < _p8 and _p8 < 10000
end
@ans = []
def rec_search(arr, stack)
if arr.empty?
puts "#{stack} #{'<--- !!!' if stack.last.values[0].to_s[2,2] == stack.first.values[0].to_s[0,2]}"
@ans = stack.dup if stack.last.values[0].to_s[2,2] == stack.first.values[0].to_s[0,2]
return
end
arr.each do |k, v|
matched = v.select{|val| stack.last.values[0].to_s[2,2] == val.to_s[0,2]}
dup_arr = arr.dup
dup_arr.delete(k)
matched.each do |new_key|
next if stack.any?{|stack_k, stack_v| stack_k==k}
stack.push({k => new_key})
puts "#{stack}"
rec_search(dup_arr, stack)
stack.pop()
end
end
end
arr = {p3: p3, p4: p4, p5: p5, p6: p6, p7: p7, p8: p8}
arr_dup = arr.dup
arr_dup.delete(:p3)
arr[:p3].each do |key|
puts "#{{p3: key}}"
rec_search(arr_dup, [].push({p3: key}))
end
puts "---"
p @ans
p @ans.map {|e| e.values[0]}.inject(&:+)
|
立方数 41063625 (345^3) は, 桁の順番を入れ替えると2つの立方数になる: 56623104 (384^3) と 66430125 (405^3) である.
41063625は, 立方数になるような桁の置換をちょうど3つもつ最小の立方数である.
立方数になるような桁の置換をちょうど5つもつ最小の立方数を求めよ.
+
|
解答
|
|
|
- 考えたこと
- 立方数のテーブルを先に作っておいて全探索したら早そうに見える
- 立方数のテーブル内の数値を文字列化し、ソートしてやったやつをキーにgroup_byしたものを作成(→ハッシュマップ)
- 上記をやると立方数のなかで並び替えたら同じになるものがまとまる
- あとはそのハッシュマップの中で5つの立方数を持つものを検索してやればいい
cubes = (1..10**5).to_a.map do |n|
n**3
end.group_by do |n|
n.to_s.split("").sort.join
end.to_a
cubes.select do |elem|
elem[1].size.to_i == 5
end.take(1).each do |elem|
p elem
end
|
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項目の分子の桁の合計を求めよ.