7

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.

7
  • 1
    I shouldn't be surprised if inaccuracies in IEEE-754 double-precision floating point come into this somewhere... :-) Oct 17, 2014 at 9:27
  • 3
    Related: sum of the reciprocal of the primes squared
    – r3mainer
    Oct 17, 2014 at 9:37
  • @squeamishossifrage that link pretty much answers my question. i doesn't exist. Oct 17, 2014 at 9:43
  • 2
    @AlbertHendriks 1/2^i converges to 1 only if you start at i = 1, not with i = 2
    – Holloway
    Oct 17, 2014 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, 2014 at 11:48

3 Answers 3

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

1
  • Yes, as @squeamishossifrage 's link shows, it goes to 0.45 Oct 17, 2014 at 10:37
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).

2
  • 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. Oct 17, 2014 at 10:41
  • @ErwinBolwidt - I am actually using the real prime numbers, not the approximate value with logarithm.
    – libik
    Oct 17, 2014 at 10:56
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

2
  • 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, 2014 at 9:35
  • i is float not integer (as for java types) use of DecimalFormat goes without saying probably should mention that.
    – aviad
    Oct 17, 2014 at 11:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.