There are several mathematical facts, many of which are somewhat well-known, which most people take to be coincidences. In this post I will show how many of these have explanations that make them less coincidental than seemed, or show their equivalence to another mathematical coincidence.

···

Fact: 10^6 - 2 = 2*31*127^2. The factorization contains two distinct Mersenne primes, and one of them is repeated.

Consequences: This is deeply related to the fact that sqrt(62) starts 7.87400787401…, repeating 7874 twice.

Explanation: This ultimately comes down to the fact that 2^7 - 5^3 = 3, and 10 = 2*5. This can be shown by factoring a polynomial function that yields 10^6 - 2 when x = 5^3.

Let x = 5^3 = 125, so x + 3 = 2^7 = 128. Then 2*10^6 = 5^6*2^7 = x^2*(x + 3) = x^3 + 3x^2. 2*(10^6 - 2) = x^3 + 3x^2 - 4 = (x - 1)(x + 2)^2 = 124*127^2 = 2^2*31*127^2 10^6 - 2 = 2*31*127^2.

Really, this comes down to the fact that factorization of numbers close to 2*10^6 follows factorization of certain cubic polynomials. The repeated 127 factor is a lot less surprising when it becomes a repeated x + 2 factor in the polynomial setting. This also shows why 126^3 = 2000376 is so close to 2*10^6; the relevant polynomial is (x + 1)^3 = x^3 + 3x^2 + 3x + 1, which is only 3x + 1 greater than x^3 + 3x^2 = 2*10^6.

The same framework also explains why 52^3 = 140608 is so close to 375^2 = 140625, a fact noticed by Wendy Krieger. If x = 25 and x + 2 = 27, we have:

3*52^3 = 24*26^3 = (x - 1)(x + 1)^3 = x^4 + 2x^3 - 2x - 1 3*375^2 = 27*25^3 = (x + 2)x^3 = x^4 + 2x^3

···

Fact: 5882353 = 588^2 + 2353^2. Also, 5882353 = (10^8 + 1)/17.

