#円周率
円周率。ただの定数であるがただの定数でない魅力と謎が詰まっている偉大な数です。
証明は簡単でないが一番馴染み深い無理数であり超越数なのではないのでしょうか?

##円周率の値
様々な方法で求められてきた歴史があります。今回の記事とはそこまで関係がないので具体的な方法を述べたりしませんが, 普通のノートpcでも現代のスペックであれば100桁くらいは簡単に(秒で)求めることができます。なぜそれで求められるか?の理論は普通に難しかったりしますが計算方法さえ認めてしまえば簡単です。
一応値を述べておきますが
π=3.141592653589 793238462643 383279502884 197169399375 105820974944 592307816406 286208998628 034825342117 067982148086 513282306647...と続いていきます。

##円周率の近似分数
今回の本題の近似分数とはなんぞや。という話です。厳密にやろうとすれば大学数学で勉強する実数の(有理数, 無理数の)稠密性なんかを考える必要がありますが直感的な説明だけで済ませますね。

まず円周率は無理数です。これも認めます。完全にランダムかどうかはわかっていません。n桁目の数はランダムであるといわれています.
一方有理数は必ずどこがでループが出てきます. 1÷6=0.666...と6のループが出てきますし, 123÷999=0.123123123...と123のループが出てきます。
6÷2なんかも6÷2=3=2.999...と書くこともできるので割り切れたとしてもループが出てくるんですね.
ループの有り無しは有理数と無理数の大きな違いの一つです。
このように有理数無理数とは全然違う数なのですが, 円周率という無理数にいくらでも近い有理数を作ることはできます。稠密なんて難しい言葉で言ったりするんですが, 雑に説明すると有理数の数列Anを

A_1=3, \quad A_2=3.1, \quad A_3=3.14,\quad ...

と定めればこの数列の極限は円周率と一致するんですね. 有理数しか現れないのに極限は無理数と同じといわれると変な感じが一瞬しますが, まあ直感的には納得できるのかなあと思います.

つまるところ, 円周率にいくらでも近い分数をつくれる.　というわけです.

##面白い事実
ここで以下のような問題を考えましょう

\text{集合$F_n$を以下のように定める.}\\
F_n:=\{\frac{a}{b}\mid 1 \leq a,b \leq 10^n-1,\quad a,b\in \mathbb{Z} \}

とする.
このとき,

F_n\text{の元で最も}\pi\text{に近いのは何だろう?}

つまり

F_1\text{とは1÷1から9÷9までで作れる数の集合で}
F_2\text{とは1÷1から99÷99までで作れる集合.}

でありこのように分母分子の桁数に制限を与える中で最も円周率に近い分数とは何なのだろう?という問題です.
それをp(n)とでもしておきましょう.

そして以下のような事実が知れれています。

\begin{align*}
p(1)&=3/1\\
p(2)&=22/7\\
p(3)&=355/113\\
p(4)&=355/113=p(3)
\end{align*}

つまり355/113とはものすごく精度がよい近似値である!!というわけです!!
これは個人的にとても面白い事実です. だって分母分子4桁まで使ってもよいのに3桁÷3桁が精度の良い分数なんですから。
しかし, これは事実として知っているだけで「ほんまに？」と思ったわけですよ.ならプログラムの出番ですね.プログラムで総当たりで調べましょう

###プログラムを作る前の考察
今回は4桁/4桁までを調べるので総当たりの計算量は10000*10000=10^8程度
このくらいなら総当たりでも調べられますが今後p(8)なんかも求めたくなるかもしれないので多少計算を省ける工夫をしてみましょう.

工夫1:分子を分母*3から探索を始める
工夫2.途中で打ち切る動作を入れる
以上!多分これだけでも相当計算量減ると思うのでこれで実装していきます!

###プログラム
プログラムの実力が圧倒的に足りないので愚直に書いていきます.

pi=3.141592653589793#このくらいあれば十分かなあ

n=int(input())
check=((10**n)-1)//3
ans=100
ans_list=[100,1]
for i in range(1,check+1):#こっちが分母
    for j in range(3*i,(10**n)):
        frac=j/i
        if abs(frac-pi)<abs(pi-ans):
            ans=frac
            ans_list=[j,i]
        else:
            if frac>ans:
                break
print(ans)
print(ans_list)

###実行結果

1
>>>3.0
>>>[3, 1]

2
>>>3.142857142857143
>>>[22, 7]

3
>>>3.1415929203539825
>>>[355, 113]

4
>>>3.1415929203539825
>>>[355, 113]

5
>>>3.1415926415926414
>>>[99733, 31746]

本当に4桁÷4桁でも355/113が最強なんですね

##ふざけたまとめ
355/113はすごい数字ですね. ちなみに僕のiPhoneの暗証番号昔355113でした.

##まじめなまとめ
n=5あたりで相当遅いので改良してくださる方がいれば教えてもらえると幸いです.

###追記
mathにmath.piなんてのあるんですね. ならこれでよろしいとおもいます.

import time
import math

n=int(input())
start=time.time()
pi=math.pi
check=((10**n)-1)//3
ans=100
ans_list=[100,1]

for i in range(1,check+1):#こっちが分母
    for j in range(int((pi)*i),(10**n)):
        frac=j/i
        if abs(frac-pi)<abs(pi-ans):
            ans=frac
            ans_list=[j,i]
        else:
            if frac>ans:
                break
print(ans)
print(ans_list)
end=time.time()
print(end-start)

めちゃくちゃ早くなったのでp(8)まで求めてしましました

6
>>>3.141592653581078
>>>[833719, 265381]

7
>>>3.1415926535898153
>>>[5419351, 1725033]

8
>>>3.1415926535897927
>>>[80143857, 25510582]

長年の謎が解けた気がして気持ちいです.