MC *_*tch 6 java arrays algorithm optimization function
以清晰易懂的方式重新发布它，没有任何无法正确显示的复杂 MathJax：
\n\n我出于兴趣探索了一些计算机科学/数论挑战网站，他们提出了以下问题，具体如下：
\n\n让P(n) = sum{1<=k<=n} \xcf\x86(k)
寻找P(10^16)
我对此进行了相当长的搜索并尝试了不同的方法：
\n\n使用 的公式\xcf\x86(n)= n * product{1<=i<=k} (Pi-1)/Pi，我尝试计算\xcf\x86(n)范围内，但这对于大型 来说变得非常低效n。我可以通过这种方法得到尽可能多的结果10^7。除此之外，它就变得太慢了。
我尝试了另一种，更直接。维基百科和 Wolfram Alpha 建议使用类似的公式直接计算P(n)：
P(n) = sum {1<=k<=n} \xcf\x86(k)= 0.5\xe2\x8b\x85(1+\xe2\x88\x91{1<=k<=n} \xce\xbc(k)\xe2\x8b\x85\xe2\x8c\x8an/k\xe2\x8c\x8b^2)
这个公式看起来更有希望。我尝试了一下，虽然离目标还很远，10^7但距离目标还很远。通过预先计算莫比斯函数的筛子，我可以得到略小于 的值10^9。我的内存不足，无法计算筛子中的更多值。而且即使可以，也需要很长的时间，而且还很遥远10^16。
以下是我用 Java 编写的第二种方法的部分代码：
\n\npublic static BigInteger PhiSummatoryFunction (long limit)\n{\n BigInteger sum = BigInteger.ZERO;\n int [] m = MoebiusSieve(limit);\n for (int i=1;i<m.length;i++)\n sum=sum.add(BigInteger.valueOf((long) (m[i]*Math.floor(limit/i)*Math.floor(limit/i))));\n return sum.add(BigInteger.ONE).divide(BigInteger.ONE.add(BigInteger.ONE));\n}\n其中 MoebiusSieve 是一个函数，它使用类似埃拉托色尼的方法计算筛子中达到特定限制的莫比斯函数值。
\n\nP(n)=n(n+1)/2\xe2\x88\x92\xe2\x88\x91{2<=i<=\xe2\x88\x9an} P(\xe2\x8c\x8an/i\ xe2\x8c\x8b)\xe2\x88\x92\xe2\x88\x91{1<=j<=\xe2\x88\x9an} P(j)\xe2\x8b\x85(\xe2\x8c\x8an/ j\xe2\x8c\x8b\xe2\x88\x92\xe2\x8c\x8an/(j+1)\xe2\x8c\x8b)
\n\n我可以计算高达 的值P(10^11)，并且使用最大内存分配，预先计算尽可能多的 \xcf\x86(n) ，因此P(n)我可以P(10^12)在 20 多分钟内计算出所有可以记忆的内容。一个重大改进，但距离仍然有点远P(10^16)。如果计算时间长一点也没关系，但从和P(10^16)之间计算时间的“跳跃”来看，我担心会花费指数级更长的时间。我的记忆力允许我“保存”最多或最多。也许有一种方法可以使用 \xce\xbc(k) 值而不是 \xcf\x86(n) 来执行求和？。P(10^11)P(10^12)350,000,000 \xcf\x86(n) values 700,000,000 \xce\xbc(k) values
我所有的计算都表明并表明我的递归是主要的时间消耗者。这是显而易见的，但我确信这需要比应有的时间更长的时间。我在递归代码下面发布了一些文档。在我看来，这是进行此计算的正确方法，但我的实现并不是最佳的。
\n\npublic static BigInteger phiR (long limit, long [] s) // limit is 10^t, s is the sieve of precomputed values of `P(n)`. Can store maximum 350,000,000 values\n { \n if (limit<s.length) \n return BigInteger.valueOf(s[(int) limit]);\n BigInteger sum = BigInteger.valueOf(limit).multiply(BigInteger.valueOf(limit).add(BigInteger.ONE)).divide(BigInteger.valueOf(2)); // this corresponds to the n\'th triangular number\n BigInteger midsum1=BigInteger.ZERO; // the first sum\n BigInteger midsum2=BigInteger.ZERO; // the second sum\n long m = 2;\n while (limit/m != limit/(m+1) && m*m<=limit) // computing the first sum, first for changing floor(limit/m) values\n {\n midsum1=midsum1.add(phiR((long) Math.floor(limit/m),s));\n m++;\n }\n for (long k = m;k*k<=limit;k++) // once the floors become constant for some values,-->\n { // can check how many times the value appears, and multiply accordingly,--> \n BigInteger midPhi = phiR((long) Math.floor(limit/k),s); // rather than compute the Phi every time\n long q = 1;\n while (limit/k==limit/(k+1)&&k*k<=limit)\n {\n q++;\n k++;\n }\n k--;\n midPhi=midPhi.multiply(BigInteger.valueOf(q));\n midsum1=midsum1.add(midPhi);\n }\n for (long d=1;d*d<=limit;d++) // computing the second sum\n if ((double)d!=Math.floor(limit/d))\n midsum2=midsum2.add(BigInteger.valueOf((long) (Math.floor(limit/d)-Math.floor(limit/(d+1)))).multiply(phiR(d,s)));\n sum=sum.subtract(midsum1).subtract(midsum2);\n return sum;\n }\n除了数组之外，建议我使用dictinariesn来获取较大的值，但我对此一无所知。是否可以进行另一项改进，使时间范围缩短为一天左右？
如果你想知道单个数字n的总，最好的方法是对n进行因式分解，并取每个因式减去 1 的乘积；例如，30 = 2 * 3 * 5，从每个因子中减去 1，然后相乘，得到总数 1 * 2 * 4 = 8。但是如果你想找到小于给定n的所有数字的总数，比对它们进行因式分解更好的方法是进行筛选。这个想法很简单：设置一个从 0 到n的数组X，将i存储在每个X_i中，然后从 0 开始遍历该数组，每当X_i = i循环遍历i的倍数时，将每个乘以 ( i \xe2\x88 \x92 1)/我。您可以在最后计算总和，也可以边加边累加。由于您的筛子很大，因此您需要将其分段。
\n\n以下是我的博客中的一些有用的页面：Sifying For Totients和Segmented Sieve of Eratosthenes。如果你在那里闲逛，你可能还会发现一些其他有趣的事情。
\n