About approximate fractions of pi

Pi

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?

Pi value

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.

Approximate fraction of pi

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.

Interesting facts

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.

Consideration before making a 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!

program

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)

Execution result

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.

Playful summary

355/113 is a great number. By the way, my iPhone PIN was 355113 a long time ago.

Serious summary

It's quite slow around n = 5, so I would appreciate it if anyone could improve it.

Postscript

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

About approximate fractions of pi
About approximate fractions of pi
About all of numpy
About assignment of numpy.ndarray
About MultiIndex of pandas
About variable of chainer
Display of fractions (list)
About max_iter of LogisticRegression () of scikit-learn
About the ease of Python
About Japanese support of cometchat
About various encodings of Python 3
About all of numpy (2nd)
About cost calculation of MeCab
About the components of Luigi
About HOG output of Scikit-Image
About the features of Python
About data management of anvil-app-server
About the return value of pthread_mutex_init ()
About the return value of the histogram.
About the basic type of Go
About the upper limit of threads-max
About circular crossover of genetic algorithms
About the behavior of yield_per of SqlAlchemy
About import error of PyQt5.QtWidgets (Anaconda)
About the size of matplotlib points
About color halftone processing of images
About the basics list of Python basics