最終更新: 2011-03-12T03:46+0900
"exactly five" って書いてあるから、同じ数字の並べ替えで作れる立方数が 6以上あってもダメだと思うんだ。
memo = Hash.new{|h,k| h[k] = [] } n = 0 k_length = 1 loop{ n += 1 cube = n*n*n k = cube.to_s.split(//).sort.join('') if k.length != k_length answer = memo.values.select{|cubes| cubes.size == 5 } if not answer.empty? answer.each{|cubes| p cubes } exit end memo.clear k_length = k.length end memo[k] << cube }
# (x-1)/x <= log10(n) < 1 (n = ?,?,...) count = 0 x = 0 loop{ x += 1 boundary = (x-1.0)/x lower_bound = (1..9).to_a.reverse.find{|n| Math.log10(n) < boundary } || 0 count += 9 - lower_bound break if lower_bound == 9 } p count
またまた「Dreamshire | Project Euler Problem 63 Solution」の解答を検討してみたい。二重のループなんてない。logの計算だって 9回だけ。どういうことだ?
というストーリーをひねり出した。「9は 10より 0.046(=1-0.954)程度小さい数だ」ってくだりがいかにも苦しい。小数だからごまかしがきいてるけど、ぴったり 10一個分小さくなる場合は n桁、n-1桁、どっち? (たぶんまだ n桁だな。1^1
がそう)
ともあれ、明かされてみればワンライナーの問題だったよ。
p (1..9).inject(0){|sum,n| sum + (1/(1-Math.log10(n))).floor }
常用対数を直接求めるメソッドが用意されてるあたりが Rubyだなとおもた。
連分数っていうらしい。a_n
の求め方、a += 1 while 0 <= r - (n - d*(a+1))**2
の条件部分が判然としない。スクリプト中のコメントにあるように、対象としてるルートの係数が必ず約分されて 1になることも理解できてない。
def next_frac(r, n, d) # (√r + n) / d = a + 1 / [(√r + n_) / d_] a = 0 a += 1 while 0 <= r - (n - d*(a+1))**2 d_ = (r - (n - d*a)**2) / d raise if (r - (n - d*a)**2) % d != 0 # why OK? n_ = -(n - d*a) return a, r, n_, d_ end def period_of(r) rnd = [r, 0, 1] arr = [] loop{ a, *rnd = next_frac(*rnd) arr << rnd period = arr.size-1 - arr.index(rnd) return period if 0 != period return 0 if rnd[2] == 0 # √r is rational. } end count = 0 1.upto(10000){|n| count += 1 if period_of(n) % 2 == 1 } p count
ところで、この問題を解くときに Math.sqrtを使うのってインチキくさくない?(だから使ってないんだけど)