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!
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.
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.
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!
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.
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
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.
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
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.
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.
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.
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.
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.
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
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.
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!
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 24 May 2024.
Recap
In the previous post, I started a series of three posts focused on the number denoted by e. We then saw why it 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 this post we will try to determine the lower and upper bounds for e.
In order to do this, we need to do seven things. First, we will then ‘discretize’ the function
for integers n. Second, we will need to introduce ourselves to the limiting process. Here, we will only restrict ourselves to the cases where x becomes infinitely large. Third, we will introduce ourselves to the binomial expansion and obtain the lower bound for e. Fourth, we will show that the function
is an increasing function. This means that the value of f(n) increases as the value of n increases. Fifth, we will combine the limiting process and the binomial expansion to obtain a very common infinite series for f(x). Sixth, we will introduce ourselves to the idea of an infinite geometric series. Seventh, we will use what we know from the infinite geometric series and the infinite series for f(x) to obtain the upper bound for e.
Discretization
In order to proceed with what I have called ‘discretization’, consider the function
It is possible to prove that this function is defined for all positive values of x. We may not be able to calculate the value by hand. And we may not have a clue what
might even mean, let alone how to calculate it. Nevertheless, if f(x) is defined for all positive values of x it must be defined for all positive integer values of x. In this f(x) is transformed to f(n), where
This is something that we can comprehend because exponentiation to a positive integer, in this case n, only signifies repeated multiplication. So now, we have to only deal with f(n).
But now we have to show that f(n) is an increasing function. In more formal mathematical terminology, we have to show that f(n) is monotonically increasing. It is easy to see from the tables in the previous post that this is true. Below is one of the tables from that post.
Since the values of x chosen were all integers, the same table would apply for n, f(n), and Δf(n). We can see that, as n increases, f(n) also increases. But this is not how we prove things in mathematics! So is there another way to prove that f(n) is increasing? Yes there is!
The Limiting Process
But before we get to that, let us introduce some aspects of the limiting process. Consider the function
We can easily see that, as n gets larger and larger, the value of g(n) gets closer and closer to 0. This is seen in the table below.
What we can say is that, as n gets infinitely large, g(n) gets infinitesimally closer to 0. Or to be rigorous, we say that the limit of g(n) as n tends to infinity is 0. Please note what this language is claiming and what it isn’t. First, it is not claiming that infinity is a number. God forbid! I have dedicated a whole post to ridding ourselves of that mathematical heresy. Second, it is not claiming that the value of g(n) ever becomes zero. It is impossible for the reciprocal of any number to equal zero. If this were not true, we could argue as follows.
But, as we know, division by zero is meaningless or ‘absurd’. Since this assumption leads to an absurdity, by the reasoning of reductio ad absurdum, we can conclude that the original assumption, namely that the reciprocal of some number can be equal to zero, is incorrect.
The way we denote the limiting process is by writing
The left side of the equation tells us what the variable of the limit is, in this case n, and how it is being made to vary, in this case getting infinitely large. It also tells us what function of the variable we are dealing with, in this case 1/n. The right side of the equation tells us the number that the value of this function approaches, in this case 0, as the variable (n) varies as specified.
Due to the limiting process, we can draw the following conclusions.
The table below can confirm our conclusions.
So what we have managed to prove, albeit not with great rigor, is that the ratio of an integer to its predecessor or to its successor approaches 1 as the integer gets larger and larger.
The Binomial Expansion and the Lower Bound for e
Now it is time for us to introduce another important result that we will be using. This is known as the binomial expansion. As seen in an earlier post, the number of ways of selecting r items out of n items is
Now consider the expression
This is called a binomial expression since there are 2 terms in the expression. Now consider the expression
Quite obviously
Here, on the right side of the equation, there are n sets of parentheses, reflecting the power n on the left side of the equation. Now we have to ask ourselves how we expand the right side. When we expand, we have to select one of the terms, either a or b, from each of the binomial terms. We could select a from all the binomial terms, leading to an. Or we could select b from all the binomial terms, leading to bn.
In general, if we select b from r of the binomial terms, this would mean we have selected a from the remaining n-r binomial terms, leading to an-rbr. In how many ways can we form the an-rbr term? This will be the same number of ways as selecting r out of n items, since, when we select r of the binomial terms to give us b, we will be auto-selecting the remaining n-r binomial terms to give us a. Hence, the binomial expansion gives us
Hence, we can conclude that
With special note are the first two terms. The first term is
Similarly, the second term is
Hence, the expansion can be expressed as
Now, all the terms that are in red are the product and quotients of natural numbers. Hence, each term is necessarily positive. This allows us to conclude that
Hence, we have obtained the lower bound for e. All we need now is to obtain the upper bound. This is somewhat more difficult. We first need to demonstrate that f(n) is an increasing function.
f(n) is an Increasing Function
Let us consider the two consecutive terms f(n) and f(n+1). We have
Taking LCM inside the parentheses, we get
Dividing the second equation by the first we get
This can be further modified to give
Choosing a new index m = n+1, the above gets transformed to
This can further be written as
Now consider consecutive terms in the expansion of the term in red above.
Dividing the second equation by the first we get
It is clear that the two terms in red will cancel. At the same time, the green terms will leave r+1 in the denominator, while the blue terms will leave m-r-1 in the numerator. Hence, the above simplifies to
Redistributing the terms and taking absolute value so we do not have to deal with a negative quantity, this is equivalent to
Since r takes values from 0 to m-1 and since m must be necessarily greater than or equal to 2 (remember m=n+1), each of the three terms above is strictly less than 1. Hence, in the expansion
each term has a smaller magnitude than the preceding term. If we write out the expansion we get
Now we have shown that the 3rd term (in red) has a greater magnitude than the 4th term (in green). Hence, the sum of the 3rd and 4th terms must be positive. Similarly for each subsequence pair of terms in the expansion. If m-1 is even, there will be an odd number of terms in the expansion, with the final term being positive. If m-1 is odd, there will be an even number of terms with the final pair of terms also yielding a positive sum. Hence, we can conclude that
However, recall that
This means that
This means that f(m) is increasing, which also means that f(n) is increasing.
Whew! That took some doing, huh?
Combining the Limit Process and the Binomial Expansion
What we can now say is that f(n) will keep getting larger as n gets larger. Recall that we had shown
This means that
if both limits exist. Now since f(n) keeps increasing, all we need to show is that there is some upper bound beyond which the expansion cannot go. That would also place an upper bound on the value of f(n).
Introducing an Infinite Geometric Series
Consider the infinite series
Here each term is multiplied by ½ to get the next term. If we multiply the whole equation by 2 we get
However, note that the terms in red are the same series with which we started. This gives us
Obtaining the Upper Bound for e
Visualization of the convergence of f(n) (Source: Algebrica)
Now once again consider the expansion for f(n), which is
Now the (r+1)th term is given by
Note that this happens to be the rth red term above and it can be modified as follows
Rearranging the terms we get
Some more rearrangement gives
Here, r varies between 0 and n. Hence, all the terms in red are necessarily positive and less than 1. However, in the limiting case, as n approaches infinity, the limiting value of each of the red terms is 1. This gives us
Writing the infinite series this will give us
For the fourth term onward, r is greater than or equal to 3. However, it is easy to see that for r> 2
As examples
Hence, we can conclude that
However, we have already shown that the terms in red add up to 2.
Hence, using the earlier lower bound result, we conclude
Conclusion
We have shown that the value of e lies between 2 and 3. Along the way we used some mathematics that we had explored earlier, like reductio ad absurdum and the method of determining the number of ways of selecting r out of n items. But we also introduced new mathematics, like the limiting process, the binomial expansion, and the infinite geometric series. The crucial step was to show that f(n) is increasing. If this were not true then showing that it has a lower and upper bound would not indicate that there is a specific value to which f(n) approaches, since it could then just oscillate between slightly above 2 and slightly below 3. The process to demonstrate this was considerably involved and also included the idea of showing that successive pairs of a sequence added to give a positive sum. This was not necessarily the most intuitive step in the process, even though, without it, we would not have been able to prove the result.
In the previous post, we introduced e and touched on what its significance is and why it is the base of the ‘natural’ logarithmic and exponential functions. In this post we have placed bounds on the value of e. Since this post end up being quite long and, I must admit, heavy, I am going to do a part of what I planned for this post in the next, where we will look at some common infinite series that have been derived for e and consider how rapidly each of these series converges to the actual value of e. In the post after that, I will deal with how we know that e is irrational. I will, however, be taking a break next week. Hence, the next post on infinite series for e will be published on Friday, 7 June 2024.
While I am enjoying the series on counting principles, I need to take a break. Hence, I will be republishing the series on e and the one on π, both which I had first published in 2024. The post below was originally published on 17 May 2024.
In the opening post of this blog, I had introduced Euler’s Identity, which states
The identity combines five numbers – 0, 1, e, i, and π – and three mathematical operators – addition, multiplication, and exponentiations – and the equality. In other words, this identity captures many diverse parts of mathematics and links them, thereby demonstrating that what we call ‘mathematics’ is a unified field in which one area neatly dovetails into the next. For a few more links I suggest you read the earlier post.
In this post, however, I wish to focus on the number e. I will be devoting three posts to it, including this one. If this now seems excessive, I hope that, after you have read the three posts, you will have had a change of heart and mind. Indeed, my hope is that you would wish for a fourth. And a fifth! I could, of course, include it all in one post. However, I have realized that the last few posts have been considerably longer than I had planned for this blog. Granted that each post did deal with a unified theme, the fact still remains that they were quite long. Hence, in the interest of not squelching all the curiosity of the reader, I feel it is best, where possible, to publish shorter posts.
In this post I wish to deal with the definition of e and its relation to a concept of mathematics that most students learn in the 9th or 10th grades. I also wish to address the significance of e that arises from the definition.
The second post on e will deal with some common bounds we can place on its value. The first post will have given us some indication of these bounds. However, in the second post I will take a more formal approach to this. This will involve looking at a few infinite series that mathematicians have derived as ways of calculating the value of e. The third post of e will deal with the issue of e being an irrational number. Along the way, in both future posts, we will learn a few more mathematical tricks to keep in our quiver should we ever need them.
When I was introduced to e, my professor at the Guru Nanak Khalsa College in Bombay (now Mumbai) just told us that it was the base of the natural logarithm (logex) and the base of the exponential function (ex). I asked him a few questions like:
Why was it this number and not some other number that was the base of both the logarithm and exponential functions?
What was the significance of the number e?
Unfortunately, all my professor could tell me was that the approximate value of e was 2.718. When I pressed him for more information, he summarily asked me to leave his class. Perhaps my mother will now understand why I hated attending classes there. I mean, if even the mathematics class was going to be transformed into one mind-numbing exercise of rote learning, the other subjects didn’t have a prayer!
I have dealt with one mathematical issue that causes me trauma elsewhere. The trauma that this professor caused me remains to this day and surfaces when I hear students confidently tell me that the value of e is 2.718281828. (Yes, they can use their calculators now to get more digits than my professor had memorized!) When I hear something like that I have a strong urge to tug at my hair, which, fortunately, is somewhat difficult for me!
Anyway, let me proceed with the definition of e and then hopefully address the two questions above.
Consider the function
Students who have learned about compound interest will recognize the similarity the above expression has to the formula for compound interest given by
where P is the principal invested, R is the interest rate as a percentage per compounding cycle, N is the number of compounding cycles, and A is the amount upon maturation of the investment. If we divided both sides of the equation by P and express the interest rate as a number rather than a percentage, the formula gets transformed to
where G is the ‘growth’, that is the ratio of the maturation amount to the principal invested, r is the interest rate per compounding cycle, and n is the number of compounding cycles.
Before proceeding, let’s consider an example so we understand how the formula works. Suppose we invest ₹1,000 at 10% interest per annum compounded annually for 3 years. Then, P = 1000, r = 0.1 (corresponding to R = 10%), and n = 3. Hence,
This gives A = ₹1331 or G = 1.331.
With the same numbers, but assuming that interest is compounded every 6 months, the value of R and r will be halved and the value of N and n will get doubled. This is because 10% per annum is the same as 5% semiannually. And in 3 years, there are actually 6 periods of 6 months each. Hence, R = 5%, r = 0.05, N = n = 6. This gives
Hence, A = ₹1340.10 and G = 1.340096. [Note: I have rounded A to 2 decimal places as is the convention for currency.]
Suppose now, that the interest rate is 100%. Then R = 100% and r = 1. Now, if we invest some amount for, say, 3 years, we will get:
But suppose, we invest only for 1 year. Then we will have
Suppose, now we keep reducing the duration of the compounding cycles. If we have 2 compounding cycles in a year, each lasting 6 months, we will have
If we change this to compounding every 4 months, we will have 3 compounding cycles, giving us
We can, of course, continue increasing the number of compounding cycles.
For the sake of the discussion, I will rename G as f(x) and n as x, yielding the following table:
The third column gives the change in the value of f(x) from the previous row. What we can observe is that the values of f(x) keep increasing from one row to the next. Also, the value of Δf(x) keeps decreasing from one row to the next. In fact, if we plotted the graph of the function, shown below, this is what we would expect.
Graph of y = f(x)
Since the graph becomes almost horizontal, it seems that the rate at which the function increases its value keeps decreasing. This is indeed the case as can be seen from the table below.
What we can see here is that x is increasing by orders of magnitude, while the corresponding values of Δf(x) keep getting smaller and smaller, while remaining positive.
Now there are 31,536,000 seconds in a year. If we put this as the value of x we will get f(x) = 2.71828177847, which represents an increase of 0.00001354128 from the value when x = 100,000.
At this stage, let us take a short detour. Suppose we have a sample of bacteria in a petri dish with enough nutrients for the bacteria to grow and undergo mitosis unhindered. Assuming no mutations occur, there will be no way of distinguishing any particular bacterium from another. All the bacteria in the sample are, in other words, identical. All are consuming nutrients and all will reach the next stage of mitosis simultaneously. Hence, 100% of the sample has the potential to undergo mitosis. But how frequently does mitosis occur?
Some bacteria need about 24 hours of feeding on the nutrients before they undergo mitosis. So here we have a doubling every day. But suppose we once again restricted ourselves to 1 day but somehow sped up the process of mitosis. What would happen? The tables above tell us exactly what would happen. If we have 100,000 cycles of mitosis in our day with only 1/100,000 of the sample undergoing mitosis each time, we will end up having 2.71826823719… times the number of bacteria with which we started.
We can see that, as the number of cycles increases indefinitely, with the fraction of bacteria undergoing mitosis each time correspondingly decreasing, the growth will be given by the limiting value of the function f(x) as x gets infinitely large.
Coming back to the issue of compound interest, every unit of currency we invest is identical to every other. Since we proposed a 100% interest rate, every currency unit is subject to growth at all times. However, if we reduce the compounding period indefinitely and correspondingly decrease the fraction of the currency units that actually multiply, at the end of the year we will have a growth equal to the same limiting value of f(x).
Now currency is an artificial human construct. However, bacteria belong to the natural world. Many other things grow in the natural world. Similarly, there are things that decay, like radioactive nuclei. All these natural phenomena are, like our sample of bacteria or the invested money, continuously growing. Continuous growth, subject to sufficiently large environments and resources to expand into, and continuous decay, subject to sufficiently large numbers of species to undergo decay, are ubiquitous natural phenomena.
The limiting value I have referred to is the number denoted by e. And we can see that we have answered both the questions I had posed. The significance of e is that it represents the limiting value of growth (i.e. a multiplicand) or decay (i.e. a divisor) when the growth or decay is continuous. And it is the base of the natural logarithm, which shows up when we know the final population and need to solve for time, and the base of the exponential function, which shows up when we need to solve for the population after a period of growth, because it represents the behavior of all natural systems.
Now, was that too hard for my professor to tell me? I do not think so. But, unfortunately, I have to face the dismal possibility that he had no clue about any of this, having resigned himself to learning by rote rather than learning by inquisitiveness.
We started a series on counting principles earlier this year. We first considered the most basic principles, namely the multiplication and addition principles. Then we looked at how permutations differ from combinations, considering some basic patterns of both including the elements of Pascal’s triangle. Next, we turned our attention to permutations of special kinds, including circular permutations and permutations of non-distinct objects. Then last week we considered combinatorial arguments and binomial identities. We are now poised to consider some ideas related to factors of numbers. I had thought I would be able to include the technique of partitions also in this post. However, I will tackle that in the next post.
In an earlier post we had looked at the ideas related to factors of numbers. But that was many months ago. So let us start here as though we are addressing these issues for the first time. We begin with the observation that every natural number, except 1, is either a prime number or a composite number. As a reminder, a prime number is one whose factors are only 1 and itself. A number that has a factor other than 1 and itself is said to be a composite number. While it would seem that 1 satisfies the condition for being a prime number, 1 is not considered to be prime. Why is this the case?
The fundamental theorem of arithmetic states that every natural number greater than 1 is either a prime number or can be expressed as a unique product of prime numbers, disregarding the order of the primes. We must admit that this theorem, like many in mathematics, is a kind of after-thought. It was introduced specifically to exclude 1 from the set of primes. And this is because including 1 in the set of primes creates more problems than it solves. This is because 1 is the multiplicative identity element. That is, the product of any number and 1 is the number itself. This means that, if we allow 1 to be defined as a prime number, we could write
Hence, any idea of a unique prime factorization would go into the gutter! However, nothing is gained by defining 1 to be a prime number. Hence, we exclude 1 from the set of primes. What this means is that every natural number greater than 1 can be written with a unique prime factorization, disregarding the order of the primes. For example,
Since multiplication is commutative, the order in which we multiply the prime numbers does not matter.
Number of Factors of N
Let us consider, for example, the number 450. We can determine the factors by using a method like that indicated in the diagram at the start of this post. However, for large numbers this may be an onerous task. However, we can resort to prime factorization and write 450 as
We can see that there are 5 prime factors with two of them being repeated twice. Hence, from what we have learned earlier, there are
ways of permuting these prime factors. However, all of them give the product of 450. Hence, if we disregard the order in which we multiply the prime factors, the prime factorization of 450 is unique and can be written as
Let us consider the factors of 450. They are 1, 2, 3, 5, 6, 9, 10, 15, 18, 25, 30, 45, 50, 75, 90, 150, 225, and 450. Hence, 450 has 18 distinct factors. Some of them are odd, like 1, 3, 5, 9, 15, 25, 45, 75, and 225. The others are even, like 2, 6, 10, 18, 30, 50, 90, 150, and 450. We can see that there are 9 factors that are odd and 9 that are even. That is curious because 9 + 9 = 18. Perhaps there is something here.
Let us consider the other prime factors. There are factors that are not divisible by 3, such as 1, 2, 5, 10, 25, and 50. There are factors that are divisible by 3 but not divisible by 9, such as 3, 6, 15, 30, 75, and 150. And there are factors that are divisible by 9, such as 9, 18, 45, 90, 225, and 450. We can see that there are 6 of each such factors and 6 + 6 + 6 = 18. In a similar way, the factors not divisible by 5 are 1, 2, 3, 6, 9, and 18. The factors divisible by 5 but not by 25 are 5, 10, 15, 30, 45, and 90. And the factors divisible by 25 are 25, 50, 75, 150, 225, and 450. Once again, there are 6 of each and 6 + 6 + 6 = 18. Surely there is some significance to this. Perhaps we can get a pattern by considering a number with fewer distinct factors.
Let us consider the number 18. It has 6 distinct factors, namely 1, 2, 3, 6, 9, and 18. Of these, 3 are odd, namely 1, 3, and 9, and 3 are even, namely 2, 6 and 18. Also 2 are not divisible by 3, namely 1 and 2, 2 are divisible by 3, but not by 9, namely 3 and 6, and 2 are divisible by 9, namely 9 and 18. We will now invoke the fact that 1 is the multiplicative identity element and that, for any natural number n, n0 = 1. Since the prime factorization of 18 is 2132, any factor of 6 can have as its factors 20, giving an odd number, or 21, giving an even number. In a similar way, any factor of 18 can have as its factor 30, giving a number not divisible by 3, or 31, giving a number divisible by 3, but not by 9, or 32, giving a number divisible by 9. In other words, there. So, since we had 21 in the prime factorization of 18, there are 1 + 1 = 2 ways of including 2 in the factor, either exclude it, giving an odd number, or include it, giving an even number. And since we had 32 in the prime factorization of 19, there are 2 + 1 = 3 ways of including 3 in the factor, exclude it completely, giving a number not divisible by 3, include only one 3, giving a number divisible by 3 but not by 9, or include both 3s, giving a number divisible by 9.
Let us see if we can generalize this result. Suppose we have the number N. Suppose its prime factorizations is
Then, the number of distinct factors of N will be
Let us put this to the test. For 18 = 2132, p1 = 2, p2 = 3, a1 = 1, and a2 = 2. According to the result, the number of factors should be (1 + 1)(2 + 1) = 6, which is correct. For 450 = 213252, p1 = 2, p2 = 3, p3 = 5, a1 = 1, a2 = 2, and a3 = 2. According to the result, the number of factors should be (1 + 1)(2 + 1)(2 + 1) = 18, which is correct.
Sum of Factors of N
Now, let us try to find the sum of the factors of a natural number. Consider the number 18. The sum of its factors will be 1 + 2 + 3 + 6 + 9 + 18 = 39. For the number 450, the sum of the factors is 1 + 2 + 3 + 5 + 6 + 9 + 10 + 15 + 18 + 25 + 30 + 45 + 50 + 75 + 90 + 150 + 225 + 450 = 1209. If we attempt to factorize 39 we get 39 = 3 × 13. Similarly 3 × 13 × 31. The repetition of the 3 and 13 seems interesting.
Let us consider another number, say 6, which has a prime factorization of 2131. The factors are 1, 2, 3 and 6, which add up to 12, which in turn can be written as 3 × 4. Similarly, the factors of 15, which has a prime factorization of 3151, are 1, 3, 5, and 15, which add up to 24, which is 4 × 6. Also, the factors of 30, which has a prime factorization of 213151, are 1, 2, 3, 5, 6, 10, 15, and 30, which add up to 72, which is 3 × 4 × 6. We can see that, when 21 appears in the prime factorization, the sum of the factors has 3 as a factor. Similarly, when 31 appears in the prime factorization, the sum of the factors has 4 as a factor. And when 51 appears in the prime factorization, the sum of the factors has 6 as a factor.
Now let us consider some other examples. These are summarized in the table below.
The results are also color coded. 21 links with 3, 22 links with 7, 31 links with 4, 32 links with 13, 51 links with 6, 52 links with 31, and 71 links with 8. Of course, if you are familiar with series of powers of natural numbers, you will recognize that
Hence, it seem as though, for a number like, say 42, the sum of the factors can be written as
We can see how this makes sense. The final expression involving a product of three terms can be expanded as follows:
We can, therefore, reach a generalization as follows for any natural number, N. Suppose the prime factorization of N is
Then the sum of the factors of N will be
Consider the number 12,600 = 23325271. According to the result we have just obtained, the sum of all the factors should be (1 + 2 + 3 + 4 + 5)(1 + 3 + 9)(1 + 5 + 25)(1 + 7) =48,360. This is confirmed here. Of course, we could use the previous result to determine that 12,600 has (3 + 1)(2 + 1)(2 + 1)(1 + 1) = 72 factors.
Using the two results we have obtained we can determine how many factors a number has and the sum of those factors without determining what those factors are. So, for example, if we are given the number 174,636,000 = 25345372111, we can determine that it has (5 + 1)(4 + 1)(3 + 1)(2 + 1)(1 + 1) = 720 factors, the sum of which is (1 + 2 + 4 + 8 + 16 + 32)(1 + 3 + 9 + 27 + 81)(1 + 5 + 25 + 125)(1 + 7 + 49)(1 + 11) = 813,404,592. We can observe that the terms in each set of parentheses form a geometric sequence with first term 1, which can easily be summed using the formula
In other words, even with extremely large numbers, we can obtain the number of factors and the sum of factors with a few lines of code in a computer.
Looking Ahead
What we have seen in this post is a way of determining the number of factors of a number and the sum of its factors without having to find all the factors. We do need to determine the prime factorization of the number. However, this is a straightforward process. Now, we used the fundamental theorem of arithmetic to help us determine both the number of factors and the sum of the factors. While this may not be a theorem that is explicitly named when we are in school, it is something that we use regularly after learning division and factorization. Hence, we used some relatively simple mathematics that we learned in elementary school to unravel the question of the number and sum of factors. While some of the formalism and symbols used might be beyond what a student in elementary can understand, the arithmetic behind it is something that elementary students can understand. This is especially so if we demonstrate how, while expanding the expression for the sum of factors, we need to choose one term from each set of parentheses without repetition.
In the next post, we will tackle the technique of partitioning. In order to set up the post, I will leave you with a question. Given that x, y, and z are natural numbers, how many solutions exist to the equation x + y + z = 100?
Acutely Obtuse 