Рассмотрим следующий список:

expected = [
'A',
'B',
'AB',
'C',
'D',
'CD',
'ABCD',
'E',
'F',
'EF',
'G',
'H',
'GH',
'EFGH',
'ABCDEFGH',
'I',
'J',
'IJ',
'K',
'L',
'KL',
'IJKL',
'M',
'N',
'MN',
'O',
'P',
'OP',
'MNOP',
'IJKLMNOP',
'ABCDEFGHIJKLMNOP',
...
]

Вот один из способов взглянуть на это - вы учитесь писать китайские иероглифы и хотите изучать их все больше и больше, репетируя их по ходу дела. Вы начинаете с A, затем идете с B, тогда уже есть последовательность, которая представляет собой пару из двух, поэтому вы объединяете ее. Затем вы идете с C и D, создаете другую пару, практикуете это. Затем вы репетируете: ABCD. Затем то же самое идет с E до H, затем репетируйте: ABCDEFGH. Список бесконечен.

Цель состоит в том, чтобы сгенерировать и распечатать n-й элемент этого списка, индексы повышаются с нуля. Предположим, что после «Z» вы снова получаете «A».

Критерии победы - длина исходного кода.

Python 2, 53 байта

x,y=0,1
exec"x^=y-x;y+=x/y;"*input()
print range(x,y)

Попробуйте онлайн!

Подобно этой конструкции с преобразованием x = u-v,y = u

JavaScript (ES6), 59 байт

Мы можем сохранить 2 байта, сделав последовательность 1 проиндексированной и используя упрощение, подобное тому, которое использует KSab :

n=>(x=g=y=>n?g(y+=y==(x^=y-x),n--):x<y?[x++,...g(y)]:[])(1)

Попробуйте онлайн!

JavaScript (ES6), 61 байт

Возвращает список целых чисел без переноса.

n=>(g=v=>n?g(u&-u^v?v*2:!!u++,n--):v?[u-v,...g(v-1)]:[])(u=1)

Попробуйте онлайн!

Основано на конструкции Дональда Кнута. Соответствующая запись OEIS: A182105 .

Как?

Это двухэтапная рекурсивная функция.

Сначала мы строим последовательность определенную как и:$(u_n,v_n)$$(u_1,v_1)=(1,1)$

Во время второго прохода мы создаем список и в конечном итоге возвращаем его.$[u_n-v_n,u_n-v_n+1,\dots,u_n]$

JavaScript (ES6), 97 байт

Возвращает заглавные буквы.

n=>(s=i='',g=v=>(s+=String.fromCharCode(65+i++%26),n--)?g(u&-u^v?v*2:!!u++):s.substr(u-v,v))(u=1)

Попробуйте онлайн!

Или 91 байт в нижнем регистре.

Python 2 , 60 байт

u=v=1
exec"v=u/v%2or 2*v;u+=1/v;"*input()
print range(u-v,u)

Попробуйте онлайн!

Основано на использовании Арнаулдом конструкции Кнута . Условие u&-u==vможет быть заменено более простым условием u/v%2>0или, альтернативно u&v>0, так как vэто всегда степень 2, которая uделится на.

Wolfram Language (Mathematica) , 80 71 байт

Range@#2+#-#2&@@Nest[If[#~BitAnd~-#==#2,{#+1,1},{#,2#2}]&@@#&,{1,1},#]&

Попробуйте онлайн!

Возвращает список целых чисел вместо строки переноса алфавита. 0 индексированные.

Использует OEIS A182105 , благодаря @Arnauld.

Печать списка бесконечно, 54 байта

Do[j=Range@i;#∣i&&Print@j[[-#;;]]&/@(2^j/2),{i,∞}]

Попробуйте онлайн!

1-индексироваться. Версия TIO имеет limвместо того, ∞чтобы предотвратить сбои.

Python 2 , 93 89 82 байта

def f(n):r=[];C=1;exec"p=C%2or 2*p;r+=[p];C=r.count(p);"*n;return range(C*p-p,C*p)

Попробуйте онлайн!

Возвращает список целых чисел. Аналогично подходу Арнаулда к Javascript .

Желе , 16 байт

1;ẎṀ+ƊẎQṭƊƊ¡ị@‘Ṿ

$13$

Полная программа. Печатает ,разделенный список целых чисел.

Древесный уголь , 45 42 35 байт

ＦＮ⊞υ⎇∧›Ｌυ¹⁼Ｌ§υ±¹Ｌ§υ±²⁺⊟υ⊟υ§αＬ⭆υκ⮌⊟υ

Попробуйте онлайн! Ссылка на подробную версию кода. 1-индексироваться. Я не мог найти простую формулу для генерации результата, поэтому я просто следовал процедуре, приведенной в вопросе. Объяснение:

ＦＮ

Повторите указанное количество nраз.

⊞υ

Вставьте следующий элемент в предопределенный пустой массив u, рассчитанный как ...

⎇∧›Ｌυ¹⁼Ｌ§υ±¹Ｌ§υ±²

... если в нем более одного элемента, uа последние два элемента имеют одинаковую длину ...

⁺⊟υ⊟υ

... затем добавьте предпоследний элемент к последнему элементу (который создает результат в обратном порядке) ...

§αＬ⭆υκ

... в противном случае следующую букву можно найти, посчитав, сколько букв мы добавили до сих пор и циклически индексируя в заранее заданный прописной алфавит. (Принимая сумму длины или длину суммы не удается, когда список пуст, и отображение списка в строку сохраняет два байта над специальным регистром пустого списка.)

⮌⊟υ

Возьмите последний элемент u, который является обращенным nэлементом желаемого списка, и неявно выведите обратное.