Sum (1 / prime [i] ^ 2)> = 1?

Question

While trying to develop an algorithm, I came across this question. This is not homework.

Let P_i = an array of first i primes. Now I need the smallest i such that

 Sum<n=0..i> 1 / (P_i[n]*P_i[n]) >= 1. 

(if such i exists).

The approximation for i'th prime is i*log(i) . So I tried this in Java:

 public static viod main(String args[]) { double sum = 0.0; long i = 2; while(sum<1.0) { sum += 1.0 / (i*Math.log(i)*i*Math.log(i)); i++; } System.out.println(i+": "+sum); } 

However, the above does not end because it converges to 0.7. However, 1/100000000^2 rounded to 0.0 in Java, so why doesn't this work. For the same reason, it doesn’t even work if you replace the 6th line with

 sum += 1.0 / (i*i) 

while this should reach 1 , if I’m not mistaken, because the sum must exceed 1/2^i , and the latter converges to 1 . In other words, this shows that Java rounding causes the sum to not reach 1 . I think that the minimum i my problem should exist.

Answer 1

On the mathematical side of this question, not on the java side:

If I understand the problem, there is no solution (no i value).

For any finite set P_i of primes {p_1, p_2, ... p_i} let N_i be the set of all integers up to p_i, {1,2,3, ..., p_i}. The sum 1 / p ^ 2 (for all p_n in P_i) will be less than the sum of all 1 / x ^ 2 for x in N_i.

The sum 1 / x ^ 2 tends to ~ 1.65 , but since 1 will never be in the set of primes, the sum will be limited to ~ 0.65

Answer 2

You cannot use double for this because it is not homogeneous. You must use fractions. I found this class https://github.com/kiprobinson/BigFraction

Then I tried to find what was going on:

  public static void main(String args[]) { BigFraction fraction = BigFraction.valueOf(1, 4); int n = 10000000, status = 1, num = 3; double limit = 0.4; for (int count = 2; count <= n;) { for (int j = 2; j <= Math.sqrt(num); j++) { if (num % j == 0) { status = 0; break; } } if (status != 0) { fraction = fraction.add(BigFraction.valueOf(1,BigInteger.valueOf(num).multiply(BigInteger.valueOf(num)))); if (fraction.doubleValue() >= limit){ System.out.println("reached " + limit + " with " + count + " firsts prime numbers"); limit += 0.01; } count++; } status = 1; num++; } } 

This conclusion has the following result:

 reached 0.4 with 3 firsts prime numbers reached 0.41000000000000003 with 4 firsts prime numbers reached 0.42000000000000004 with 5 firsts prime numbers reached 0.43000000000000005 with 6 firsts prime numbers reached 0.44000000000000006 with 8 firsts prime numbers reached 0.45000000000000007 with 22 firsts prime numbers 

And nothing more in a minute. I debug it and found that it grows slower and slower, I don’t think that it can reach 1 even at infinity :) (but I don’t know how to prove it).

Answer 3

I think you can lose the necessary accuracy if you use the default value of Math.log multiplied by float i . I think this can be handled with the appropriate RoundingMode. See setRoundingMode