Neil Sloane posted this on the NMBRTHRY list. I'm replying here because this seems to be a programming problem as well as a math and number theory problem. Date: Fri, 25 Mar 2005 08:56:33 -0500 From: "N. J. A. Sloane" <njas@research.att.com> Subject: Sum of reciprocals of primes To: NMBRTHRY@LISTSERV.NODAK.EDU I keep seeing quotes that the sum of 1/p for all the primes p that mankind has ever seen will never exceed 4. Just how hard would it be to compute the next term in these two sequences? Neil Sloane %I A016088 %S A016088 5,277,5195977 %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)). %D A016088 Calvin C. Clawson, Mathematical Mysteries, The Beauty and Magic of Numbers, Plenum Press, NY and London, 1996, page 64. %H A016088 <a href="http://www.research.att.com/~njas/sequences/Sindx_1.html#1overn">Index entries for sequences related to decimal expansion of 1/n</a> %t A016088 s =0; k =1; Do[ While[ s =N[ s +1/Prime[ k ], 36 ]; s <= n, k++ ]; Print[ Prime[ k ] ]; k++,{n,1,3} ] %Y A016088 Cf. A046024. %K A016088 nonn,bref,nice,hard,more %O A016088 1,1 %A A016088 Robert G. Wilson v (rgwv(AT)rgwv.com) %E A016088 a(3) corrected by Ulrich Schimke (UlrSchimke(AT)aol.com), who estimates that a(4) is approximately 1.8*10^18. %I A046024 %S A046024 3,59,361139 %N A046024 a(n) = smallest k such that Sum_{ i = 1..k } 1/prime(i) exceeds n. %C A046024 The corresponding primes prime(a(n)) are in A016088. %C A046024 Index m for which the prime harmonic number p[ m ] := Sum[ 1/Prime[ k ],{k,1,m} ] >= n. %H A046024 E. W. Weisstein, <a href="http://mathworld.wolfram.com/PrimeNumber.html">Link to a section of The World of Mathematics.</a> %H A046024 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HarmonicSeriesofPrimes.html">Harmonic Series of Primes</a> %Y A046024 Cf. A004080, A16088. %K A046024 nonn,more,bref,nice %O A046024 1,1 %A A046024 Eric W. Weisstein (eric(AT)weisstein.com) It would be straightforward to set up a distributed computation to sum 1/p for p < 1.8e18, and locate the specific P that bumps the sum over 4. In a few more years the resources will be available to many of us as individuals. I've thought about doing similar computations myself, but always get bogged down in "As long as you're touching all those primes, what else do you want to compute?". I also want sum 1/(p-1), product P, etc. For the specific problem of finding the 4-crossing, it may not be necessary to touch every prime: group the primes into small blocks, whose reciprocals are nearly equal, and compute the upper & lower bounds on the reciprocal sum. Does this save any work? Finding A(5) will be more challenging: the terms grow roughly as Eth powers, so A(5) will be somewhere around (1.8 * 10^18) ^ 2.718 ~= 10^50. Absent some theory advances, we won't be computing that sum anytime soon. Odlyzko & friends have pushed exact computations of pi(N) up to around N = 10^21 using a zeta function based formula, so perhaps sum(1/p) could be tackled similarly. This doesn't require touching every prime. Sequence comment: The Sequence database contains many related sequences such as A016088 and A046024. They are usually cross referenced, but it would be nice to do a little better. In this case, if I started with A046024, I might conclude that I didn't need to look at A016088, since the contents were obvious and I wasn't interested in the exact numbers. This would cause me to miss the little note at the end of A016088 about the estimate for A(4). Both sequences also omit the asymptotic formula for sum 1/p, which is something like gamma + loglog p. Wish: When several related sequences are in the database, designate one of them as Main, and include a short article about all of them and the relationships. Then each related sequence can point to the Main one. This would be especially helpful for sequences which count groups of different kinds. Rich rcs@cs.arizona.edu