Explanation: First of all, a noteworthy fact about this identity is that 2353 = 588*4 + 1. The equality 5882353 = (10^8 + 1)/17 means that 1/17 is close to 0.05882353 (actually it's slightly less). The expansion of 4/17 is equal to the expansion of 1/17 cyclically permuted four digits backwards. Thus, 4/17 is about 0.2353. This explains why 2353 = 588*4 + 1 is not a third coincidental fact but a consequence of the connection to 1/17.

In order to find numbers a and b such that a^2 + b^2 = a||b (where || means concatenation), we need to solve a^2 + b^2 = 10^n a + b, where n is the number of digits in b. In general, integer solutions to this equation are rare. In this case, we also know that b = 4a + 1. In order to figure out the connection to 1/17, it helps to extract the essential features of the first equality. So to find other solutions similar to this one, we may decide to substitute b = 4a + 1 into the equation, giving a^2 + (4a + 1)^2 = 10000a + 4a + 1. This gives us the quadratic equation 17a^2 - 9996a = 0.

The two solutions are a = 0 and a = 588, the latter of which is 9996/17. So we recovered our original solution. But why is the sum like the digits of 1/17? Well, 9996 = 10^4 - 4, so 1/9996 = 0.0001000400160064… follows the powers of 4. If we make a decimal that follows the powers of 4 times 588, we get 588/9996 = 1/17. The first 8 digits are 0588 followed by 588*4 = 2352, which is (almost) exactly the same digit sequence as our sum of squares.

The next example of this phenomenon occurs when b = 10a + 1, with 990^2 + 9901^2 = 99009901 = (10^10 + 1)/101. However, in this case, the concatenation is 5 digits, so an extra 0 needs to be placed in front of 9901. The next example after that is when b = 16a + 1, where a = (10^64 - 16)/257 and a^2 + b^2 = (10^128 + 1)/257.

···

Fact: 7^6 = 117649, and 117647 are the first 6 digits of 2/17.

This one appears on the Wikipedia list of mathematical coincidences. Sometimes equivalent apparently coincidental statements are given instead, like 17*7^6 = 2*10^6 + 33. However, I found a somewhat satisfying explanation for it (in my opinion) when thinking in different bases.

The coincidence can be given as 2*10^6 ~= 7^6*17. Specifically, the fact that 117649 is close to the last 6 digits of 2/17 is really saying that the number itself is close to 2*10^6/17. Now, 2*10^6 = 2^7*5^6 can be refactorized as 50^3*16. Let's look at this in base 7.

50 = 7^2 + 1, so 50 in base 7 is 101_7. Using Pascal's triangle to expand (x + 1)^3, we get that 50^3 in base 7 is 1030301_7. Multiply this by 16, which is 22_7, and you get 22666622_7. This is remarkably close to 23000000_7, which is 17*7^6.

Maybe this doesn't explain the coincidence as part of a "natural" pattern, but at least it seems like a collision of diverse circumstances rather than a freak accident of matching digits. Row 3 of Pascal's triangle has repeated digits in the middle, those digits are a factor of the base (7) minus one, and the value (7^2 - 1)/3 just happens to have a subset of the prime factors of 7^2 + 1.

The ultimate test of whether such an explanation is sufficient is if it allows us to find analogous patterns in other bases. Let's try base 4. We have 101_4 = 17, 1030301_4 = 17^3, and 11333311_4 = 17^3*5 = 24565 is close to 12000000_4 = 6*4^6 = 24576. Unfortunately, 5 and 17 are coprime, so 17^3*5 isn't nearly as nice as 50^3*16.

We can even try the same thing in base 10. We have 101^3 = 1030301, 101^3*33 = 33999933, and 34*10^6 = 34000000. However, the only larger relevant base here is base 101, because 101 is prime. So this isn't nearly as interesting as what happens in bases 7 and 10.

As a bonus, this explains why one of the approximations to sum(7^(i - 1)/10^i, i=1..infinity) looks like 5/17. We have sum(7^(i - 1)/10^i, i=1..infinity) = 1/3, but sum(7^(i - 1)/10^i, i=1..6) = 0.294117, the first 6 digits of 5/17. This is equivalent to sum(10^i*7^(5 - i), i=0..5) ~= 5/17*10^6. This is true because 7^6 ~= 2/17*10^6 implies 10^6 - 7^6 = 15/17*10^6, and sum(10^i*7^(5 - i), i=0..5) = (10^6 - 7^6)/3.

···

Fact: 1/41 = 0.024390243902439… has an unusually short period of 5 in base 10.

All primes p other than 2 or 5 have a reciprocal with a repeating period in base 10. This period is always some factor of p - 1, and usually seems to be pretty large. However, if p divides some small repunit (number made out of ones), the period can be shorter.

For some short-period primes, the reason the period is so short is clear. 1/11 = 0.090909… has a period of 2 digits because 11 is a 2-digit repunit. 1/37 = 0.027027027… has a period of 3 digits because it's obvious 111 is divisible by 3 (its digits sum to 3) and 111/3 = 37.

However, 1/41 has a period of 5 digits because 41*271 = 11111, and the primes 41 and 271 look very random, with no reason why they would have to be this way. It turns out that repunits of prime length (and more generally, cyclotomic polynomials at n = 10) factoring into random-looking prime factors is the rule, not the exception, but for someone new to repeating decimals it might be tempting to try to make a connection between this short period and some mathematical propery of the number 41.

As a matter of fact, some partial explanation does exist. Because 41 divides 11111, it also divides 99999. (For those unfamiliar with the math behind repeating decimals, this is the direct reason 1/41 has a 5-digit period at all: because 1 = 0.999… can be divided into chunks of 5 digits as 0.99999 99999 99999 … and each chunk can be divided by 41.) Because 41 divides 99999, it also divides 99999 + 41 = 100040. Because 41 doesn't divide 10, it must divide 10004. (We can also use this trick to show that if k divides 10^n - 1, k also divides each of the n-digit cyclic permutations of k. This is why cyclic numbers like 142857 exist.)

The number 10004 seems worthy of interest, because the polynomial n^4 + 4 factors as (n^2 - 2n + 2)(n^2 + 2n + 2). If we can find a theoretical reason why this would lead to a number of the form n^4 + 4 being divisible by 4n + 1, that would explain why certain numbers have reciprocals with period 5 in some bases. We might also notice that 41*61 = 2501 = 50^2 + 1, and 41 and 61 are oddly "symmetric" around 51, whereas most numbers one above squares don't have simple patterns in their factorization. This is related to the above, because 2501 = 10004/4.

As it turns out, when n = 10, the polynomial factorization becomes 10004 = 82*122. Then 82 = 2*41, so this can be refactored as 41*244. So the ultimate reason this seems to happen in base 10 is that 4 = 2^2 and also 4*2 = 10 - 2.

Of course, this is just one explanation. It breaks the "coincidence" into a lot of steps, but it's not obvious why all the steps should even exist. It could be seen as just "explaining" the coincidence with another coincidence. However, we can generalize this construction to find a family of period-5 reciprocals in other bases.

The factorization n^4 + 4 = (n^2 - 2n + 2)(n^2 + 2n + 2) is part of a general pattern of factorizations n^4 + 4k^4 = (n^2 - 2kn + 2k^2)(n^2 + 2kn + 2k^2). Let's assume we're working in base-n with an arbitrary k, and 4k^4 < n so 4k^4 is a single digit. Then the number n^4 + 4k^4 is a cyclic permutation of 4k^4*n + 1.

By analogy, we would want 4k^4*n + 1 to be a divisor of n^2 - 2kn + 2k^2, just like 41 divides the factor 82. The simplest way to do this is to let the quotient be 2k^2 (the ratio of the last digits), which means we want 4k^4*2k^2 = 8k^6 = n - 2k. So we choose our base n = 8k^6 + 2k. (Note that when k = 1, this equals 10.) Now 4k^4*n + 1 divides n^4 + 4k^4, which means it divides n*(n^4 + 4k^4) - (4k^4*n + 1) = n^5 - 1. Thus, 4k^4*n + 1 has period 5 in base n = 8k^6 + 2k. (Note that a divisor of n^5 - 1 could also have period 1, but 4k^4 + 1, being two digits long, is too small to have period 1 without nonrepeating digits at the beginning.)

After 41, the second smallest number with this property is 33025 in base 516. In this base, the number 33025 is written with the digits 64:1. 1/33025 has the expansion 0.0:8:32:63:515:0:8:32:63:515…. As it turns out, 33025 = 5^2*1321, and the full factorization of 516^5 - 1 is 5^2*103*521*1321*20641.

···

Fact: 2^10 = 1024 is close to 10^3 = 1000.

This is pretty well known, as it is the basis for the names of a lot of units used in computing. A kilobyte, for instance, could mean 1000 or 1024 bytes, and a <prefix 10^(3n)>-byte could mean either 10^(3n) or 2^(10n) bytes. Even more remarkable is the repeated appearance of 10, which happens to be the base of our number system. This leads to further coincidences involving families of powers of 2 sharing both the same first and last digits, as the last 2 digits of powers of 2 repeat with period 20. Example: 256, 268435456, 281474976710656, ….

Most people, including Wikipedia, generally think there is no further explanation behind this coincidence. However, I can offer an explanation that removes at least a little bit of the mystery. First, many people try to make the coincidence "simpler" by removing factors of 2^3 to turn it into 2^7 = 128 ~= 125 = 5^3. As remarkable as this is (see item #1), it gets rid of the shared appearance of 10 and is not the approach I'll be using here.

Instead, I'll be showing that 2^(5*2) is close to a multiple of 5^3 (note the repeated 5's, which can be derived from the repeated 10's in the original expression), and that this is part of a pattern in the 10th powers. First, n^5 = n (mod 5), which comes from Fermat's little theorem. As it happens, we can show something deeper about 5th powers: if n = 5k ± 1, then n^5 = 25k ± 1 (mod 5^3). This is because (5k ± 1)^5 = 3125k^5 ± 3125k^4 + 1250k^3 ± 250k^2 + 25k ± 1, and all the coefficients except the last two are divisible by 5^3. Furthermore, if n is an odd square, both n and n^5 are congruent to 1 mod 8, and we see that if 5k ± 1 = 1 (mod 8), then 25k ± 1 = 5(5k ± 1) -/+ 4 = 1 (mod 8) as well. Therefore, n^5 = 25k ± 1 (mod 8). If n is an even square, then n = 5k ± 1 is divisible by 4, and so 25k ± 1 is also divisible by 4. It thus follows that n^5 = 25k ± 1 (mod 4) in this case. Putting these results together, we see that if n = 5k ± 1 is an odd square, then n^5 = 25k ± 1 (mod 500), and in at least half of all cases this is true mod 1000 as well.

Now, if m is not a multiple of 5, then m^2 = 5k ± 1 for some k, and so the above result applies: (m^2)^5 = m^10 = 25k ± 1 (mod 500). In particular, 2^10 = 24 (mod 500). It just happens that 2^10 = 24 (mod 1000) as well, and the difference is 1000 itself.

Now we can generalize this to other bases. For m = 3, we have 3^2 = 9 = 5*2 - 1, and 25*2 - 1 = 49. In fact, we have 3^10 = 59*1000 + 49. So if anyone builds a ternary computer with memory that can be addressed by strings of 10 "trits", the ternary equivalent of bits, they can say it has 59 kilotrits of memory, even if it isn't exact.

We can generalize this to other bases in a different way as well. For the same reason n = 5k ± 1 implies n^5 = 25k ± 1 (mod 5^3), we also have n = pk ± 1 implies n^p = p^2*k ± 1 (mod p^3) for all primes p > 2. The expression (pk + 1)^p expands as sum(p^i*choose(p, i)*k^i, i=0..p). Because p > 2, the first term is divisible by p^3, and because choose(p, i) is divisible by p for 1 < i < p - 1, the terms up to the penultimate term are also divisible by p^3. Therefore, the last two terms, p^2*k + 1, are the value mod p^3. For (pk - 1)^p, the expansion is the same but with alternating signs. Because there are an even number of terms, the same reasoning tells us that the value mod p^3 is p^2*k - 1.

Now if m does not divide p, then m^((p - 1)/2) = ±1 (mod p). (This is because m^(p - 1) = 1 (mod p) by Fermat's little theorem, and the only possible square roots of 1 mod p are 1 and -1.) Therefore, if m does not divide p, then m^(p*(p - 1)/2) = p^2*k ± 1 = p*m^((p - 1)/2) -/+ (p - 1) (mod p^3).

As an example, 2^3 = 7 + 1 and 2^21 = 6114*7^3 + 7^2 + 1. However, this is not especially close to a multiple of 21^3 because 6114 isn't divisible by 27. None of these examples feel as "magical" as 2^10 ~= 10^3, so I would say this coincidence is only partly resolved.

···

Fact: The last 3-digit string to appear in a power of 2 is 000.

Explanation: I heard about this from the user Ecl1psed on the Googology and Apeirology server, and at first it looks like a 1 in 1000 chance. However, there may be some phenomenon at play that make this not quite as rare as it looks. Given a 3-digit string s in 2^n (interpreted as a number from 0 to 999), there are only two possible strings that can appear in 2^(n + 1) at the same position, namely 2s mod 1000 and 2s + 1 mod 1000. In the cases of s = 000 or s = 999 (and only in those cases), one of the possible strings at the same position in 2^(n + 1) is s itself. If the concatenation of the powers of 2 is a normal number (which I believe is conjectured to be the case), each 000 has a 1/2 chance of being followed by a 000 in the next power of 2, which has a 1/2 chance of being followed by a 000 in the next power of 2, and so on. So the expected number of consecutive occurrences of 000 is 2 (and same for 999) whereas most 3-digit strings cannot appear in the same position in two consecutive powers of 2. If the powers of 2 are short (not much longer than 50 or 100 digits), this means that the strings 000 and 999 have a greater-than-average chance of occurring multiple times close together. Again, if the concatenation of the powers of 2 is a normal number, all 3-digit strings appear with the same frequency. Because 000s tend to appear together, the distance to the first occurrence of 000 has a higher-than-average chance of being exceptionally long. In fact, we can make the same argument for the substring 00, which may further increase the variance in the distance between occurrences of 000.

···

Finally, here are some interesting coincidences that are related to each other, even though I haven't found a single unifying explanation for all of them.

We have the remarkable identity 3^10*109 + 2 = 23^5. This is, in fact, the abc-triple with the best known quality, first found by Eric Reyssat. As a consequence, 109^(1/5) is very close to 23/9, so close that it even starts with 2.555555…, and its continued fraction starts [2; 1, 1, 4, 77733, 2, 1, 1, 1, 3, 13, 1, 9715, 1, 3, 2, 1, 7, 1, 4, 52999, …]. (For those unfamiliar with continued fractions, they give you the closest rational approximations to a number by truncating the sequence to a certain number of terms. The larger the next term cut off, the better the approximation. The continued fraction for 23/9 is [2; 1, 1, 4]. The next term is 77733, which means that 23/9 is a very good approximation for 109^(1/5) as 77733 is a very large term to see in a continued fraction expansion that doesn't exhibit any special patterns. As a rule of thumb, a term that is greater or equal to n appears with a frequency of about 1/n terms.)

You might also notice the other large terms in the continued fraction, 9715 and 52999. These terms come from dividing especially good rational approximations to (23^5 - 2)^(1/5) by 9. I'm not sure, but I believe that those rational approximations can be derived from approximations to the function 23*(1 - 1/x)^(1/5) and substituting x = 23^5/2.

There are some folk who really like continued fractions; I do think they're cute, myself (and you can tell, can't you?). It is, however, Some Work to do ordinary arithmetic with them, as can be discerned from the combined length and sketchiness of HAKMEM Item 101B, by Bill Gosper. In this note I'd like to outline how taking square roots is not too laborious within Continued Fractions.

As a rather long-winded prelude, we might remark that what we might today call "Newton-Raphson" iteration, in the specific form $$\frac{p}{q} \mapsto \frac{p^2 + A q^2}{2 p q} $$ gives rapidly-improving rational approximations to the square root of any rational number $A$; and that this, or something like it, has already been found in cuneiform clay tablets.

From a different perspective, consider: every positive integer $A$ that isn't a square is between two squares, and certainly isn't the square of a half-integer either, and so there is a unique integer $N$ with $|\sqrt{A}-N| \lt \frac{1}{2}$, and so the powers $(\sqrt{A}-N)^k$ are decreasing in absolute value, but also are algebraically reducible $(\sqrt{A}-N)^k = q_k \sqrt{A} - p_k$, which again gives interesting sequences of rational approximations: $$\sqrt{A} = \frac{ p_k + (\mathrm{small})^k}{q_k}$$ and considering further that $$ \frac{p^2 + A q^2}{2pq} - \sqrt{A} = \frac{(p - q\sqrt{A})^2}{2pq} $$ we might deduce that this second family of approximations refines (in a way... it's slower, of course) the Ancient Method.

But perhaps there remains a salmon of doubt that there might be better approximations? Ah, well, Liouville has already worked out some stern constraints, relating $\mathrm{small}^k$ and $q_k$, and one can calculate that we're already quite close to them -- but perhaps there's an epsilon of room for improvement? Well. Liouville incidentally is as good a reminder as any that "$\sqrt{A}$" means The Positive Solution $x$ to the equation $x^2 - A = 0$. Actually, let's call that $x_0$, with $$ x_0^2 - A = 0 $$ And as there's an integer with $N \lt \sqrt{A} \lt N+1$, we can write $x_0 = N+y_0$, with $$ y_0^2 + 2N y_0 - ( A - N^2)$$ and since by construction $0 \lt y_0 \lt 1$, it is just as good as anything to define $x_1 = \frac{1}{y_0}$ satisfying $$ 1 + 2 N x_1 - (A - N^2) x_1^2 = 0$$ and... perhaps we can see where this is going?

There's a fairly ordinary action of $SL(2,\mathbb{Z})$ on two-dimensional vector spaces, which extends to a fairly-ordinary action on $\mathbb{Z}[x,y]$ preserving homogeneous subspaces; and then restricting to homogeneous polynomials of degree two, we might say $$ L : ax^2 + bxy + cy^2 \mapsto a(x+y)^2 + b(x+y)y + cy^2 \\\\ = a x^2 + (b+2a) xy + (a+b+c)y^2 $$ and $$ D = \left(\begin{array}{cc} 1 & 0 \\\\ 1 & 1 \end{array}\right) : ax^2 + bxy + cy^2 \mapsto ax^2 + bx(x+y) + c(x+y)^2 \\\\ = (a+b+c)x^2 + (b+2c)xy + cy^2 .$$

Much the same action also works on each homogeneous space, and in each space also the action preserves the (integral) discriminant. But the quadratic discriminant, $\Delta(a x^2 + b xy + c y^2) = b^2 - 4 a c$, is particularly special, because on those polynomials with real roots ($x / y$), the discriminant is also positive. In the case we started with, the polynomial defining a square root, we are for the moment looking for the positive root, and walking in $SL(2,\mathbb{Z})$ in such a way that we don't loose this separation of the two roots: that is, we keep $a$ and $c$ of opposite signs, and walk first as far "left" as possible, and then as far "down"... Let's illustrate with $\sqrt{7}$, which as we all know is between $2$ and $3$: $$ \begin{array}{ccccl} a & b & c \\\\ \hline \\\\ 1 & 0 & -7 \\\\ 1 & 4 & -3 & L^2 & (-7+9\cdot 1 \gt 0)\\\\ 2 & -2 & -3 & D & (1 + 2\cdot 4 - 4\cdot 3 \lt 0)\\\\ 2 & 2 & -3 & L & (-3-2\cdot 2+4\cdot 2\gt 0)\\\\ 1 & -4 & -3 & D \\\\ 1 & 4 & -3 & L^4 & \mathrm{continues\\ periodically} \end{array} $$ From this we read the exponents $2,1,1,1,4$ and note that the sequence $1,1,1,4$ will repeat forever after: $$ \sqrt{7} = 2 + \frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{2+\sqrt{7}}}}} \\\\ = 2 + \frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{4 +\dots }}}} $$ Because we've chosen $a$ positive, and resolved to keep it so as we walk in $SL(2,\mathbb{Z})$, so $c$ is negative; and under that constraint the sizes of the coefficients are reasonably well-behaved; $a, -c$ are at most $\Delta/4$, and $|b| \lt \sqrt{\Delta}$; thus there are only finitely many $a,b,c$ with a given discriminant, which means that eventually some triple will be revisited in our walk --- hence every real quadratic number has an eventually-periodic continued fraction. The converse is a somewhat easier argument.

