Делимость

[Руст]

Предлагаю задачи от участников Mathlinks. Недавно меня буквально забрасывали задачами, пока не перестал отвечать.

Determine all $n\in\mathbb{N}$ such that $\left \lfloor{\frac{n}{k}}\right \rfloor$ divides n for $1\le k\le n.$

Determine all $n\in\mathbb{N}$ such that $\left \lceil{\frac{n}{k}}\right \rceil$ divides n for $1\le k\le n.$

[Sonic86]

Руст в сообщении #824805 писал(а):

Determine all $n\in\mathbb{N}$ such that $\left \lfloor{\frac{n}{k}}\right \rfloor$ divides n for $1\le k\le n.$

Заметим, что если $n\geqslant D^2$, то для любого $d\leqslant D$ верно $\lfloor\frac{n}{\lfloor\frac{n}{d}\rfloor}\rfloor=d$. Тогда из $n\geqslant D^2$ следует $\Psi(D)=\operatorname{lcm} \{1,2,...,D\} \mid n$. Последняя растет очень примерно как $e^D$, что при достаточно большом $D$ больше, чем $D^2$. В результате по индукции можно получить, что $n$ не может быть достаточно большим, только нужно пользоваться точными оценками, а их получить - проблема, хотя больше техническая.

-- Пн фев 10, 2014 17:59:11 --

Хотя можно забить на точные оценки и делать грубо.
Например, $2^{[\log_3 D]}3^{[\log_2 D]}\mid \operatorname{lcm}\{1,2,...,D\}$,
$2^{[\log_2 D]}3^{[\log_3 D]}5^{[\log_5 D]}>\frac{D^3}{30}>D^2$ уже при $D>30$. Остается перебрать случай $n\leqslant 30^2$ (хотя на самом деле можно до $5^2$ проверять).

[Руст]

$n$ должно делиться на $lcm(1,2,...,D), D=[\sqrt{D}]$.
$D=1$ решения $n=1,2,3$.
$D=2$ решения $n=4,6,8$,
$D=3$ решение $n=12$ (18>(3+1)*(3+1)),
$D=4$ решение $n=24$.
Если $D\ge 5$ то $lcm(1,2,...,D)\ge (D+1)^2$. Для 5, 6 $60>7^2$. При $D=7$ выполняется даже $lcm(1,2....,D)\ge 4(D+1)^2$.
Так как между D и 2D всегда есть простое ($D\ge 7$) за счет чего $lcm$ вырастит как минимум в $D+1>4$ раз всегда будет $lcm>(D+1)^2, D>4$.

Второе условие является дополнительным к первому, а именно дополнительно делимость на $[\sqrt n]+1$.
Поэтому решениями остаются только $n=1,2,4,6,12$.