Вероятность остатков.

[dreamkiller]

Sonic86 в сообщении #623058 писал(а):

Напишите, пожалуйста, попытки решения явно, я Вам подскажу. Задача очень хорошая А кратко я Вам написал уже: сначала выпишите формулу для $N_n-N_{n-1}$ явно, а потом делайте тривиальные оценки.
Или колитесь, откуда задача тогда кусок решения выпишу.

Точного источника задачи не знаю, давал преподаватель.
$N_n-N_{n-1} =[n/2]+ 2n \sum_{q=1}^{[n/2]} (\frac {1}{2q} - \frac {1}{2q+1})$, если я правильно понял.

[Sonic86]

dreamkiller в сообщении #623114 писал(а):

$N_n-N_{n-1} =[n/2]+ 2n \sum_{q=1}^{[n/2]} (\frac {1}{2q} - \frac {1}{2q+1})$, если я правильно понял.

Ну только надо писать либо $\approx$ вместо $=$, либо выписывать погрешность $O(...)$.
Ну все Чему равна сумма?
И потом из рекуррентного соотношения ищем $N_n$ с точностью до $O(...)$

[dreamkiller]

Sonic86 в сообщении #623182 писал(а):

dreamkiller в сообщении #623114 писал(а):

$N_n-N_{n-1} =[n/2]+ 2n \sum_{q=1}^{[n/2]} (\frac {1}{2q} - \frac {1}{2q+1})$, если я правильно понял.

Ну только надо писать либо $approx$ вместо $=$, либо выписывать погрешность $O(...)$.
Ну все Чему равна сумма?
И потом из рекуррентного соотношения ищем $N_n$ с точностью до $O(...)$

Все равно не понимаю, как получить $5/4 - \ln2$. У меня почему-то получается . Что $N_n \approx \frac{n(n-1)}{4} - n(n+1)\ln 2$

[Sonic86]

dreamkiller в сообщении #623188 писал(а):

Все равно не понимаю, как получить $5/4 - \ln2$. У меня почему-то получается . Что $N_n \approx \frac{n(n-1)}{4} - n(n+1)\ln 2$

Вы уже все нашли, воспользуйтесь теперь классическим определением вероятности. Здесь $N_n$ - благоприятствующее число случаев.
И, кстати, в строгом доказательстве соотношения типа $\approx$ неприемлемы - лучше переписать с использованием $O(...)$.

[dreamkiller]

Всего случаев $n^2$. Но тогда $ \frac{N_n}{n^2} \approx 1/4 - \ln 2$, где я теряю единицу?

[Sonic86]

dreamkiller в сообщении #623267 писал(а):

где я теряю единицу?

А! Понял. Она теряется в ряде для $\ln 2$ (в нем нет первого члена)

[dreamkiller]

Sonic86 в сообщении #623274 писал(а):

dreamkiller в сообщении #623267 писал(а):

где я теряю единицу?

А! Понял. Она теряется в ряде для $\ln 2$ (в нем нет первого члена)

Действительно. Тогда все сходится. Всем спасибо за помощь(В особенности Sonic86).

[nnosipov]

dreamkiller в сообщении #623114 писал(а):

Точного источника задачи не знаю, давал преподаватель.

"На его месте должен был быть я" (с) Извиняюсь за некропостинг, но не смог пройти мимо (тоже предлагаю своим студентам эту задачу). Касательно первоисточника и точной формулировки задачи:

von zur Gathen & Gerhard in Modern Computer Algebra писал(а):

The fact that two random integers are coprime with probability $6/\pi^2$ is a theorem of Dirichlet (1849). Dirichlet also proves the fact, surprising at first sight, that for fixed $a$ in a division the remainder $r=a \bmod{b}$, with $0<r<b$, is more likely to be smaller than $b/2$ than larger: If $p_a$ denotes the probability for the former, where $1<b<a$ is chosen uniformly at random, then $p_a$ is asymptotically $2-\ln{4} \approx 61{.}37\%$.

-- Ср июл 24, 2019 01:23:43 --

gris в сообщении #620646 писал(а):

Или зафиксировать первое число, а второе считать не большим его, выбираемым равновероятно. Тогда вероятность будет зависеть от первого числа.

Вот прям как у классика :)