« 2009年6月 | トップページ | 2009年8月 »

2009年7月

2009年7月30日 (木)

Project Euler - Problem 43 : 0.09s (Ruby 1.9)

問題はこちらをご覧ください。


実はこの問題は以前、Scheme で解いたときに記事を投稿しているのですが、改めて Ruby 版として投稿します。

素直に解くと次のようになるでしょうか?

(自作の "math_tool.rb" に関してはこちらをご覧ください)

require 'math_tool' Div_List = [nil, 2, 3, 5, 7, 11, 13, 17] def check(arr) 7.downto(1) do |i| return false unless (arr[i, 3].to_i % Div_List[i]) == 0 end return true end ans = Array.new (0 .. 9).to_a.permutation do |num_arr| next if num_arr[0] == 0 ans.push(num_arr.to_i) if check(num_arr) end puts ans.inject(:+)

素直に解いたと言っても、Pandigital な数だけを探索の対象とするために "Array#permutation" を使ったり、早く候補を絞り込めるように、割る数を大きい方から適用したりしています。

このコードでは Ruby 1.9 で約 13 秒ほどで答えが出ます。


ところで総当たりって無駄なことしてると思いませんか?

10 桁目が 0 になる場合を除いても、10 桁の Pandigital な数は全部で 3265920 個もあります。でも d8d9d10 に当てはまる整数は 44 個しかありません。

そこで、まず d8d9d10 に当てはまる数を配列に入れておいて、その数を元に d7 に入る数、d6 に入る数……と順に探していくことにします。

ただし、途中に 0 が来ても桁落ちをしないようにそれぞれの数自体を配列の形で保持しておきます。

# -*- coding: utf-8 -*- require 'math_tool' # require 'pp' Seq_List = (0 .. 9).to_a class Array # * 配列の左に数字を 1 個つけ足す。 # * 新しい配列を数字と見なした時、上位 3 桁が d で割りきれる # ものを選ぶ。 def make_new_array(d) arr = (Seq_List - self).map{|i| [i] + self} return arr.select{|a| a[0, 3].to_i % d == 0} end # * d1 を決め、条件に合う Pandigital 数を完成させる。 # * d1 が 0 の場合は 0 を返す。 def finish arr = Seq_List - self return 0 if arr == [0] return (arr + self).to_i end end # d8d9d10 の候補を ans に収めていく。 ans = Seq_List.permutation(3).select{|arr| arr.to_i % 17 == 0} # pp ans # ans のデータを元に条件に合う配列を作っていく。 [13, 11, 7, 5, 3, 2].each do |d| ans = ans.map{|a| a.make_new_array(d)}.flatten(1) # pp ans end ans = ans.map{|a| a.finish} # pp ans puts ans.inject(:+)

この方法だと、最初に考える数が少ない上に、次第に候補が絞り込まれていくのでかなり短い時間で答えが出ます。(コメントアウトされているコードの "#" を外して実行すると、実際に候補が絞り込まれていく様子が眺められます)

自分の環境では、Ruby 1.9 で約 0.1 秒ほどで答えが出ます。

Problem 37 と同様に、アプローチの仕方を変えるととんでもなく速くなる問題でした。

2009年7月29日 (水)

Project Euler - Problem 42

問題はこちらをご覧ください。


今回は何にも工夫をしていません。

ファイルを読み込んで、単語の値を求めて、三角数かどうかを判定して……問題文のとおりのことしかしてません。

To_Value = "A".ord - 1 class String # 単語の値を求める def to_word_value self.bytes.to_a.map{|char| char - To_Value}.inject(:+) end end class Integer # == 三角数であれば、何番目かを返す。 def triangle? x = ((1 + 8 * self) ** 0.5 - 1) / 2 if x == x.to_i then return x.to_i else return false end end end arr = IO.read("words.txt").delete("\"").split(",") puts arr.map{|s| s.to_word_value}.select{|v| v.triangle?}.size

Project Euler - Problem 41

問題はこちらをご覧ください。


いきなり全ての桁の Pandigital 数を調べる前に、各桁の pandigital 数の構成要素について、ちょっと考えてみましょう。

