On: The Mystery of 355/113

[drostie]

The numbers that you're producing can be better produced by the following Python code:

    from fractions import Fraction as frac
    def continued_fraction(x, n=10):
        """Represent x as a continued fraction out to n places."""
        last = int(x)
        out = []
        for i in range(n):
            x = 1/(x - last)
            last = int(x)
            out.append(last)
        return out

    def bras(x, n=10):
        """Compute the best rational approximations to x."""
        base = int(x)
        nums = continued_fraction(x, n)
        S = lambda depth, i = 0: \
            frac(1, nums[i]) if depth == 0 else 1 / (nums[i] + S(depth - 1, i + 1))
        return ', '.join(str(x) for x in (base,) + tuple(base + S(k) for k in range(n)))

    from decimal import Decimal
    print(bras(Decimal('3.1415926535897932384626433832795028841971693993')))
    # 3, 22/7, 333/106, 355/113, 103993/33102, 104348/33215, 208341/66317,
    # 312689/99532, 833719/265381, 1146408/364913, 4272943/1360120

These are the best rational approximations to pi, which are determined by the continued fraction of pi:

    pi ~=  3 + 1/(7 + 1/(15 + ...))
    pi = 3 + [7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, ...]

Large numbers are opportunities to "grab a lot of extra digits" and thus the large qualities come when we truncate after 7, 15, 292, and 14.

You may wonder what the "most irrational" number is, in the sense that all of its best-rational-approximations are of low quality. That distinction belongs to:

    phi = (1 + Decimal(5).sqrt()) / 2 # golden ratio
    continued_fraction(phi) # [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
    bras(phi) # 1, 2, 3/2, 5/3, 8/5, 13/8, 21/13, 34/21, 55/34, 89/55, 144/89

Those last numbers you may recognize from your intro to programming as the Fibonaccis.

[abecedarius → drostie]

Here's some simpler code that computes the same result -- I'm too tired and dumb to work out if it will for any number:

    def rationalizations(x):
        """Generate good rational approximations of x in order of
        increasing denominator."""
        assert 0 <= x
        ix = int(x)
        yield ix, 1
        if x != ix:
            for numer, denom in rationalizations(1.0/(x-ix)):
                yield denom + ix * numer, numer

    import itertools, math
    def show(x, n): return list(itertools.islice(rationalizations(x), n))

    print show(math.pi, 11)
    # [(3, 1), (22, 7), (333, 106), (355, 113), (103993, 33102),
    # (104348, 33215), (208341, 66317), (312689, 99532),
    # (833719, 265381), (1146408, 364913), (4272943, 1360120)]

From https://github.com/darius/sketchbook/blob/master/misc/ration...

[drostie → abecedarius]

It's true, my code is longer because it computes an explicit continued fraction representation (and also because it's not written as two generator scripts).