2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Наивный вопрос про алгоритм Гудстейна
Сообщение16.07.2016, 10:41 


01/11/10
118
Из вики (теорема Гудстейна):
Рассмотрим представление целых положительных чисел в виде суммы степенных членов с одинаковым основанием.

Например, запишем число 581, используя основание 2.
$581=2^{2^{2+1}+1}+ 2^{2^{2}+2}+2^2+1$ (1)

Будем попеременно (рекурсивно) применять к получившемуся выражению две следующие операции:
1. увеличение «основания» на 1;
2. вычитание 1.

Таким образом, после применения первой операции будет получено выражение:
$3^{3^{3+1}+1}+3^{3^{3}+3}+3^3$ (2)
После третьей:
$4^{4^{4+1}+1}+4^{4^{4}+4}+4^4$(3)
После четвёртой:
$4^{4^{4+1}+1}+4^{4^{4}+4}+(3\cdot 4^3+3\cdot 4^2+3\cdot 4+3)$ (4)


Объясните, пожалуйста, почему при применении шага 2, т.е. вычитание единицы, к выражению (3), необходимо "разбивать" последнее слагаемое $4^4$ ?
Почему бы, например, не записать применение шага 2 к (3) так:
$4^{4^{4+1}+1}+4^{4^{4}+4}+4^4-(1)$(3.1) ?

Мне кажется шаг 2 - вычитание единицы, как-то неоднозначно описан.
Применим шаги 1,2 к выражению (3.1):
$5^{5^{5+1}+1}+5^{5^{5}+5}+5^5-(1)$(3.2.1)
$6^{6^{6+1}+1}+6^{6^{6}+6}+6^6-(2)$(3.2.2)

В итоге получится выражение вида:
$n^{n^{n+1}+1}+n^{n^{n}+n}+n^n-(x)$(3.3)
где $x$ тоже можно как-нибудь разложить в виде $n^5-n^{3}$ или $n^{n^{n-1}-n}-n^{n-2}$ и т.п.
В итоге вопрос сведется к тому, превысит ли когда-нибудь выражение в скобках левую часть, т.е. последовательность обнулиться, уйдет в минус, или нет.

В качестве попыток решения:
Может быть в алгоритме построения новой формулы после шага 2 нельзя применять вычитание, точнее "минус" в новой формуле писать нельзя (ведь вычитание единицы и есть шаг 2) ? Или есть явное требование "разбивать" последнее слагаемое предыдущей формулы, но в вики об этом не сказано ?

В общем, я вижу несколько интерпретаций как шаг 2 - вычитание единицы из числа описанного формулой на шаге $n-1$ меняет запись формулы (и соответственно число) на шаге $n$.
Алгоритм построения новой формулы, по крайне мере в вики, как-то неоднозначно описан (как именно вычитание единицы из числа, указанного формулой $n-1$ должно менять формулу $n$?), или я чего-то не понимаю. Объясните, плиз.

 Профиль  
                  
 
 Re: Наивный вопрос про алгоритм Гудстейна
Сообщение16.07.2016, 11:06 
Заслуженный участник
Аватара пользователя


23/07/05
18032
Москва
shkolnik в сообщении #1138172 писал(а):
Объясните, пожалуйста, почему при применении шага 2, т.е. вычитание единицы, к выражению (3), необходимо "разбивать" последнее слагаемое $4^4$ ?
Почему бы, например, не записать применение шага 2 к (3) так:
$4^{4^{4+1}+1}+4^{4^{4}+4}+4^4-(1)$(3.1) ?
Потому что запись в виде $4^4-1$ не есть запись числа в системе счисления с основанием $4$. Таковой является только запись в виде $3\cdot 4^3+3\cdot 4^2+3\cdot 4+3$. В системе счисления с основанием $4$ есть только цифры $0,1,2,3$. А цифры $-1$ нет.

shkolnik в сообщении #1138172 писал(а):
В итоге вопрос сведется к тому, превысит ли когда-нибудь выражение в скобках левую часть, т.е. последовательность обнулиться, уйдет в минус, или нет.
В данном случае очевидно, что $n^{n^{\ldots}}$ будет расти быстрее, чем $(x)$.

 Профиль  
                  
 
 Re: Наивный вопрос про алгоритм Гудстейна
Сообщение16.07.2016, 12:09 


01/11/10
118
Someone в сообщении #1138175 писал(а):
Потому что запись в виде $4^4-1$ не есть запись числа в системе счисления с основанием $4$. Таковой является только запись в виде $3\cdot 4^3+3\cdot 4^2+3\cdot 4+3$. В системе счисления с основанием $4$ есть только цифры $0,1,2,3$. А цифры $-1$ нет.

Значит, все-таки "минус" использовать нельзя ?
Получается, что формулы, с использованием "минуса" не эквивалентны формулам, в которых дозволены только "плюсы". Что же тогда понимать под "вычитанием единицы" в формулировке Гудстейна ?
Он решил ввести вычитание без введения "минуса" в формулы ?
Someone в сообщении #1138175 писал(а):
В данном случае очевидно, что $n^{n^{\ldots}}$ будет расти быстрее, чем $(x)$.

Поэтому я и спросил, как именно вычитание единицы из числа описываемого формулой на шаге $n-1$ отражается на записи формулы на шаге $n$ ?
Если в ней "минусы" использовать нельзя - тогда ответ очевиден. Как впрочем и если можно - очевиден и противоположен.

От этой записи (возможности или невозможности использовать в записи формулы числа знака "-") - и зависит, какое именно число будет этой формулой выражаться.

 Профиль  
                  
 
 Re: Наивный вопрос про алгоритм Гудстейна
Сообщение16.07.2016, 13:08 
Заслуженный участник
Аватара пользователя


23/07/05
18032
Москва
shkolnik в сообщении #1138184 писал(а):
Что же тогда понимать под "вычитанием единицы" в формулировке Гудстейна ?
То же самое, что и всегда понимается под вычитанием единицы.

По-моему, Вы просто придуриваетесь с целью троллинга.

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

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



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

Сейчас этот форум просматривают: vicvolf


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

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