задан 11 Июн 21:32

10|600 символов нужно символов осталось
1

Пусть 1<=i<=j<=40. При фиксированном j число i, взаимно простое c j, принимает ф(j) значений, где ф -- функция Эйлера. Поэтому количество пар таких чисел будет равно сумме ф(1)+ф(2)+...+ф(40). Значения функции Эйлера вычисляются несложно, и значение суммы можно найти вручную. Оно равно 490.

Ответ на вопрос о вероятности зависит от того, что понимать под двумя взятыми наугад числами. Будем считать, что первое число выбирается случайно, и вероятность выбора каждого числа равна 1/40. Для второго числа независимо делаем то же самое, то есть числа могут совпадать. Тогда упорядоченных пар (i,j) с условием НОД(i,j)=1 будет 2*490-1=979. Действительно, для i<=j и i>=j будет по 490 случаев, и одну пару с условием i=j=1 посчитали дважды. Вероятность будет равна 979/1600, что примерно равно 0,6118. Можно отметить, что асимптотическая вероятность равна 6/п^2, и это довольно близко значение.

Есть также способ вычисления сумм вида ф(1)+...+ф(N) при помощи функции Мёбиуса, но я не думаю, что это будет проще.

ссылка

отвечен 11 Июн 22:28

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,091

задан
11 Июн 21:32

показан
26 раз

обновлен
11 Июн 22:28

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru