Задача придумана не мной, но мне показалась интересной и достойной освещения на форуме.

Максимально составным числом называется натуральное число $%m,$% число делителей у которого больше, чем у любого числа, меньшего $%m.$%

Задача. Найти наибольшее максимально составное число вида $%n!$%.

задан 28 Июн '17 19:03

изменен 29 Июн '17 1:42

1

Термин "сверхсоставное число" более употребителен. См. также https://ru.wikipedia.org/wiki/Сверхсоставное_число

(28 Июн '17 19:13) EdwardTurJ

@EdwardTurJ, спасибо. Пытался вспомнить этот термин, а Википедия здесь заблокирована.

(28 Июн '17 19:19) Urt
1

@Urt: а через прокси этот запрет не обходится? А то у нас тоже много чего заблокировано (почти что "близнецы-братья" :)), но зайти можно в принципе на какой угодно сайт.

(29 Июн '17 0:01) falcao
1

@falcao: Извиняюсь, что "не в теме", а почему и где Википедия заблокирована?

(29 Июн '17 0:16) Роман83
2

@falcao, спасибо за совет! 1) Узнал о такой возможности и получил первый опыт. 2) Воспользовался ссылкой от EdwardTurJ - весьма интересно.

@Роман83, для информации - В настоящее время Википедия в целом на всех языках заблокирована в Анталье ("Я не говорю за всю Одессу...").

(29 Июн '17 0:25) Urt
1

@Urt: Вы в Анталье живете или на курорте?

(29 Июн '17 0:43) Роман83

@Urt: это что же тогда получается -- выходит, что туристы, которые туда приезжают и "юзают" wi-fi, тоже не могут получить справку по каким-то вопросам? Никогда бы не подумал на такое!

(29 Июн '17 0:44) falcao
1

@Urt: по поводу условия: правильно ли я понимаю, что надо найти ВСЕ факториалы с таким свойством? А то с отдельными примерами трудностей вроде как нет.

(29 Июн '17 0:48) falcao

@Роман83, мы сюда приезжаем часто и надолго. На работе только информирую (такие условия и зарплата :)).

@falcao, я тоже был крайне удивлен этой ситуацией. Раньше (по крайней мере, в апреле) все было нормально. Возможно, временно.

По поводу условия - да, это так: ВСЕ факториалы. Думаю, что Ваши "отдельные примеры" как раз и есть все примеры. Подправил амеченную Вами неточность в условии.

(29 Июн '17 0:58) Urt

@Urt: постановка вопроса теперь понятна, и есть некий общий план доказательства, но сейчас я уже не успеваю ничего оформить. Надо как можно быстрее отходить ко сну: обычно я сплю когда придётся, но сейчас днём это делать стало невозможно из-за шума в соседней квартире (там ремонт -- со всеми вытекающими).

(29 Июн '17 2:33) falcao

@falcao, даже представить не мог, что так быстро можно найти идею решения этой задачи. Чувствовал бы себя не комфортно, если бы пошел спать, загрузив уважаемых людей задачкой, решение которой лишь увидел и осознал. Надеюсь, что этот коммент Вы прочтете уже утром. Хорошего Вам дня!!! К сожалению, ремонт - это надолго, нужно уезжать...

(29 Июн '17 2:59) Urt
показано 5 из 11 показать еще 6
10|600 символов нужно символов осталось
3

Для начала проиллюстрируем на примере основную идею. Из таблицы, приведённой здесь, видно, что при $%1\le n\le7$% все числа вида $%n!$% являются сверхсоставными ("максимально составными"). Рассмотрим число $%8!$% и поймём, по какой причине оно таковым не является. Оно делится на $%2^7$%, и тогда можно его уменьшить, разделив на 16 и домножив на новое простое число 11 (или на 13). Количество делителей при этом не уменьшится, согласно известной формуле, в которой перемножаются показатели степеней в каноническом разложении, увеличенные на 1. Показатель 7 давал "вклад" 8 в это произведение, а теперь он стал равен 3, и появился показатель 1 при 11. Произведение осталось равно $%(3+1)(1+1)=8$%, то есть такое же число делителей наблюдается у меньшего числа, и потому $%8!$% не будет сверхсоставным.

Покажем, что при $%n\ge8$% такое явление будет наблюдаться всегда. Обозначим через $%\nu-1$% показатель степени при двойке в каноническом разложении $%n!$%. Попытаемся разделить $%n!$% на число вида $%2^k$%, и домножить на наименьшее простое число $%p$%, которое превосходит $%n$%. Запишем условие, при котором произведение заведомо окажется меньше факториала. Для этого нужно неравенство $%2^k > p$%, но число $%p$%, согласно Постулату Бертрана, меньше $%2n$%. Поэтому нам достаточно иметь $%2^k\ge2n$%, беря наименьшее $%k$% с таким свойством. При этом должна иметь место делимость, то есть $%k\le\nu-1$%, что будет верно автоматически, как мы увидим из дальнейшего.

Теперь в системе показателей у нас $%\nu-1$% уменьшится на $%k$%. Появится новый простой делитель с показателем 1, и тогда вместо $%\nu$% мы получим в произведении $%2(\nu-k)$%. Мы хотим, чтобы у меньшего числа делителей было как минимум столько же, что означает $%2(\nu-k)\ge\nu$%, то есть $%\nu\ge2k$%, что мы запишем как $%2^{\nu}\ge4^k$%.

Ввиду того, что $%k=\lceil\log2n\rceil < \log2n+1$%, мы имеем $%4^k < 16n^2$%, и тогда нам достаточно неравенства $%2^{\nu-1}\ge8n^2$%. Для $%n=15$% мы имеем $%\nu-1=11$%, и неравенство имеет место; то же верно для $%n=14$%. Далее можно доказать по индукции, что для всех нечётных $%n\ge15$% неравенство выполняется. В самом деле, при увеличении $%n$% на $%2$%, левая часть, то есть степень двойки, на которую делится факториал, увеличивается как минимум вдвое. Правая же часть умножается на $%(\frac{n+2}n)^2$%, что заведомо меньше 2, так как $%\frac2n < \sqrt2-1$%.

Таким образом, остаётся отдельно проверить значения $%9\le n\le13$%. При $%n < 13$% мы можем добавить простой множитель 13, деля факториал на 16, что было возможно уже при $%n=8$%. Для $%n=13$% показатель степени двойки в разложении факториала равен 10. Добавляя простой множитель 17, мы делим факториал на 32, и число уменьшается. Количество делителей при этом становится больше, так как вместо множителя 11 в произведении получится $%(5+1)(1+1)=12$%.

ссылка

отвечен 29 Июн '17 14:27

@falcao, это как раз из тех решений, которые восхищают и делают сами задачи красивыми!!! Спасибо!

(29 Июн '17 15:11) Urt

@Urt: а у Вас в решении тоже использовался Постулат Бертрана?

(29 Июн '17 15:40) falcao

@falcao, в имеющемся у меня решении от JimmyK4542 Постулат Бертрана не использовался. В нем показано, что при $%n\ge 20$% число $%13n!/16$% имеет не меньше делителей, чем n! и для $%8 \le n\le 19$% осуществляется проверка в соответствии со списком, содержащим 1000 первых сверхсоставных чисел.

(29 Июн '17 16:14) Urt
1

@Urt: да, в таком виде оно выглядит попроще, хотя я сразу же заметил идею с Постулатом Бертрана, наблюдая случай 8!. Остальное -- это уже чисто технические проверки.

По-моему, лучше брать не 13/16, а 7/8. Тогда оно работает при n>=10.

(29 Июн '17 19:13) falcao
1

@falcao, я тоже подумал, что лучше использовать коэффициент 7/8. При этом получается неравенство $%e_1\ge 3e_4+5$% (где $%e_1, e_4$% - степень двойки и семерки в $%n!$%), которое работает при $%n\ge 10$%. Случаи $%n= 8$% и $%n=9$% легко проверить.

(29 Июн '17 21:12) Urt

@Urt: да, и я тоже к такому заключению в итоге пришёл!

(29 Июн '17 22:57) falcao

@falcao, следуя решению от JimmyK4542, я поначалу также использовал строгое неравенство, что в общем-то некорректно. Это приводило к необходимости дополнительных проверок и, по-видимому, послужило причиной выбора автором коэффициента 13/16. После Вашего предыдущего комментария я перепроверил вариант с коэффициентом 7/8 и убедился в его работоспособности при $%n \ge 10$%.

(29 Июн '17 23:17) Urt
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×879
×370

задан
28 Июн '17 19:03

показан
575 раз

обновлен
29 Июн '17 23:18

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

по почте:

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

по RSS:

Ответы

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

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