I'll leave it to the energetic reader (I do flatter myself) to adapt the preceding --- so far as it does adapt --- to directly computing the continued fraction of the $k$th real root of a general polynomial.

But now I emphasize a fine point as deserving attention: the representation of $SL(2,\mathbb{Z})$ on homogeneous polynomials is linear. Furthermore, we have another linear representation of $SL(2,\mathbb{Z})$, the defining representation, by which we can give ourselves two commuting actions of $SL(2,\mathbb{Z})$ on pairs of quadratic polynomials. The point of this is: should we want to compute the square root of a number $w$ somewhere between two and three, e.g., we know that the result will be between the square roots of two and of three --- that, so far as the continued fractions agree (or the underlying walks in $SL(2,\mathbb{Z})$), so will run the continued fraction of our underspecified number. But The Marvelous Thing is: once we find that these two continued fractions disagree, we can ask for more of the continued fraction for $w$ without re-computing the earlier polynomials establishing the first terms for $\sqrt{w}$. This is because the polynomial to start with for computing (e.g.) $\sqrt{5/2}$ is $2 x^2 - 5 y^2$, which is simply an appropriate linear combination of $1 x^2 - 3 y^2$ and $1 x^2 - 2 y^2$.

To illustrate, here's working out the beginning of $e^{1/2}$, which maybe we know from some other argument.

