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

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

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

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

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

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