The Mystery of 355/113 | Hacker News Reader

The Mystery of 355/113

davidbau.com

192 pointsColinWright65 comments

In Chinese the fraction 355/113 has been known as the 密率 ("detailed ratio") and 22/7 as the 约率 ("approximate ratio"). It is documented in the Book of Sui, volume 16:

宋末，南徐州從事史祖沖之，更開密法，以圓徑一億為一丈，圓周盈數三丈一尺四寸一分五厘九毫二秒七忽，朒數三丈一尺四寸一分五厘九毫二秒六忽，正數在盈朒二限之間。密率，圓徑一百一十三，圓周三百五十五。約率，圓徑七，週二十二。 [1]

While it suggests that the value was calculated around the end of the Liu Song Dynasty (~479 CE) by Zu Chongzhi to have an upper bound of 3.1415927 and lower bound of 3.1415926, the 密法 method is not explained.

It has been thought that Zu may have used a "method of averaging days" to calculate an intermediate value between two prior known approximations of 22/7 and 157/50 [2]. Not a very satisfying result for anyone who wants to find something special in the numbers 355 and 113.

[1] https://zh.wikisource.org/wiki/%E9%9A%8B%E6%9B%B8/%E5%8D%B71...

[2] http://books.google.com/books?id=QlbzjN_5pDoC&lpg=PA34&#...

There is no mystery here. If you pick a random real number and find the best quality approximation of it — as calculated by log_b 1/|x-a/b| — then the median quality of the best such approximations within a tolerance of 1/1024 is around 3.19. So with respect to the measure this article is talking about, pi is completely normal and 355/113 is a completely unexceptional best approximation with a denominator of at most nine binary digits (about 3 decimal digits). 355/113 isn't even the best quality approximation of pi by the given criterion — that would be 22/7, which, as mentioned in the article, has a quality measure of 3.429288337281781.

Julia code to figure this out can be found here:

https://gist.github.com/3170899

These kinds of articles about pi, or numbers, where they try to summon up some mystery and wonder around it, come across to me as not very genuine. I get the impression it gets upvoted because people want to feel like they're smarter, or more geeky and hip for having looked at it.

I don't know, I've met folks for whom math is so magical they do nothing but talk about it all the time. I can recognize that passion in other pursuits as well, from knitting to physics.

I find a close correlation between people who play with numbers to people who like to solve puzzles.

Or perhaps math are fun and people upvote a post they liked.

I wonder if mathematicians recite beautiful proofs as fourplay...

Probably not, since most (?) beautiful proofs are symbolic and not very recitable.

"I wonder if mathematicians recite beautiful proofs as fourplay ... "

I see what you did there.

One of the most "mind boggling" areas of math is number theory

Math dealing with real/complex numbers has been vastly explored, and there are very powerful tools, and computers are very good at these kind of problems (Calculus, etc)

With number theory, progress is much harder, things work in a completely different logic (think for example that 5+3 can be 0 for example)

One of the places where these mysterious sides of math comes together is this: http://en.wikipedia.org/wiki/Riemann_zeta_function

> ...for example that 5+3 can be 0 for example

When is that example true? It seems like you made that up.

mod 8?

Hardly the 'mystery of number theory' the poster was talking about. There was no 'mod 8' syntax expressed in the example.

Yes, it is http://en.wikipedia.org/wiki/Modular_arithmetic

But you don't need to write "mod 8" in a congruence class

Oh, you want "the mystery of number theory" you can start with http://en.wikipedia.org/wiki/Fermat%27s_little_theorem

It was solved, and he (Fermat) was likely wrong, given the resulting proof.

(5 + 3) % 8 = 0 is not the same as 5 + 3 = 0

I'm not looking for mystery, I'm wondering why people think it exists, and are faking its existence by being imprecise.

>With number theory, progress is much harder, things work in a completely different logic (think for example that 5+3 can be 0 for example)

I wasn't aware that the modulo operation had been raised to a field of mathematics.

