Сумма делителей 403

[km621]

От нечего делать Вася нашел все трехзначные числа с суммой делителей 403. Сделайте это и Вы.

Ответ получен, но как математически обосновать данный ответ я не знаю.

[gris]

Ну можно начать с посмотреть, какие паттерны:) дают нечётную сумму делителей

[Andrey A]

Да. И на олимпиадную задачу оно никак не тянет, так Васе и передайте.

[Dendr]

Ну... $403=13\cdot31$. А формула суммы делителей через каноническое разложение известна.
Значит, задача сводится к нахождению простых $p_i$ таких, что сумма нескольких первых членов геометрической прогрессии $1+p_i+p_i^2+...$ равна одному из этих трех чисел.
Тут уже перебор, в конце концов. Для меньших двух чисел он проводится даже в уме:
$13=1+3+3^2$
$31=1+2+2^2+2^3+2^4=1+5+5^2$

Для 403 лучше подойти более системно и заметить, что $p=2$ не годится (поскольку 404 - не степень двух), а для остальных случаев максимальная степень должна быть четной, но не превосходить 403. Тройку можно тоже проверить "вручную" и отсеять, а для остальных должно быть верно $1+p+p^2=403$, но это уравнение не имеет натуральных корней.
Поэтому в ответе запишем $3^22^4=144$ и $3^25^2=225$.

На олимпиаду в 21-м веке не тянет, конечно, но для подготовки - почему нет?

[km621]

Andrey A в сообщении #1567034 писал(а):

Да. И на олимпиадную задачу оно никак не тянет, так Васе и передайте.

Это уже к организаторам отборочного тура ЮМШ.

-- 21.10.2022, 06:34 --

Dendr в сообщении #1567039 писал(а):

Ну... $403=13\cdot31$. А формула суммы делителей через каноническое разложение известна.
Значит, задача сводится к нахождению простых $p_i$ таких, что сумма нескольких первых членов геометрической прогрессии $1+p_i+p_i^2+...$ равна одному из этих трех чисел.
Тут уже перебор, в конце концов. Для меньших двух чисел он проводится даже в уме:
$13=1+3+3^2$
$31=1+2+2^2+2^3+2^4=1+5+5^2$

Для 403 лучше подойти более системно и заметить, что $p=2$ не годится (поскольку 404 - не степень двух), а для остальных случаев максимальная степень должна быть четной, но не превосходить 403. Тройку можно тоже проверить "вручную" и отсеять, а для остальных должно быть верно $1+p+p^2=403$, но это уравнение не имеет натуральных корней.
Поэтому в ответе запишем $3^22^4=144$ и $3^25^2=225$.

На олимпиаду в 21-м веке не тянет, конечно, но для подготовки - почему нет?

Спасибо за объяснение..совсем вылетело это свойство из головы.

[Andrey A]

km621 в сообщении #1567247 писал(а):

... совсем вылетело это свойство из головы.

И то что $m<\sigma (m).$ При том, что нечетное значение $\sigma (m)$ возможно только, если $m$ — целый квадрат, или удвоенный целый квадрат (но тогда оно кратно тройке). Насчет школьной олимпиады согласен.