2^2^...^2

[nikov]

Надо написать программу, которая принимает на вход натуральное число $n,$ и печатает, сколько различных значений может принимать выражение $2\uparrow2\uparrow\dots\uparrow2$ ($n$ двоек) при всевозможных расстановках скобок ($\uparrow$ - это оператор возведения в степень).
Например, при $n=3$ результат равен $1$, так как $(2\uparrow2)\uparrow2 = 2\uparrow(2\uparrow2).$

[maxal]

A002845

[nikov]

maxal писал(а):

http://www.research.att.com/~njas/sequences/A002845

Да, вот меня и интересует, с помощью какой программы это вычислено.

[luitzen]

nikov писал(а):

maxal писал(а):

http://www.research.att.com/~njas/sequences/A002845

Да, вот меня и интересует, с помощью какой программы это вычислено.

Выложил тут статьи из The American Mathematical Monthly, посвящённые этой проблеме, включая те две, что упомянуты на странице про A002845.

Я так понимаю, что равенство $2 \uparrow (2 \uparrow 2) = (2 \uparrow 2) \uparrow 2$ является единственной причиной, по которой число значений при различных расстановках скобок не равняется числу расстановок скобок. Видимо, можно просто перебирать различные расстановки и отбрасывать те, в которых встречается подформула $(2 \uparrow 2) \uparrow 2$.

Наверное, пора уже думать об инструментальных средствах: о языке и о структуре данных, используемой для представления способа расстановки скобок .

~~~~

maxal в следующем сообщении писал(а):

В результате совместного обсуждения с Руст родились новые тождества:
[…]
которые невозможно объяснить с помощью одного лишь тождества $2 \uparrow (2 \uparrow 2) = (2 \uparrow 2) \uparrow 2$.

Спасибо! Подозревал что-то подобное, но составить примеры не смог .

[maxal]

luitzen в сообщении #195293 писал(а):

Я так понимаю, что равенство $2 \uparrow (2 \uparrow 2) = (2 \uparrow 2) \uparrow 2$ является единственной причиной, по которой число значений при различных расстановках скобок не равняется числу расстановок скобок. Видимо, можно просто перебирать различные расстановки и отбрасывать те, в которых встречается подформула $(2 \uparrow 2) \uparrow 2$.

В результате совместного обсуждения с Руст родились новые тождества:

$$(2 \uparrow 2) \uparrow (2 \uparrow 2) = (2 \uparrow (2 \uparrow 2)) \uparrow 2$$

$$(2 \uparrow 2) \uparrow (2 \uparrow (2 \uparrow 2)) = (2 \uparrow (2 \uparrow (2 \uparrow 2))) \uparrow 2$$

$$(2 \uparrow (2 \uparrow 2)) \uparrow (2 \uparrow 2) = ((2 \uparrow 2) \uparrow (2 \uparrow 2)) \uparrow 2$$

которые невозможно объяснить с помощью одного лишь тождества $2 \uparrow (2 \uparrow 2) = (2 \uparrow 2) \uparrow 2$.

[maxal]

Первые два тождества из указанных выше являются частными случаями следующего:

$$(x \uparrow y) \uparrow z = (x \uparrow z) \uparrow y.$$

И третье - тоже, но вкупе с тождеством для 3-х двоек.
Интересно найти тождество необъяснимое подобным образом.

[ka3a4ok]

maxal в сообщении #226796 писал(а):

Интересно найти тождество необъяснимое подобным образом.

$ (((2 \uparrow 2)\uparrow 2)\uparrow 2)\uparrow 2 = 2 \uparrow (2 \uparrow (2\uparrow 2))) = 2\uparrow 16 = 65536$

Этот пример иллюстрирует обобщение свойства "трех двоек".
$(...((X \uparrow Z) \uparrow Z)\uparrow ... \uparrow Z)=X \uparrow (Z\cdot Z\cdot...\cdot Z) = X \uparrow (Z \uparrow K)$, где Z и K - правильные(в контексте задачи) степени двойки.