Pandigital 数のうち、1 桁と 4 桁と 7 桁以外は構成する数を足すとすべて 3 の倍数になります。したがって、これらの数からなる Pandigital 数は 3 の倍数になるため、素数には成りえません。

また、1 桁の Pandigital 数は 1 しかなく、これは当然素数ではありません。

したがって最大の素数を探すのであれば、7 桁と 4 桁のみを探せば良いことになります。

実際の答えは 7 桁の Pandigital 数なのですが、今回のコードでは、7 桁で見つからなかった場合には 4 桁も探すようになっています。

require 'math_tool' def pandigital_prime(d) # d : 桁数 (1 .. d).to_a.reverse.permutation do |arr| num = arr.to_i return num if num.prime? end return nil end puts (pandigital_prime(7) or pandigital_prime(4))

Project Euler - Problem 39, 40

Problem 39 の問題はこちらをご覧ください。

この問題は、「Problem 9」でも使用した、"pythagorean_triples" メソッド("math_tool.rb" を参照のこと)を使えばすぐに答えが出ます。

require 'math_tool' puts (0 ... 1000).to_a.sort_by{|i| pythagorean_triples(i).size}.last

今回は "Enumerable#sort_by" というメソッドを使って見ました。結構メモリを消費するらしいのですが、コードが簡潔に書けるのは良いですね。



Problem 40 の問題はこちらをご覧ください。

今回は、数字を順に文字列に変換して、文字列全体の長さが 1000000 を越えるまで繰り替えしました。

その上で、指定された桁の数を取り出して計算しています。

数の大きさやや文字列の長さに理論上上限のない Ruby の機能があってこその解法だと思います。

str = "0" num = 1 str << num.to_s and num = num + 1 while str.size <= 100_0000 puts (0 .. 6).inject(1){|p, i| p = p * str[10 ** i].to_i}

ところで 1000000 もの長さのある文字列ってどんなのでしょうか?実際に画面に表示させるとどのくらい時間がかかるのでしょうか?

2009年7月23日 (木)

Project Euler - Problem 38 : 0.1s (Ruby 1.9)

問題はこちらをご覧ください。


この記事の中では、連結積を m * (1, 2, ..., n) という形で表すことにします。

すると、n > 1 なので、m は 1 〜 4 桁の数になります。

それぞれの桁の中で連結積の最大値を求める場合、m x 1 すなわち m が大きいほど良いことが分かります。

そこで、m を 1 〜 4 桁の場合に分けて、それぞれ m が大きい方から連結積を求めてみました。

最近私の頭の中では、Panditital 数といえば順列 (permutation) が条件反射的に出てくるようになっています。そこで今回も、連結積を求めるメソッドでは permutation を使っています。

また、二つの式を "and" でつないで、一つの "while 修飾子" で制御しています。

# -*- coding: utf-8 -*- require 'math_tool' # * d : 連結積を m * (1, 2, ..., n) の形で表した場合の m の桁数 # * m が大きい順に連結積を求めていき、連結積が見つかった場合は # その数を、見つからなかった場合には 0 を返す。 def find_max(d) (1 .. 9).to_a.reverse.permutation(d).each do |arr| m = arr.to_i i = 2 arr = arr + (m * i).to_a and i = i + 1 while arr.size < 9 return arr.to_i if arr.pandigital? end return 0 end ans = Array.new (1 .. 4).each{|d| ans.push(find_max(d))} puts ans.max

2009年7月22日 (水)

Project Euler - Problem 37 : 0.09s (Ruby 1.9)

問題はこちらをご覧ください。


この問題は以前 Scheme で Project Euler を解いていた時にも記事にしましたが、改めて Ruby ならこうなるということで……。

とりあえず、問題文を素直に解釈したコードは次のようになりました。

require 'prime' require 'math_tool' class Integer def check? d = 1 while true d = d * 10 q, r = self.divmod(d) return true if q == 0 return false unless (q.prime? and r.prime?) end end end ans = Array.new Prime.each do |n| next if n < 10 unless n.to_a.any?{|i| i > 2 and i.even?} ans.push(n) if (n.prime? and n.check?) end break if ans.size == 11 end puts ans.inject(:+)

