求和(1/质数[i]^2) >= 1？

Question

在设计算法时，我遇到了这个问题。这不是作业。

定义 P_i 为前 i 个质数的数组。现在我需要找到最小的 i，使得

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

如果存在这样的i，则：

i​​​​​​​​​​​​质数的近似值为i*log(i)。 因此，我在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);
}

然而，上述方法并没有结束，因为它会收敛到0.7。然而，在Java中，1/100000000^2会被计算成0.0，所以这就是为什么它不起作用的原因。出于同样的原因，即使您将第6行替换为以下内容，它也不起作用：

sum += 1.0 / (i*i)

如果我没错的话，这个值应该达到1，因为总和增加得比1/2^i更快，而后者趋向于1。换句话说，这表明Java的舍入导致总和无法达到1。我认为我的问题的最小值i应该存在。

- Albert Hendriks

---

我不应该感到惊讶，如果IEEE-754双精度浮点数的不准确性在这里出现... :-) - T.J. Crowder

相关链接：质数倒数平方和 - r3mainer

@AlbertHendriks 只有当你从 i = 1 开始，而不是从 i = 2 开始时，1/2^i 才会收敛于 1。 - Holloway

有趣的是，它们并没有。通过对 int primes 的 double 滚动求和，我得到了 0.4522474194... 并且还在继续计算（速度越来越慢），在计算了 5,000,000 个质数之后，而正确的数字是 0.4522474200... 。@T.J.Crowder - Will Ness

@T.J.Crowder 更正：当然存在不准确性，只是足够小以至于给人一种不存在的印象...当对10,000个质数进行分块求和时，结果略有不同（在3300万个质数后为0.4522474198...）。 - Will Ness

Answer 1

在这个问题的数学方面，而不是Java方面：

如果我理解了这个问题，就没有解决方案（没有i的值）。

对于任何有限的素数集P_i {p_1，p_2，... p_i}，让N_i成为所有整数的集合，直到p_i，{1,2,3，...，p_i}。对于P_i中的所有p_n，1/p^2的总和将小于N_i中所有1/x^2的总和。

1/x^2的总和 趋于约为1.65，但由于1永远不会在质数集中，因此总和受到约0.65的限制。

- Holloway

---

是的，正如@squeamishossifrage的链接所示，它会变成0.45。 - Albert Hendriks

Answer 2

您不能使用double进行此操作，因为它不是均匀的。您应该使用分数。我找到了这个类：https://github.com/kiprobinson/BigFraction

然后我尝试查找发生了什么：

  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++;
        }
    }

这是输出结果：

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

一分钟后我没有看到任何变化。我进行了调试，发现它的增长速度越来越慢，我不认为它可以无限地达到1 :) （但不知道如何证明）。

- libik

---

自然对数去哪了？或者在你的方法中不需要吗？我问这个问题是因为我刚刚尝试了OP的算法，使用50位精度的BigDecimal，它也收敛到接近0.7。 - Erwin Bolwidt

@ErwinBolwidt - 我实际上使用的是真实的质数，而不是用对数近似的值。 - libik

Answer 3

我猜当你使用默认的Math.log乘以float i时，你可能会失去所需的精度。我认为这可以通过使用适当的舍入模式来处理。请参见setRoundingMode

- aviad

---

Math.log 返回一个双精度浮点数，而 i 是整数，所以乘法的结果是一个双精度浮点数。我不明白 RoundingMode 怎么会有帮助，因为这里没有使用 DecimalFormat。 - Zharf

i是浮点数而不是整数（对于Java类型而言），使用DecimalFormat应该是不言自明的，但可能还是值得提一下。 - aviad