The Erdős–Borwein constant, named after
Paul Erdős
Paul Erdős ( ; 26March 191320September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in discrete mathematics, g ...
and
Peter Borwein, is the sum of the
reciprocals of the
Mersenne number
In mathematics, a Mersenne prime is a prime number that is one less than a power of two. That is, it is a prime number of the form for some integer . They are named after Marin Mersenne, a French Minim friar, who studied them in the early 17t ...
s.
By definition it is:
:
Equivalent forms
It can be proven that the following forms all sum to the same constant:
:
:
:
:
where σ
0(''n'') = ''d''(''n'') is the
divisor function
In mathematics, and specifically in number theory, a divisor function is an arithmetic function related to the divisors of an integer. When referred to as ''the'' divisor function, it counts the ''number of divisors of an integer'' (includi ...
, a
multiplicative function
In number theory, a multiplicative function is an arithmetic function f of a positive integer n with the property that f(1)=1 and
f(ab) = f(a)f(b) whenever a and b are coprime.
An arithmetic function is said to be completely multiplicative (o ...
that equals the number of positive
divisor
In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a '' multiple'' of m. An integer n is divisible or evenly divisibl ...
s of the number ''n''. To prove the equivalence of these sums, note that they all take the form of
Lambert series
In mathematics, a Lambert series, named for Johann Heinrich Lambert, is a series taking the form
:S(q)=\sum_^\infty a_n \frac .
It can be resummed formally by expanding the denominator:
:S(q)=\sum_^\infty a_n \sum_^\infty q^ = \sum_^\infty ...
and can thus be resummed as such.
Irrationality
In 1948, Erdős showed that the
constant ''E'' is an
irrational number
In mathematics, the irrational numbers are all the real numbers that are not rational numbers. That is, irrational numbers cannot be expressed as the ratio of two integers. When the ratio of lengths of two line segments is an irrational number, ...
. Later, Borwein provided an alternative proof.
Despite its irrationality, the
binary representation
A binary number is a number expressed in the base-2 numeral system or binary numeral system, a method for representing numbers that uses only two symbols for the natural numbers: typically "0" (zero) and "1" (one). A ''binary number'' may also ...
of the Erdős–Borwein constant may be calculated efficiently.
Applications
The Erdős–Borwein constant comes up in the
average case analysis of the
heapsort
In computer science, heapsort is an efficient, comparison-based sorting algorithm that reorganizes an input array into a heap (a data structure where each node is greater than its children) and then repeatedly removes the largest node from that ...
algorithm, where it controls the constant factor in the running time for converting an unsorted array of items into a heap.
[.]
References
External links
*
{{DEFAULTSORT:Erdos-Borwein Constant
Mathematical constants
Irrational numbers
Borwein constant