In its most general form, a continued fraction can be written as such:

where {an} and {bn} are infinite sequences of integers. If the sequences are finite, or end, the whole expression can be evaluated to a rational number, which takes the form of p/q where p/q are integers. We call b0 the integral part, or the integer part, of the fraction.

Finite Continued Fractions

Let's take 9/6 as an example. We can use the Euclidean Algorithm which has the form of:

9 = q0*6 + r0 where q0 = 1 and r0 = 3

6 = q1*3 + r1 where q1 = 2 and r1 = 0

since r1 = 0, we can stop the algorithm. Many people's introduction to this algorithm is for the purpose of finding the greatest common divisor/factor but here, we will use it to construct our finite continued fraction.

Taking the terms of the sequences {qn} to be our sequence of partial denominators, {bn}, and {rn} to be our sequence of partial numerators, {an} we get the following:

I strongly suggest repeating this process by yourself with other positive, rational numbers. Since integers are a subset of rational numbers, where they are in the form of q/1 where q is an integer, integers are the most trivial cases of continued fractions -- a fraction.

Remark: to find the continued fraction form of 6/9, we shift all the terms over by one place and set the b0 term to 0.

So far, we have only dealt with finite continued fractions -- what about infinite continued fractions?

Infinite Continued Fractions

Let's take a small detour to explain real numbers and how one can construct the reals.

