4 ms·

I decided to try every integer denominator less than 1,000,000 to see how rare this is. A few fun facts: Constraining denominators to 4 digits (<10,000) there

I decided to try every integer denominator less than 1,000,000 to see how rare this is. A few fun facts: Constraining denominators to 4 digits (<10,000) there are NO better fractions than 355/113. Constraining denominators to 5 digits (<100,000) and excluding multiples (eg. 710/226), 1601 fractions exist which better approximate pi than 355/113. The best is 312689/99532 which is off by 2.914335439641036e-11 Considering denominators up to 6 digits <1,000,000 and excluding multiples, there are 162,141. The best is 3126535/995207 which is off by 1.1426415369442111e-12 This was done somewhat subptimally with a potentially buggy implementation in python. It's in a gist here: https://gist.github.com/thecadams/df3e12571294e3f7a9f5c07e91ebbfd0 https://gist.github.com/thecadams/df3e12571294e3f7a9f5c07e91...

robin_reala 4y ago
Out of interest, do you get the same sort of results for other numbers that look a little like pi (small irrational number)? Or is this something peculiar to pi?
LeoPanthera 4y ago
I did a similar thing (also with some ugly python) to generate the closest integer fraction approximations in increasing length: 3/1 = 3.0 22/7 = 3.142857142857143 311/99 = 3.1414141414141414 355/113 = 3.1415929203539825 99733/31746 = 3.1415926415926414 312689/99532 = 3.1415926536189365 The jump in length from 355/113 to the next one is quite noticeable, and it does not happen with other irrational numbers, such as e, which progress more smoothly: 8/3 = 2.6666666666666665 19/7 = 2.7142857142857144 87/32 = 2.71875 193/71 = 2.7183098591549295 878/323 = 2.718266253869969 1457/536 = 2.718283582089552 2721/1001 = 2.7182817182817183 25946/9545 = 2.7182818229439496 49171/18089 = 2.718281828735696 271801/99990 = 2.7182818281828185
- Someone 4y ago
  You missed 13/4 = 3.25, 16/5 = 3.2, 19/6 = 3.16667, 179/57 = 3.14035, 201/64, 223/71, 245/78, 267/85, 289/92, 333/106, 52163/16604 https://shreevatsa.wordpress.com/2011/01/10/not-all-best-rational-approximations-are-the-convergents-of-the-continued-fraction/ https://shreevatsa.wordpress.com/2011/01/10/not-all-best-rat...
  - LeoPanthera 4y ago
    I intentionally omitted fractions that were less accurate than others of equal length.
    - Someone 4y ago
      You’re discriminating against bases other than base 10 ;-) Why would the base you write the numbers down in affect whether a rational number is considered “best so far”?
      - genewitch 4y ago
        π/1, then. in base π.
      - crdrost 4y ago
        You don't need to discriminate to do it, as mentioned in comments below about continued fractions. In brief, π can be represented as a stream of integers, [ 3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, 1, 84, 2, 1, 1, 15, 3, 13, 1, 4, 2, 6, 6, 99, 1, 2, 2, 6, 3, 5, 1, 1, 6, 8, 1, 7, 1, 2, 3, 7, 1, 2, 1, 1, 12, 1, 1, 1, 3, 1, 1, 8, 1, 1, 2, 1, 6, 1, 1, 5, 2, 2, 3, 1, 2, 4, 4, 16, 1, 161, ...] To process into a rational approximation you want to maintain the two last aproximations a/b, c/d, and to get the first two numbers right you want to start with a/b = 0/1 and c/d = 1/0, zero and infinity. When you come to a number N in the sequence you form the new rational approximation (N*c + a)/(N*d + b). So you absorb 3 to generate 3/1, then you absorb 7 to generate (3×7+1)/(7×1+0)=22/7, then you absorb 15 to generate (15×22 + 3)/(15×7 + 1) = 333/106, then you absorb 1 to get this magical approximation (333 + 22)/(106 + 7) = 355/113, etc. In a sense what makes it magical is that the next number is very large. The larger it is the more decimal places you get “for free” truncating just before it. That is because this procedure is calculating the continued fraction 3 + 1/(7 + 1/(15 + 1/(1 + ...))) And you can sort of see that when we fill in the “...” with 0 to truncate the expansion there, that is not so different from truncating it with 1/292 to truncate one step later or 1/293 to truncate two steps later. Those numbers are very close to zero!
akovaski 4y ago
With a 7 digit denominator, 5419351/1725033 is quite nice. The offset jumps down to 2.21447793E-14. https://gist.github.com/akovaski/ce7a4230ed2ea0275f70e33c77eafa13 https://gist.github.com/akovaski/ce7a4230ed2ea0275f70e33c77e... see also: https://qin.laya.com/tech_projects_approxpi.html https://qin.laya.com/tech_projects_approxpi.html https://math.stackexchange.com/questions/1462062/is-there-a-formula-to-approximate-pi-in-the-form-of-dfracpq https://math.stackexchange.com/questions/1462062/is-there-a-...
pfortuny 4y ago
But 22/7 is unbeatable for relative error in the denominator size (nbr of bits)?
KolenCh 4y ago
A more efficient way to search possible fractions close to π is via continued fraction. Then you can have a sequence that has increasing larger denominator where all are approximately π. Each of the fraction there would be closest to π in the nearby region (nearby in the sense that if you change the size of denominator slightly, and at the same time the numerator accordingly.) So this is close to what your getting at, just not with exhaustive search and an artificial constraint (say 10000)
civilized 4y ago
You can save yourself some trouble with a bit of math. Continued fractions are known to provide the best approximations under a reasonable definition of "best": https://blogs.scientificamerican.com/roots-of-unity/what-8217-s-so-great-about-continued-fractions/ https://blogs.scientificamerican.com/roots-of-unity/what-821... Computing the continued fraction for pi actually presents some technical obstacles though - it has to be done numerically, since there's no known pattern to the sequence, and to do that, it seems like you need to compute higher and higher-precision numerical approximations to pi in order to accurately compute higher terms in the continued fraction expansion. Turns out there is another way: https://math.stackexchange.com/a/720082/ https://math.stackexchange.com/a/720082/

