Pi. It's just a constant, but it's not just a constant. It's a great number full of charm and mystery. It's not easy to prove, but isn't it the most familiar irrational number and transcendental number?
There is a history that has been sought in various ways. Since it has nothing to do with this article, I will not explain the specific method, but even with a normal notebook PC, if it is a modern specification, about 100 digits can be easily obtained (in seconds). The theory of why it is required is usually difficult, but it is easy once the calculation method is accepted. I will mention the value for the time being π = 3.141592653589 793238462643 383279502884 197169399375 105820974944 592307816406 286208998628 034825342117 067982148086 513282306647 ... and so on.
What is the approximate fraction of this subject? It is a story. If you want to do it strictly, you need to think about the density of real numbers (rational and irrational numbers) that you study in university mathematics, but you can just explain it intuitively.
First of all, pi is an irrational number. I also admit this. I don't know if it's completely random. The number in the nth digit is said to be random. On the other hand, for rational numbers, where does the loop always come out? 1 ÷ 6 = 0.666 ... and 6 loops come out, and 123 ÷ 999 = 0.123123123 ... and 123 loops come out. You can also write 6 ÷ 2 as 6 ÷ 2 = 3 = 2.999 ..., so even if it is divisible, a loop will appear. The presence or absence of a loop is one of the major differences between rational numbers and irrational numbers. In this way, it is a completely different number from rational numbers and irrational numbers, but it is possible to create rational numbers that are as close as possible to irrational numbers called pi. Dense is often said in difficult words, but to explain it roughly, the rational sequence An
A_1=3, \quad A_2=3.1, \quad A_3=3.14,\quad ...
If you decide, the limit of this sequence matches the circumference ratio. It seems strange for a moment when it is said that the limit is the same as an irrational number even though only rational numbers appear, but it is intuitively convincing. I wonder if.
After all, you can make fractions that are as close to pi as you like.
Let's consider the following problem here
\text{set$F_n$Is defined as follows.}\\
F_n:=\{a/b\mid b\neq 0,\quad 0 \leq a,b \leq 10^n-1,\quad a,b\in \mathbb{Z} \}
And. At this time,
F_n\text{Most under}\pi\text{What is close to?}
In other words
F_1\text{Is a set of numbers that can be made from 1 ÷ 1 to 9 ÷ 9}
F_2\text{Is a set that can be made from 1 ÷ 1 to 99 ÷ 99.}
So what is the closest fraction to the pi in limiting the number of digits in the denominator and numerator? Let's call it p (n).
And the following facts are known.
\begin{align*}
p(1)&=3/1\\
p(2)&=22/7\\
p(3)&=355/113\\
p(4)&=355/113=p(3)
\end{align*}
In other words, 355/113 is an extremely accurate approximation !! This is a very interesting fact personally, because you can use up to 4 digits in the denominator and numerator, but 3 digits ÷ 3 digits is an accurate fraction. However, just knowing this as a fact made me wonder, "Really?" Then the program comes into play. Let's brute force the program.
This time, we will check up to 4 digits / 4 digits, so the amount of calculation per round robin is about 10000 * 10000 = 10 ^ 8. If this is the case, you can check it by brute force, but you may want to ask for p (8) in the future, so let's devise a way to omit some calculations.
Ingenuity 1: Start searching for the numerator from the denominator * 3 Ingenuity 2. Insert an action to stop in the middle That's it! I think that this alone will reduce the amount of calculation considerably, so I will implement it with this!
The ability of the program is overwhelmingly insufficient, so I will write it honestly.
pi=3.141592653589793#I wonder if this is enough
n=int(input())
check=((10**n)-1)//3
ans=100
ans_list=[100,1]
for i in range(1,check+1):#This is the denominator
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]
Even with 4 digits ÷ 4 digits, 355/113 is really the strongest.
355/113 is a great number. By the way, my iPhone PIN was 355113 a long time ago.
It's quite slow around n = 5, so I would appreciate it if anyone could improve it.
There is math.pi in math. Then I think this is all right.
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):#This is the denominator
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)
It became so fast that I asked for p (8)
6
>>>3.141592653581078
>>>[833719, 265381]
7
>>>3.1415926535898153
>>>[5419351, 1725033]
8
>>>3.1415926535897927
>>>[80143857, 25510582]
I feel that the mystery of many years has been solved.
Recommended Posts