Modulo operations is part of "number theory 101"

And ok, addition is nice and fun. Then you go to multiplication

Then you end up with Galois Fields.

Never underestimate the amount of discussion that goes into things like 1+1=2

Maybe there is a little mystery.

Enumerate all the fractions with at most 3-digit denominator (0, 1, 1/2, 1/3, 2/3, 1/4, ..., 998/999) between 0 and 1. Now what is the probability that amongst them we find an approximation to a random real that is at least as good as 355/113 is to pi?

Seems to be about 15%, so not much mystery here. But we allow denominators as large as 999 because we use the decimal system. In hexadecimal it would be at most 2-digit denominators, up to ff = 255.

In this case, the probability is about 1%. Much more mystery. So it comes down to, how large a set of denominators we think 113 is drawn from, and whether living in a 1 in 100 universe is enough to be mysterious in this case.

Sampled by this python code (takes minutes to run): https://gist.github.com/3172978

And in base-128 it would be only denominators up to 127, which is an even more amazing 0.2% ;)

...and an overflow in your numerator.

Seriously: this kind of thinking is more numerology than number theory.

Why not go till fff in base 16? And also atleast double digit in base 127? It can turn out in both cases that the probability is way higher.

So just a note, you've got a great deal of repetition in your search. 0.5, for instance, turns up once for every even denominator. That's going to skew your percentages a bit.

Yes, the constructed list contains a lot of duplicates (removing duplicates with the python set operations shortens it by 40% - would be a worthwhile optimization for the runtime, too), but my percentages are not based on that.

But: I sampled a random real, and looked at whether any fraction in the list is close enough to this real. And repeated the sampling 1000 times. This is how the percentages are calculated, and the duplicates in the list don't affect this.

FWIW, all of the convergents from the continued fraction expansion of a number have "quality" greater than 2. Conversely, the Thue–Siegel–Roth theorem says that any algebraic number and any epsilon > 0, the algebraic number has only finitely many approximations with quality more than 2 + epsilon; so the "quality" values of successive best approximations are a series which converges to 2 from above.

This was how the first known transcendental numbers -- the Liouville numbers -- were constructed: They have approximations with unbounded quality, thus they cannot be algebraic. In practice, however, this isn't a very useful method: "Almost all" transcendental numbers also obey the Thue–Siegel–Roth theorem.

Is it also the case that all transcendental numbers have approximations of unbounded quality? Or only that Liouville numbers have approximations of unbounded quality, and therefore cannot be algebraic?

Liouville numbers have approximations of unbounded quality and thus cannot be algebraic. "Most" transcendental numbers only have finitely many approximations of quality higher than 2 + epsilon for any epsilon.

Pi has the continued fraction expansion:

3; 7, 15, 1, 292, 1, ...

That 355/113 is one of the best possible rational approximations to PI, and it occurs right after the 292. In general, a best rational approximation cut off at a very large term in the CF expansion will provide more accuracy than you would think.

355/113 is actually [3,7,15,1]. The reason it's particularly good compared to its length is because it falls right before the 292 term (since 1/292 is a much smaller contribution than 1/1).

Ah, indeed you are correct. I had that wrong.

So, as noted in one of the comments to the original article, the question of why 355/113 is particularly good can be restated as a question of why the 292 term in that expansion is so large.

I wrote a quick script to walk through Q, spitting out fractions with high "quality". Here are some early values:

  22/7: 3.42928833728
  355/113: 3.20195874233
  710/226: 2.79251047296

A quick search through 1/1 - 100,000/100,000 shows no other interesting values. My algorithm is extremely naive though (brute force), a faster search could potentially be used to find other high quality values much more quickly.

Update - A slightly optimized algorithm, and nothing special found with denominators up to the hundreds of millions. I know this means nothing wrt actual mathematics though...

By your output you're performing some redundant checks. 355/113 == 710/226. Not sure how you're performing the search, but removing those may speed things up.

