素数の逆数の場合は、小数点第1位から循環が始まるが、合成数の場合、
例えば 6の逆数は、0.1[6]となり、循環しない部分と循環する部分が混在している。
前者を純循環小数、後者を混循環小数と呼ぶ。
6のような数についても循環節を見つけるためにはどうしたらよいか。
まず、何によって循環性を検出するかを考える。
いくつかの数を例にとり、商と余りを順に求めていくと、以下のようになる。
6 | 7 | 12 | 13 | ||||
---|---|---|---|---|---|---|---|
商 | 余り | 商 | 余り | 商 | 余り | 商 | 余り |
1 6 6 | 4 4 4 |
1 4 2 8 5 7 1 |
3 2 6 4 5 1 3 |
0 8 3 3 | 10 4 4 4 |
0 7 6 9 2 3 0 |
11 9 12 3 4 1 11 |
この表より、商と余りが繰り返された時点で、循環節と判断できることがわかる。
したがって、前のプログラムを以下のように修正すればよい。
プログラムは以下のとおり。
10 ' cycle_m 20 ' 30 input N 40 dim Q%(N),R%(N) 50 for I=1 to N:Q%(I)=0:R%(I)=0:next I 60 ' 70 A=1 80 B=A*10\N:A=res 90 Q%(A)=B:R%(A)=A 100 ' 110 B=A*10\N:A=res 120 if and{Q%(A)=B,R%(A)=A} then 160 130 Q%(A)=B:R%(A)=A 140 goto 110 150 ' 160 S=Q%(A):T=R%(A) 170 A=1:F=0 180 B=A*10\N:A=res 190 if and{B=S,A=T} then print "[";:F=1 200 Q%(A)=B:R%(A)=A:print B; 210 if F=0 then 180 220 ' 230 B=A*10\N:A=res 240 if and{B=S,A=T} then print "]":end 250 Q%(A)=B:R%(A)=A:print B;:goto 230
循環節の長さを表す公式は以下のとおりである。
n が 2, 5 以外の素因子を持つ場合、
n = 2a・5b・n', (10, n') = 1
k = max {a, b}
e = mod n' での 10 の位数
とおくと、m/n は、はじめの k桁は循環せず、k+1 から循環し、循環節の長さは e である。
証明は、和田 秀男、 『数の世界−整数論への道』参照のこと。
前 | この章の目次 | 次 |
---|