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
フェルマーの小定理の証明と例題 _ 高校数学の美しい物語