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

Question

While trying to devise an algorithm, I stumbled upon this question. It's not homework.

Let P_i = an array of the 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).

An approximation for the 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 doesn't finish because it converges to 0.7. However 1/100000000^2 rounds to 0.0 in Java, so that's why it doesn't work. For the same reason it doesn't even work if you replace the 6th line with

sum += 1.0 / (i*i)

while that should reach 1 if I'm not mistaken, because the sum should incease faster than 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 of my problem should exist.

Answer 1

On the maths side of this question, not the java side:

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

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 of 1/x^2 tends to ~1.65 but since 1 will never be in the set of primes, the sum is limited by ~0.65

Answer 2

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

Then I tried to find whats happening :

  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 is having this output :

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 extremely slower and slower, I do not think, it can reach 1 even in infinity :) (but dont know how to prove it).