Erdős–Borwein constant
The Erdős–Borwein constant is the sum of the reciprocals of the Mersenne numbers. It is named after Paul Erdős and Peter Borwein.
By definition it is:
- [math]\displaystyle{ E=\sum_{n=1}^{\infty}\frac{1}{2^n-1}\approx1.606695152415291763\dots }[/math][1]
Equivalent forms
It can be proven that the following forms all sum to the same constant:
- [math]\displaystyle{ E=\sum_{n=1}^{\infty}\frac{1}{2^{n^2}}\frac{2^n+1}{2^n-1} }[/math]
- [math]\displaystyle{ E=\sum_{m=1}^{\infty}\sum_{n=1}^{\infty} \frac{1}{2^{mn}} }[/math]
- [math]\displaystyle{ E=1+\sum_{n=1}^{\infty} \frac{1}{2^n(2^n-1)} }[/math]
- [math]\displaystyle{ E=\sum_{n=1}^{\infty}\frac{\sigma_0(n)}{2^n} }[/math]
where σ0(n) = d(n) is the divisor function, a multiplicative function that equals the number of positive divisors of the number n. To prove the equivalence of these sums, note that they all take the form of Lambert series and can thus be resummed as such.[2]
Irrationality
Erdős in 1948 showed that the constant E is an irrational number.[3] Later, Borwein provided an alternative proof.[4]
Despite its irrationality, the binary representation of the Erdős–Borwein constant may be calculated efficiently.[5][6]
Applications
The Erdős–Borwein constant comes up in the average case analysis of the heapsort algorithm, where it controls the constant factor in the running time for converting an unsorted array of items into a heap.[7]
References
- ↑ (sequence A065442 in the OEIS)
- ↑ The first of these forms is given by (Knuth 1998), ex. 27, p. 157; Knuth attributes the transformation to this form to an 1828 work of Clausen.
- ↑ "On arithmetical properties of Lambert series", J. Indian Math. Soc., New Series 12: 63–66, 1948, http://www.renyi.hu/~p_erdos/1948-04.pdf.
- ↑ "On the irrationality of certain series", Mathematical Proceedings of the Cambridge Philosophical Society 112 (1): 141–146, 1992, doi:10.1017/S030500410007081X, Bibcode: 1992MPCPS.112..141B.
- ↑ (Knuth 1998) observes that calculations of the constant may be performed using Clausen's series, which converges very rapidly, and credits this idea to John Wrench.
- ↑ "The googol-th bit of the Erdős–Borwein constant", Integers 12 (5): A23, 2012, doi:10.1515/integers-2012-0007.
- ↑ The Art of Computer Programming, Vol. 3: Sorting and Searching (2nd ed.), Reading, MA: Addison-Wesley, 1998, pp. 153–155.
External links
- Weisstein, Eric W.. "Erdos-Borwein Constant". http://mathworld.wolfram.com/Erdos-BorweinConstant.html.
|  | |
 |  |
