2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 сложность записи натурального числа с помощью (1,*,+)
Сообщение26.01.2008, 23:49 
Модератор
Аватара пользователя


11/01/06
5328
Для натурального числа $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\}.$$

 Профиль  
                  
 
 
Сообщение27.01.2008, 16:40 


17/01/08
110
Пусть слева имеется 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$, что и требовалось доказать.

 Профиль  
                  
 
 
Сообщение27.01.2008, 20:42 
Модератор
Аватара пользователя


11/01/06
5328
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$

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

 Профиль  
                  
 
 Re: сложность записи натурального числа с помощью (1,*,+)
Сообщение28.01.2008, 10:28 
Аватара пользователя


28/01/08
13
Москва
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 $

 Профиль  
                  
 
 Re: сложность записи натурального числа с помощью (1,*,+)
Сообщение28.01.2008, 10:55 
Модератор
Аватара пользователя


11/01/06
5328
CD_Eater писал(а):
Нельзя доказать недоказуемое :)
$n=21080618$
$ a_6 + a_{n-6} < a_{n-1} + 1 $

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

 Профиль  
                  
 
 
Сообщение28.01.2008, 11:11 
Аватара пользователя


28/01/08
13
Москва
Неравенство получено прямым вычислением.
Покажите своё "доказательство", и вопрос "кто из нас ошибся" быстро разрешится ;)

 Профиль  
                  
 
 
Сообщение28.01.2008, 13:28 
Модератор
Аватара пользователя


11/01/06
5328
CD_Eater писал(а):
Неравенство получено прямым вычислением.
Покажите своё "доказательство", и вопрос "кто из нас ошибся" быстро разрешится ;)

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

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

$$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, здесь уже не работает.

 Профиль  
                  
 
 
Сообщение28.01.2008, 14:09 
Аватара пользователя


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

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

 Профиль  
                  
 
 
Сообщение28.01.2008, 14:18 
Модератор
Аватара пользователя


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

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

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

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

 Профиль  
                  
 
 
Сообщение28.01.2008, 17:55 
Аватара пользователя


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

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

 Профиль  
                  
 
 
Сообщение28.01.2008, 18:13 
Модератор
Аватара пользователя


11/01/06
5328
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$ ? Если вы имете в виду именно это утверждение, то хотелось бы ознакомиться с его доказательством.

 Профиль  
                  
 
 
Сообщение02.02.2008, 00:24 
Модератор
Аватара пользователя


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

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

 Профиль  
                  
 
 
Сообщение09.02.2008, 15:32 
Аватара пользователя


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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group