I think the cost of removing them (checking every value to see if it's a multiple of another) is greater than the benefit of removing them. My search terminated though (with no interesting finds) - my fractional values were getting too small and I got a ZeroDivisionError.

You can easily generate all fractions in lowest terms within a disk by using a recursive Farey sequence generator.

Reading about Farey sequences led me to http://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree. This could be used to perform a search of the space of rational numbers with denominator < threshold with each number examined only once.

Edit: Oops, suggested an infinitely long search

The Wilf-Calkin tree also does that:

http://en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree

I refer to it as Wilf-Calkin because that's how Neil Calkin refers to it, despite the alphabetical ordering on the Wikipedia page.

Even better, there's an explicit formula for generating rationals, without repeats:

http://en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree#Breadt...

Neat, that was in a tab I hadn't reached yet. Though for the purposes of this sort of search, the Stern-Brocot tree has the nice property of being a binary search tree. Allowing you to constrain the breadth as well as the depth of the search.

http://en.wikipedia.org/wiki/Continued_fraction#Best_rationa... will teach you how to find the best approximations in no time.

If you understand that, read http://blog.wolfram.com/2011/06/30/all-rational-approximatio... :-)

I had a quick go too:

    num     den     difference to pi
    1	1	2.1415926535898
    3	1	0.14159265358979
    22	7	0.0012644892673497
    333	106	8.3219627529107e-05
    355	113	2.6676418940497e-07
    103993	33102	5.7789062424263e-10
    104348	33215	3.3162805834763e-10
    208341	66317	1.2235634727631e-10
    312689	99532	2.914335439641e-11
    833719	265381	8.7152507433075e-12
    1146408	364913	1.6107115641262e-12
    4272943	1360120	4.0412118096356e-13
    5419351	1725033	2.2204460492503e-14
    80143857	25510582	4.4408920985006e-16

Lua script to generate (dirty):

    local max = 100000000
    local c = {}
    local min , j = math.huge
    for i=1,max do
        local a = math.pi-math.abs(math.cos(i))
        if a < min then
            min = a
            j = i
            table.insert ( c , j )
        end
    end

    local min , j = math.huge
    for k=1,#c do
        for i=1,max do
            local a = math.abs(math.pi-c[k]/i)
            if a < min then
                min = a
                j = i
                print(c[k],j,min)
            end
        end
    end

It's not actually the difference to pi that matters, it's the "quality" of the approximation, as described in the article. You can always get better approximations by using larger denominators, it's just that some approximations are, given the size of the denominator, unreasonably good.

355/113 is one of those.

True, I didn't do the quality measure they talk of. I was just fascinated by:

"For example, use any scientific calculator to compute cos(355) in radians. The oddball result is due to the freakish closeness of 355/113 to pi."

And wanted to see what else would fit this criteria...

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.

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

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

I think that code must be doing something wrong. 355/113 = 710/226 but you have different values for both

This is called Diophantine approximation.

http://en.wikipedia.org/wiki/Diophantine_approximation

p.s. Take a look at the "Liouville's result" part.

355/113 has good enough precision to aproximate pi on single precision floating point

Not quite, but close. I get the delta as one part in 2^21.8. The mantissa of a IEEE float is 24 bits (including the leading one).

355/113 is a convergent of the continued fraction for pi. The convergents of a continued fraction (for an irrational number) give the best rational approximations to the number. I'm teaching this stuff this summer; here's a link to my notes on this:

http://www.millersville.edu/~bikenaga/number-theory/approxim...

For instance, 278/125 is the best rational approximation to the cube root of 11 having denominator less than 155. The proof is pretty easy --- you don't have to do it by trial and error.

As for why 355/113 doesn't come up in other expressions for pi --- I'm not sure why it should. The fact that two expressions converge to pi is no reason that I can see to expect that they should involve the same integer coefficients, say. There are infinitely many integers. There are infinitely many expressions for pi.

> and it causes various oddities elsewhere in math.

Could someone elaborate? First, explain the one example from the article (cos(355)) and perhaps show some other oddities?

If p/q is a close approximation to π, then cos(p), taken in radians, will be close to +1 or -1, because it implies that p is close to an integer multiple of π, and therefore cos(p) is close to the cosine of an integer multiple of π:

   p/q =~ π 
   p =~ qπ
   cos(p) =~ cos(qπ)

In turn, the cosine of an integer multiple of π is +1 or -1 because the period of cosine (as a trigonometric function) is 2π radians, with maxima at 0, 2π, 4π, ... and minima at π, 3π, 5π, ...

I've never been compelled to use any fractional approximation of pi. Either I'm doing it in my head and pi is ~3, I'm doing it on paper and pi is ~3.14, or I'm using a calculator and pi is as many digits as I feel like.

We already have the decimal representation memorized for more digits than this approximates, so unless your diameter is given to you in 113ths, is there any practical application here?

Okay, I'll bite - why does this matter?

http://www.smbc-comics.com/index.php?db=comics&id=2674

You are kind of stretching though. Why do we have to assume that 355/113 is "magical" in order to advance mathematics:

Firstly, you do realise that I'm not the author, I just submitted it, don't you?

Secondly, there are some curious things about pi. It does turn up in places that apparently have nothing to do with circles. It's a bit like e in that regard.

Next, we don't have to assume it's "magical," but some of the properties are noteworthy. The fact that 355/113 is such a good approximation, and yet it doesn't appear to turn up naturally in any of the proven convergences is a bit odd. Why does it not turn up? The only place it does turn up is when you write down the ad hoc continued fraction to express the value you already know. That seems unnatural, and immediately leads to a desire for further investigation.

And finally, mathematicians have a feel for things that are "natural," and that's what they end up exploring. Often it leads nowhere interesting, but sometimes it leads to unexpected connections, and occasionally to equally unexpected applications. But in all, some questions just feel right for exploration, and some properties of pi fall into that category. You never really know exactly what will advance math - we only have intuition to guide us in deciding what is an "interesting question."

Very useful when performing integer mathematics... First met it in Brodies Starting Forth I always remember it as 113355 (split it in half)

Having gone away to check my memory I notice that he also provides: 1068966896 / 340262731 which is suppose to be accurate to E-18

if one wanted to find the 'best' converging sequence, you might go about it by brute force. Seems lots of people beat me to it. http://pastebin.com/iujCgUSu

  my $lasterror = 3;
  for (1..10000){ my $d = $_;
      for (3..40000){ my $n = $_;
         if (abs(($n/$d) - pi) < $lasterror){
         $lasterror = abs(($n/$d) - pi);
         print "\n $n / $d: error $lasterror";}}}
  
  #  output
  # 3 / 1: error 0.141592653589793
  # 13 / 4: error 0.108407346410207
  ...
  # 355 / 113: error 2.66764189404967e-007

That's not a converging series. That's just a sequence of ratios that have successively smaller errors. But there's nothing to relate each ration to the next one.

correct - one of observations in the article was that many of the series identified so far lack the magical 355/113 - I was curious what a converging series would look like, not the equation that describes such a series.

I would be interested in identifying this next super series in terms of an equation but given the few minutes on break, and that total it is unlikely someone as bad at math, such as myself, could come up with this series in a few minutes - I opted for the fun programming route.

You still seem confused. What you have is not a converging series, period. You just have a list of successively-closer ratios. A series (in math) is the sum of the terms in a sequence (which itself is a discrete function). You don't have a discrete function, and you definitely don't have the sum of anything.

He does have a converging sequence, though. Many people don't understand the technical (but obvious to mathematicians) distinction between sequence and series.

Thanks Colin, sequence - that was the term I needed, and my intention.

Very interesting stuff.

Lovers of pi might like Eve Andersson's Pi Land: http://www.eveandersson.com/pi/

As for sequences, I particularly liked pimasterfromhk's.

Try fourth root of (9^2 + 19^2/22)

I just saw all the numbers and bailed.

Reply on news.ycombinator.com