"Rich" == Richard Schroeppel <rcs@CS.Arizona.EDU> writes:
Rich> It would be straightforward to set up a distributed computation Rich> to sum 1/p for p < 1.8e18, and locate the specific P that bumps Rich> the sum over 4. In a few more years the resources will be Rich> available to many of us as individuals. I've thought about Rich> doing similar computations myself, but always get bogged down in Rich> "As long as you're touching all those primes, what else do you Rich> want to compute?". I also want sum 1/(p-1), product P, etc. ... Rich> Odlyzko & friends have pushed exact computations of pi(N) up to Rich> around N = 10^21 using a zeta function based formula, so perhaps Rich> sum(1/p) could be tackled similarly. This doesn't require Rich> touching every prime. Ah, this piqued my attention. Since I was one of the "friends" involved in the combinatorial formula (which was the one used for the above quoted values -- the analytic formula seems much more difficult to get to work in a practical range), I can outline what needs to be done for an algorithm which will probably be O(x^(2/3) + epsilson) (but there's a serious issue of precision -- see below) to calculate sum_{p <= x} 1/p to sufficient accuracy. Once you have an algorithm for that, you can find the crossover point you want by binary search (or even better, interpolation search): for k a positive integer, let p_k denote the k'th prime, and set S(x,k) = sum { 1/n | 1 <= n <= x, and p_j does not divide n for j<=k }. Then, we have the recursion, for k>0: S(x,k) = S(x,k-1) - (1/p_k) S(x/p_k,k-1) (*) and S(x,0) = sum_{n<=x} 1/n Now S(N,sqrt(N)) = sum_{ sqrt(N) <= p <= N} 1/p (this is tricky this sum will be very close to log(2), so the "extra" amount is important). The key to the algorithm is to use the recursion (*) as long as k>=k_0 (for some convenient k_0, like 5) and x >= N^(2/3). We can then evaluate the values of S(x,a) that we have left by means for a tree data structure (see Lagarias, Miller and Odlyzko, Math. Comp. 1984 (I think)). Since the number of summands involved in all of the intermediate sums is <=N, it means that we need to know the initial values of sum_{1 <= i <= k} 1/k (for all k <= N^2/3) to at least an accuracy of (1/(2N)). However, the fact that the recursion (*) involves subtraction might well make this numerically unstable and force a lot more precision to be needed. Maybe someone will be motivated to make it work. Victor