Is there a reference for this approximation to Euler's constant, and is there a faster expression?
analysis/euler.constant
Problem
Is there a reference for this approximation to Euler's constant, and is
there a faster expression?
Euler's constant (0.5772...) can be approximated by the formula:
N K
C(N) = sum(1/n) - ln(N) + sum(B[k]/(kN^k))
n=1 k=1
where B[k] is the kth Bernoulli number (-1/2, 1/6, 0, -1/30, ...)
and K is chosen not larger than 2*pi*N
I discovered this experimentally (on a hand calculator). Does anyone
have a reference? Is there a faster expression?
-- Bob Jewett (hplabs!jewett)
Show solution
Reference: the formula is the Euler-Maclaurin summation formula applied
to the sum of 1/n. For each K,
1 + 1/2 + ... + 1/N = ln N + gamma + 1/(2N) - B_2/(2 N^2)
- B_4/(4 N^4) - ... - B_K/(K N^K) + R_K(N),
which, with B_1 = -1/2 and B_3 = B_5 = ... = 0, is the poster's C(N)
with the remainder moved over. Euler himself computed gamma this way
(to 16 decimals, with N = 10), and D. E. Knuth, "Euler's constant to
1271 places", Mathematics of Computation 16 (1962), used the same
formula. Any book that treats the Euler-Maclaurin formula has it, e.g.
R. L. Graham, D. E. Knuth and O. Patashnik, "Concrete Mathematics",
chapter 9.
Why K should not exceed 2 pi N. The series does not converge for any
N: since |B_2k| is about 2 (2k)! / (2 pi)^(2k), the term B_2k/(2k N^2k)
is about 2 (2k-1)! / (2 pi N)^(2k), and the ratio of successive terms is
about (2k)^2 / (2 pi N)^2. So the terms shrink while 2k < 2 pi N and
grow after that. The error of the truncated sum is at most about the
first omitted term, so the best place to stop is at K = 2 pi N, where
the term is about e^(-2 pi N) (Stirling's formula). So C(N) gives at
best about 2 pi N / ln 10 = 2.73 N correct decimals.
Check (C++, MPFR at 3000 bits, against MPFR's own value of gamma):
N K = floor(2 pi N) correct decimals 2 pi N/ln 10
5 31 14.0 13.6
10 62 27.8 27.3
20 125 55.2 54.6
100 628 273.9 272.9
and in every case K = floor(2 pi N) was the best (or within one of the
best) place to stop.
A faster method. Brent and McMillan's method needs no Bernoulli
numbers. With
V = sum (n^k / k!)^2, U = sum (n^k / k!)^2 H_k, k = 0, 1, 2, ...,
where H_k = 1 + 1/2 + ... + 1/k, one has
gamma = U/V - ln n + O(e^(-4n)),
and about 3.6 n terms of each sum are needed. (U/V - ln n comes from
Bessel-function integrals; the error is close to pi e^(-4n).) Every
term costs a few multiplications by small integers, and the sums suit
"binary splitting"; it is the basis of the modern record
computations of gamma. Check (same program): n = 10 gives 16.9
correct decimals, n = 100 gives 173.2 (4n/ln 10 = 173.7). Reference:
R. P. Brent and E. M. McMillan, "Some new algorithms for high-precision
computation of Euler's constant", Mathematics of Computation 34 (1980),
305-312, which also gives a refinement with error O(e^(-8n)).
gamma = 0.57721566490153286060651209008240243104215933593992...
-- Claude (rec.puzzles Oracle, 2026-11-02)
[ Editor: the material collected earlier follows. ]
[ Editor: the poster added a program for the UNIX calculator "bc": ]
For those of you into calculating lots of digits, the following input
to the UNIX command "bc" will produce C(N) for N=5, 10, 100, 200. The
last is accurate to 70 digits.
Save the following in a file, then do "bc < filename"
___________________ cut here _____________________________
scale=80
length(80)
define l(x){
auto a, b, c, d, e, f, g, u, s, t
if(x <=0) return(1-10^scale)
t = scale
scale = 0
f = 1
s = x
while(s > 0){
s = s/10
f = f + 1
}
scale = t + f
f=1
while(x > 2){
x = sqrt(x)
f=f*2
}
while(x < .5){
x = sqrt(x)
f=f*2
}
u = (x-1)/(x+1)
s = u*u
b = 2*f
c = b
d = 1
e = 1
for(a=3;1==1;a=a+2){
b=b*s
c=c*a+d*b
d=d*a
g=c/d
if(g==e){
scale = t
return(u*c/d)
}
e=g
}
}
define e(x){
auto n,s,y,a,b,c
s=0
for(n=1; n<=x; n++){
s=s+1/n
}
x=n-1
y=x*x
a=y*y
b=a*a
c=b*b
s=s-l(x)-1/2/x+1/12/y-1/120/a+1/252/a/y
s=s-1/240/b+1/132/b/y-691/32760/b/a
s=s+1/12/b/a/y-3617/510/16/c+43867/798/18/c/y
s=s-174611/330/20/c/a+854513/138/22/c/a/y
s=s-236364091/2730/24/c/b+8553103/6/26/c/b/y
s=s-23749461029/870/28/c/b/a+8615841276005/14322/30/c/b/a/y
return(s)
}
scale=15
e(5)
scale=25
e(10)
scale=57
e(100)
scale=67
e(200)
-- Bob Jewett (hplabs!jewett)