Функция строк-подпоследовательностей

Есть некоторое правило: строка является правильной, если, разбив её на подстроки, каждый из которых начинается в позиции x_k и заканчивается в позиции x_2k, то ни одна подстрока не будет являться подпоследовательностью любой последующей подстроки.

Разбивка на подстроки строки ABCABC:

Подстрока 1: AB (с 1-й буквы до 2-й)

Подстрока 2: BCA (с 2-й буквы до 4-й)

Подстрока 3: CABC (с 3-й буквы до 6-й)

Подстрока N является подпоследовательностью подстроки X, если в подстроке X можно, убрав некоторые буквы, получить строку N.

Например, AAAA - подпоследовательность строки ABABABA. Удалим три буквы B, и будет строка AAAA.

Теперь, пусть функция n(k) является длиной самой длинной правильной строки, записанной k-ичным алфавитом.

n(1) = 3, используя строку AAA. Добавление ещё одной A приведёт к тому, что мы разберём AAAA на AA и AAA, одна является подпоследовательностью другой.

n(2) = 11. Логическим перебором можно показать это:

****

... вставить дерево перебора для n(2) ...

****

Пусть Ack(n) = 2{n-1}n.

Границы для n(3) и нижняя граница для n(4) (верхней ещё не нашли):

2{7197}158384 < n(3) < 2{(2{4}5)-1}(2{4}5)

Ack^Ack187196(1) < n(4).

Нижняя граница для n(4), вероятно, довольно слабая, так как n(k) растёт даже быстрее, чем {k,k (1) 2}, то есть чем линейная нотация массивов. Скорее всего, n(4) > {4,4,4,4}, то есть больше, чем супертет.

Есть также другая функция, связанная с этой, но растущая несколько быстрее. Пусть последовательность строк является правильной, если ни одна строка не является подпоследовательностью любой последующей строки, а также строка под номером k имеет длину k+1.

Далее, F(n) - длина самой длинной правильной последовательности строк, записанной с использованием n-ичного алфавита.

F(1) = 2, используя две строки: AA и AAA

F(2) >= 7, используя семь строк: AA, ABA, ABBB, BBABB, BBBBAB, BBBBBBA и BBBBBBBB. Может быть и больше.

Известно также, что F(4) > {3,4,2,1,2} в нотации массивов.