Аддитивная цепочка
Аддитивная цепочка — последовательность натуральных чисел, начинающаяся с единицы, в которой каждый последующий элемент является суммой каких-то двух предшествующих элементов (в том числе, возможно использование одного и того же предшествующего элемента — удвоение). Формально, в аддитивной последовательности [math]\displaystyle{ a_i }[/math] выполнены условия:
- [math]\displaystyle{ a_0 = 1 }[/math];
- для любого [math]\displaystyle{ i \gt 0 }[/math], [math]\displaystyle{ a_i = a_j + a_k }[/math], где [math]\displaystyle{ j, k \lt i }[/math].
Одной из практически интересных разновидностей аддитивной цепочки является цепочка, заканчивающаяся числом [math]\displaystyle{ n }[/math], в которой каждый последующий элемент является удвоением предыдущего или суммой предыдущего и первого элементов:
- для любого [math]\displaystyle{ i \gt 0 }[/math], [math]\displaystyle{ a_i = a_{i-1} + a_{i-1} }[/math] или [math]\displaystyle{ a_i = a_{i-1} + a_0 }[/math].
Такая цепочка соответствует последовательности операций при возведении в степень [math]\displaystyle{ n }[/math] «слева направо» (удвоение показателя степени соответствует возведению в квадрат, прибавление единицы — умножению на основание). Пример такой цепочки для [math]\displaystyle{ n = 10 }[/math]:
- 1, 2 = 1+1, 4 = 2+2, 5 = 4+1, 10 = 5+5.
См. также
Литература
- С. Б. Гашков. Задача об аддитивных цепочках и ее обобщения // Математическое просвещение 15.0 (2011): 138-153.