Пусть $%n>1$% - натуральное число, $%d(n)$% - наименьший делитель $%n$%, отличный от 1, $%D(n)$% - наибольший делитель $%n$%, отличный от $%n$%, $%\tau(n)$% - количество натуральных делителей числа $%n$%.

а) Найдите все такие $%n$%, что $%n=d(n)+\tau(n)$%

б) Найдите все такие $%n$%, что $%n=D(n)+\tau(n)$%

в) Найдите все такие $%n$%, что $%n=D(n)+d(n)+\tau(n)$%

задан 16 Апр 16:28

1

пока удалось придумать только отдельные примеры а) 6; б) 8;12; в) 9

(16 Апр 20:08) Lyudmyla

@Lyudmyla, там совсем несложно, это с олимпиады для 6 или 7 класса, точно не помню.

(16 Апр 23:49) Казвертеночка
10|600 символов нужно символов осталось
3

Пусть $%n=p_1^{k_1}\ldots p_r^{k_r}$% -- каноническое разложение. Тогда $%d(n)=p_1$%, $%D(n)=n/p_1$%, $%\tau(n)=(k_1+1)\ldots(k_r+1)$%.

а) Здесь $%n-p_1$% -- число делителей $%n$%. Ясно, что $%n$% не простое. Числа от $%2$% до $%p_1-1$% не делят $%n$%, и потому среди остальных чисел имеется не более двух, которые не делят $%n$%. Понятно, что $%n-1$% делит $%n$% только при $%n=2$%, но это значение не подходит. Далее, $%n-2$% делит $%n$% только если $%2$% делится на $%n-2$%, то есть $%n=3$% или $%n=4$%. Ни то, ни другое не подходит. Случай, когда $%n$% делится на $%n-3$%, даёт новое значение $%n=6$%, и оно подходит. При $%n\ge8$% у нас появляется уже слишком много "не делителей": к ранее рассмотренным $%p_1-2$%, добавились три новых, так как $%p_1-1 < n-3$%.

Таким образом, в этом пункте есть только $%n=6$%.

б) Здесь $%n-D(n)=(p_1-1)p_1^{k_1-1}\ldots p_r^{k_r}=(k_1+1)\ldots(k_r+1)$%. Основная идея в том, что левая часть почти всегда больше правой. Хорошо известно, что $%2^x > x$% для всех чисел, откуда $%p^k\ge2^k\ge k+1$%, причём равенство имеет место только при $%p=2$%, $%k=1$%. Поэтому далее рассматриваем только случай $%(p-1)p^{k-1}\le k+1$%, где $%p=p_1$%, $%k=k_1$%.

Если $%p\ge5$%, то левая часть не меньше $%4\cdot5^{k-1} > 4^k\ge2k+1 > k+1$%. При $%p=3$% левая часть равна $%2\cdot3^{k-1}\ge2^k$%, откуда $%k=1$%. Получается решение $%n=3$%, а других сомножителей тут уже не будет.

Наконец, пусть $%p=2$%. Из $%2^{k-1}\le k+1$% следует $%k=1,2,3$%. При $%k=3$% имеет место равенство, поэтому подходит $%n=8$%, а других сомножителей уже не будет. Если $%k=2$%, то отношение $%p_2^{k_2}\ldots p_r^{k_r}$% к $%(k_2+1)\ldots(k_r+1)$% равно $%\frac32$%. При $%p > 2$% отношение $%p^k/(k+1)$% не меньше $%3^k/(k+1)\ge3/2$%, и равенство имеет место только в одном случае. Здесь получается решение $%n=12$%, и других нет.

Если $%k=1$%, то правая часть уравнения чётна, а левая нечётна. Итого три решения: $%\{3,8,12\}$%.

в) Здесь проще всего проверить несколько чисел в начале, показав при помощи оценок, что других решений нет. Уравнение имеет вид $%\tau(n)=n-p-\frac{n}p$%, где $%p$% -- наименьший простой делитель $%n$%. Понятно, что $%n$% не простое, и тогда $%n\ge p^2$%. Наибольшее значение величины $%p+\frac{n}p$% достигается при $%p=2$%, что видно из характера возрастания/убывания функции $%x+\frac{n}x$%. Отсюда $%\tau(n)\ge\frac{n}2-2$%. С другой стороны, среди чисел от $%\frac{n}3$% до $%n$%, имеется не более трёх делителей $%n$%, откуда $%\tau(n)\le\frac{n}3+2$%. Получается $%n\le24$%, и эти значения проверяются перебором. Подходит только $%n=9$%.

В принципе, эти же соображения подходят и для решения предыдущих пунктов.

ссылка

отвечен 17 Апр 0:32

@falcao, большое спасибо! Там гораздо проще всё, особенно первые два пункта. И даже смекалки не нужно, чисто бухгалтерская задача :)

(17 Апр 1:40) Казвертеночка
1

@Казвертеночка: я сразу стал писать на "чистовик", без "обкатки". Думал, что будет коротко, но по мере написания всё постепенно усложнялось, а менять по принципу "поплыли обратно" (с) я не захотел :)

(17 Апр 2:19) falcao

@falcao, количество делителей натурального числа n не превосходит 2*sqrt(n), наименьший делитель, отличный от 1, не превосходит sqrt(n) (либо, в случае простого числа, равен самому числу, но это здесь не релевантно), а наибольший делитель, отличный от самого числа, не превосходит половины числа. Таким образом, в первом пункте достаточно перебрать от 1 до 9, во втором - от 1 до 16, ну а в третьем - от 1 до 36, это чуть дольше и нуднее, но вполне по силам любителям посчитать в уму :)

(17 Апр 11:24) Казвертеночка
1

@Казвертеночка: у меня в последнем пункте получается оценка сверху 24. Для первых двух пунктов диапазон ещё меньше. Если бы я начал с последнего пункта, то решение было бы короче. А так я немного "перестарался" :)

(17 Апр 18:09) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×512
×98
×19
×3
×1

задан
16 Апр 16:28

показан
46 раз

обновлен
17 Апр 18:09

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

по почте:

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

по RSS:

Ответы

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

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