このコードで工夫したのは以下の二点です。

  • "Integer#check?" で右から切り詰める場合と左から切り詰める場合を一度に調べる。
  • 調べる数に 2 以外の偶数が含まれている場合は切り詰める過程で必ず素数でなくなるので、予め調べる対象から除外する。

このコードでも Ruby 1.9 なら約 2.4 秒で答えが出ますが、もう少し考える余地があります。


詳しい考察はここを読んでいただきたいのですが、以下のコードのように条件に合う素数を作っていく方法でかなりの高速化が可能です。

# -*- coding: utf-8 -*- require 'math_tool' class Integer # * 左から切り詰める場合の逆の動作でチェックする。 def check? d = 1 begin d = d * 10 m = self % d return false unless m.prime? end until m == self return true end end # * 整数 n の右に数字を付けて素数を作る。 # * 右から切り詰める場合の逆の動作。 def make_new_prime(p) arr = [1, 3, 7, 9].map{|x| p * 10 + x} return arr.select{|i| i.prime?} end lst = [2, 3, 5, 7] # 一桁の素数 arr = Array.new until lst.empty? lst = lst.map{|i| make_new_prime(i)}.inject(:+) arr = arr + lst end ans = arr.select{|i| i.check?} puts ans.inject(:+)

このコードでは Ruby 1.9 で約 0.08 秒で答えが出ます。

数学だけではないのでしょうが、答えを出す方法は一つではないんですよね。

2009年7月21日 (火)

Project Euler - Problem 36 : 0.1s (Ruby 1.9)

問題はこちらをご覧ください。


問題を素直にコーディングすると次のようになると思います。

なお、「先頭に0を含めて回文にすることは許されない」という文面から、「2 進法で表した際に先頭と最後の数字は 1 でなければならない」ということが分かります。従って調べる対象となる数は奇数に限定されます。

(自作の "math_tool.rb" に関してはこちらをご覧ください)

require 'math_tool' ans = Array.new (1 .. 99_9999).step(2) do |i| ans.push(i) if (i.palindromic? and i.to_a(2).palindromic?) end puts ans.inject(:+)

この考え方でも、そこそこの時間で解答が得られます。(Ruby 1.9 で約 0.6 秒でした)

ただし、ちょっと無駄な計算が多い気がします。


例えば、1 〜 100万までの数の中で、10 進法で回文数になる数はたった 1998 個しかありません。

このことは irb で、"math_tool.rb" 読み込んだ上で

(1 .. 100_0000).select{|i| i.palindromic?}.size

とすると分かります。


そこで、まず 10 進法の回文数を作って、その数が 2 進法でも回文数になるかを調べてみましょう。(ここでも偶数は予め除外しました)

require 'math_tool' ans = Array.new (1 .. 999).each do |n| [:odd, :even].each do |flag| a = n.make_palindromic(flag) break if a.even? ans.push(a) if a.to_a(2).palindromic? end end puts ans.inject(:+)

この方法だと、Ruby 1.9 で約 0.1 秒で答が出ます。

いきなり問題を解こうとするのではなく、じっくり腰を据えてアルゴリズムを吟味してみるのも面白いと思いませんか?

2009年7月19日 (日)

Project Euler - Problem 35 : 1.0s (Ruby 1.9)

問題はこちらをご覧ください。


この問題に関しては、以前にも記事を書きました。

基本的な考え方は以前と変わっていませんので、アルゴリズムに関する説明は以前の記事をご覧ください。

わざわざまた記事を書いたのは、コードを見直して、「若干見やすくなったかな?」と感じたので……ただそれだけです。

# -*- coding: utf-8 -*- require 'math_tool' class Array # == 循環素数となる配列か? def circular_prime? len = self.size arr = self * 2 len.times do |i| next if i.zero? return false unless arr[i, len].to_i.prime? end return true end end p_lst = prime_list(100_0000) # 一桁の素数はそのまま循環素数として扱う。 index = p_lst.find_index{|i| i > 9} ans = p_lst[0, index] p_lst.drop(index).each do |i| arr = i.to_a # 偶数または 5 を含む数を除外する。 next if arr.any?{|j| j.even? or j == 5} ans.push(i) if arr.circular_prime? end puts ans.size

2009年7月15日 (水)

