Найти вероятность того, что два случайно выбранных целых числа (из n целых) будут относительно простыми

Question

Я столкнулся с проблемой поиска указанной вероятности, и моей первой попыткой было найти следующий алгоритм: я считаю количество пар относительно простых.

int rel = 0
int total = n * (n - 1) / 2
for i in [1, n)
    for j in [i+1, n)
        if gcd(i, j) == 1
            ++rel;
return rel / total

, что O (n ^ 2) .

Вот моя попытка уменьшить сложность:

Наблюдение (1): 1 относительно простое по отношению к [2, n], поэтому пары n - 1 тривиальны.

Замечание (2): 2 не является относительно простым числом к ​​четным числам в диапазоне [4, n], поэтому оставшиеся нечетные числа относительно простые числа к 2, поэтому

 #Relatively prime pairs = (n / 2) if n is even 

                         = (n / 2 - 1) if n is odd.

Так что мой улучшенный алгоритм будет:

int total = n * (n - 1) / 2
int rel = 0
if (n % 2) // n is odd
    rel = (n - 1) + n / 2 - 1
else // n is even
    rel = (n - 1) + n / 2

for i in [3, n)
    for j in [i+1, n)
        if gcd(i, j) == 1
            ++rel;
return rel / total

При таком подходе я мог бы уменьшить два цикла, но наихудшая временная сложность все равно O(n^2).

Вопрос: Мой вопрос: можем ли мы использовать какие-либо математические свойства, кроме указанных выше, для нахождения желаемой вероятности в линейном времени?

Спасибо.

Answer 1

Вам нужно будет вычислить суммарную функцию Эйлера для всех целых чисел от 1 до n .Тойент Эйлера или функция фи, φ (n), является арифметической функцией, которая подсчитывает количество натуральных чисел, меньших или равных n, которые являются относительно простыми по отношению к n.

Для эффективного вычисления функции вы можете использовать модифицированную версию Сито Эратосфена .

Вот пример кода C ++ -

#include <stdio.h>

#define MAXN 10000000

int phi[MAXN+1];
bool isPrime[MAXN+1];

void calculate_phi() {
    int i,j;
    for(i = 1; i <= MAXN; i++) {
        phi[i] = i;
        isPrime[i] = true;
    }

    for(i = 2; i <= MAXN; i++) if(isPrime[i]) {
        for(j = i+i; j <= MAXN; j+=i) {
            isPrime[j] = false;
            phi[j] = (phi[j] / i) * (i-1);
        }
    }

    for(i = 1; i <= MAXN; i++) {
        if(phi[i] == i) phi[i]--;
    }
}

int main() {
    calculate_phi();
    return 0;
}

В нем используется формула продукта Эйлера, описанная на странице Википедии Totient Function.

Вычислить сложность этого алгоритма немного сложно, но гораздо меньше, чем O(n^2).Вы можете получить результаты для n = 10^7 довольно быстро.

Answer 2

Для каждого простого p вероятность его случайного деления числа от 1 до n равна

[ n / p ] / n

([ x ] - наибольшее целое число, не превышающее x ).Если n большое, это примерно 1 / p .

Вероятность деления двух таких случайно выбранных чисел составляет

([ n / p ] / n ) ²

Опять же, это 1 / p ² для больших n .

Два числа взаимно просты, если простое число не делит оба, поэтому рассматриваемая вероятность - произведение

Π _{p простое} (1 - ([ n / p ] / n ) ² )

Достаточно рассчитать его для всех простых чисел, меньших или равных n .Поскольку n уходит в бесконечность, этот продукт приближается к 6 / π ² .

Я не уверен, что вы можете использовать функцию totient напрямую, как описано в других ответах.

Answer 3

Число целых чисел в диапазоне 0 .. n, взаимно простых с n, является функцией времени Эйлера от n. Вы вычисляете сумму таких значений, например, называется суммативной функции. Методы для вычисления этой суммы быстро, например, описано здесь . Вы должны легко получить метод с лучшей, чем квадратичной сложностью, в зависимости от того, насколько быстро вы реализуете функцию totient.

Еще лучше ссылки, перечисленные в энциклопедии целочисленных последовательностей: http://oeis.org/A002088,, хотя многие ссылки требуют некоторых математических навыков.

Используя эти формулы, вы даже можете получить реализацию, которая является сублинейной.