In my Sequences and Series class, which was later renamed to Introduction to Mathematical Analysis, we proved that the set of real numbers can be constructed from a Cauchy sequence of rational numbers. I will spare you from the proof of such but in summary, say we have π, which is an irrational number, we can have a sequence of increasingly close approximations:

an = [3, 3.1, 3.14, 3.141, 3.1415, ...]

Notice how each term is truncated; this implies that each of these can be written in the form of a rational number.

an = [3/1, 31/10, 157/50, ...]

note: as much as I would *love* to write all of those fractions out, I am lazy :D

We've already seen that it is possible to write rational numbers as continued fractions and since the limit of the given sequence is π, we can write π as an infinite continued fraction approximation.

This is π's simple continued fraction approximation. What makes it simple is that for all n, an = 1. This allows us to write our continued fractions in the form of a list:

π = [3; 7, 15, 1, 292, 1, 1, ...]

Remark: Despite each example here being a simple continued fraction, there are many out there that are NOT simple. However, every real number does have a simple continued fraction form.

More About Continued Fractions

For a more in-depth and rigorous introduction that is also directed towards beginners, I recommend looking at these notes which were made for a short course on continued fractions by Dr. Gautam Gopal Krishnan.

A more analytical approach by Dr. Swastik Kopparty for his Algorithmic Number Theory class can be found here.

