Повторное размещение его в понятной и понятной форме без какого-либо сложного MathJax, который не отображается должным образом:
Я изучил некоторые сайты, посвященные проблемам информатики / теории чисел, для забавы, и они представили следующую проблему, в точности следующую:
Пусть P(n) = sum{1<=k<=n} φ(k)
Найти P(10^16)
Я долго об этом искал и пробовал разные подходы:
Используя формулу для φ(n)= n * product{1<=i<=k} (Pi-1)/Pi, я попытался вычислить φ(n) в диапазоне, но это становится очень неэффективным для больших n. Я мог бы добраться до 10^7 с таким подходом. Помимо этого, он просто становится слишком медленным.
Я попробовал другой, более прямой. Википедия и Wolfram Alpha предлагают аналогичные формулы для прямого вычисления P(n):
P(n) = sum {1<=k<=n} φ(k)= 0.5⋅(1+∑{1<=k<=n} μ(k)⋅⌊n/k⌋^2)
Эта формула казалась намного более перспективной. Я попробовал это и смог продвинуться намного дальше 10^7, но все еще далеко от цели С предварительным расчетом сита функции Мёбиуса я мог получить чуть меньше 10^9. Моей памяти было недостаточно, и я не мог больше вычислять значения в сите. И даже если бы я мог, это все еще занимает много времени и очень далеко от 10^16.
Вот часть кода, который я использовал для второго подхода, написанного на Java:
public static BigInteger PhiSummatoryFunction (long limit)
{
BigInteger sum = BigInteger.ZERO;
int [] m = MoebiusSieve(limit);
for (int i=1;i<m.length;i++)
sum=sum.add(BigInteger.valueOf((long) (m[i]*Math.floor(limit/i)*Math.floor(limit/i))));
return sum.add(BigInteger.ONE).divide(BigInteger.ONE.add(BigInteger.ONE));
}
Где MoebiusSieve - это функция, которая вычисляет значения функции Мебиуса до определенного предела в сите с использованием метода, подобного эратосфену.
- После понимания и реализации нового рекурсивного метода для этого вычисления, который я нашел в Интернете:
P (n) = n (n + 1) / 2 − ∑ {2
Я могу вычислять значения до P(10^11), и с максимальным выделением памяти, предварительно вычисляя столько φ (n), сколько возможно, и, следовательно, все P(n), которые я могу для запоминания, я могу вычислить P(10^12) всего за более 20 минут. Значительное улучшение, но все еще немного далеко от P(10^16). Это нормально, если вычисление займет немного больше времени, но я боюсь, что P(10^16) займет экспоненциально больше времени, судя по «скачку» во времени вычислений между P(10^11) и P(10^12). Моя память позволяет мне «сохранять» до 350,000,000 φ(n) values ИЛИ до 700,000,000 μ(k) values. Возможно, есть способ выполнить суммирование, используя значения μ (k), а не φ (n) ?.
Все мои вычисления предполагают и показывают, что моя рекурсия является выдающимся потребителем времени. Это очевидно, но я уверен, что это займет больше времени, чем следовало бы. Я публикую ниже код рекурсии с некоторой документацией. Мне кажется, это правильный способ сделать это вычисление, но моя реализация не оптимальна.
public 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
{
if (limit<s.length)
return BigInteger.valueOf(s[(int) limit]);
BigInteger sum = BigInteger.valueOf(limit).multiply(BigInteger.valueOf(limit).add(BigInteger.ONE)).divide(BigInteger.valueOf(2)); // this corresponds to the n'th triangular number
BigInteger midsum1=BigInteger.ZERO; // the first sum
BigInteger midsum2=BigInteger.ZERO; // the second sum
long m = 2;
while (limit/m != limit/(m+1) && m*m<=limit) // computing the first sum, first for changing floor(limit/m) values
{
midsum1=midsum1.add(phiR((long) Math.floor(limit/m),s));
m++;
}
for (long k = m;k*k<=limit;k++) // once the floors become constant for some values,-->
{ // can check how many times the value appears, and multiply accordingly,-->
BigInteger midPhi = phiR((long) Math.floor(limit/k),s); // rather than compute the Phi every time
long q = 1;
while (limit/k==limit/(k+1)&&k*k<=limit)
{
q++;
k++;
}
k--;
midPhi=midPhi.multiply(BigInteger.valueOf(q));
midsum1=midsum1.add(midPhi);
}
for (long d=1;d*d<=limit;d++) // computing the second sum
if ((double)d!=Math.floor(limit/d))
midsum2=midsum2.add(BigInteger.valueOf((long) (Math.floor(limit/d)-Math.floor(limit/(d+1)))).multiply(phiR(d,s)));
sum=sum.subtract(midsum1).subtract(midsum2);
return sum;
}
Мне предложили использовать dictinaries , в дополнение к массиву, для больших значений n, но я ничего не знаю об этом. Можно ли сделать еще одно улучшение, чтобы установить временные рамки на день или около того?