Аддитивная цепочка

Аддитивная цепочка — последовательность натуральных чисел, начинающаяся с единицы, в которой каждый последующий элемент является суммой каких-то двух предшествующих элементов (в том числе, возможно использование одного и того же предшествующего элемента — удвоение). Формально, в аддитивной последовательности ${\displaystyle a_{i}}$ выполнены условия:

• ${\displaystyle a_{0}=1}$;
• для любого ${\displaystyle i>0}$, ${\displaystyle a_{i}=a_{j}+a_{k}}$, где ${\displaystyle j,k<i}$.

Одной из практически интересных разновидностей аддитивной цепочки является цепочка, заканчивающаяся числом ${\displaystyle n}$ в которой каждый последующий элемент является удвоением предыдущего или суммой предыдущего и первого элементов:

• для любого ${\displaystyle i>0}$, ${\displaystyle a_{i}=a_{i-1}+a_{i-1}}$ или ${\displaystyle a_{i}=a_{i-1}+a_{0}}$.

Такая цепочка соответствует последовательности операций при возведении в степень ${\displaystyle n}$ «слева направо» (удвоение показателя степени соответствует возведению в квадрат, прибавление единицы — умножению на основание). Пример такой цепочки для ${\displaystyle n=10}$:

1, 2 = 1+1, 4 = 2+2, 5 = 4+1, 10 = 5+5.