[プロジェクト・オイラー]
Probem 「整数座標における直角三角形」
点P(x1, y1)と点Q(x2, y2)はともに整数係数の点であり, 原点O(0,0)と合わせてΔOPQをなす.各係数が0と2の間にあるとき,
すなわち0 ≤ x1, y1, x2, y2 ≤ 2のとき, 直角三角形は14個できる:では, 0 ≤ x1, y1, x2, y2 ≤ 50のとき, 直角三角形は何個作れるか?
各桁の2乗を足し合わせて新たな数を作ることを, 同じ数が現れるまで繰り返す.例えば
44 → 32 → 13 → 10 → 1 → 1
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89のような列である. どちらも1か89で無限ループに陥っている.
驚くことに, どの数から始めても最終的に1か89に到達する.では, 10,000,000より小さい数で89に到達する数はいくつあるか.
|
+
|
解答
|
|
|
require 'set'
def square_sum_each_digit(n)
return n.to_s.split("").map{|d| d.to_i**2}.inject(&:+)
end
def find_cycle(n, group_89)
memo = [n]
t = n
loop {
t = square_sum_each_digit(t)
memo << t
return true, memo if t==89 or group_89.include?(t)
return false,[] if t==1 or t==n
}
end
ans = Set[]
(1..10_000_000).to_a.each do |n|
found,memo = find_cycle(n, ans)
if found
# puts "#{n} => #{memo}"
ans = ans.merge(memo)
end
puts "n=#{n}..." if n%100000==0
end
p ans.length
#p ans.all?{|e| found,_ = find_cycle(e,[]); found}
|
集合 {1, 2, 3, 4} の各数字をちょうど一度用い, また四則演算 (+, －, *, /) と括弧を使うことにより, 異なる正の整数を作ることができる.例えば,
8 = (4 * (1 + 3)) / 2
14 = 4 * (3 + 1 / 2)
19 = 4 * (2 + 3) － 1
36 = 3 * 4 * (2 + 1)
12 + 34 のように数字をつなげることは許されないことに注意しよう.
集合 {1, 2, 3, 4} を使うと, 36 を最大とする 31 個の異なる数が得られる.
最初の表現できない数に会うまで, 1 から 28 の各数を得ることができる.最長の連続した正の整数 1 から n の集合を得ることができる,
4 つの異なる数字 a < b < c < d を見つけよ. 答えを文字列 abcd として与えよ.
|
+
|
解答
|
|
|
- 考えたこと
- 全探索的なコードを考えたが、時間がかかりすぎてうまく行かない。数学的なトリックが必要か。
def calc_cataran_results(perms, ops)
ans = []
a,b,c,d=perms[0],perms[1],perms[2],perms[3]
# ((a+b)+c)+d
eval_statements = "((#{a} #{ops[0]} #{b}) #{ops[1]} #{c}) #{ops[2]} #{d}"
tmp = eval(eval_statements) rescue nil
ans.append(tmp)
# (a+(b+c))+d
eval_statements = "(#{a} #{ops[0]} (#{b} #{ops[1]} #{c})) #{ops[2]} #{d}"
tmp = eval(eval_statements) rescue nil
ans.append(tmp)
# (a+b)+(c+d)
eval_statements = "(#{a} #{ops[0]} #{b}) #{ops[1]} (#{c} #{ops[2]} #{d})"
tmp = eval(eval_statements) rescue nil
ans.append(tmp)
# a+((b+c)+d)
eval_statements = "#{a} #{ops[0]} ((#{b} #{ops[1]} #{c}) #{ops[2]} #{d})"
tmp = eval(eval_statements) rescue nil
ans.append(tmp)
# a+(b+(c+d))
eval_statements = "#{a} #{ops[0]} (#{b} #{ops[1]} (#{c} #{ops[2]} #{d}))"
tmp = eval(eval_statements) rescue nil
ans.append(tmp)
return ans.compact.uniq
end
numbers = (1..100).to_a
numbers.combination(4) do |perms|
printf perms.join(",")
ans = []
['+','-','*','/'].repeated_combination(3) do |ops|
ans.concat calc_cataran_results(perms, ops)
ans = ans.uniq
end
if !ans.empty? && (1..28).to_a.all? {|e| ans.include?(e) }
puts "really???"
puts ans.to_s
printf " => match!!! #{ans.sort.join(',')} \n"
break
else
printf " => not match... #{ans.sort.join(',')} \n"
end
#exit 0
end
|
一辺の長さが整数の正三角形は面積が整数にならないことを示すのは簡単である.
しかし, 5-5-6の辺を持つ殆ど正三角形に近い擬正三角形 (almost equilateral triangle) は面積が12で整数である.
以降, 二等辺三角形で, 3つめの辺の長さが他と1つしか違わないもの (5-5-6, 5-5-4等) を, 擬正三角形と呼ぶ.
さて, 周囲の長さが1,000,000,000以下の面積が整数になる擬正三角形を考え, その周囲の長さの総和を求めよ.
ある数の真の約数とは, それ自身を除く約数すべてである. 例えば, 28 の真の約数は 1, 2, 4, 7, 14 である.
これらの約数の和は 28 に等しいため, これを完全数と呼ぶ.面白いことに, 220 の真の約数の和は 284 で, 284 の真の約数の和は 220 となっており,
二つの数が鎖をなしている. このため, 220 と 284 は友愛数と呼ばれる.さらに長い鎖はあまり知られていないだろう.
例えば, 12496 から始めると, 5 つの数の鎖をなす.この鎖は出発点に戻っているため, 友愛鎖と呼ばれる.
いずれの要素も 1,000,000 を超えない最長の友愛鎖の最小のメンバーを求めよ.
|
+
|
解答
|
|
|
- 考えたこと
- 約数の和をメモ化して地道に求める
- 素数は明らかに約数の和が少ないはずなので、さらにそこで高速化できそう（やってないけど）
def make_divisors(n)
divisors = []
for i in 1..((n**0.5)+1).to_i
if n % i == 0
divisors << i
if i != n / i
divisors << n/i
end
end
end
divisors.delete(n)
divisors.uniq.sort
end
@divisors_sums = {}
def make_divisors_sum(n)
if @divisors_sums.has_key?(n)
return @divisors_sums[n]
end
@divisors_sums[n] = make_divisors(n).inject(&:+)
return @divisors_sums[n]
end
def find_cycle(n)
sums = [n]
loop {
sums << make_divisors_sum(sums.last)
return false,sums if sums.last.nil? or sums.last >= 1_000_000 or sums.length>50
return true, sums if sums.last==n
}
return sums
end
ans = []
(1..1_000_000).to_a.each do |n|
found,sums = find_cycle(n)
if found
puts "#{n} => #{sums}"
ans = sums.dup if ans.length < sums.length
end
end
p ans
|