robin_reala 4y ago

Out of interest, do you get the same sort of results for other numbers that look a little like pi (small irrational number)? Or is this something peculiar to pi?

LeoPanthera 4y ago

I did a similar thing (also with some ugly python) to generate the closest integer fraction approximations in increasing length: 3/1 = 3.0 22/7 = 3.142857142857143 311/99 = 3.1414141414141414 355/113 = 3.1415929203539825 99733/31746 = 3.1415926415926414 312689/99532 = 3.1415926536189365 The jump in length from 355/113 to the next one is quite noticeable, and it does not happen with other irrational numbers, such as e, which progress more smoothly: 8/3 = 2.6666666666666665 19/7 = 2.7142857142857144 87/32 = 2.71875 193/71 = 2.7183098591549295 878/323 = 2.718266253869969 1457/536 = 2.718283582089552 2721/1001 = 2.7182817182817183 25946/9545 = 2.7182818229439496 49171/18089 = 2.718281828735696 271801/99990 = 2.7182818281828185

Someone 4y ago
You missed 13/4 = 3.25, 16/5 = 3.2, 19/6 = 3.16667, 179/57 = 3.14035, 201/64, 223/71, 245/78, 267/85, 289/92, 333/106, 52163/16604 https://shreevatsa.wordpress.com/2011/01/10/not-all-best-rational-approximations-are-the-convergents-of-the-continued-fraction/ https://shreevatsa.wordpress.com/2011/01/10/not-all-best-rat...
- LeoPanthera 4y ago
  I intentionally omitted fractions that were less accurate than others of equal length.
  - Someone 4y ago
    You’re discriminating against bases other than base 10 ;-) Why would the base you write the numbers down in affect whether a rational number is considered “best so far”?
    - genewitch 4y ago
      π/1, then. in base π.
    - crdrost 4y ago
      You don't need to discriminate to do it, as mentioned in comments below about continued fractions. In brief, π can be represented as a stream of integers, [ 3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, 1, 84, 2, 1, 1, 15, 3, 13, 1, 4, 2, 6, 6, 99, 1, 2, 2, 6, 3, 5, 1, 1, 6, 8, 1, 7, 1, 2, 3, 7, 1, 2, 1, 1, 12, 1, 1, 1, 3, 1, 1, 8, 1, 1, 2, 1, 6, 1, 1, 5, 2, 2, 3, 1, 2, 4, 4, 16, 1, 161, ...] To process into a rational approximation you want to maintain the two last aproximations a/b, c/d, and to get the first two numbers right you want to start with a/b = 0/1 and c/d = 1/0, zero and infinity. When you come to a number N in the sequence you form the new rational approximation (N*c + a)/(N*d + b). So you absorb 3 to generate 3/1, then you absorb 7 to generate (3×7+1)/(7×1+0)=22/7, then you absorb 15 to generate (15×22 + 3)/(15×7 + 1) = 333/106, then you absorb 1 to get this magical approximation (333 + 22)/(106 + 7) = 355/113, etc. In a sense what makes it magical is that the next number is very large. The larger it is the more decimal places you get “for free” truncating just before it. That is because this procedure is calculating the continued fraction 3 + 1/(7 + 1/(15 + 1/(1 + ...))) And you can sort of see that when we fill in the “...” with 0 to truncate the expansion there, that is not so different from truncating it with 1/292 to truncate one step later or 1/293 to truncate two steps later. Those numbers are very close to zero!

akovaski 4y ago

With a 7 digit denominator, 5419351/1725033 is quite nice. The offset jumps down to 2.21447793E-14. https://gist.github.com/akovaski/ce7a4230ed2ea0275f70e33c77eafa13 https://gist.github.com/akovaski/ce7a4230ed2ea0275f70e33c77e... see also: https://qin.laya.com/tech_projects_approxpi.html https://qin.laya.com/tech_projects_approxpi.html https://math.stackexchange.com/questions/1462062/is-there-a-formula-to-approximate-pi-in-the-form-of-dfracpq https://math.stackexchange.com/questions/1462062/is-there-a-...

pfortuny 4y ago

But 22/7 is unbeatable for relative error in the denominator size (nbr of bits)?

KolenCh 4y ago

A more efficient way to search possible fractions close to π is via continued fraction. Then you can have a sequence that has increasing larger denominator where all are approximately π. Each of the fraction there would be closest to π in the nearby region (nearby in the sense that if you change the size of denominator slightly, and at the same time the numerator accordingly.) So this is close to what your getting at, just not with exhaustive search and an artificial constraint (say 10000)

civilized 4y ago

You can save yourself some trouble with a bit of math. Continued fractions are known to provide the best approximations under a reasonable definition of "best": https://blogs.scientificamerican.com/roots-of-unity/what-8217-s-so-great-about-continued-fractions/ https://blogs.scientificamerican.com/roots-of-unity/what-821... Computing the continued fraction for pi actually presents some technical obstacles though - it has to be done numerically, since there's no known pattern to the sequence, and to do that, it seems like you need to compute higher and higher-precision numerical approximations to pi in order to accurately compute higher terms in the continued fraction expansion. Turns out there is another way: https://math.stackexchange.com/a/720082/ https://math.stackexchange.com/a/720082/