Project Euler - Problem 34

問題はこちらをご覧ください。


この問題は Problem 30 と同じ考え方ができます。

まず調べる上限ですが、8 桁以上になると「各桁の数の階乗の和」の桁が元の数の桁に追いつかなくなります。

したがって、9! x 7 までを調べればいいことが分かります。

また、Problem 30 と同じくメモ化をして時間短縮を図りました。

require 'math_tool' fact_sum = (0 .. 9).map{|i| i.factorial} ans = Array.new (10 .. fact_sum[9] * 7).each do |n| q, r = n.divmod(10) sum = fact_sum[q] + fact_sum[r] ans.push(n) if n == sum fact_sum[n] = sum end puts ans.inject(:+)

Project Euler - Problem 33

問題はこちらをご覧ください。


今回は何の工夫もしていません。問題をそのままコードにしてみました。

require 'mathn' # n : numerator 分子, d : denominator 分母 def nontrivial?(n, d) nq, nr = n.divmod(10) dq, dr = d.divmod(10) return false if nr != dq or dr.zero? return n/d == nq/dr end ans = Array.new (10 .. 98).each do |n| # n : 分子 (n + 1 .. 99).each do |d| # d : 分母, n/d < 1 なので n < d ans.push(n/d) if nontrivial?(n, d) end end puts ans.inject(:*)

Ruby では "mathn.rb" を読み込んでおけば、分数の計算を普通にできます。分数を足していけば自動的に約分をしてくれます。

2009年7月14日 (火)

Project Euler - Problem 32

問題はこちらをご覧ください。


ゆっくり考えると分かることですが、「掛けられる数」、「掛ける数」、「積」の組み合わせが 9 桁になるのは「1 桁 x 4 桁 = 4 桁」と「2 桁 x 3 桁 = 4 桁」のみです。

そこでまず総当たりで調べてみます。

(自作の "math_tool.rb" に関してはこちらをご覧ください)

require 'math_tool' def check(a_min, a_max, b_min, b_max) ans = Array.new (a_min .. a_max).each do |a| (b_min .. b_max).each do |b| c = a * b break if c > 9999 # 積は 4 桁でなければならない。 d = a.to_a + b.to_a + c.to_a ans.push(c) if (d.size == 9) and d.pandigital? end end return ans end ans = check(1, 9, 1234, 9876) + check(12, 98, 123, 987) puts ans.uniq.inject(:+)

これでも Ruby 1.9 で約 0.5 秒ほどで答えは出るのですが、例えば「1 x 1234」といった明らかに数字が重なる組み合わせも調べているので、少し無駄な気がします。


そこで重複を避けるために、順列を使って掛けられる数と掛ける数を作ってみます。

require 'math_tool' # m 桁 x n 桁の積を考える。 def product(m, n) ans = Array.new seq = (1 .. 9).to_a seq.permutation(m) do |arr_a| (seq - arr_a).permutation(n) do |arr_b| c = arr_a.to_i * arr_b.to_i break if c > 9999 # 積は 4 桁でなければならない。 ans.push(c) if (arr_a + arr_b + c.to_a).pandigital? end end return ans end ans = product(1, 4) + product(2, 3) puts ans.uniq.inject(:+)

この方法だと、掛けられる数と掛ける数に重複がないので、その分計算量が減らせます。 Ruby 1.9 で約 0.15 秒ほどで答えが出ます。


順列や組み合わせが手軽に使えるので、こういった問題を解くときは Ruby で解くと楽ですね。

2009年7月12日 (日)

Project Euler - Problem 31

問題はこちらをご覧ください。


以前「計算機プログラムの構造と解釈」を読んだことがあって、その中にちょうど「両替問題」の解説がありました。

今回はそのコードを Ruby に書き直したもので、答を出しました。

ということで、今回は自分の頭を使っていませんので、コードは記載しません。

Project Euler - Problem 30

問題はこちらをご覧ください。


まず、調べる数の上限を探さなければいけません。

実際に計算してみると分かるのですが、元の数が 7 桁以上になると「各桁を 5 乗した和」の桁数が追いつかなくなります。

そこで、調べる数の上限は "95 x 6" となります。