I used both of these as initial readings for a project with my school's Mathematics department and found them both very helpful.

Why This Topic?

I am currently participating in a Directed Reading Program and the topic I am reading about is, you guessed it, continued fractions. It has turned less into a reading project and more of a light research project but either way, I'm having loads of fun.

I might share the Github repo for it towards the end of the semester but for now, it shall stay private.

Feel free to ask questions!

Just wrapped up some Java code to compute logarithms in continued fractions. The results were pretty cool! As a bonus, the code is completely general. With most log implementations, the general logarithm is computed with the natural log using the base change identity. With this algorithm, it's totally base agnostic. And since Euler's number has an extremely regular structure as an SCF, natural logs can be computed with theoretically unlimited precision.

Here's the output of a small Groovy program to compute logarithms of a test value:

In mathematics, a continued fraction is an expression where a number is represented as the sum of its integer part and the reciprocal of another number, which is itself represented as the sum of its integer part and another reciprocal, and so on, until the last reciprocal is of a whole number with no fractional part. By convention, instead of writing out the full nested fraction form, we can denote a continued fraction by writing the integer part, followed by a semicolon, followed by the fractional parts separated by commas, all enclosed within square brackets.

Every distinct real number can be represented as a unique continued fraction. Rational numbers have finite, terminating continued fractions. Irrational numbers have infinite, non-terminating continued fractions.

The larger a given term in a continued fraction is, the less significant it is, since taking the reciprocal of a large number produces a small number to be added to the previous term. If the continued fraction of a number contains a large term, the number can be closely approximated with the shorter (finite) fraction obtained by truncating the longer (or infinite) continued fraction just before the large term. Conversely, the smaller a given term is, the more significant it is, with a value of 1 being the most significant in normal continued fractions.

For example, the continued fraction for the circle constant pi (π = 3.141592… = [3; 7, 15, 1, 292, …]) starts off with several large terms, so it can be closely approximated with simple fractions. The first fractional term is 7, which is already reasonably big, so we can chop off all the fractional terms and simply approximate π as 3.0, with an error of only 4.507%. The next fractional term is 15, over twice as large, so we can truncate the continued fraction after the 7 and approximate π as 3 + 1 / 7 = 22 / 7 = 3.142857…, with an error of only 0.040%. By this metric, π is not very irrational — it is very well approximated by simple ratios.

