Kempner series
Encyclopedia
The Kempner series is a modification of the harmonic series
, formed by omitting all terms whose denominator expressed in base 10 contains a 9 digit. That is, it is the sum
where the prime indicates that n takes only values whose decimal expansion has no 9s. The series was first studied by A. J. Kempner in 1914. The series is interesting because of the counter-intuitive result that, unlike the harmonic series, the Kempner series converges (Kempner showed this value was less than 80 and Baillie showed that to 20 decimals, the actual sum is 22.92067 66192 64150 34816
).
Schmelzer and Baillie found an efficient algorithm
for the more general problem of any omitted string of digits. For example, the sum of 1/n where n has no "42" is about 228.44630 41592 30813 25415. Another, more striking, example: the sum of 1/n where n has no occurrence of the digit string "314159" is about 2302582.33386 37826 07892 02376. (All values are rounded in the last decimal place).
The same argument works for any omitted digit. The result is also true if strings of k digits are omitted, for example if we omit all denominators that have a decimal substring of 42. This can be proved in almost the same way. First we observe that we can work with numbers in base 10k and omit all denominators that have the given string as a "digit". The analogous argument to the base 10 case shows that this series converges. Now switching back to base 10, we see that this series contains all denominators that omit the given string, as well as denominators that include it if it is not on a "k-digit" boundary. For example, if we are omitting 42, the base-100 series would omit 4217 and 1742, but not 1427, so it is larger than the series that omits all 42s.
Farhi considered generalized Kempner series, namely, the sums S(d, n) of the reciprocals of the positive integers that have exactly n instances of the digit d where 0 ≤ d ≤ 9 (so that the original Kempner series is S(9, 0)). He showed that for each d the sequence of values S(d, n) for n ≥ 1 is decreasing and converges to 10 ln 10. Interestingly, the sequence is not in general decreasing starting with n = 0; for example, for the original Kempner series we have S(9, 0) ≈ 22.921 < 23.026 ≈ 10 ln 10 < S(9, n) for n ≥ 1.
The upper bound of 80 is very crude, and Irwin showed by a slightly finer analysis of the bounds that the value of the Kempner series is between 22.4 and 23.3.
Baillie developed a recursion that expresses the contribution from each k+1-digit block in terms of the contributions of the k-digit blocks for all choices of omitted digit. This permits a very accurate estimate with a small amount of computation.
.
Harmonic series (mathematics)
In mathematics, the harmonic series is the divergent infinite series:Its name derives from the concept of overtones, or harmonics in music: the wavelengths of the overtones of a vibrating string are 1/2, 1/3, 1/4, etc., of the string's fundamental wavelength...
, formed by omitting all terms whose denominator expressed in base 10 contains a 9 digit. That is, it is the sum
where the prime indicates that n takes only values whose decimal expansion has no 9s. The series was first studied by A. J. Kempner in 1914. The series is interesting because of the counter-intuitive result that, unlike the harmonic series, the Kempner series converges (Kempner showed this value was less than 80 and Baillie showed that to 20 decimals, the actual sum is 22.92067 66192 64150 34816
).
Schmelzer and Baillie found an efficient algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
for the more general problem of any omitted string of digits. For example, the sum of 1/n where n has no "42" is about 228.44630 41592 30813 25415. Another, more striking, example: the sum of 1/n where n has no occurrence of the digit string "314159" is about 2302582.33386 37826 07892 02376. (All values are rounded in the last decimal place).
Convergence
Kempner's proof of convergence is simple and is repeated in many textbooks, for example Hardy and Wright and Apostol. We group the terms of the sum by the number of digits in the denominator. The number of n-digit positive integers that have no 9 digits is exactly 8(9n−1), and each is greater than or equal 10n−1, so the contribution of this group to the sum is less than 8(9/10)n−1. Therefore the whole sum is bounded byThe same argument works for any omitted digit. The result is also true if strings of k digits are omitted, for example if we omit all denominators that have a decimal substring of 42. This can be proved in almost the same way. First we observe that we can work with numbers in base 10k and omit all denominators that have the given string as a "digit". The analogous argument to the base 10 case shows that this series converges. Now switching back to base 10, we see that this series contains all denominators that omit the given string, as well as denominators that include it if it is not on a "k-digit" boundary. For example, if we are omitting 42, the base-100 series would omit 4217 and 1742, but not 1427, so it is larger than the series that omits all 42s.
Farhi considered generalized Kempner series, namely, the sums S(d, n) of the reciprocals of the positive integers that have exactly n instances of the digit d where 0 ≤ d ≤ 9 (so that the original Kempner series is S(9, 0)). He showed that for each d the sequence of values S(d, n) for n ≥ 1 is decreasing and converges to 10 ln 10. Interestingly, the sequence is not in general decreasing starting with n = 0; for example, for the original Kempner series we have S(9, 0) ≈ 22.921 < 23.026 ≈ 10 ln 10 < S(9, n) for n ≥ 1.
Approximation methods
The series converges extremely slowly. Baillie remarks that after summing 1027 terms the remainder is still larger than 1.The upper bound of 80 is very crude, and Irwin showed by a slightly finer analysis of the bounds that the value of the Kempner series is between 22.4 and 23.3.
Baillie developed a recursion that expresses the contribution from each k+1-digit block in terms of the contributions of the k-digit blocks for all choices of omitted digit. This permits a very accurate estimate with a small amount of computation.
Name of this series
Most authors do not name this series. The name "Kempner series" is used in MathWorld and in Havil's book Gamma on the Euler–Mascheroni constantEuler–Mascheroni constant
The Euler–Mascheroni constant is a mathematical constant recurring in analysis and number theory, usually denoted by the lowercase Greek letter ....
.