Hacker News Reader

Comment by cadamsau | Hacker News Reader

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/df3e12571294e3f7a9f5c07e91...

View on HN

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

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-rat...

I intentionally omitted fractions that were less accurate than others of equal length.

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”?

π/1, then. in base π.

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!

> 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

The OP did not have the sequence of best rational approximations derived from the continued fraction, but

    3/1 = 3.0      
    22/7 = 3.142857142857143      
    311/99 = 3.1414141414141414      
    355/113 = 3.1415929203539825

That is decimal-based, picking, for any number of digits, the best (according to some criterion) approximation of pi using that number of decimal digits.

They skipped 333/106, for example, because the better approximation 355/113 uses the same number of decimal digits, and included 311/99 because it happens to (just) need 5 decimal digits.

Well, OK, but I specifically wanted decimal fractions. I'm not a mathematician, from my perspective this is just a fun calculator trick. Maybe your calculator has other bases, I'm afraid mine doesn't!

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-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/

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)

With a 7 digit denominator, 5419351/1725033 is quite nice. The offset jumps down to 2.21447793E-14.

https://gist.github.com/akovaski/ce7a4230ed2ea0275f70e33c77e...

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

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?

Reply on news.ycombinator.com