Compare that to the golden ratio phi (φ = 1.618033…), which is called the most irrational number because it is the number which can be least well approximated by finite fractions. The continued fraction for the golden ratio is an infinite string of ones ([1; 1, 1, 1, 1, …]), so every term is as significant as it can possibly be. To match the accuracy of the approximation of π without any fractional terms (4.507%) with φ, we need to keep the first three fractional terms of φ to get 5 / 3 = 1.666666… and an error of 3.006%. To match the accuracy of π approximated with one fractional term (0.040%), we need to keep the first eight fractional terms of φ to get 55 / 34 = 1.617647… and an error of 0.024%.

Some infinite continued fractions have repeating patterns, while others are random. The only numbers with infinite continued fractions that repeat exactly are quadratic irrational numbers, which are numbers that are the solution to some quadratic equation with rational coefficients.

For example, the continued fraction of the golden ratio consists of a repeating single-part unit {1}, while the continued fraction for the irrational number √(19) repeats the six-part unit {2, 1, 3, 1, 2, 8}. Other numbers have continued fractions that do not repeat exactly, but still show patterns. The continued fraction for Euler's number e = 2.718281... (a transcendental number) starts with the integer part 2 and then consists of three-part units of the form {1, 2 n, 1} with n starting from 1, giving the continued fraction [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, …]. Conversely, the continued fraction for π (also transcendental) is presumed (but not proven) to be random; no pattern has been found in the first several thousands of terms.

In normal usage of continued fractions, the first term is any real integer (positive, negative, or zero), the remaining terms are real non-zero positive integers, and the numerator of each fractional term is one. These are called simple continued fractions. The notion of continued fractions can be extended to include non-integer or complex terms, or numerators other than one, giving rise to generalized continued fractions. Unlike with simple continued fractions, there is no consensus on a concise way to write generalized continued fractions, so they must be written out in their full fraction form.

Suppose $x$ is an irrational number and we want a rational approximation to $x$ which is close but also has a small denominator (when expressed as a fraction in its lowest terms). If the approximation's denominator is to be as small as possible, i.e., equal to 1, so that the approximation is an integer, then there are two good choices: $[x]$ (the greatest integer which $x$ is greater than or equal to) and $[x] + 1$. These are the two closest integers to $x$. One of them may be closer than the other, but there's no need to worry about that too much; we just want an approximation which is close enough. So we can say that $[x]$ is our first good rational approximation to $x$.

But perhaps we'd like a closer rational approximation to $x$. The denominator of this approximation will have to be greater than 1, but, still, let's try and avoid making it too large. How can we find such an approximation?

Well, if we let $\{x\} = x - [x]$, then we have

\begin{equation} x = [x] + {x}. \end{equation}

If we have a good rational approximation to $\{x\}$, then we can substitute that for $\{x\}$ in the above equation to get a good rational approximation to $x$. But how do we find a good rational approximation to $\{x\}$?

If we just try the same strategy again and take $[\{x\}]$, that doesn't really work because $\{x\}$ is always greater than or equal to 0 and less than 1, so $[\{x\}]$ is always 0, and substituting this approximation to $\{x\}$ into the equation just gets us

\begin{equation} x \approx [x] + 0 = [x] \end{equation}

so it doesn't improve the approximation at all. However, if we take the reciprocal of $\{x\}$, $1/\{x\}$, well, that can be any real number greater than 1. (If $\{x\} = 1/2$, then $1/\{x\} = 2$; if $\{x\} = 1/3$, then $1/\{x\} = 3$; etc.) So $[1/\{x\}]$ can be any positive integer. And

\begin{equation} x = [x] + \cfrac 1 {1/\{x\}}, \end{equation}

so if you substitute a good rational approximation to $1/\{x\}$, such as $[1/\{x\}]$, for $1/\{x\}$ in this equation, then we get another good rational approximation, which is our second good rational approximation to $x$.

\begin{equation} x \approx [x] + \cfrac 1 {[1/\{x\}]}. \end{equation} But you could also work out the second good rational approximation to $1/\{x\}$, by doing exactly what we've just described but with $1/\{x\}$ in place of $x$, and substitute that second good rational approximation into the equation, rather than the first. By doing that, we get the third good rational approximation to $x$!

That's the whole of it, really, but some expansion on that last point about how to get the third good rational approximation wouldn't hurt. Let's assign some names to the expressions we've been dealing with, for convenience:

