Найдите количество натуральных делителей числа N = 10^40 (10 в степени 40), не представимых в виде m^n (m в степени n), где m и n натуральные числа, причем n > 1.

задан 28 Апр '17 7:55

По источнику http://pk.math.msu.ru/sites/default/files/variants/Lomonosov/Maths/lomonosov-math-9-2013.pdf
решение задачи 981 (задача 2). У меня получилось 985. Несколько раз проверил. Вроде все варианты рассмотрел.

(28 Апр '17 7:57) Rams

У меня тоже 981 получилось. По каким формулам Вы считали?

(28 Апр '17 9:42) falcao

Делители 2^p·5^r (0<=p<=40, 0<=r<=40), всего 41·41=1681. Квадраты: p=2·k; r=2·k (k=0,1,...,20), 21·21=441.

Кубы: 14·14=196. И кубы, и квадраты (p=6·k; n=6·k), 7·7=49. Остается: 196–49=147.

Пятые степени: 9·9=81. Из них квадраты p=10·k; r=10·k (k=0,1,...,4), всего 25. Кубы: p=15·k; r=15·k (k=0,1,2); таких 9. Остается 81–(25+9)+1=48 (для p=0; r=0, и в квадратах, и в кубах есть число N=1. Поэтому добавил единицу, чтобы два раза не отнять одно и то же число). Продолжение в следующих комментариях.

(28 Апр '17 13:49) Rams

Седьмые степени: 6·6=36. Из них квадраты: p=14·k; r=14·k (k=0,1,2), 3·3=9. Кубы: p=21·k; r=21·k (k=0,1), 2·2=4. Пятые степени p=35·k; r=35·k, 2·2=4. Остается 36–(9+4+4)+2=21.

N=m^11. Всего 16. Квадраты 4, кубы 4. Остается: 16–8+1=9.

N=m^13. Всего 16. Квадраты 4, кубы 4. Остается: 16–8+1=9.

N=m^17. Всего 3·3=9. Квадраты 4. Остается 9–4=5.

N=m^19. Всего 3·3=9. Квадраты 4. Остается 9–4=5.

N=m^23. Всего: 4. N=m^29. Всего: 4 .

N=m^31. Всего: 4. N=m^37. Всего: 4 .

Из всего остается:

1681–(441+147+48+21+9+9+5+5+4+4+4+4)+4=984

(Последняя четверка, для последних 4-х случаев (для N=1)).

(28 Апр '17 13:50) Rams

@Rams: при таком способе подсчёта пропускается случай, когда число является квадратом, кубом и пятой степенью. Далее, если 1 мы везде формально учитываем, то надо учитывать все кратные пересечения (она является и 7-й степенью, и 11-й, и прочее). Такой учёт очень сложен, и 1 надо просто исключить изначально. Я сейчас приведу два способа решения.

(28 Апр '17 14:54) falcao
10|600 символов нужно символов осталось
0

Все делители числа $%10^{40}$% имеют вид $%2^m5^n$%, где $%0\le m,n\le40$%. Нас интересует количество упорядоченных пар $%(m,n)$%, для которых $%НОД(m,n)=1$%. Пара $%(0,0)$% не входит, пары $%(1,0)$% и $%(0,1)$% входят. Остаётся подсчитать число пар для случая $%1\le m,n\le40$%. Рассмотрим два способа.

Если $%m=n$%, то пара всего одна: $%(1,1)$%. Положим $%m < n$%, учитывая, что столько же пар будет с условием $%m > n$%. Количество значений $%m$%, подходящих для данного $%n$%, равно значению функции Эйлера $%\varphi(n)$%. Такие значения нетрудно найти и сложить между собой: $%\varphi(2)+\varphi(3)+\cdots+\varphi(40)=489$%. Умножаем на 2, и прибавляем 3 для трёх особо учитываемых пар. Итого $%981$%.

Второй способ: две пары учитываем отдельно в самом начале. Далее рассматриваем $%40^2$% пар для случая $%1\le m,n\le40$%. Из них надо исключить те пары, где имеется общий простой делитель. Для значений $%p=2,3,5,...,37$% вычитаем сумму чисел вида $%[\frac{40}p]^2$%. Это $%20^2+13^2+8^2+5^2+3^2+3^2+2^2+2^2+1^2+1^2+1^2+1^2=688$%. В соответствии с формулой включений и исключений, нужно учесть попарные пересечения, то есть количество пар, для которых оба числа делятся на $%pq$% при простых $%p < q$%. Ясно, что при $%p=2$% нужно учитывать $%q=3,5,...,19$%, при $%p=3$% будет $%q=5,7,...,13$%, при $%p=5$% получится $%q=7$%. Для каждой такой пары рассматриваем $%[\frac{40}{pq}]^2$%. Имеем $%(6^2+4^2+2^2+1^2+1^2+1^2+1^2)+(2^2+1^2+1^2+1^2)+1^2=68$%. Наконец, есть одно трёхкратное пересечение для случая делимости обоих чисел на $%30=2\cdot3\cdot5=30$%; его тоже учитываем.

Окончательный результат: $%2+1600-688+68-1=981$%.

ссылка

отвечен 28 Апр '17 15:12

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

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

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

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

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

отмечен:

×1,301
×35

задан
28 Апр '17 7:55

показан
1365 раз

обновлен
28 Апр '17 15:12

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

по почте:

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

по RSS:

Ответы

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

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