(自作の "math_tool.rb" に関してはこちらをご覧ください)

require 'math_tool' LIMIT = 6 * (9 ** 5) def check?(n) sum = 0 n.to_a.each{|i| sum = sum + i ** 5} return n == sum end puts (2 .. LIMIT).select{|i| check?(i)}.inject(:+)

何の工夫もしていないこのコードでもそこそこ速いんですが、何か工夫をする余地はないのか、いろいろ考えてみました。


例えば……

123, 132, 213, 231 などの数は「各桁を 5 乗した和」が同じ値になります。

これらの同じ数で構成されている数の計算は重複していて無駄ですから、これを排除できないか?

結論から言うと、数の構成要素を調べたりすることでかなり時間をくってしまって実効速度はかえって遅くなってしまいました。


次に考えたのは、1234 の「各桁を 5 乗した和」は 123 の「各桁を 5 乗した和」に 4 の 5 乗を足したものですよね。

そこで、小さい順に数を調べていって、その結果を配列に溜め込んでいき、後の計算に利用することで、計算量を減らせないかと考えました。

この方法は結構うまくいきました。(ちなみに一桁の数を 5 乗したものが元の数と同じになることがないのは自明ですので初めからチェックしていません)

require 'math_tool' LIMIT = 6 * (9 ** 5) sum = (0 .. 9).map{|i| i ** 5} ans = Array.new (10 .. LIMIT).each do |n| q, r = n.divmod(10) s = sum[q] + sum[r] ans.push(n) if n == s sum[n] = s end puts ans.inject(:+)

何も工夫しないコードが約 2.5 秒かかっていたのが、このコードでは約 0.5 秒ほどで答が出ます。

そのかわり、約 35 万個の要素を持つ配列を使用するので、メモリーを消費することになりますが……。

Project Euler - Problem 29

問題はこちらをご覧ください。


この問題は、28 = 44 = 162といったものを探しいって取り除いていくべきでしょうが、二重ループの総当たりでも大した時間がかからなかったので、それで終わらせてしまいました。

なんの工夫もしていないので、恥ずかしくてコードをお見せできません。

2009年7月 9日 (木)

Project Euler - Problem 28

問題はこちらをご覧ください。


この問題は、辺の数と四隅の数字を「じーっ」と眺めていると解けます。

辺の数 : 四隅の数 : 公差 3 : 3, 5, 7, 9 : 2 5 : 13, 17, 21, 25 : 4 7 : 31, 37, 43, 49 : 6

このような法則が見つかりますのでこれを使ってコードを書いてみました。

sum = 1 i = 1 (3 .. 1001).step(2) do |m| d = m - 1 4.times do i = i + d sum = sum + i end end puts sum

銀河英雄伝説

最近、「銀河英雄伝説」をまた読み出しました。

「銀英伝」との最初の出会いは高校生のころだったと思います。友人に勧められて読み始めたのでした。

当時は「グイン・サーガ」にはまっていた時期で、「グイン・サーガ」と比べて文章が硬くて密度が濃かったので、結構読むのに苦労した覚えがあります。でもストーリーの面白さや登場人物の魅力に惹かれて、気がつけば本編をすべて読んでいました。

その後、大好きな道原かつみさんが漫画化したものも読みました。おかげで私の頭の中ではヤン、ユリアン、ラインハルト、キルヒアイスなど、主だった登場人物の顔は道原かつみ版の顔以外はありえない状況です。


創元 SF 文庫で復活したのは知っていたのですが、何となく買いそびれていました。でも、やっぱりもう一度読みたくなって、先日買ってしまいました。

自分が年をとったせいか、以前は硬くて読みにくいと思っていた文章も、それほど苦労せずに読めています。

だいたいのストーリーは覚えているつもりなので、今度はじっくりと腰を据えて、細かい内容まで目を通しながら読んでいければと思っています。

ちなみに私の好きな登場人物はヤンとシェーンコップです。自分と一緒でちょっと屈折した人が好きなのかな?

2009年7月 8日 (水)

Project Euler - Problem 27

問題はこちらをご覧ください。


総当たりで a と b を調べてもいいのですが、ちょっと考えると a と b の探索範囲をかなり絞り込めます。

