Вероятность появления взаимно простых чисел

[wrest]

B3LYP в сообщении #1726193 писал(а):

мне хочется понять что-то в математике, чтобы не было “за деревьями не видно леса”.

B3LYP в сообщении #1726174 писал(а):

мне интересно изучать теорию простых чисел, вдруг когда-нибудь удастся придумать что-нибудь с этим разложением.

Тогда почитайте например про функцию Эйлера и её свойства.
https://ru.wikipedia.org/wiki/%D0%A4%D1 ... 1%80%D0%B0

[wrest]

B3LYP в сообщении #1726193 писал(а):

если никому тут не интересно обсуждать общие приёмы алгоритмической оптимизации, жаль...

Неинтересно тут другое: играть с вами в угадайку что вы там написали и как ускорили, не видя вашего кода

B3LYP в сообщении #1726193 писал(а):

Но зачем мне это делать, если это увеличивает сложность кода и соответственно вероятность ошибок?

Вот код который считает очень быстро, код очень простой, одна строчка на pari/gp:
pt(n)=my(s=sum(i=1,n,eulerphi(i)));return((2*s-1)/(n^2))
Но вот разобраться в нём для вас было бы неплохо, с математической стороны вопроса.
Это код считает искомую вероятность по формуле

$$P(n)=\dfrac{1}{n^2} \left( 2 \sum \limits _{k=1}^n \varphi(k) -1 \right)$$

где $\varphi(k)$ функция Эйлера
Почему это работает?

[B3LYP]

Мне хочется продолжить свои изыски, чтобы в итоге “отвелосипедить” функцию Эйлера; я статью в Вики про неё ещё не читал, и пока даже не просмотрел внимательно ответы в теме.
Переписал алгоритм и думал что он должен ускориться, но нет – чуть даже замедлился. Попробовал немного провести “среднеуровневую оптимизацию” (поварьировал размеры динамических массивов и пр.) – не помогло. Тогда я упростил код, убрав дополнительные массивы – стало чуть быстрее и заодно уменьшилась потребность в памяти. Итого новый алгоритм всего на 20% быстрее считает график выше, и ясно что без функции Эйлера тут никак.
В новом алгоритме изначально быстрее стал заполнятся массив со списком простых чисел для каждого перебираемого числа, но это ничего не изменило, поскольку лимитирующей стадией является перебор N*N пар чисел. Для каждой итерации этого перебора, разные алгоритмы ещё запускали один цикл или два вложенных цикла (по спискам простых делителей), но особой разницы не было. Если мы считаем P(100000), то итераций будет 10 миллиардов и на моём компьютере всё это считается примерно 5 минут.

wrest в сообщении #1726201 писал(а):

Вот код который считает очень быстро, код очень простой, одна строчка на pari/gp:

Как-то уж очень просто. Как я понимаю, вы с вашими высокоуровневыми языками программирования можете найти готовую библиотеку для чего угодно, а я привык изобретать велосипеды со своим Delphi. И вдруг я когда-то довелосипедируюсь до того, что придумаю что-то новое, чего в ваших библиотеках нет?

[Dmitriy40]

B3LYP в сообщении #1726231 писал(а):

лимитирующей стадией является перебор N*N пар чисел.

Так вот этого вот перебора и не нужно если знаем результат для N-1, достаточно перебора только N чисел (или одного вычисления функции Эйлера, что ещё быстрее).
Если не знаем, то плюс перебор всех чисел до N.
Но никаких внутренних циклов (ни одного ни двух) не надо.

[wrest]

B3LYP в сообщении #1726231 писал(а):

И вдруг я когда-то довелосипедируюсь до того, что придумаю что-то новое, чего в ваших библиотеках нет?

Непременно!
Но функцию Эйлера можно иногда и в уме вычислить, не то что в билиотеке или на дельфи
Например $\varphi(1000)=1000*(1-1/2)(1-1/5)=1000\cdot 1/2 \cdot 4/5 =400$ - чисел меньших 1000 взаимно просты с ним

-- добавлено через 9 минут --

B3LYP в сообщении #1726231 писал(а):

но это ничего не изменило, поскольку лимитирующей стадией является перебор N*N пар чисел.

Ну так если пара скажем (1000,1001) взаимно проста, то и пара (1001,1000) -- тоже. Зачем же перебирать обе?

[wrest]

B3LYP в сообщении #1726231 писал(а):

Если мы считаем P(100000), то итераций будет 10 миллиардов и на моём компьютере всё это считается примерно 5 минут.

Насчёт Delphi не знаю, а на Си без всяких библиотечных функций, то есть с честным решетом, P(10^5) на планшете считается за 0,03с. Потому что сложность должна быть не O(n^2), а окололинейная, т.е. в примерно n раз (в 10^5 в этом случае) быстрее.