Recent posts

About

A non-violent anarchist Mathematics teacher and Christian who has views about everything under the sun.

  • Mathematical Displacement

    Launching Pad

    Russian Matryoshka dolls. (Source: Cambridge Mathematics)

    We are in the middle of a series on counting principles. In The Inclusion-Exclusion Principle, we saw a method of counting that ensured we counted everything while not double counting anything. Now, we are ready to go ahead with our study of derangements as promised.

    Understanding Derangements

    Let us first define what a derangement is. A derangement is a permutation or arrangement in which no item occupies a position it previously occupied. This, I guess, is still a little vague. So let us consider a couple of examples.

    Suppose we have a set of n letters that are in the mailperson’s bag. Obviously, each of these letters has an address on the envelop. However, if the mailperson delivers them such that no letter is delivered to the address on its envelop, then we have a derangement.

    Or suppose n patrons of a restaurant check their coats in with the maître d’. On their way out the patrons collect the coats, but none of them receives their own coats. In that case, we have a derangement.

    We could visualize a derangement as below

    Here, we have five items (A, B, C, D, and E). However, none of the items in green matches the corresponding item in red. Using the ordering ABCDE, the above derangement is BEACD. In what follows, I will use red lettering to indicate an item that is not deranged, that is, an item that is placed where it belongs. And I will use green lettering to indicate an item that is deranged, that is, an item that is not placed where it belongs.

    We can begin counting the number of possible derangements with small set sizes. For example, with 2 items, A and B, there are 2 permutations:

    As shown above, there is only one derangement.

    If we increase the set size to 3 items, A, B, and C, there will be 6 permutations:

    As can be seen above, there are only 2 full derangements.

    We can increase the set size to 4 items, A, B, C, and D, to get 24 permutations:

    As seen above, there are 9 full derangements, indicated in green boxes.

    Now, with a set of 5 items, we will have 5! or 120 different permutations. I don’t know about you, but I’m disinclined to even write out all these permutations, let alone scrutinize each to determine which items are deranged, then determine which permutations are indeed full derangements, and then to count the number of full derangements. If you have way too much time on hand for mind numbing tasks, please feel free to step away and undertake this not just for a set of 5 items, but a set of (say) 10 items, for which you can write down and scrutinize all the 3,628,800 permutations!

    You see, the factorial function grows at an alarming rate. What might even be manageable for a set of 5 items, with 120 permutations, becomes an onerous task for a set that is just double the size, with millions of permutations. Hence, there must be a better way of determining the number of derangements given the size of the set. And, thankfully, there is!

    We will proceed along two routes, both yielding the same result. But because the paths are different, we will discover different insights on the process. The first route we will adopt will use the inclusion-exclusion principle that we saw in the previous post. The second route will use a recursive formula.

    Derangements using the Inclusion-Exclusion Principle

    Given n items, there are n! different ways of permuting them. Out of these n! ways, there are (n – 1)! arrangements in which item 1 is fixed in its own position. These (n – 1)! arrangements include arrangements in which some other items may also be in their own positions. Similarly, there are (n – 1)! arrangements in which item 2 is fixed in its own position. Again, these (n – 1)! arrangements include arrangements in which some other items may also be in their own positions.

    Of course, for each of the n items there are (n – 1)! arrangements in which that item is fixed in its own position. Since there are n items in all, we are looking at

    arrangements in which at least 1 item is fixed in its own position.

    So now we have in consideration the initial n! less the arrangements in which 1 item is fixed. Hence under consideration now are

    arrangements. It is clear, however, that there has been double counting for arrangements in which any pairs of items are both in their own positions. Hence, per the inclusion-exclusion principle, we now need to add all the arrangements in which pairs of items are fixed in their positions.

    Suppose items 1 and 2 are fixed. There are (n – 2)! such arrangements and these arrangements include arrangements in which items other than 1 and 2 are also fixed in their positions. There are, of course nC2 different pairs of items and for each such pair there will be (n – 2)! arrangements in which the items in the pair are fixed in their positions. So we are looking at

    arrangements in which 2 or more items are fixed in their positions. As mentioned, due to double counting, these need to be added back. After this adjustment we will be considering

    arrangements. Of course, now we have overcompensated for the arrangements in which 3 items are fixed in their positions. We will need to subtract these.

    Now supposed items 1, 2, and 3 are fixed in their positions. There are (n – 3)! such arrangements and these will include arrangements in which items other than 1, 2, and 3 are also fixed in tier positions. There are nC3 different triplets of items and for each such triplet there will be (n – 3)! arrangements in which the items of that triplet are fixed in their positions. So we are looking at

    These arrangements will need to be subtracted from the running total that we have, yielding

    Continuing in this manner, we can see that the final number of derangements after all the appropriate inclusion-exclusion will be

    This can be written in a more compact form as

    Using this formula we obtain the table below for values of n up to 10.

    Derangements using a Recursive Formula

    The second method for counting derangements is by using a recursive formula. We will first derive the recursive formula and then modify to demonstrate that it is equivalent to the one we just derived. Once again, we start with a set of n items. Now consider item 1. In order for us to end with a derangement, this item must be placed in one of positions 2 to n. Hence, there are n – 1 ways of placing item 1. Since the number of derangements is a whole number, we can conclude that

    where X is another whole number that we have to determine. Till now, we have placed 1 of the n items in a position other than its own.

    Now let us focus on the kth item since it has been dislodged by item 1. We can either place it in position 1 or in one of the remaining n – 2 positions. It we place the kth item in position 1, then we still have to derange the remaining n – 2 items, which can be done in Dn – 2 ways. If we do not place the kth item in position 1, then there are still n – 1 items, including the kth item, that have to be deranged, which can be done in Dn – 1 ways. Since the kth item must go either in position 1 or in one of the other n – 2 positions, the two cases are mutually exclusive and exhaustive. Hence, we can conclude that

    The expression in the square brackets should remind us of the binomial identity

    You will recall from The World of Sagacious Selections, in which we dealt with combinatorial arguments, that we derived the above result for choosing r out of n items by focusing on one item, concluding that the selection either does contain this item, represented by the first term on the right, or does not contain this item, represented by the second term on the right.

    While deriving the recursive equation

    we used the same idea of focusing on one item and deciding whether it still needs to be deranged, represented by the first term in the square brackets, or has already been deranged, represented by the second term.

    This can be expanded and rearranged as follows:

    Supposed we designate

    Then we can see that the earlier equation can be written as

    Using this recursively we get

    Substituting in terms of the derangement values we get

    This can be rearranged as

    We can now substitute values for n to obtain the corresponding expressions for Dn. This will give us

    Considering the expression for D6, we can see that it can be rewritten as

    And since 0!=1!=1, we can further write it as

    Using sigma notation, this can be written as

    This can be generalized to

    which is exactly the same expression we obtained earlier using the inclusion-exclusion principle.

    Derangements and the Inclusion-Exclusion Principle

    The formula for derangements can be further written as

    where the nested parentheses show how the inclusion-exclusion principle works, much like the matryoshka dolls in the image at the start of this post. What this formula tells us it that we can calculate the number of derangements by considering the total number of permutations and subtracting the cases where at least 1 item is fixed, subtracting the cases where at least 2 items are fixed, subtracting the cases where at least 3 items are fixed, and so on. Due to the fact that (-1)n oscillates between 1 and -1, the nested parentheses accomplish the same final result as do the alternating signs in the original formula we obtained, namely

    Why Derangements aren’t Deranged

    So far the discussion has been reasonably theoretical. And you might wonder if there is any reason for understanding derangements beyond the curiosity of mathematicians. I’ve tried to determine how the idea of derangements came about but have not been able to land on a definitive answer. It is quite likely, as in many cases in mathematics, that some mathematician just toyed with the idea and that the idea later found applications. So what are some of these applications?

    In the workplace, if you wish to ensure everyone in a team has the opportunity to be responsible for every process, the idea of derangements is essential. In fact, if the team leader intentionally uses the idea of derangements, he/she could reallocate in a more efficient manner than just reassigning and checking if he/she has obtained a full derangement.

    In coding, the idea of derangements is used to check for coding errors. In stochastic processes, derangements are used to determine the entropy of a system. In chemistry, the idea of derangements are used in the study of isomers, the number of which increases rapidly especially for compounds with long carbon chains. In graph theory, the idea of derangements can be used to determine unique walks or paths in a graph. In optimization, derangements are used in situations similar to the traveling salesman problem or the assignment problem.

    In other words, while it is likely that the idea of derangements began with the toying of a mathematician, it has a wide range of applications today. But what surprises me in something that I am going to deal with in the next post. It is a result that is shocking to say the least and downright mysterious. Whatever could it be? And with that cliff hanger, I bid you au revoir for a week.

  • The Inclusion-Exclusion Principle

    Recapitulation

    We are currently in the middle of a series on counting principles. At the conclusion of the previous post, I had promised you that we would look at the idea of derangements. However, I realized that we need to lay some ground work before we get to derangements. When we count, how do we ensure that we are not double counting any element? In other words, “How do we ensure that we count every item without counting any item more than once?” Anyone who is involved in any kind of statistical study needs to pay attention to this so that each data point is given the same weightage. So let me introduce you to the inclusion-exclusion principle.

    Basics with Two Categories

    We begin with the most basic set-up with all items classified into two categories (say A and B). Since items can have multiple classifications, we can represent this using the Venn diagram below:

    The Venn diagram has three regions labelled 1, 2, and 3. Set A includes regions 1 and 2, while set B includes regions 2 and 3. If we just add the number of items in sets A and B, we can see that the central region (2) will be counted twice. In other words, the items that belong in both sets will be double counted. To avoid this, we need to subtract the items that belong in the intersection of the two sets.

    This can be written as

    The last term on the right side of the equation recognizes that some items have been ‘included’ more than they need to be and explicitly ‘excludes’ them from the count. This adjustment by excluding what was included too many times is what gives the principle its name.

    Counting with Three Categories

    Of course, we know that demographics includes many more than two categories. So how would the inclusion-exclusion change if we had three categories? The Venn diagram below indicates the situation.

    As shown in the diagram, there are now 7 distinct regions. Set A includes regions 1, 2, 4, and 5. Set B includes regions 2, 3, 4, and 6. And set C includes regions 4, 5, 6, and 7. If we add sets A, B, and C, we will count regions 2, 5, and 6 twice and region 4 thrice. We can proceed as before and exclude the intersection regions of two sets. But since region 4 belongs to A∩B, B∩C, and C∩A, we will have excluded region 4 thrice. This means that regions 1, 2, 3, 5, 6, and 7 are now counted once, but region 4 is not counted. Of course, it is a simple matter to add it back to include it. This is represented as

    We have encountered the terms like the ones in red before in the case where we had only two categories, A and B, and had to compensate for overcounting the regions in the intersection of the two sets. The term in green is a new term, introduced because, by compensating for the overcounting of the regions in the intersections of pairs of sets, we ended up undercounting the intersection of all three sets.

    Extension to Four Categories

    What would happen if there were more than 3 categories? Unfortunately, a 2 dimensional representation will no longer suffice. So let us label the regions as follows: 1: only A; 2: only B; 3: only C; 4: only D; 5: only A and B; 6: only A and C; 7: only A and D; 8: only B and C; 9: only B and D; 10: only C and D; 11: only A, B, and C; 12: only A, B, and D; 13: only A, C, and D; 14: only B, C, and D; and 15: A, B, C, and D.

    Now set A includes regions 1, 5, 6, 7, 11, 12, 13, and 15. Similarly set B includes regions 2, 5, 8, 9, 11, 12, 14, and 15. Set C includes regions 3, 6, 8, 10, 11, 13, 14, and 15, And D includes regions 4, 7, 9, 10, 12, 13, 14, and 15. Now, when we just add A, B, C, and D, the regions 5 to 10 will be counted twice, regions 11, 12, 13, and 14 will be counted thrice, and region 15 four times. The over counting for regions 5 to 10 would need an ‘exclusion’ by subtracting the intersection of pairs of sets. However, this would mean that the regions that involve the intersection of exactly three sets (i.e. 11, 12, 13, and 14) would have been ‘excluded’ three times over, meaning that they would not be ‘included’ anymore. It would also mean that the region 15 has been counted negative 2 times! This can be adjusted by now ‘including’ these four regions. However, this means that region 15 is now ‘included’ 2 times. Hence, we make a final adjustment and subtract the intersection of all four sets. This is represented as

    Here the red terms represent the adjustments for regions 5 to 10, the green ones for regions 11 to 14 and the blue one for region 15.

    Generalization

    If we continue in this manner, adding more categories, we will be able to demonstrate that

    This can be written in a more compact form as

    I recommend you take a close look at how the last two equations are actually the same as we will need such ‘parsing’ of formulas in future posts!

    What we have seen here is that we can recursively ‘exclude’ intersections with greater number of sets and in so doing avoid the twin traps of overcounting and undercounting. With this foundation, in the next post we will look at a way of counting ‘derangements’. Stay grounded till then.

  • Prime Powers in Factorials

    Optimus Prime (Source: Wikipedia)

    In the previous post in the series on Counting Principles, we looked at the technique of partitions. I concluded with the promise to deal with the exponent of prime p in the number n!. And you may be wondering what in the world that means. First, let us remind ourselves what n! denotes. Read ‘n factorial’, it is defined as the product of all natural numbers up to and including n. Hence, 2! = 1 × 2, 5! = 1 × 2 × 3 × 4 × 5, etc.

    Now suppose we divide 5! by 2. How many times can we do it before we get a remainder? Now, 5! = 120. Dividing this by 2 gives us 60. Dividing this by 2 gives us 30. Dividing this by 2 gives us 15. Since 15 is an odd number, we cannot divide it by 2 without getting a remainder. Hence, 120 could be divided by 2 three times. Hence, the exponent of 2 in 5! is 3, which is to say that the largest possible power of 2 that can divide 5! is 23.

    In a similar way, 7! = 5040. Let us try to divide by 3. 5040 divided by 3 gives us 1680. Dividing this by 3 gives 560. Now, it is clear that 560 is not divisible by 3. Hence, the exponent of 3 in 7! is 2, which means that the largest power of 3 that can divide 7! is 32.

    Our purpose here is to obtain a generalized method of obtaining this exponent without actually performing the division. Let us look closer at the division of 7! by 3. 7! can be expanded as

    It is clear that only the numbers in red allow a division by 3. And there are two such numbers. Since we are dividing by 3, we can realize that every third number will be a multiple of 3. Hence, since we are dealing with 7!, and 7 ÷ 3 = 2 ⅓, we can conclude that there will be two multiples of 3 from 1 to 7. Hence, the exponent of 3 in 7! is 2.

    If, on the other hand, we wanted to find the exponent of 3 in 20!, we would proceed as follows.

    Once again, the numbers in red allow a division by 3. However, the numbers is purple allow for a division by 9, that is 32. Here we can see that every third number is a multiple of 3 and every ninth number is a multiple of 9. This is obvious. Since 20 ÷ 3 = 6 ⅔, there will be 6 multiples of 3 from 1 to 20. And since 20 ÷ 9 = 2 ²⁄₉, there will be 2 multiples of 9 from 1 to 20. Since each multiple of 9 contributes another factor of 3, this means that the exponent of 3 in 20! will be 6 + 2 = 8. We can check this an perform

    which is clearly not divisible by 3. Let us proceed to generalize this result for any number n! and any prime p.

    First let us define the floor function. Given a real number x, the floor function is defined as follows

    In plain English, the floor of x, denoted by ⌊x⌋ is the greatest integer that is less than or equal to x. Hence, if x = 2.1, ⌊x⌋ = 2. If x = 3.78, ⌊x⌋ = 3. Care must be taken with negative numbers. If x = -2.93, ⌊x⌋ = -3. If x = -5.41, ⌊x⌋ = -6. Of course, if x = 7, ⌊x⌋ = 7 and if x = -7, ⌊x⌋ = -7.

    Consider the earlier calculations, 7 ÷ 3 = 2 ⅓, 20 ÷ 3 = 6 ⅔, and 20 ÷ 9 = 2 ²⁄₉, giving us 2 multiples of 3, 6 multiples of 3, and 2 multiples of 9 respectively. It is clear that these numbers represent the floors ⌊2 ⅓⌋ = 2, ⌊6 ⅔⌋ = 6, and ⌊2 ²⁄₉⌋ = 2.

    In other words, when determining the exponent of 3 in 7!, we obtained ⌊7 ÷ 3⌋ = 2, to give the result of 2. Similarly, when determining the exponent of 3 in 20!, we obtained ⌊20 ÷ 3⌋ = 6 and ⌊20 ÷ 32⌋ = 2, to give the result of 8.

    We are now in a position to generalize the result. In general, every pth number will be a multiple of p. Even more generally, every (pk)th number will be a multiple of pk. Hence, there will be ⌊n ÷p⌋ multiples of p from 1 to n, ⌊n ÷p2⌋ multiples of p from 1 to n, ⌊n ÷p3⌋ multiples of p3 from 1 to n, etc.

    Hence, the exponent of p in n! is given by

    Let us use this result to determine the exponent of 3 in 100!. Since 34 ≤ 100 ≤ 35, r = 4. Hence,

    If we perform the calculation we will realize that

    which is not divisible by 3.

    So, how many zeroes are there at the end of 100!? Now, a zero at the end of a number indicates a multiple of 10. So we are trying to determine the exponent of 10 in 100!. However, 10 = 2 × 5. Moreover, for every multiple of 5, we have at least 2 multiples of 2. See the figure below, where numbers in red are multiples of 2 but not 5, numbers in purple are multiples of 5 but not 2, and numbers in green are multiples of 2 and 5.

    There are at least 2 red or green numbers for each purple or green number. Hence, to find the exponent of 10 in 100!, we need only to find the exponent of 5 in 100!. Per the earlier formula, this is

    This means that there are 24 zeroes at the end of 100!. Indeed, we can use a computational engine and determine that

    100! = 93, 326, 215, 443, 944, 152, 681, 699, 238, 856, 266, 700, 490, 715, 968, 264, 381, 621, 468, 592, 963, 895, 217, 599, 993, 229, 915, 608, 941, 463, 976, 156, 518, 286, 253, 697, 920, 827, 223, 758, 251, 185, 210, 916, 864, 000, 000, 000, 000, 000, 000, 000, 000. It is clear that there are 24 zeroes at the end of the number.

    In this post we dealt with the exponent of a prime p in the number n!. We obtained a relatively easy to apply formula to determine this. In the next post, we will tackle what are known as derangements. Till then, stay sane!

  • The Technique of Partitions

    After an extended break for Lent, we continue with the series on counting principles. I had ended the last post in the series with a promise that we will look into the technique of partitioning. And I had left you with a problem to solve: Given that x, y, and z are natural numbers, how many solutions exist to the equation x + y + z = 100? Let us begin to address this with a simpler problem.

    Suppose we are given that x + y = 10 and that x and y are natural numbers, how many solutions are there? Here, we can write y = 10 – x. Now, we can simply increase x from the smallest value 1 to the largest value 9. We can obtain the following ordered pairs as solutions: (1, 9), (2, 8), (3, 7), (4, 6), (5, 5), (6, 4), (7, 3), (8, 2), and (9, 1). We can visualize this as follows

    Since all the ‘1’s are identical, there is no sense in thinking of ordering them. However, we can see the partition in red. Including the partition, there are 10 + 1 = 11 items, the 10 identical ‘1’s and the partition, that need to be placed in a row. However, only the position of the partition matters. If the partition is in position 2, then we have x = 1 and y = 9. However, the partition cannot be placed in positions 1 and 11 because then either x or y would be zero. Hence, what we have is a choice of 9 positions for the partition, from position 2 to position 10, giving us 9 solutions to the original equation.

    What we can say is that, we had 11 items to place. However, we were first constrained to fill each of the variables x and y with a 1, thereby ensuring that we have only positive values for each of them. This left nine items, including eight ‘1’s and the partition. And since we had one partition, the problem boiled down to choosing one position out of nine, which is 9C1 = 9.

    Now, let us consider the original problem. We want to find the number of natural number solutions to the equation x + y + z = 100. We recognize that, since there are three variables, we will need two partitions, leaving us with 102 items. However, we will first have to distribute one ‘1’ to each of the variables to ensure that we have only natural number solutions. This leaves us with 99 items. Now, the two items have to be placed in the 99 positions that remain, which can be done in 99C2 = 4851 ways. This means that there are 4851 solutions to the equation x + y + z = 100 such that x, y, and z are natural numbers.

    We can generalize this process. Suppose we have n identical items that need to be divided into r groups such that no group is empty. Now, for r groups we will need r – 1 partitions, leading to a total of n + r – 1 items. Now, we need to fill each of the groups with one item to ensure that no group is empty. This leaves us with n – 1 items. And we have to place r – 1 partitions, which can be done in n – 1Cr – 1.

    We can now relax the restriction on the numbers and say that they need not be natural numbers (i.e. greater than zero), but whole numbers (i.e. greater than or equal to zero). In this case, we are permitting empty groups. Now the problem reduces to placing r – 1 partitions in n + r – 1 positions, which can be done in n + r – 1Cr – 1 ways. Hence, if we return to the original problem, the number of solutions to x + y + z = 100 such that x, y, and z are whole numbers is 102C2 = 5151.

    In this post, we looked at the technique of partitions. In the next post, we will consider the exponent of a prime number p in the number n! Look out for that!

  • Descending the Ivory Tower

    As mentioned earlier, I am taking a break from publishing new material for a few weeks. During these weeks I am republishing the series on e and the one on π. The post below was originally published on 20 September 2024. I will resume with the series on counting principles next Friday.

    Coming Back Full Circle

    This is the final post in this series of posts on π. We began with A Piece of the Pi, where we looked at the early ways of approximating the value of π based on circumscribing and inscribing a circle with regular polygons. We saw that this method, while perfectly sound, had two drawbacks. First, it only provides upper and lower bounds for the value of π rather than an actual approximation of the value. Second, the method converges extremely slowly. This was followed by Off On a Tangent, in which we introduced infinite series Machin-like methods based on the inverse tangent functions. This was followed by The Rewards of Repetition, in which we introduced iterative methods used to approximate the value of π. Last week, we looked into the Gauss-Legendre algorithm, which is a powerful iterative method. In this post, we move toward some methods that are used more commonly for the purpose.

    Efficient Digit Extraction Methods

    Efficient methods for approximating π often are based on the Bailey-Borwein-Plouffe formula (BBP) from 1997, by David Bailey, Peter Borwein, and Simon Plouffe, according to which

    Right away, we can see the strangeness of this formula. There seems to be no rationale linking the four terms in the parentheses, nor any indication for why the formula includes the 16k factor in the denominator.

    This was later improved upon by Fabrice Bellard’s formula, according to which

    It is clear that things have gotten stranger than before! However, Bellard’s formula converges more rapidly than does the BBP formula and is still often used to verify calculations.

    The advantage of the BBP and Bellard methods is that they converge so rapidly that there is hardly any overlap between the digits of terms. This allows the calculation to be started at a higher value of k than 0 in order merely to check the last string of digits of π than the whole string. After all, if we have previously checked a certain formula for accuracy till 1,000,000,000 digits, then the next time we generate digits using the same formula, we need only to check the digits from the 1,000,000,001th digit.

    This advantage of the BBP and Bellard formulas makes them particularly suited for this digit check. Due to this, they are often categorized as efficient digit extraction methods.

    Ramanujan Type Algorithms

    The Ramanujan series for π (Source: Facebook)

    Despite that rapidity with which the BBP and Bellard formulas converge, they are not used today to calculate further digits of π. This is because from Ramanujan we have the infinite series approximation

     which converges even more rapidly. This is a very compact formula. Yet, almost all the elements of the formula (√2, 9801, (4k)!, 1103, 26390, (k!)4, and 3964k) are, if we are being honest, weird. Only perhaps the 2 in the numerator can be considered as not weird. Even the fact that this series gives us approximations for the reciprocal of π rather than π itself is strange since this does not function as series that give us approximations for π. In particular, since it approximates 1/π, it cannot be used for digit checks like the BBP and Bellard formulas. However, it is precisely because the series gives the reciprocal of π that it converges much more rapidly than the BBP and Bellard formulas.

    In 1998, inspired by the Ramanujan formula, the brothers David and Gregory Chudnovsky, derived the formula

    Here, every single element is weird! However, the Chudnovsky algorithm converges so rapidly that each additional term gives approximately 14 additional digits of π. If you are interested you can find the 120 page proof of the Chudnovsky algorithm here.

    The Chudnovsky algorithm is so rapid that it is the one that has been used often since 1989 and exclusively since 2009. The results are checked by the BBP and/or Bellard formulas. On Pi Day 2024 (i.e. March 14, 2024), the Chudnovsky algorithm was used to calculate 105 trillion digits of π. Just over three months later, on Tau Day 2024 (i.e. June 28, 2024), the calculation was extended to 202 trillion digits.

    Forced to Compromise

    Despite the rapidity of the Chudnovsky algorithm, it is the Gauss-Legendre algorithm that actually converses more rapidly. However, after April 2009, the Gauss-Legendre algorithm has not been used, the final calculation on 29 April 2009, yielding 2,576,980,377,524 digits in 29.09 hours.

    If the Gauss-Legendre algorithm is more rapid, why is it not used anymore? Let us recall the algorithm. The Gauss-Legendre algorithm begins with the initial values:

    The iterative steps are defined as follows:

    Then the approximation for π is defined as

    So at each step, we need to have an, bn, pn, and tn in memory, while an+1, bn+1, pn+1, tn+1 and πn have to be calculated. Once this latter set has been calculated, the former set has to be replaced with the latter set before this can be done. The calculation done in April 2009 used a T2K Open Supercomputer (640 nodes), with a single node speed of 147.2 gigaflops, and computer memory of 13.5 terabytes! By contrast, the December 31, 2009 calculation using the Chudnovsky algorithm to yield 2,699,999,990,000 digits used a simple computer with a Core i7 CPU operating at 2.93 GHz and having only 6 GiB of RAM. The difference in the hardware requirements and consequent costs are so large that recent calculations have used the less efficient Chudnovsky algorithm rather than the more efficient Gauss-Legendre algorithm. So it seem that even mathematicians have to climb down from their ivory towers and confront the banal realities of the world!

  • The Rewards of Repetition

    As mentioned earlier, I am taking a break from publishing new material for a few weeks. During these weeks I am republishing the series on e and the one on π. The post below was originally published on 6 September 2024.

    Coming Back Half Circle

    Representation of iteration (Source: Study.com)

    We are in the middle of a series of posts on π. We began with A Piece of the Pi and followed it up with Off On a Tangent. In the first post I demonstrated that the definition of π is inadequate for the task of approximating the value of π. I then looked at a common approach to approximating the value of π using regular polygons. In the second post, I introduced the idea of infinite series methods to approximate the value of π and we saw what made some series converge quicker than others. In this post I wish to look at some iterative methods of approximating the value of π. The iterative methods, in general, tend to converge more rapidly than even the infinite series methods.

    However, the mathematics behind these iterative methods is significantly higher than what I planned for this blog. Due to this, I will not give the details of the iterative methods but only give an outline to the methods, discussing how each step is accomplished and showing how the whole process fits together. However, that too will have to wait till the next post because laying the groundwork for the iterative methods will take the rest of this post!

    Convergence of an Infinite Series

    To begin with, let us consider the difference between an infinite series and an iterative process. In an infinite series, one must keep adding (or multiplying if the series if a product) more terms to bring the sum (or product) closer to the actual value of the number we are approximating. Since, for the series to be viable, it must converge, this means that each subsequent term of the series is smaller in magnitude. After all, given a sequence {an}, one condition for convergence is

    Riemann sum iterations (Source: MIT OpenCourseWare)

    This necessarily means that subsequent terms can only alter the approximation by increasingly smaller amounts, thereby essentially decreasing the speed with which the series converges. In other words, the very nature of a series means that it cannot converge as rapidly as we would want. A milestone calculation using an infinite series was in November 2002 by Yasumasa Kanada and team using a Machin-like formula (introduced in the previous post), resulting in 1,241,100,000,000 digits in 600 hours. In April 2009, the Gauss-Legendre algorithm that we will discuss in this post and the next was used by Daisuke Takahashi and team to determine 2,576,980,377,524 digits in 29.09 hours. We can see that this involves more than twice the number of digits obtained by Kanada and team in less than 1/20 of the time, indicating how fast the iterative process is. Why is this the case?

    Convergence of Iterative Formulas

    Iterative methods use current approximate values of the quantity to obtain better approximations of the quantity. To see how this works let us consider an iterative method used to obtain one of the iterative formulas for π.

    Given two positive numbers, a and b, the arithmetic mean (AM) and geometric mean (GM) of the numbers is given by

    Now suppose we generate the iterative formula

    All we need are starting values of a0 and b0 and we should be able to generate the iterative series.

    Suppose we choose a0 = 2 and b0 = 1. Then we get the following table

    As can be seen from the last column, by the time we reach the third iteration, the AM and GM values have converged and are equal. Here I must observe that the final column betrays the inability of the Google Sheets computational engine to calculate beyond a certain lower bound for the error. Hence, the final column should be taken with a pinch of salt. The values of an and bn will never be equal if we start with different values of an and bn.

    Suppose we start with the numbers a little further apart. Say a0 = 200 and b0 = 1. We would get the following table

    As can be seen, the values of AM and GM have converged by the fifth iteration.

    So what if we make a0 = 1,000,000 and b0 = 1? We would get the following table

    This table reveals the limitations of the Google Sheets computational engine since all the errors after the 6th iteration are the same. This is impossible. However, you get the idea. The error between AM and GM has dropped to below 1 part in 10 billion by the 6th iteration.

    The above tables demonstrate the rapid convergence of iterative formulas. And this fact of rapid convergence is used in most iterative methods for approximating π.

    The Gauss–Legendre Algorithm

    Depiction of fixed point iteration such as involved in the Gauss-Legendre Algorithm (Source: IITM Department of Mathematics)

    One of the first iterative methods is the Gauss–Legendre algorithm, which proceed as follows. We first initialize the calculations by setting

    The iterative steps are defined as follows:

    Then the approximation for π is defined as

    Using the algorithm, we get the following table

    As can be seen, the Google Sheets engine is overwhelmed by the 3rd iteration itself. However, the approximation to π is already correct to 8 decimal places by then. In general, the Gauss–Legendre algorithm doubles the number of significant figures with each iteration. This means that the convergence of this iterative method is not linear, like the infinite series methods, but quadratic. The fourth iteration of the algorithm gives us

    where the red 7 indicates the first incorrect digit, meaning that in 4 iterations, we have 29 correct digits of π, indicating how rapidly the method converges.

    Wrapping Up

    Quite obviously, many readers may be wondering how such iterative methods are found and how we can be certain that they are reliable methods for approximating π. In the next post, we will break down the Gauss-Legendre algorithm into the distinct parts. Some parts involve mathematics at the level of this blog and we will unpack those. For the other parts, which involve mathematics at a higher level than expected for this blog, I will only give broad outlines and the results. (I will provide links for readers who wish to see the higher mathematics.)

    In the post after that I will look at some quirky infinite series and iterative methods that mathematicians have devised over the years. This will show us how creative mathematicians have had to be precisely because the definition of π is practically useless for approximating its value. This, of course, sets it apart from e, the definition of which is perfectly suited to obtaining accurate approximations of its value.

    However, despite the rapid convergence of the iterative methods, most recent calculations, including the 202 trillion digit approximation of π done on 28 June 2024, use the Chudnovsky algorithm. We will discuss this powerful algorithm that involves a quirky infinite series in the post after the next. We will also consider why the Chudnovsky algorithm is preferred to iterative methods.

  • Off On A Tangent

    As mentioned earlier, I am taking a break from publishing new material for a few weeks. During these weeks I am republishing the series on e and the one on π. The post below was originally published on 16 August 2024.

    A Slice of the Pi

    A visualization of the distribution of digit values in the digits of π (Source: The Flerlage Twins)

    We are in the middle of a study of π. In the previous post, A Piece of the Pi, we introduced π. We saw how its definition itself, based on measurement, is inadequate for calculating the value of π to a great accuracy. We then saw how mathematicians circumvented this problem by using inscribed and circumscribed regular polygons to obtain lower and upper bounds for the value of π. We saw that that endeavor culminated with the efforts of Christoph Grienberger, who obtained 38 digits in 1630 CE using a polygon with 1040 sides! We realized that this method, while mathematically sound, converges too slowly to be of any long term practical use.

    At the end of the post, I stated that there were two broad approaches to address this issue, one using iterative methods and the other using infinite series. We will deal with the infinite series approach here and keep the iterative method for later.

    Snail’s Pace To Infinity

    Since π is a constant related to the circle, it should come as no surprise that the most common infinite series are derived using the circular functions, a.k.a. the trigonometric functions. Specifically, since 2π is the measure of the angle around a point in radians, the inverse trigonometric functions, which map real numbers to angles are used.

    Now we haven’t yet dealt with deriving infinite series using calculus in this blog. I assure you I will get to that soon. For now, I ask you to take my word with what follows. Using what is known as the Taylor series, we can obtain

    which is known as the Gregory-Leibniz series after James Gregory and Gottfried Leibniz, who independently derived it in 1671 and 1673 respectively.

    Using the Gregory-Leibniz series and knowing that arctan 1 is π÷4 we can substitute x = 1 to obtain

    We can take increasingly more terms of this series to see how it converses. Doing so gives us the following

    We can see that this series also converges quite slowly. Even after n = 10000, we only have π accurate to 2 decimal places! Unfortunately, even though I have a Wolfram Alpha subscription, the computational engine timed out for values greater than 10000. So that’s the maximum I was able to generate. But it should be clear that this series produces values that are no better than the ones generated using the regular polygons.

    Machin-like Formulas

    However, mathematicians are quite creative. Using the formulas

    it is not too difficult to obtain

    as derived by John Machin in 1706 or

    as derived by Leonhard Euler in 1755. Of course, to evaluate the inverse tangent functions, both Machin and Euler would have had to use series similar to the one from the Maclaurin series. Using his equation, Machin obtained 100 digits for π, while Euler used his equation to obtain 20 digits of π in under one hour, a remarkable feat considering that this had to be done by hand!

    Formulas such as the previous two are called Machin-like formulas and were very common in the era before computational devices like calculators and computers were invented. This finally led to the 620 digits of π calculated by Daniel Ferguson in 1946, which remains the record for a calculation of π done without using a computational device. Interestingly, in 1844 Zacharias Dase used a Machin-like formula to calculate π to 200 decimal places. And he did it all in his head! Now that’s not only some commitment, it’s a gargantuan feat of mental gymnastics!

    Convergence of Machin-like Series

    We can see why the Machin-like formulas converge more quickly than the original Gregory-Leibniz series. With x = 1, the powers of x are all identical. This means that the convergence is dependent solely on the slowly increasing denominators of the alternating series.

    However, the Machin-like formulas, split x into smaller parts. And since

    each subsequent term is dependent also on the convergence of a geometric series with common ratio between 0 and 1. Since the geometric series converges reasonably rapidly, all we have to do is determine an appropriate split, such as done by Machin and Euler. Naturally, the smaller the parts, the more rapid will be the convergence. Hence, even though

    the Machin-like formulas use smaller fractions, like 1/5 and 1/239, as used by Machin, or 1/7 and 3/79, as used by Euler, to ensure much more rapid convergence.

    Other Infinities

    In addition to infinite series, which involve the summation of infinite terms, mathematicians have also derived infinite products. In 1655, John Wallis derived the equation involving the infinite product, known as the Wallis product, given by

    which can also be written as

    The derivation of this, however, requires an iterative formula. Hence, we will leave a further study of the Wallis product for the next post.

    However, what we can understand from the study of π compared to what we discovered with e is that mathematicians are skilled at overcoming limitations by looking at things from a different perspective. There is a certain intuition and creativity involved in such innovative ideas and calls into question the unfortunately oft repeated untruth that mathematics is a purely left-brained activity.

  • A Piece of the Pi

    As mentioned earlier, I am taking a break from publishing new material for a few weeks. During these weeks I am republishing the series on e and the one on π. The post below was originally published on 9 August 2024.

    Definitionally Limited

    (Source: Live Science)

    Almost everyone who has studied beyond Grade 4 has probably heard of the mathematical constant π. Students are told that π represents the ratio of the circumference of a circle to its diameter. That is all well and good. But how do we calculate it? I mean, we could potentially use a piece of string to measure both the circumference and the diameter. Even assuming no error in determining one exact rotation around the circle (for the circumference) and diametrically opposite points (for the diameter), the experiment is limited by the measuring instruments.

    Suppose, however, we have access to measuring instruments (necessarily hypothetical) that can measure to the accuracy of the Planck length (i.e. 1.616255)×10-35 m), we will still only get measurements with about 40 significant figures. Since the accuracy of a mathematical calculation cannot exceed the accuracy of the least accurate number in the calculation, we will get a result that has 40 significant figures for π. Actually, if we look at any measuring instrument, we will see that there are hardly any that give more than 4 significant figures. This means that even obtaining 3.1416 as a 5 digit approximation for π is a pipedream if we take the measurement.

    However, we are told quite early on that π is an irrational number. This means that, when we attempt to write π in a decimal format, the expression continues endlessly without any pattern of repetition. What this means is that the definition of π cannot be used to determine its value! In fact, we should have known this precisely from the definition. If C÷D is irrational, at least one of the numbers, C and D, must be irrational. Otherwise, C÷D will give us a rational number. So we can see that the definition of π that is based on measurement is an impractical way of obtaining the value of an irrational number like π.

    Now, if you refer back to our posts on e, especially the opening post, you will realize that this is exactly the opposite issue we faced there. The definition of e was able to give us results to as great an accuracy as we desire. While we had to do quite a bit of heavy mathematics before we obtained a usable infinite series, once we had obtained the desired infinite series, we could use it to obtain the value of e to any arbitrary level of accuracy.

    Not so with π since its definition in terms of measured lengths renders it limited precisely because no measuring instrument can be indefinitely accurate.

    Why the Symbol

    Before we proceed, however, it is interesting to make a brief detour concerning the history of how the Greek letter π came to be used to denote this ratio. The earliest known use of the π in a similar context was to designate the semiperimeter of the circle. With the Greek letters δ and ρ representing the diameter and radius of the circle, the many mathematicians used the ratios

    to denote what we currently would denote as π and 2π respectively.

    In his 1727 paper An Essay Explaining the Properties of Air, Euler used π to denote the ratio of the circumference to the radius. Just 9 years later, in 1736 in his book Mechanica, Euler used π to denote the ratio of the circumference to the diameter. From then on he consistently used the latter designation and, because he corresponded prodigiously with other mathematicians, his notation eventually was adopted though, even till 1761 there was quite a bit of fluidity.

    Despite the confusing history of the symbol, something utterly lacking in the case of e, π has been the more popular number and more efforts have been made to calculate its digits than the digits of e. Obviously, this means that mathematicians have some other result, necessarily stemming from the definition of π, that allow the generation of different infinite series that can be used to calculate the value of π. The current record stands at 105 trillion digits, which required 75 days of dedicated computer time by a computer company. But if the definition ofπ is limited, how in the world do mathematicians calculate its digits?

    The Polygon Method

    The original impetus came from the study of polygons, specifically regular polygons. In the figure below we see the same circle repeatedly inscribed and circumscribed by regular polygons. On the left we have pentagons. In the middle are hexagons. And on the right are octagons.

    Here it is possible to define the circle as having a radius of 1 unit. Then the distance of the vertices of the inscribed polygon to the center of the circle will also be 1 unit. And the perpendicular distance of the center of the circle from the sides of the circumscribed polygon will also be 1 unit. Using this, the perimeter of both polygons can be determined. Also we can easily see that the circumference of the circle has a value between the perimeters of the two polygons. This allows us to place lower and upper bounds on the value of π. With polygons having more sides our accuracy becomes better and we can get tighter bounds.

    Using this method with 96-sided regular polygons, Archimedes, in the 3rd century BCE, obtained that

    This gives us

    which most students in middle school will realize are accurate only to 3 significant figures! 96 sides and 3 significant figures! I don’t know about you, but I think this is a really poor payoff. I applaud Archimedes for sticking with his 96-sided polygons.

    Not to be outdone by the redoubtable Archimedes, Liu Hui from the Wie Kingdom used a 3,072-sided polygon and determined that the value of π was 3.1416. That’s a factor of 32 more sides yielding just 2 more digits!

    Not having any other methods at the time, around 480 CE and using Liu Hui’s algorithm with a 12,288-sided polygon, Zu Chongzhi showed that π could be approximated by 355÷113, which gives 3.1415929…, accurate to 6 digits. In 499 CE, Aryabhatta used the value 3.1416, though, unfortunately, he does not tell us the method he used or if he was using someone else’s value.

    Mathematicians continues using this polygon method for the next few centuries. In 1424 CE Jamshīd al-Kāshī determined 9 sexagesimal digits of π, the equivalent of about 16 decimal digits, using a polygon with 3×228 sides! Finally, Christoph Grienberger obtained 38 digits in 1630 CE using a polygon with 1040 sides!

    I do not wish to detract from the achievements of any of these great mathematicians. The patience and perseverance they displayed is exemplary. Morover, they achieved what they did in an age before calculators and computers. They only had their hands and minds to work with. Despite their achievements – or rather precisely because of them – it is evident that the polygon method is wonderfully accurate, but also woefully inefficient.

    The Path Forward

    Apart from the slowness with which the polygon method converges to the value of π, it is evident that, when you have a finite number of terms, here represented by the finite number of sides of the polygon, regardless of how large the number of sides may be, the final result will only be achieved as a value between two bounds specified by the inscribed and circumscribed polygons. Due to this, mathematicians have devised what can only be described honestly as ‘workarounds’, methods that yield the value of π but not because of some direct application of the definition.

    These methods fall into two large branches. First, we have the methods that rely on some kind of iterative formula. Second, we have methods that yield an infinite series. We must ask ourselves how an iterative formula or infinite series can be generated for a number that is defined in terms of the ratio of two lengths. In the next two posts we will see just how this is done.

  • Rationally Irrational

    As mentioned earlier, I am taking a break from publishing new material for a few weeks. During these weeks I am republishing the series on e and the one on π. The post below was originally published on 14 June 2024.

    Recapitulation

    Visualizing the irrationality of e (Source: Mathematica Stack Exchange)

    We have reached our final post in this series on the number e. In the first post of the series, we introduced e and looked at the reasons for which it is the base of the natural logarithm and the exponential function. In the second post of the series, we used various techniques to determine that e lies between 2 and 3, a fact that will be important in today’s post. In the previous post, we considered three examples of infinite series for e to show that more advanced mathematics does not guarantee quicker convergence to the value of e. In today’s post, we will demonstrate that e is an irrational number.

    Reductio ad Absurdum using Bounds

    Since e lies between 2 and 3, e cannot be an integer. We will now use reductio ad absurdum, a method we introduced in another post. So we will begin by assuming that e is a rational number. Hence, suppose

    Since e is not an integer, it follows that q cannot be 1. Hence, q>1. Now, we also know that 

    Combining the two we get

    If we multiply this equation by q! we will get

    Distributing the q! into the parentheses on the right side we get

    Now the left side, being the product of natural numbers, is a natural number. On the right side, the terms in green are all integers since the numerator q! is necessarily a multiple of the denominators. This means that, for the equation to hold, the terms on the right must add up to an integer. Let us designate this sum as R. Then

    Now, since q > 1, it follows that

    Taking the reciprocals of each term we get

    This means that

    Hence, we can conclude that

    However, we have seen, when we obtained the lower and upper bounds for e, that the infinite series

    Hence, without the leading 1, the sum must be 1. This allows us to conclude that R < 1. However, since all terms in R involve the products and quotients of positive integers, it must follow that R is positive. However, there is no integer between 0 and 1, which means that R cannot be an integer. This means that the terms in red in the equation

    do not give an integral sum, which is something that was required for the equation to hold. Since we reached this requirement when we assumed that e is rational, we have reached something absurd, namely that this is possible only if we can find an integer between 0 and 1. This concludes the proof by reductio ad absurdum.

    Reductio ad Absurdum using Partial Fractions

    I would like to contribute another proof using reductio ad absurdum that I have not seen anywhere else. This uses the concepts surrounding partial fractions. While partial fractions is normally used in the context of algebra, I’d like to explore its implications in the context of arithmetic.

    Now, it is clear that

    What sets apart the expression in green from the expressions in red is that the one in green only has prime numbers or powers of prime numbers in the denominator. This is not true in the case of the expressions in red, since 6 and 12 do not satisfy the criterion.

    So suppose we restrict the splitting of a given fraction into its arithmetic partial fractions where the denominators consist only of prime numbers or the powers of prime numbers. Suppose then that we have a number N such that

    where

    are distinct prime numbers and

    Now any divisor of N can have a particular prime pk appear from 0 to ak times. For example, the divisors of 12 are 1, 2, 3, 4, 6, and 12. The prime factorization of 12 is 

    Hence, the prime factorization of any divisor of 12 can have 20, as in 1 and 3, or 21, as in 2 and 6, or 22, as in 4 and 12. Or it could have 30 as in 1, 2, and 4, or 31, as in 3, 6, and 12. In other words, any prime pk, which appears as a power ak in the prime factorization of N, can appear as a power from 0 to ak in divisors of N. Hence, there are ak ways in which pk can appear in divisors of N, excluding 1. Hence, the number of divisors of N that are prime numbers or powers of prime numbers is

    This means that, if we are able to write 

    then splitting it into its arithmetic partial fractions would involve at most P terms. However, P is a finite natural number.

    Yet, from the expression

    it is clear that e is expressed as the sum of an infinite series. But in the denominators we have all the natural numbers without exception. And we know that there are infinitely many primes in the set of natural numbers. This means that the infinite series for e includes terms that involve infinitely many prime numbers. For example, the term that contains pk! in the denominator, when split into its arithmetic partial fractions, will contain a finite number of terms that involve all prime numbers and powers of prime numbers that are less than pk.

    However, since there is no limit to pk, there is no way to combine all the terms into a finite series, such as is required by the arithmetic partial fraction expansion of

    Now, we know that 

    The inherent pattern involved in the denominators allows us a concise way of combining the infinite terms to give the resulting sum as 2. In general, if we have an infinite set of fractions where the denominators form a discernible pattern, we might be able to combine the terms to give us a determined sum. If the primes themselves appear after some discernible pattern, then too we would possibly be able to combine the infinite terms to yield a determined sum. Since the primes do not appear in any discernible pattern, such a combination is impossible, even in theory.

    In other words, we have reached a contradiction, where infinitely many fractions with distinct denominators involving infinitely many unpatterned primes and their powers are combined to produce the sum of a finite number of fractions, therefore yielding a rational number. So once again, by reductio ad absurdum the result is proved and we conclude that e is irrational.

    Wrapping Up

    We have devoted four posts to the study of the number e. The impetus for this study came from the opening post of this blog in which I introduced Euler’s Identity, stating that it was an example of beauty in mathematics. During the course of these four posts, we have looked at the definition of e. We also saw how e is related to the ideas of compound interest and, therefore, to the ideas of growth and decay that occur in natural systems. We were able, then, to see why e is the ‘natural’ base for logarithms and exponential functions. 

    Then we obtained a lower and an upper bound for the value of e. Along the way we introduced some key ideas, notable among which were the limiting process, infinite geometric sequences, and the binomial expansion. This allowed us to obtain an infinite series for e. 

    Following this we explored three infinite series for e to determine the speed at which they converge to the value of e. We saw that more advanced mathematics does not guarantee speedier results. This allowed us to conclude that we need to be wary when claims are made that something is based on more rigorous mathematics. 

    Finally, we proved that e is irrational. We did this in two ways, both involving reductio ad absurdum, a mathematical strategy for proofs that we had introduced earlier. I introduced a proof that I have not seen elsewhere, though this may just be an indication of my ignorance rather than my ingenuity.

    This does not exhaust the study of e. By no means! But this does conclude our exploration at this stage. It has been fruitful and insightful for me. I hope you can say the same.

  • Infinitely Expressed

    As mentioned earlier, I am taking a break from publishing new material for a few weeks. During these weeks I am republishing the series on e and the one on π. The post below was originally published on 7 June 2024.

    Recapitulation

    I’m back with another post after taking a break for a week. The last week of May was particularly busy as I was teaching a class called Introduction to the New Testament. During the week I also gave a lecture on Causes and Symptoms of Religious Discord, which you can find here if you’re interested. Anyway, back to Acutely Obtuse, we are in the middle of a four part series on the number e. In the last but one post, I started this series. We then saw why e is the base of the natural logarithm and the base of the exponential function. We also saw the relation between e and compound interest. In the previous post, we determined that e lies between 2 and 3. In the next post we will show that e is irrational. Given that e is irrational, it follows that it cannot be expressed as a ratio of two integers. This also means that it cannot be expressed as the sum of a finite number of rational numbers because the sum of rational numbers is necessarily rational.

    Introduction to Infinite Series

    Of course, this leaves open the possibility that e could be represented as the sum of an infinite series, that is a series that does not have a finite number of terms. In the previous post we looked at the limiting process and concluded that

    Using sigma notation, we can write

    This means that e can indeed be expressed as the sum of an infinite series. However, the above series is not the only one that has been shown to converge to the value of e. In this post, I wish to consider the above series and two others that have been derived for determining the value of e. However, while we just about managed to derive the first series without the use of any calculus, most of the series that have been derived require the use of calculus. Since I do not wish to introduce any advanced calculus at this stage in the blog, I will be considering one series that is derived from the first one itself and accepting, but not deriving, a second that has been derived using some advanced calculus.

    But first we must ask ourselves why additional series are needed. If we already have a workable series, why should we bother to obtain more series? Mathematicians, after all, tend to be quite frugal, rarely doing more than is required. So why would they bother with more series representations for e when they already have one that one can use to obtain the value of e to any level of accuracy that might be needed?

    Rationale for Other Infinite Series

    To answer this question, we need to look at the values obtained by using the original series. Here are the first twenty values we obtain from the original series.

    The red digits indicate where the current approximation for e begins to differ from the previous approximation. As can be seen, this series gives on average one additional digit of e for each additional term. Of course, for most purposes 10 or 12 digits of e is more than sufficient. In the table above, we have determined the value of e accurately to 18 digits. Why then would we need to determine more digits?

    Computations of the digits of irrational numbers like π and e are used to measure the computational power of supercomputers. As we include more terms of an infinite series, two things must be done. First, the existing approximation of e must be kept in memory while the latest term is calculated. Second, the existing approximation and the latest term need to be added to obtain the new approximation. However, as we go down the terms in the series, each term becomes decreasingly small, requiring greater storage of memory. Since pushing things to and pulling things from memory are time intensive processes, at least from the perspective of a supercomputer, each new approximation tests the limits of the computational system to a greater extent.

    However, once we have obtained the first (say) 18 digits of e, as we have above, it is pointless to use the same process to obtain the same results. Mathematicians hate repeating things because they know that they aren’t going to get new results. Hence, using the same series to obtain 1 billion digits from a set of computers to see which one is the fastest would be fine once. After that no new information is being generated.

    However, mathematicians think, “If we are going to use infinite series to test the power of computational systems, why not generate series that give more digits per term?” In other words, if we can generate a new series that gives 2 additional digits per term, then with the same amount of time and same number of terms, we can generate 2 billion digits instead of 1 billion. And if someone can produce a series that gives 10 digits per term, then for the same price we can generate 10 billion digits. For people involved in the computational side of things, it does not matter which series is used. Any series can be used to arbitrate between competing computational systems. However, for mathematicians, the goal is to obtain new information. Hence, any series that promises more digits per term is to be valued for the additional information it can provide.

    So mathematicians resort to all sorts of manipulations to produce new series that could provide more digits per term. The two that I have selected do precisely that.

    Combining Terms

    The approach for the second series recognizes that we can pair up terms and not affect the sum. Now, in general, consecutive terms can be written as

    This term simplifies to 

    However, since we have grouped the terms, n cannot now take all the values earlier specified or we will overcount. We can overcome this by replacing n with 2k to get

    Hence, the original sum can be expressed as

    Substituting values for k we get

    We can see that each term is quite simple and that there is an easily recognizable pattern, which makes this easy to program. If we use this infinite series, we will get the following table:

    Of course, as we should have expected, since we combined two terms of the original series to give a single term of the new series, the new series approaches the value of e twice as quickly as the original series. This means that we get, on average, 2 additional digits of e for each term of the new series. While this is laudable, as mentioned earlier, once this new series has been used, it will fail to produce any new information after a single use. This means that mathematicians will look for newer series to put into play. We could, as the approach to the second series suggests, combine more terms. For example, if we combine three consecutive terms we get

    Replacing n+2 with 3k we get

    This series obviously will converge to the value of e three times as fast as the original series. However, we can see that this process might become quite unwieldy. Finding the LCM of multiple terms is not a difficult matter. However, expressing them in a compact form that is conducive to programming is not necessarily a given. Already, while combining only 3 terms, we actually have quite a bit of deft algebraic manipulations to undertake. And remember, once a series is used, it pretty much becomes obsolete! Hence, we must discover new ways with which to express e.

    Using Advanced Calculus

    The third series I wish to consider is derived using the lower and upper incomplete gamma functions and the Taylor series. While the mathematics involved is certainly above the level of the blog at this stage, the end result is

    If we substitute the values of k, we will get

    Once again, each term is quite simple and we can easily recognize the pattern. So this too would be a good series to use for programming. But what kind of approximations of e does this series yield? The table below is instructive.

    What we can see is that the third series converges slightly quicker than the original series but considerably slower than the second series we considered. 

    Rejecting the Snake Oil

    Over the years, mathematicians have derived many infinite series for e using all sorts of techniques. They have also used continued fractions, infinite products, and recursive functions. All these techniques are needed precisely because e is an irrational number, which we will discuss in the next post. However, as we have seen, there is little real world advantage to be gained from deriving more expressions for e. The requirement for new series comes from the realm of computation, where the computing power of a computational engine can be measured by having it perform processor intensive calculations such as are needed by these expressions for e. Mathematicians use this requirement to get the computational engines to churn out more digits of famous irrational numbers like e, π, and φ.

    A definition of e in terms of the rectangular hyperbola xy = 1 (Source: Wikipedia)

    However, what we have seen in this post is something that we are rarely told about. In fact, I think what we have discovered is intentionally kept from us because it would reveal something we dare not admit. Now, hopefully, the mathematics involved in obtaining the original series, which was discussed in the previous post, was not too onerous. Granted that it was heavier than most other mathematical concepts I have dealt with so far in the blog, I believe it was not too difficult for most readers. The second series we considered was derived by combining the terms of the original series as pairs. Hence, this too did not require much advanced mathematics. However, the third series did require quite a bit of advanced mathematics and I avoided explaining it in this post. Despite this, the resultant series does not converge as quickly as the second series, which was obtained using much simpler mathematics.

    What this tells us is that the level of mathematics involved in deriving an infinite series for e, or for that matter any irrational number, is no indicator of how quickly the series will converge to the desired value. This runs contrary to the intuition many people have about mathematics, namely that we need increasingly more complicated mathematics for more complicated problems. This is not the case and there are many instances when relatively simple mathematics can be put to use to solve extremely complicated problems. In my opinion, this is precisely what undergirds mathematical theorems like Gödel’s Incompleteness Theorems and some of the Millennium Prize Problems such as – P vs NP and the Riemann Hypothesis. It is also what lies behind the deceptively simple, but heretofore unsolved, Collatz Conjecture. 

    In these days of increased dependence on Machine Learning, it pays to step back and understand that mathematics itself does not give us any guarantees or advice about what methods would work best for a given problem. Until we develop machines that are actually able to replicate human thought, any idea that more advanced computing capabilities would yield lasting solutions is, in my view, a pipedream. Unfortunately, too many of us are mathematically ill equipped to recognize when we are being sold snake oil in mathematical garb!