以前 Scheme で解いた時の考察をここにも書きましたが、あの後さらに思いついたことがあったので、改めて考察をしていきたいと思います。


自分なりの考察を書いていく前に、まずは総当たりでどのくらい時間がかかるか試してみましょう。

require 'math_tool' max = [1, 41, 40] # max = [a, b, n], n : n² + an + b が合成数となる最小の数 -999.upto(999) do |a| -999.upto(999) do |b| n = 0 n = n + 1 while (n * n + a * n + b).prime? max = [a, b, n] if n > max[2] end end puts(max[0] * max[1])
real 0m5.732s user 0m5.580s sys 0m0.036s

と、いうことで Ruby 1.9 で約 5.7 秒かかりました。


では、a と b の探索範囲について考えてみましょう。

なお、ここから先は

v = n² + an + b … (1)

として考えていきます。


まずは b の探索範囲から考えてみます。

n = 0 の時、(1) の式は v = b となります。この時 v が素数となるためには、当然 b も素数でなければなりません。したがって b は 1000 以下の素数となります。

さらに、b が偶数の場合、n が偶数の時には v も偶数となるため、n は 2 以上の値を取ることができません。そこで b = 2 の場合は初めから考えなくても良さそうです。

まとめると、b は 1000 未満の奇素数ということになります。

いきなり b の探索範囲が大幅に減りました。(1998個 → 167個)


次に a について考えてみます。

(1) の式は v = n(n + a) + b と変形できます。

n と n + a がともに奇数の場合、b が奇素数のため v は偶数となり、v が素数となるのは v = 2 の場合のみになります。

したがって、より多くの素数を探すためには、n と n + a のどちらかは偶数である必要があります。ところが a が偶数の場合、n が奇数の時 n + a も奇数となってしまうため、この条件に反してしまいます。

以上のことから、a は奇数でなければなりません。

ということで a の探索範囲はここで半分になりました。


さらに、例題として n = 39 が成立する式が示されているので、n > 39 を満たす式を見つけないと、問題自体が成立しません。

そこで (1) の式に n = 40 を代入してみると、v = 40² + 40a + b となります。

v は素数ですので v > 0 とすることができます。したがって、40² + 40a + b > 0 となります。この式を変形すると、a > -40 - b/40 となります。

また、n = b の時、v = b² + ab + b = b(b + a + 1) となり、v は合成数となってしまいます。したがって n は b 以上になることはできません。

このことから、b を大きい方から調べていった場合、b がその時点での n の最大値より小さくなった場合、そこで探索を中止しても良いと考えられます。

以上のことを踏まえて書いたコードは次のようになりました。

require 'math_tool' max = [1, 41, 40] # max = [a, b, n], n : n² + an + b が合成数となる最小の数 prime_list(1000).reverse_each do |b| break if b < max[2] a_min = -40 - b.div(40) (a_min ... 1000).each do |a| next if a.even? n = 1 n = n + 1 while (n * n + a * n + b).prime? max = [a, b, n] if n > max[2] end end print("a * b = #{max[0] * max[1]}\n")

このコードを実行すると、

real 0m0.567s user 0m0.508s sys 0m0.012s

ということで、約 0.56 秒で答えが出ました。総当たりで調べたときの 1/10 の時間で答えが出ました。


コードを書く前にいろいろ考えて、アルゴリズムを吟味したり探索範囲を絞っていって、実際に実効速度が速くなるととてもうれしいものです。

一度解いた問題も、「もっといい解法はないか?」と考え直すことが多いので、ひとつの問題を解くのに結構時間がかかっています。

まあ、いろいろ考えるのが好きなので、Project Euler はじっくりと取り組んでいこうと思っていますけど……。

2009年7月 3日 (金)

Project Euler - Problem 26

問題はこちらをご覧ください。


基本的には分子をどんどん 10 倍していって分母で割ったときに余りが 1 になるところを探していきます。(余りが 1 になったところからまた繰り返しが始まるので……)

ただし、分母を素因数分解したときに、因子に 2 や 5 が含まれているとそのままの考え方では通用しなくなります。

