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.

I shouldn't be surprised if [inaccuracies in IEEE-754 double-precision floating point](http://stackoverflow.com/questions/588004/is-floating-point-math-broken) come into this somewhere... :-) — T.J. Crowder, Oct 17 '14 at 09:27
Related: [sum of the reciprocal of the primes squared](http://mathoverflow.net/q/53443) — r3mainer, Oct 17 '14 at 09:37
@squeamishossifrage that link pretty much answers my question. i doesn't exist. — Albert Hendriks, Oct 17 '14 at 09:43
@AlbertHendriks 1/2^i converges to 1 only if you start at i = 1, not with i = 2 — Holloway, Oct 17 '14 at 10:28
@T.J.Crowder interestingly enough, they don't. by simple rolling summation on doubles from int primes, I got to 0.4522474194... and counting (slower and slower), after 5,000,000 primes, whereas the correct number is 0.4522474200... . — Will Ness, Oct 18 '14 at 11:48
@T.J.Crowder correction: of course the inaccuracy exists, it's just small enough to give the impression that it isn't there... when summing by chunks of 10,000 primes, the results are slightly different (0.4522474198... after 33 million primes). — Will Ness, Oct 18 '14 at 12:57

score 7 · Accepted Answer · answered Oct 17 '14 at 10:14

7

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

answered Oct 17 '14 at 10:14

Holloway

6,412
1
26
33

Yes, as @squeamishossifrage 's link shows, it goes to 0.45 – Albert Hendriks Oct 17 '14 at 10:37

score 2 · Answer 2 · answered Oct 17 '14 at 09:57

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).

Where has the natural logarithm gone? Or is this not necessary in your approach? I'm asking because I just tried the OP's algorithm using BigDecimal with 50-digit precision and it also converges to almost 0.7. — Erwin Bolwidt, Oct 17 '14 at 10:41
@ErwinBolwidt - I am actually using the real prime numbers, not the approximate value with logarithm. — libik, Oct 17 '14 at 10:56

aviad · Answer 3 · 2014-10-17T09:31:33.927

0

I guess you might loose the precision you need when you use default Math.log multiplied by float i. I think this can be handled by using an appropriate RoundingMode. Please see setRoundingMode

edited Oct 17 '14 at 09:31

answered Oct 17 '14 at 09:26

aviad

8,229
9
50
98

`Math.log` returns double though, `i` is an integer so the result of the multiplication is a double. I don't see how `RoundingMode` would help since there's no `DecimalFormat` used here. – Zharf Oct 17 '14 at 09:35
i is float not integer (as for java types) use of DecimalFormat goes without saying probably should mention that. – aviad Oct 17 '14 at 11:56

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

3 Answers3