\begin{align*} t_0 &= x, \\\\ a_0 &= [x] = [t_0], \\\\ x_0 &= [x] = a_0, \\\\ t_1 &= \frac 1 {\{x\}} = \frac 1 {x - [x]} = \frac 1 {t_0 - x_0}, \\\\ a_1 &= \left[ \frac 1 {\{x\}} \right] = [t_1], \\\\ x_1 &= [x] + \frac 1 {[1/\{x\}]} = a_0 + \cfrac 1 {a_1}. \end{align*}

The real numbers $x_0$ and $x_1$ are our two good approximations so far. Note that $a_0$ and $a_1$ are both integers. I've assigned the names carefully so that you can see how $t_2$, $a_2$ and $x_2$ can be worked out in the same way that $t_1$, $a_1$ and $x_1$ were worked out:

\begin{align*} t_2 &= \frac 1 {t_1 - a_1} = \frac 1 {1/\{x\} - [1/\{x\}]} = \frac 1 {\{1/\{x\}\}}, \\\\ a_2 &= [t_2] = \left[ \frac 1 {\{1/\{x\}\}} \right], \\\\ x_2 &= a_0 + \cfrac 1 {a_1 + \cfrac 1 {a_2}} = [x] + \cfrac 1 {[1/\{x\}] + \cfrac 1 {[1/\{1/\{x\}\}]}}. \end{align*}

This $x_2$ is our third good rational approximation to $x$. ($a_1 + 1/a_2$ is our second good approximation to $1/\{x\}$.) Also, note that $a_2$ is, once again, an integer. Our first good rational approximation could be written in terms of a single integer, our second good rational approximation could be written in terms of two integers, and now our third good rational approximation can be written in terms of three integers.

In general, the recurrence relations are

\begin{align*} t_{n + 1} &= \frac 1 {t_n - a_n}, \\\\ a_{n + 1} &= [t_{n + 1}], \\\\ x_{n + 1} &= a_0 + \cfrac 1 {a_1 + \cfrac 1 {\ddots + \cfrac 1 {a_{n + 1}}}}, \end{align*}

and so we get three infinite sequences. The sequence $x_0$, $x_1$, $x_2$, \dots is our infinite sequence of good rational approximations to $x$. Each good rational approximation has a greater denominator, than the previous good rational approximation, but it's not too great. (In fact, it can be proven that every approximation in this sequence is the best approximation with its denominator, in the sense that there are no approximations closer to $x$ with the same denominator or a smaller denominator. I haven't shown that here, but hopefully the way I've explained the construction has helped you see why one might expect this to be the case, or at least expect the approximations to be economical with respect to denominator size in some sense.)

The other interesting sequence here is $a_0$, $a_1$, $a_2$, \dots, which supplies us with the integers that we use to construct the good rational approximations in the other sequence. These integers are called the partial quotients of $x$. The expressions involving these integers which the good rational approximations are equal to, i.e. those of the form $$ a_0 + \cfrac 1 {a_1 + \cfrac 1 {\ddots + \cfrac 1 {a_n,}}} $$ are called continued fractions. The sequence $a_0$, $a_1$, $a_2$, \dots is accordingly called the continued fraction expansion of $x$.

The continued fraction expansion is a way of representing $x$ in terms of integers, much like the decimal expansion of $x$. Compared to the decimal expansion, it has advantages and disadvantages. Probably more disadvantages than advantages, really. It has the nice property that it's unique: no two irrational numbers have the same continued fraction expansion. Also, it doesn't involve any arbitrary choice of base, although there is some arbitrariness in the choice to use $[x]$ instead of $[x] + 1$ as the first good approximation---in fact, people do sometimes find it useful to form continued fraction expansions that use $[x] + 1$, or the ceiling of $x$, instead of $[x]$, or which just use the closest integer. But its major crippling disadvantage is that expressing the continued fraction expansions of the sum or product of two real numbers in terms of their individual continued fraction expansions is in general a very complex and impractical task. Even just negation is tricky: consider the golden ratio $\sqrt 2$, which has the very simple continued fraction expansion

$$ 1, 2, 2, 2, \dots $$

Yet its negation, $-\sqrt 2$, has the continued fraction expansion

$$ -2, 1, 1, 2, 2, 2, \dots $$

It's the same after a certain point, but there's an extra finite sequence of integers added at the front, whose composition is not easy to predict. (I imagine it can be predicted in some way, but I don't know how you'd do it. It's certainly the case, as you can see if you think about it for a minute, the first term in the continued fraction expansion of a negative irrational number $x$ will be $-a_0 - 1$ where $a_0$ first term of the continued fraction expansion of the negation of $x$.)

Final note: I've only been talking about irrational numbers here, because for these numbers you can be assured that $a_n$ is never at any point equal to $t_n$, so that $t_{n + 1} = 1/(t_n - a_n)$ is always well-defined and does not involve a division by zero. If $t_n$ does equal $a_n$ at some point then $x$ is exactly equal to the continued fraction

$$ a_0 + \cfrac 1 {a_1 + \cfrac 1 {\ddots + \cfrac 1 {a_n,}}} $$