Вычислить вероятность делимости одного числа на другое

[farewe11]

У нас есть набор натуральных чисел: {1, 2, .. , N}. Из этого набора выбираем 2 числа: a и b.
Найти вероятность того, что a делится на b нацело.

Начинаю решение с того, что диапазон, в котором лежат все делители числа а: {1, 2,.. , a/2}. Вероятность того, что b лежит в этом диапазоне: a/2N.
Но как вычислить вероятность делимости? Про сами числа, их простоту, длину диапазона ничего не сказано..

[venco]

Попробуйте наоборот: для произвольного $b$ сколько есть чисел $a$ делящихся на $b$? Посчитайте сколько всего подходящих пар, и поделите на общее количество пар.

[farewe11]

venco в сообщении #436797 писал(а):

для произвольного $b$ сколько есть чисел $a$ делящихся на $b$?

Таким образом мы найдем вероятность того, что случайное $a$ делится на фиксированное $b$. Похоже, это то, что нужно, спасибо :)

[Хорхе]

Возможно, лыжи не едут, но мне кажется, что тут все далеко не так просто.

[VAL]

Хорхе в сообщении #436830 писал(а):

Возможно, лыжи не едут, но мне кажется, что тут все далеко не так просто.

Это лыжи :)

[venco]

Хорхе в сообщении #436830 писал(а):

Возможно, лыжи не едут, но мне кажется, что тут все далеко не так просто.

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

[nnosipov]

venco в сообщении #436845 писал(а):

Хорхе в сообщении #436830 писал(а):

Возможно, лыжи не едут, но мне кажется, что тут все далеко не так просто.

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

С остаточным членом проблемы будут.

[VAL]

nnosipov в сообщении #436855 писал(а):

venco в сообщении #436845 писал(а):

Хорхе в сообщении #436830 писал(а):

Возможно, лыжи не едут, но мне кажется, что тут все далеко не так просто.

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

С остаточным членом проблемы будут.

А зачем остаточный член, если есть точеная формула? В предположении, что числа различны:

$$\frac{\sum_{i=1}^n(\lfloor\frac ni\rfloor-1)}{C_n^2}$$

Понятно, что это не замкнутая формула, но где написано, что нужна именно замкнутая?

[Хорхе]

Тьху, я почему-то решил, что мы одно и то же несколько раз считаем. Это лыжи, точно.

[nnosipov]

VAL в сообщении #436857 писал(а):

А зачем остаточный член, если есть точеная формула? В предположении, что числа различны:

$$\frac{\sum_{i=1}^n(\lfloor\frac ni\rfloor-1)}{C_n^2}$$

Понятно, что это не замкнутая формула, но где написано, что нужна именно замкнутая?

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

[farewe11]

nnosipov в сообщении #436865 писал(а):

VAL в сообщении #436857 писал(а):

А зачем остаточный член, если есть точеная формула? В предположении, что числа различны:

$$\frac{\sum_{i=1}^n(\lfloor\frac ni\rfloor-1)}{C_n^2}$$

Ого. Уважаемые математики, поясните, пожалуйста, как с помощью суммы вы представили вероятность события? :) Я просто пока не так сильно владею теорвером..

[VAL]

nnosipov в сообщении #436865 писал(а):

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

Раз не грех, вспомните. Можно вслух :)

-- 20 апр 2011, 06:40 --

farewe11 в сообщении #436878 писал(а):

VAL в сообщении #436857 писал(а):

В предположении, что числа различны:

$$\frac{\sum_{i=1}^n(\lfloor\frac ni\rfloor-1)}{C_n^2}$$

Ого. Уважаемые математики, поясните, пожалуйста, как с помощью суммы вы представили вероятность события? :) Я просто пока не так сильно владею теорвером..

В числителе подсчитано число пар различных чисел, в которых одно число кратно другому. В знаменателе - общее число пар.

[nnosipov]

VAL в сообщении #436905 писал(а):

nnosipov в сообщении #436865 писал(а):

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

Раз не грех, вспомните. Можно вслух :)

Проблема делителей Дирихле. Вот первое, что попалось под руку: http://dic.academic.ru/dic.nsf/enc_math ... 0%95%D0%99

[VAL]

nnosipov в сообщении #436915 писал(а):

Проблема делителей Дирихле. Вот первое, что попалось под руку: http://dic.academic.ru/dic.nsf/enc_math ... 0%95%D0%99

Спасибо! Приблизительно это я и предполагал. Но вдруг...