[math-fun] First time harmonic series exceeds 100
I've long wondered what is the smallest n for which (*) 1 + 1/2 + 1/3 + . . . + 1/n > 100. Roughly, I thought it was where ln(n) = 100, i.e., n ~ e^100 ~ 2.688 x 10^43. But more exactly, it would be closer to where 100 - ln(n) = gamma (Euler's), i.e. let K = floor( e^(100-gamma) ). Then n should be fairly close to K (which is roughly only 1.509 x 10^43). Mathematica gives K as exactly K = 15092688622113788323693563264538101449859497 and to my surprise it claims that 1 + 1/2 + 1/3 + . . . + 1/K > 100 but 1 + 1/2 + 1/3 + . . . + 1/(K-1) < 100 (!). Can someone confirm that this K is exactly the least n for which (*) holds? Thanks, Dan P.S. Anyone know a useful upper bound U(n) for the error E(n) = |(1+1/2+1/3+...+1/n) - ln(n) - gamma| ? Evidently E(n) gets very small very fast.
that large integer value was first computed here: Boas, R. P. and Wrench, J. W. "Partial Sums of the Harmonic Series." Amer. Math. Monthly 78, 864-870, 1971. this on-line article has that reference, and other interesting info: http://mathworld.wolfram.com/HarmonicSeries.html bob baillie ----- Daniel Asimov wrote:
I've long wondered what is the smallest n for which
(*) 1 + 1/2 + 1/3 + . . . + 1/n > 100.
Roughly, I thought it was where ln(n) = 100, i.e.,
n ~ e^100 ~ 2.688 x 10^43.
But more exactly, it would be closer to where
100 - ln(n) = gamma (Euler's), i.e. let K = floor( e^(100-gamma) ).
Then n should be fairly close to K (which is roughly only 1.509 x 10^43).
Mathematica gives K as exactly
K = 15092688622113788323693563264538101449859497
and to my surprise it claims that
1 + 1/2 + 1/3 + . . . + 1/K > 100 but 1 + 1/2 + 1/3 + . . . + 1/(K-1) < 100 (!).
Can someone confirm that this K is exactly the least n for which (*) holds?
Thanks,
Dan
P.S. Anyone know a useful upper bound U(n) for the error
E(n) = |(1+1/2+1/3+...+1/n) - ln(n) - gamma| ? Evidently E(n) gets very small very fast.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Dan, see the following sequences in the OEIS: %S A082912 ,2,12367,15092688622113788323693563264538101449859497, %S A096618 ,1,12367,15092688622113788323693563264538101449859497, Neil
There's also the following paper (which was an ANTS 7 poster): "Computing Prime Harmonic Sums" by Eric Bach and Jonathan Sorenson http://euclid.butler.edu/~sorenson/papers/sum1p.pdf I realize that this isn't about the original problem (the first time the sum of the harmonic series exceeds n), but about a related but much harder problem -- the first time the sum of the reciprocals of the sums of the primes exceed n -- harder just because the latter series grows like log log n. Victor
Victor said:
... a related but much harder problem -- the first time the sum of the reciprocals of the sums of the primes exceed n -- harder just because the latter series grows like log log n.
Me: once again, see the OEIS: %S A016088 5,277,5195977,1801241230056600523 %N A016088 a(n) = smallest prime p such that Sum_{ primes q = 2, ..., p} 1/q exceeds n. %C A016088 The indices of these primes are in A046024: a(n) = A000040(A046024(n)). ... %E A016088 Eric Bach comments that the next element in the sequence is about 4.2 * 10^49, so i t may remain unknown for all eternity. and %S A046024 3,59,361139,43922730588128390 %N A046024 a(n) = smallest k such that Sum_{ i = 1..k } 1/prime(i) exceeds n. Neil
njas:
%N A016088 a(n) = smallest prime p such that Sum_{ primes q = 2, ..., p} 1/q exceeds n. ... %E A016088 Eric Bach comments that the next element in the sequence is about 4.2 * 10^49, so it may remain unknown for all eternity.
Bosh! The paper describes an algorithm which takes around x^1/3 space and x^2/3 time. When x = 4 * 10^49, these are roughly 10^16 and 10^33. We have facilities today that handle 10^16 storage. Current world computing capability is ~10^25 instructions/year. (10^8.5 machines, 10^9.5 inst/sec, 10^7.5 sec/year) I looked over their algorithm; at first blush, it seems very parallelizable. So with current resources, we could have the value for a(5) in a mere 10^8 years. This might seem like a long time, especially if your job is behind this one in the queue, but it's far short of eternity. Rich -----Original Message----- From: math-fun-bounces+rschroe=sandia.gov@mailman.xmission.com on behalf of N. J. A. Sloane Sent: Wed 11/8/2006 8:38 PM To: math-fun@mailman.xmission.com; math-fun Cc: njas@research.att.com Subject: Re: [math-fun] First time harmonic series exceeds 100 Victor said:
... a related but much harder problem -- the first time the sum of the reciprocals of the sums of the primes exceed n -- harder just because the latter series grows like log log n.
Me: once again, see the OEIS: %S A016088 5,277,5195977,1801241230056600523 %N A016088 a(n) = smallest prime p such that Sum_{ primes q = 2, ..., p} 1/q exceeds n. %C A016088 The indices of these primes are in A046024: a(n) = A000040(A046024(n)). ... %E A016088 Eric Bach comments that the next element in the sequence is about 4.2 * 10^49, so i t may remain unknown for all eternity. and %S A046024 3,59,361139,43922730588128390 %N A046024 a(n) = smallest k such that Sum_{ i = 1..k } 1/prime(i) exceeds n. Neil
DanA writes
I've long wondered what is the smallest n for which
(*) 1 + 1/2 + 1/3 + . . . + 1/n > 100.
Roughly, I thought it was where ln(n) = 100, i.e.,
n ~ e^100 ~ 2.688 x 10^43.
But more exactly, it would be closer to where
100 - ln(n) = gamma (Euler's), i.e. let K = floor( e^(100-gamma) ).
Then n should be fairly close to K (which is roughly only 1.509 x 10^43).
Mathematica gives K as exactly
K = 15092688622113788323693563264538101449859497
and to my surprise it claims that
1 + 1/2 + 1/3 + . . . + 1/K > 100 but 1 + 1/2 + 1/3 + . . . + 1/(K-1) < 100 (!).
Can someone confirm that this K is exactly the least n for which (*) holds?
Thanks,
Dan
Let H := Harmonic(K) and g:= Euler's constant (gamma ~ .577), then H - g 1 1 K = e - - - --------------- + O(??), 2 H - g 1 24 (e + -) 2 where ?? is < a finite negative power of e^(H-g)+1/2 ! (I.e., these three terms satisfy the Euler-Maclaurin equation identically.) E.g., For H = 100, this instantly gives K ~ 15092688622113788323693563264538101449859496.864101
P.S. Anyone know a useful upper bound U(n) for the error
E(n) = |(1+1/2+1/3+...+1/n) - ln(n) - gamma| ? Evidently E(n) gets very small very fast.
Use the Euler-Maclaurin expansion of H(n) = Digamma(n+1) + gamma. The lead term is ~ 1/(2n+2). You have a big n. --rwg SOUP-KITCHEN UP TO HIS NECK PS, MIT AIMemo 304, (Acceleration of Series) (if anyone can find one) transforms H(n) into another n term series which "converges faster", i.e., the lead terms are >> the final ones.
I gurgled,
Let H := Harmonic(K) and g:= Euler's constant (gamma ~ .577), then
H - g 1 1 K = e - - - --------------- + O(??), 2 H - g 1 24 (e + -) 2
where ?? is < a finite negative power of e^(H-g)+1/2 !
Bullbleep.
(I.e., these three terms satisfy the Euler-Maclaurin equation identically.) This is just an artifact of an irrevertible divergent series. Newton's method works just fine:
H - g 1 1 1 K = e + - - --------------- - ---------------- 2 H - g 1 H - g 1 2 24 (e + -) 48 (e + -) 2 2 11 7 5227 - ------------------ + ------------------ + --------------------- + ... H - g 1 3 H - g 1 4 H - g 1 5 1920 (e + -) 3840 (e + -) 2903040 (e + -) 2 2 2 But since e^H is large, all you need are the first two terms. --rwg Save the DOUBLE-STRAND BLADDERSNOUT.
I blurted
Let H := Harmonic(K) and g:= Euler's constant (gamma ~ .577), then
H - g 1 1 K = e - - - --------------- + O(??), 2 H - g 1 24 (e + -) 2
where ?? is < a finite negative power of e^(H-g)+1/2 !
Bullbleep.
(I.e., these three terms satisfy the Euler-Maclaurin equation identically.) This is just an artifact of an irrevertible divergent series. Newton's method works just fine:
H - g 1 1 1 K = e + - - --------------- - ---------------- 2 H - g 1 H - g 1 2 24 (e + -) 48 (e + -) 2 2
11 7 5227 - ------------------ + ------------------ + --------------------- + ... H - g 1 3 H - g 1 4 H - g 1 5 1920 (e + -) 3840 (e + -) 2903040 (e + -) 2 2 2
Off by 1: H - g 1 1 1 K = e - - - --------------- - ---------------- 2 H - g 1 H - g 1 2 24 (e + -) 48 (e + -) 2 2 11 7 5227 - ------------------ + ------------------ + --------------------- + ... H - g 1 3 H - g 1 4 H - g 1 5 1920 (e + -) 3840 (e + -) 2903040 (e + -) 2 2 2 --rwg <ENTHUSIASTIC UNCHASTITIES> (Borat endorsement. Not.)
----- Original Message ----- From: "R. William Gosper" <rwg@osots.com> To: <math-fun@mailman.xmission.com> Sent: Friday, November 10, 2006 07:14 Subject: [math-fun] Inverse HarmonicNumber oops
I blurted
Let H := Harmonic(K) and g:= Euler's constant (gamma ~ .577), then
H - g 1 1 K = e - - - --------------- + O(??), 2 H - g 1 24 (e + -) 2
where ?? is < a finite negative power of e^(H-g)+1/2 !
Bullbleep.
(I.e., these three terms satisfy the Euler-Maclaurin equation identically.) This is just an artifact of an irrevertible divergent series. Newton's method works just fine:
H - g 1 1 1 K = e + - - --------------- - ---------------- 2 H - g 1 H - g 1 2 24 (e + -) 48 (e + -) 2 2
11 7 5227 - ------------------ + ------------------ + --------------------- + ... H - g 1 3 H - g 1 4 H - g 1 5 1920 (e + -) 3840 (e + -) 2903040 (e + -) 2 2 2
Off by 1:
H - g 1 1 1 K = e - - - --------------- - ---------------- 2 H - g 1 H - g 1 2 24 (e + -) 48 (e + -) 2 2
11 7 5227 - ------------------ + ------------------ + --------------------- + ... H - g 1 3 H - g 1 4 H - g 1 5 1920 (e + -) 3840 (e + -) 2903040 (e + -) 2 2 2
You might prefer the asymptotic series which I gave in "Inverse of Harmonic Numbers", sci.math, 2006 Apr. 4: <http://groups.google.com/group/sci.math/msg/0926db8773d69b81>. You had also said in your previous post:
But since e^H is large, all you need are the first two terms.
Although I certainly suspect this is true (assuming we know that our result must be an integer), I know of no proof, only a heuristic argument. David W. Cantrell
participants (7)
-
Daniel Asimov -
David W. Cantrell -
N. J. A. Sloane -
R. William Gosper -
Robert Baillie -
Schroeppel, Richard -
victor＠idaccr.org