循環小数

自明の問題はつまらないので、ちょっとぐらい難しい奴をやろうと思って、正解者数が少なめの「d<1000であるdに対して、1/dの循環小数の最大循環桁数は？」というのを探してみた。オイラープロジェクトの26問目。そんなに難しくないだろうと思ったけど、いろいろ考え出すと単純じゃないことが分かった。

たとえば、d=7では、

1/7=0.(142857)

で6桁が循環してる。同様に1/3（0.3333……）は1桁が循環してる。

1/11=0.(90)
1/19=0.(526315789473684210)
1/987=0.(10131712259371833839918946301925025329280648429
58459979736575481256332320162107396149949341438703140830
80040526849037487335359675785207700)

とかいう感じ。ちょっと調べ見た感じ、循環には2つのパターンがある。

0.XYZabcabcabc   -- (1)
0.abcabcabc      -- (2)

いきなり循環を始める(2)のタイプと、頭に数桁の非循環部がある(1)のタイプがある。で、とりあえず(2)だけ調べることにした。意外に重たい処理なので、(1)をやるのは若干ためらわれて、まだやってない。

Rubyにはbigdecimalという標準ライブラリがある。浮動小数点を文字列として扱って好きなだけ桁数を増やせる。まあ、いろいろ力業。

require 'bigdecimal'

# 0.abcdabcd....
# 0.XYZabcdabcd....

figs = 2100

def rep?(str)
  (1..(str.length / 2)).each do |i|
    ary = str.scan(/.{#{i}}/)
    u = ary.uniq
    if u.size == 1 then
      return i, u
    end
  end
  return 0
end

max = 0

(1..1000).each do |i|
  a = BigDecimal("1",figs) / BigDecimal(i.to_s)
  b = a.to_s.sub(/^0\./,"").sub(/E.*/,"")
  c = rep?(b)
  print "1/", i, "\n"
#  print "figs: ", a, "\n"
  print "repeating: ", c, "\n"
  max = c[0] if (c[0] > max)
end

print "max: ", max, "\n"

出力は、こんな感じ。

1/217
repeating: [30, ["460829493087557603686635944700"]]
1/218
repeating: [108, ["458715596330275229357798165137614678899082568807339449541284403669
724770642201834862385321100917431192660550"]]
1/219
repeating: [8, ["45662100"]]
1/220
repeating: [2, ["45"]]
1/221
repeating: [48, ["452488687782805429864253393665158371040723981900"]]
1/222
repeating: [3, ["450"]]
1/223
repeating: [222, ["4484304932735426008968609865470852017937219730941704035874439461883
408071748878923766816143497757847533632286995515695067264573991031390
134529147982062780269058295964125560538116591928251121076233183856502
24215246636771300"]]
1/224
repeating: 0
1/225
repeating: [1, ["4"]]
1/226

見ていると、どうも1/dの循環桁数は必ず(d-1)以下になっているようで、しかも、かなりの頻度で(d-1)桁の繰り返しが登場しているっぽい。というわけで、正解は990〜1000個の繰り返しじゃないかと思うのだけど、全然ツメが甘い感じ。