:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте ::
Путь: Математика » Быстрые вычисления » The Apery's constant
  The Apery's constant



Если Вы найдете статью полезной и интересной - не сочтите за труд, переведите материал или хотя бы часть его и отправьте на адрес algolist@manual.ru. Задать вопросы или просто написать письмо можно также на странице контактов.

Статья любезно предоставлена:
© Xavier Gordon
web: numbers.computation.free.fr

z(3) = 1.20205690315959428539973816151144999076498629234049ј


  1  Introduction



The Apery's constant is defined by the formula

z(3) = Ґ
е
n = 1 
1
n3
.
(1)

It is the value of the Riemann Zeta function

z(s) = Ґ
е
n = 1 
1
ns
for s = 3. The values of the Zeta function for s = 2n are known to be fractions of p2n, for example Euler proved
z(2) = p2
6
,    z(4) = p4
90
,    z(6) = p6
945
,    ј
Such formulas does not exist for z(2n+1), and few things are known about these numbers. A breakthrough was made in 1978, when Apery proved that z(3) is irrational (see [1], [2] and [3]). Unhappily, his proof does not extends to other value of z(2n+1). It is not known if z(3) is transcendental or not.

  2  Computation of Apery's constant



The expression (1) is very slow to converge. Acceleration on this series based on asymptotic expansion with Bernoulli numbers, as what can be done for the Euler's constant (see The Euler's constant gamma) can be done. The use of Euler's transformation is also efficient.

2.1  Some basic formulas

Observe that the function z(s) may be rewritten as

z(s)
=
Ґ
е
n = 1 
1
ns
= Ґ
е
k = 0 
1
(2k+1)s
+ Ґ
е
k = 0 
1
(2k+2)s
=
Ґ
е
k = 0 
1
(2k+1)s
+ 1
2s
z(s),

hence the definition formula becomes

z(s) = 2s
2s-1
Ґ
е
k = 0 
1
(2k+1)s
,

and for s = 3

z(3) = 8
7
Ґ
е
k = 0 
1
(2k+1)3
.

An interesting formula is deduced from

2 ж
з
и
2s-1
2s
ц
ч
ш
z(s)-z(s)
=
2 Ґ
е
k = 0 
1
(2k+1)s
- Ґ
е
k = 0 
1
(k+1)s
2s-1-1
2s-1
z(s)
=
Ґ
е
k = 0 
(-1)k
(k+1)s
,

leading, with s = 3, to the alternating series

z(3) = 4
3
Ґ
е
k = 0 
(-1)k
(k+1)3
.

2.2  Euler's transformation

In 1755, Euler gave the first version of what is now called Euler's transformation. This transformation is an efficient way to accelerate the convergence of an alternating series (see Acceleration of the convergence of series for a more precise description of this method, together with other acceleration techniques). Before applying it to z(3), we recall Euler's result

Theorem 1 Let S = u0-u1+u2-... be a convergent alternating series, then

S =
lim
n® Ґ 
Sn =
lim
n® Ґ 
ж
з
и
1
2
n
е
k = 0 
(-1)k
2k
Dku0 ц
ч
ш
,

and D is the forward difference operator defined by

Dku0 = (-1)k k
е
j = 0 
(-1)j ж
з
и
k
j
ц
ч
ш
uj.

The first values of Dku0 are

D0u0
=
u0,
D1u0
=
u0-u1,
D2u0
=
u0-2u1+u2,
D3u0
=
u0-3u1+3u2-u3,
...,
Dku0
=
u0-ku1+ k(k-1)
2!
u2- k(k-1)(k-2)
3!
u3+...+(-1)kuk.

If we apply the theorem to the series

z(3) = 4
3
Ґ
е
k = 0 
(-1)k
(k+1)3
,

so uj = 1/(j+1)3, the first iterates are given

S10
=
1.20(1763441817045221115...),
S20
=
1.202056(688008082065896...),
S30
=
1.20205690(2987009688364...),
S60
=
1.202056903159594285(289...).

The rate of converge is correct and geometric. Other acceleration techniques can also be applied to compute efficiently z(3) (see Acceleration of the convergence of series), like the one described in [9] for example.

2.3  Asymptotic expansion

Using the asymptotic expansion formula with Bernoulli's numbers to the function f(t) = 1/t3 (Euler-Maclaurin summation formula) gives

z(3) @ n
е
k = 1 
1
k3
+ 1
2n2
- 1
2n3
+ 1
2n2
p
е
k = 1 
(2k+1)B2k
n2k
.

This expansion is helpful to compute a few hundred digits of z(3).

2.4  Fast converging series to z(3)

Another family of approaches consists in using recent geometrically convergent series for z(3), of the same kind than the series given by Apery :

z(3) = 5
2
Ґ
е
n = 1 
(-1)n-1 (n!)3
n3 (2n)!
(see [1] for a proof).

In 1996, T. Amdeberhan used a recent series acceleration method [5] to obtain faster series. In [6], he provides the formulas

z(3) = 1
4
Ґ
е
n = 1 
(-1)n-1 56n2-32n+5
(2n-1)2
((n-1)!)3
(3n)!
and
z(3) = Ґ
е
n = 0 
(-1)n
72
5265n4+13878n3+13761n2+6120n+1040
(4n+1)(4n+3)(n+1)(3n+1)2(3n+2)2
(n!)2 (2n)!
(4n)!
.

