Неравенство про кол-во делителей натурального числа

[m_kristy]

Пусть $k$– количество делителей натурального числа $n$. Докажите, что $k^2<4n$.
Решение:
1) Пусть $n$ – не полный квадрат.
Кол-во всех делителей числа $n$, которые меньше $\sqrt{n}$ равно $\frac{k}{2}$. Следовательно, $\frac{k}{2}\leqslant n_{\frac{k}{2}}<\sqrt{n}$.
$k^2<4n$.
2) Пусть $n$ – полный квадрат.
Кол-во всех делителей числа $n$, которые не превосходят $\sqrt{n}$ равно $\frac{k+1}{2}$. Следовательно, $\frac{k+1}{2}\leqslant n_{\frac{k+1}{2}}\leqslant\sqrt{n}$.
$k^2<k^2+2k+1\leqslant 4n$,
$k^2<4n$.

Проверьте пожалуйста. Не сильно перемудрила?
Можно ли решить задачку, не рассматривая по отдельности случаи полного квадрата и не полного квадрата?

[Sonic86]

m_kristy в сообщении #1088198 писал(а):

Можно ли решить задачку, не рассматривая по отдельности случаи полного квадрата и не полного квадрата?

Можно сразу записать неравенство $\frac{k+1}{2}\leqslant n_{\frac{k+1}{2}}\leqslant\sqrt{n}$ и сказать, что единица может
получиться от того, что $n$ м.б. квадратом. И разные случаи не рассматривать.

m_kristy в сообщении #1088198 писал(а):

Проверьте пожалуйста. Не сильно перемудрила?

Все хорошо. В зависимости от требований можно еще объяснить, как число делителей $\leqslant\sqrt{n}$ связано с числом всех делителей $n$.

[Shadow]

Найдите все натуральные $n$, такие, что $\tau^2(n)>n$
$\tau(n)$ - количество натуральных делителей $n$

[m_kristy]

Shadow, и как это найти?

[Shadow]

Ну, их немало - порядка тридцати. Воспользоватся мультипликативности функции числа делителей, перебрать степеней двойки, тройки....
Вашу задачу можно усилить, $k^2 \le 3n$, причем равенство достигается только при $n=12$

[Sonic86]

(про усиление)

Shadow в сообщении #1088426 писал(а):

Вашу задачу можно усилить, $k^2 \le 3n$, причем равенство достигается только при $n=12$

Если уж охота усиливать, то этому усилению есть общеизвестный предел:
https://ru.wikipedia.org/wiki/%D0%A4%D1 ... 1.82.D0.B0

[m_kristy]

Shadow в сообщении #1088231 писал(а):

Найдите все натуральные $n$, такие, что $\tau^2(n)>n$
$\tau(n)$ - количество натуральных делителей $n$

Попробуем построить функцию $\tau$ числа делителей.
$\tau(2^k)=1+k,$
$\tau(2^k3)=2(1+k),$
$\tau(2^k3^2)=3(1+k),$
$\tau(2^k3^m)=(1+k)(1+m),$
$\tau(2^k3^m5^l)=(1+k)(1+m)(1+l),$
$\tau(q_1^{k_1}q_2^{k_2}...q_n^{k_n})=\prod\limits_{i=1}^n (1+k_i),$ где $q_j$ – простые числа (неповторяющиеся).
Докажем последнюю формулу по индукции:
1) $\tau(q^k)=(1+k),$ где $q$ – простое;
2) Пусть равенство $\tau(q_1^{k_1}q_2^{k_2}...q_n^{k_n})=\prod\limits_{i=1}^n (1+k_i)$ – верно;
3) $\tau(q_1^{k_1}q_2^{k_2}...q_n^{k_n}q_{n+1}^{k_{n+1}})=\tau(q_1^{k_1}q_2^{k_2}...q_n^{k_n})(1+k_{n+1})=\\=(1+k_{n+1})\prod\limits_{i=1}^n (1+k_i)=\prod\limits_{i=1}^{n+1} (1+k_i).$

Найдем все натуральные $a$, такие, что $\tau^2(a)>a.$
Разложим $a$ на простые сомножители и приведем разложение к каноническому виду: $a=q_1^{k_1}q_2^{k_2}...q_n^{k_n}.$
$\tau ^2(q_1^{k_1}q_2^{k_2}...q_n^{k_n})>q_1^{k_1}q_2^{k_2}...q_n^{k_n},$
$(\prod\limits_{i=1}^n (1+k_i))^2>q_1^{k_1}q_2^{k_2}...q_n^{k_n},$
$\prod\limits_{i=1}^n (1+k_i)^2>q_1^{k_1}q_2^{k_2}...q_n^{k_n}$.
Перебор:
$\sum\limits_{i=1}^n k_i=1:$ $\{2; 3\}$;
$\sum\limits_{i=1}^n k_i=2:$ $\{4; 6; 10; 14; 15\}$;
$\sum\limits_{i=1}^n k_i=3:$ $\{8; 12; 18; 20; 28; 30; 42\}$;
$\sum\limits_{i=1}^n k_i=4:$ $\{16; 24; 36; 40; 54; 56; 60; 84; 90; 126; 132; 140; 210\}$;
$\sum\limits_{i=1}^n k_i=5:$ $\{32; 48; 72; 80; 108; 120; 168; 180; 252; 300; 420\}$;
и т.д. (дальше сил не хватило)
Найденных чисел уже 38 и их еще не мало.
Как эта задачка поможет при решении моей задачки?

[Sonic86]

m_kristy в сообщении #1088551 писал(а):

ак эта задачка поможет при решении моей задачки?

Эту задачу для решения Вашей решать не нужно - это из ракетницы по воробьям
Вы же уже все решили, расслабьтесь.
А Shadow, видимо, просто хочет развить тему - предлагает решить аналогичную задачу посложнее.

[m_kristy]

Sonic86, да я понимаю, что я решила свою задачку. Просто интересно что и как.
Кстати, функцию числа делителей правильно получила?

[Sonic86]

m_kristy в сообщении #1088578 писал(а):

Кстати, функцию числа делителей правильно получила?

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

[Shadow]

m_kristy в сообщении #1088551 писал(а):

Найденных чисел уже 38 и их еще не мало.

Всего их 52 - слишком много для ручного перебора. Когда писал свое первое сообщение знал, что их число ограничено (наиболшее простое - 11, наибольшая степен двойки - 6), но не знал, что их так много будет.

m_kristy в сообщении #1088551 писал(а):

Как эта задачка поможет при решении моей задачки?

Никак, Вы ее решили еще в стартовом сообщении. Просто это другой подход, откуда например сразу видно, что $\dfrac{\tau^2(n)}{n} \le 3$
Частное больше 1 только для степеней двойки (до пятой) - максимальное -во второй, и три в первой, во всех остальных случаях частное меньше (либо равно ) 1.

$\max \dfrac{\tau^2(n)}{n}=\dfrac{\tau^2(2^2)}{2^2}\cdot \dfrac{\tau^2(3^1)}{3^1}=\dfrac{9}{4}\cdot \dfrac{4}{3}=3$