Bash
ProjectEuler
数学

Project Euler Q26 【逆数の循環節 その1】

Project Eulerをワンライナーで解いてみる。
間違っていたらコメントください。

問題

単位分数とは分子が1の分数である. 分母が2から10の単位分数を10進数で表記すると次のようになる.

\frac{1}{2} = 0.5\\
\frac{1}{3} = 0.(3)\\
\frac{1}{4} = 0.25\\
\frac{1}{5} = 0.2\\
\frac{1}{6} = 0.1(6)\\
\frac{1}{7} = 0.(142857)\\
\frac{1}{8} = 0.125\\
\frac{1}{9} = 0.(1)\\
\frac{1}{10} = 0.1

$0.1(6)は 0.166666...$ という数字であり, 1桁の循環節を持つ. $1/7$ の循環節は6桁ある.

$d < 1000$ なる $1/d$ の中で小数部の循環節が最も長くなるような d を求めよ.

アプローチ

1.まずフェルマーの小定理を用います。
習った気がするけどさすがにもう覚えてない。。

フェルマーの小定理

p が素数,a が任意の自然数のとき\\
a^p≡a\;mod\;p\\
特に,a が p と互いに素な自然数のとき\\
a^{p−1}≡1\;mod\;p

a=10,pを2,5以外の任意の素数とする。
(pが2,5の場合は1以外の共通の約数を持つ為、aと互いに素にならない。)

すると、$p-1$が循環節の桁数となる。

2.循環小数になる数はリストアップできたが、まだ不十分である為
真の循環節の桁数を算出する。
例えば$1/13 = 0.(076923)$であるが、この循環節の桁数は$13-1=12$ではない。

解答

seq 3 999 |
grep -v "^5$" |
factor |
awk -M 'NF==2{printf $2" ";for(i=1;i<=999;i++){v=(10^i)%$2;if(v==1){printf i" ";break}};print ""}' |
sort -k2,2n |
tail -1 |
awk '$0=$1'
983

そうだ、俺mod苦手だった。。

※2018/01/22修正
最後の出力を答えだけにした

答え合わせ

こちらのサイト様と一致していればOKとした。
http://kingyojima.net/pje/026.html

参考にさせて頂いたサイト様

http://www004.upp.so-net.ne.jp/s_honma/mathbun/mathbun36.htm
フェルマーの小定理の証明と例題 _ 高校数学の美しい物語