A few months later, T. Amdeberhan and D. Zeilberger [7] obtained a better series

z(3) = Ґ
е
n = 0 
(-1)n 205n2+250n+77
64
(n!)10
((2n+1)!)5
.
(2)

This formula was used by Greg Fee and Simon Plouffe to obtain 520,000 decimal places of z(3) in 1996.

A better series, deduced from [7] (and used by S. Wedeniwski to obtain more than 128 million decimal places of z(3) in 1999) is

z3)=Ґ
е
n=0 
(-1)n(126392n5+412708n4+531578n3+336367n2+104000n+12463)
24
((2n+1)!(2n)!n!) 3
(3n+2)!((4n+3)!)3
(3)

These series can be used either with a classical approach, giving a complexity of O(n2) to compute n digits of z(3), or with a binary splitting approach, leading to a quasi-linear time O(nlog3(n)).

2.5  Use of the derivatives of the Gamma function

In [4], E. Karatsuba used a generic approach to compute n digits of z(3) in time O(nlog3(n)). The method is based on the series expansion for the Gamma function :

log(G(s+1)) = -gs +
е
k = 2 
(-1)k
k
z(k)sk.
By successive differentiation at s = 0, we obtain
2 z(3) = - Gўўў(1) + 3 Gў(1)Gўў(1) -2Gў(1)3.
(4)
The derivatives of the Gamma function at x = 1 are defined by
G(k)(1) = у
х
Ґ

0 
e-t logk(t) dt.
These integrals can be computed in several ways, for example by a series expansion of e-t, giving
G(k)(1) = Ґ
е
n = 1 
(-1)n
n!
у
х
N

0 
tn logk(t) dt + O(e-Nlogk(N)).
Another approach consists in using integration by parts, leading to the final result [8]
z(3) = - G(1,N)3 - 3G(1,N)G(2,N) - 3G(3,N) + O(e-N)
(5)
where
G(s,N) = 4N
е
k = 1 
(-N)k
k!ks
.

Using a binary splitting approach, these family of methods leads to a complexity of O(nlog3(n)) to compute n digits of z(3). However, the constant in front of the O is big compared to the one obtained with series like (2), making this approach significantly less interesting.


  3  Records of computation



Number of digits When Who Notes
16 ??? Legendre
32 1887 Stieljes Stieljes also computed z(k) for 2 Ј k Ј 70 to 32 decimal places. The computation permitted him to obtain 32 decimal places of the Euler constant g with the formula g = 1-log(3/2)-(z(3)-1)/3/43-(z(5)-1)/5/45 ј
520,000 1996 Greg Fee and Simon Plouffe The computation was done with a 64 bit experimental version of Maple with formula (2).
1,000,000 1997 Bruno Haible and Thomas Papanikolaou The computation took 8 hours on a HP 9000/712 machine.
10,536,006 1997, May Patrick Demichel The computation took 360 hours on a HP 9000/871 (160 Mhz) and used a classical approach.
14,000,074 1998, Feb Sebastian Wedeniwski The computation took 53 h 22 min on 2 x UltraSPARC 200 MHz, 6 x Pentium II 233 MHz, 4 x Pentium 133 MHz
32,000,213 1998, Mar Sebastian Wedeniwski The computation took 35 h 21 min on 9 x MIPS R10000 180 MHz
64,000,091 1998, Jul Sebastian Wedeniwski The computation took 33 h on Power2 SC 135 MHz and PowerPC 604e 233 MHz
128,000,026 1998, Dec Sebastian Wedeniwski The computation took 39 hours 22 minutes on a 10 processor machine (IBM S/390 G5 CMOS (9672-RX6), ca 420 Mhz, 2 GB central storage, 14 GB expanded storage) from formula (3) with a binary splitting approach. Verification was made with the same formulae and a different slitting process and different FFT, in two weeks on two machines (IBM Power2 SC 135 MHz, 2 GB RAM and IBM PowerPC 604e 233 MHz, 1 GB RAM).


Related links on z(3)

Apery's Constant by Steven Finch


  References



[1]
A. van der Poorten, A Proof that Euler missed...Apйry's proof of the irrationality of , Math. Intelligencer 1 (1979), 196-203.

[2]
F. Beukers, A note on the irrationality of z(3), Bull. London Math. Soc. 11 (1979) 268-272.

[3]
J. M. Borwein and P. B. Borwein, Pi and the AGM: A study in analytic number theory and computational complexity, Wiley 1987.

[4]
E. A. Karatsuba, Fast Calculation of the Riemann Zeta function z(s) for Integer Values of the Argument s, Problems of Information Transmission 31 (1995) 353-362.

[5]
H.S. Wilf, D. Zeilberger, Rational functions certify combinatorial identities, Jour. Amer. Math. Soc. 3 (1990) 147-158.

[6]
T. Amdeberhan, Faster and faster convergent series for zeta(3), Elec. J. Comb. 3 (1996)

[7]
T. Amdeberhan and D. Zeilberger, Hypergeometric series acceleration via the WZ method, Elec. J. Comb. (Wilf Festschrifft Volume) 4 (1997)

[8]
J. M. Borwein, D. M. Bradley and R. E. Crandall, Computational strategies for the Riemann zeta function, CECM preprint 98:118 (1998)

[9]
P. Borwein, An efficient algorithm for the Riemann Zeta function