17 непредставимых чисел

[Ktina]

Назовём натуральное число представимым, если его можно представить как в виде суммы простого числа составных чисел, так и в виде суммы составного числа составных чисел, а также в виде суммы простого числа простых чисел и в виде суммы составного числа простых чисел.

В противном случае назовём натуральное число непредставимым.

Докажите, что существует ровно 17 непредставимых чисел.

[gris]

Первое представимое число это $16=5+11=3+3+5+5=8+8=4+4+4+4$ (ПП,ПС, СП,СС). Так как $4$ наименьшее составное, то от $1$ до $15$ все число непредставимы. Ну и $17$ и $19$ тоже из-за формата СС. В других форматах все числа, начиная с $12$ представимы. Вот они 17 непредставимых чисел.
То есть в пределах двадцатки задача решена. Ну а дальше тоже, наверное .
Там тысячи теорем.

[mihaild]

Составное число простых чисел получить всегда можно: если четное, то разбиваем на двойки, если нечетное - то на двойки и одну тройку. Если случайно получилось простое число, то переразбиваем три двойки на две тройки. Аналогично с составным числом составных: разбиваем на четверки, останется число от $0$ до $3$, если не $0$, то приклеиваем нужное число четверок к остатку, чтобы получилось $9$, $10$ или $15$. С простым числом составнях похоже: разбиваем на составное число составных, из которых все, кроме одного - четверки, дальше склеиваем четверки, пока не получим простое число.
Для простого числа простых надо думать, либо знать какой-то результат, которого я не знаю (ну или поверить в гипотезу Гольдбаха).

[Ktina]

mihaild в сообщении #1292062 писал(а):

Для простого числа простых надо думать, либо знать какой-то результат, которого я не знаю (ну или поверить в гипотезу Гольдбаха).

Там попроще...

[mihaild]

Ну да, можно разбить на двойки и одну-две тройки, потом переразбивать либо семерки двоек в пару семерок, либо тройки двоек в пару троек - получается разбиение на от чуть меньше чем $\frac{n}{2}$ слагаемых до на чуть больше чем $\frac{n}{7}$, а простое число в этом промежутке найдется.

[Ktina]

mihaild
Можно даже ещё проще...

[urod]

Если $p$ простое, то все числа от $2p$ до $5p$ включительно представимы в виде суммы простого числа простых чисел. Доказательство: если $2p\le x\le 3p$, то возьмём сумму $p$ двоек и будем заменять двойки на тройки, пока не получим $x$. Если $3p<x\le 5p$ включительно, то возьмём сумму $p$ троек и будем заменять их на пятёрки, пока не получим $x$ или $x+1$. Если получили $x+1$ и осталась хоть одна тройка, заменим её на двойку. Если получили $x+1$ и остались одни пятёрки, заменим две из них на 2 и 7.

Теперь докажем, что любое натуральное от 15 представимо в виде суммы простого числа простых чисел. Пусть $x\ge 15$, тогда обозначим $y=x/4$, округлённое вниз. По постулату Бертрана, в интервале $[y,2y]$ есть хотя бы одно простое число. Обозначим его $p$. Нам достаточно доказать, что $2p\le x\le 5p$. В самом деле, $2p\le 2(2y)=4y\le 4(x/4)=x$, a $5p\ge 5y\ge 5(x/4-3/4)=x+x/4-15/4=x+(x-15)/4\ge x$

Кроме того, поскольку 2 и 3 простые, то все числа от 4 до 10, а также от 6 до 15, представимы как сумма простого числа простых чисел.

Значит, все числа от 4 представимы как сумма простого числа простых чисел.