сложность записи натурального числа с помощью (1,*,+)

[maxal]

Для натурального числа $n$ положим $a_n$ равным минимальному натуральному числу такому, что существует арифметическая формула, содержащая $a_n$ единиц, а также скобки и операции сложения и умножения, значение которой равно $n$.

Нетрудно видеть, что $a_1 = 1$ и для $n>1$

$$a_n = \min\left\{ \min_{1\leq m\leq n-1} a_m + a_{n-m}, \min_{d|n\atop 1<d<n} a_d + a_{n/d}\right\}.$$

Докажите, что для любого $n>1$,

$$\min_{1\leq m\leq n-1} a_m + a_{n-m} = a_1 + a_{n-1} = 1 + a_{n-1}$$

и, таким образом, общая формула упрощается до:

$$a_n = \min\left\{1 + a_{n-1}, \min_{d|n\atop 1<d<n} a_d + a_{n/d}\right\}.$$

[Kid Kool]

Пусть слева имеется m единиц, и скобки расставлены так, что число равно $a_m$, а справа - (n-m) единиц, и число равно $a_{n-m}$. Уберем слева самую левую единицу. Тогда левое число уменьшится как минимум на 1 (доказательство - индукция по максимальной глубине вложенности скобочной структуры). Теперь поставим знак "+" между левым и правым числом. Полученное число окажется не больше $a_m+a_{n-m}-1$ и имеет (n-1)-у единицу. Значит, $a_{n-1} \leqslant a_m+a_{n-m}-1$, что и требовалось доказать.

[maxal]

Kid Kool писал(а):

Пусть слева имеется m единиц, и скобки расставлены так, что число равно $a_m$, а справа - (n-m) единиц, и число равно $a_{n-m}$.

Вы что-то путаете. Чтобы получить значение $m$, нужно иметь как минимум $a_m$ единиц, но не наоборот. То есть не факт, например, что вообще существует арифметическая формула, в которой $m$ единиц и которая равна $a_m$.

Kid Kool писал(а):

Полученное число окажется не больше $a_m+a_{n-m}-1$ и имеет (n-1)-у единицу. Значит, $a_{n-1} \leqslant a_m+a_{n-m}-1$

Это соответственно тоже ниоткуда не следует.

[CD_Eater]

maxal писал(а):

Докажите, что для любого $n>1$,

$$\min_{1\leq m\leq n-1} a_m + a_{n-m} = a_1 + a_{n-1} = 1 + a_{n-1}$$

Нельзя доказать недоказуемое
$n=21080618$
$ a_6 + a_{n-6} < a_{n-1} + 1 $

[maxal]

CD_Eater писал(а):

Нельзя доказать недоказуемое
$n=21080618$
$ a_6 + a_{n-6} < a_{n-1} + 1 $

Поясните, как именно вы получили получили это неравенство? А вдруг вы где-то ошиблись

[CD_Eater]

Неравенство получено прямым вычислением.
Покажите своё "доказательство", и вопрос "кто из нас ошибся" быстро разрешится

[maxal]

CD_Eater писал(а):

Неравенство получено прямым вычислением.
Покажите своё "доказательство", и вопрос "кто из нас ошибся" быстро разрешится

Ваш контр-пример я перепроверил, предполагая, что вы считали по второй (упрощенной) формуле (по первой бы вам пришлось выполнить порядка $10^{14}$ операций для указанного $n$). Значения получились такими:
$a_{21080618-1} + 1 = 55$
$a_6 + a_{21080618-6} = 54$
То есть, действительно, получаем противоречие. Частично открываю карты - никакого доказательства и не было, и вы это раскусили, поздравляю! Переходим ко второй части.

Докажите (ну или опровергните формулу ):

$$a_n = \min\left\{1 + a_{n-1}, \min_{d|n\atop 1<d<n} a_d + a_{n/d}\right\}.$$

Замечание: здесь уже не предполагается справедливость $\min\limits_{1\leq m\leq n-1} a_m + a_{n-m} = 1 + a_{n-1}$ в общем виде, а всего лишь выполнение вышеуказанной формулы. Соответственно контр-пример, указанный CD_Eater, здесь уже не работает.

[CD_Eater]

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

Ещё замечу, что мои вычисления производились не в предположении верности вашей формулы (чтобы потом получить противоречие с ней же), а в смысле абсолютной достоверности.

[maxal]

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

Добавлено спустя 3 минуты 20 секунд:

CD_Eater писал(а):

Ещё замечу, что мои вычисления производились не в предположении верности вашей формулы (чтобы потом получить противоречие с ней же), а в смысле абсолютной достоверности.

То есть, вы использовали исходную формулу (что указана первой в начальной формулировке)? И искали не минимальный контр-пример? Поясните.

[CD_Eater]

Чтобы найти честный минимум сумм, недостаточно ограничиться одной комбинацией слагаемых (как вы подумали), но и нет необходимости перебирать ВСЕ комбинации $a_m + a_{n-m}$. Истина, как всегда, где-то посередине.

Найденный контрпример - минимальный.

[maxal]

CD_Eater писал(а):

Чтобы найти честный минимум сумм, недостаточно ограничиться одной комбинацией слагаемых (как вы подумали),

Если вы имете в виду исходную постановку задачи, то она отнюдь не отражает мое мнение. Я специально сформулировал ее именно в такой форме.

CD_Eater писал(а):

но и нет необходимости перебирать ВСЕ комбинации $a_m + a_{n-m}$. Истина, как всегда, где-то посередине.

Опять загадками говорите. Почему бы просто не объяснить, как именно вы пришли к своему контр-примеру?

CD_Eater писал(а):

Найденный контрпример - минимальный.

В каком именно смысле? Означает ли это, что равенство

$$\min_{1\leq m\leq n-1} a_m + a_{n-m} = 1 + a_{n-1}$$

справедливо для всех $n<21080618$ ? Если вы имете в виду именно это утверждение, то хотелось бы ознакомиться с его доказательством.

[maxal]

CD_Eater, могу вас поздравить еще раз. Вы будете упомянуты в новой редакции книги Ричарда Гая "Unsolved Problems in Number Theory" в связи с прогрессом в решении одной из проблем раздела F26. А именно, ваш контр-пример послужил толчком к нахождению контр-примера к тождеству $a_p = a_{p-1} + 1$ для всех простых $p$ (именно эту проблему я планировал эту выставить как третью часть, но не успел ). Контр-пример $p=353942783$ был недавно найден Мартином Фуллером (понятно, что это же число является контр-примером ко второй части).
Ричард попросил меня узнать ваше настоящее имя. Поэтому прошу сообщить мне ваше имя в ЛС в английской транскрипции (если, конечно, вам это интересно).
А заодно, может быть, все-таки расскажете как именно вы нашли свой контр-пример (лучше прямо в этом топике), потому что ничего внятного на этот счет я Ричарду сообщить не могу.

UPD. Последовательности в OEIS, связанные с этой задачей: A005245, A189123, A189124, A189125.

[CD_Eater]

Просто начал пытаться найти доказательство, но интуитивно понял, что последовательность $a_i$ схожа со случайным процессом, поэтому в ней могут быть найдены флуктуации любого размера. То есть, нужно найти возрастающую подпоследовательность длины 6, чтобы получить контрпример - и такая подпоследовательность нашлась. Подпоследовательность длины 7 была бы контрпримером ко второму вашему утверждению. Однако для её поисков нужен был или комп с ОЗУ больше чем у моего, или усложнённый алгоритм (было лень).

Просьба именовать меня как "Igor aka CD_Eater from Moscow".