そこで、循環節の長さを考える場合は、次のように分けて考えると分かりやすいと思います。

  1. 分母 d が 2 または 5 の因子を含まない場合
  2. 分母 d が 2 または 5 以外の因子を持たない場合
  3. その他の場合

1. の場合は (10 ** n).modulo(d) == 1 を満たす最小の n がそのまま循環節の長さになります。

例えば、分母 d が 7 の場合、n = 6 の時に上の式が成立します。実際の計算でも循環節はの長さは 6 になります。

2. の場合は割りきれてしまうので、循環節の長さは 0 となります。

3. の場合は、分母 d から 2 や 5 の因子を除去した数字で循環節を考えます。

例えば、分母 d が 15 だった場合、

1/15 = 1/(5 * 3) = 1/5 * 1/3 = 0.2 * 0.3333... = 0.0666...

となり、分母 d が 3 の時と同じ結果になります。


この問題を扱ったブログの中に「『フェルマーの小定理』を使えばいい……」といった言葉が散見されましたが、ここにも書いてあるように、「フェルマーの小定理」は分母が素数の時にしか適応できません。分母が合成数の場合まで考えるなら、「フェルマーの小定理」を拡張した「オイラーの定理」を使って考えるべきです。

まあ、「オイラーの定理」で検討すると、「分母が素数の時の方が、分母が合成数の時よりも循環節が長くなりそうだ」ということに気づくのですが……

ただし、「フェルマーの小定理」も「オイラーの定理」も循環節の最小値を保証しているわけではありません。

例えば分母が 11 の場合、「フェルマーの小定理」に当てはめると循環節の長さは "10" になりそうですが、実際には

1.0/11 = 0.090909...

となるので、循環節の長さは "2" になります。

ですから、「フェルマーの小定理」をそのまま適応するだけでは、この問題は解けません。地道に計算するしかないようです。

def count(m) m = m / 2 while m.even? m = m / 5 while m.modulo(5).zero? return 0 if m == 1 n = 10 c = 1 until n.modulo(m) == 1 n = n * 10 c = c + 1 end return c end max = [0, 0] 999.downto(2) do |i| break if i < max[1] c = count(i) max = [i, c] if c > max[1] end puts max[0]

「フェルマーの小定理」や「オイラーの定理」を検討すると、循環節の長さが分母の数以上になることはないことが分かります。

そこでこのコードでは、分母を大きい方から調べていって、分母が循環節の長さの最大値以下になった時点で計算を中断しています。

2009年7月 2日 (木)

Project Euler - Problem 25

問題はこちらをご覧ください。


フィボナッチ数列の求め方は Problem 2 の方法がそのまま使えます。(ただし、 Problem 2 では初めの数字の並びが違うので要注意ですが……)

求めた数値の桁数を数えるのではなく、直接 10 の 999 乗と比較した方がずっと速く答が出せました。

こんな方法ができるのも、Ruby の扱える整数に上限のない Ruby ならではでしょうか?

LIMIT = 10 ** (1000 - 1) a, b = 1, 0 i = 1 while a < LIMIT a, b = a + b, a i = i + 1 end puts i

Project Euler - Problem 24

問題はこちらをご覧ください。


順列といえば "permutation" ということで、こんなコードを書いてみました。

require 'math_tool' Index = 100_0000 (0 .. 9).to_a.permutation.each_with_index do |arr, i| if i + 1 == Index then puts arr.to_i break end end

これでもそこそこ速いんですが、"permutation" は律儀にすべての順列を当たってくれるので、今回のように「100 万番目だけを知りたい」といった場合には、少々無駄な処理をしています。

そこで、「n 番目」だけを知るためのコードを書いてみました。

require 'math_tool' Index = 100_0000 class Array # * 配列 arr を順列として並び替えた時の n 番目を返す。 def permutation_count(n) n = n - 1 arr = Array.new(self) ans = Array.new until arr.empty? a = (arr.size - 1).permutation_size q, n = n.divmod(a) ans.push(arr.delete_at(q)) end return ans end end puts (0 .. 9).to_a.permutation_count(Index).to_i

この方法だと、Ruby 1.9 で約 0.05 秒ほどで答が出ます。


※自作の "math_tool.rb" に関してはこちらをご覧ください。

« 2009年6月 | トップページ | 2009年8月 »

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