Русская Википедия:Аддитивная цепочка

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Шаблон:Значения Аддитивная цепочка — последовательность натуральных чисел, начинающаяся с единицы, в которой каждый последующий элемент является суммой каких-то двух предшествующих элементов (в том числе, возможно использование одного и того же предшествующего элемента — удвоение). Формально, в аддитивной последовательности <math>a_i</math> выполнены условия:

• <math>a_0 = 1</math>;
• для любого <math>i > 0</math>, <math>a_i = a_j + a_k</math>, где <math>j, k < i</math>.

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

• для любого <math>i > 0</math>, <math>a_i = a_{i-1} + a_{i-1}</math> или <math>a_i = a_{i-1} + a_0</math>.

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

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

См. также

• Разностная аддитивная цепочка

Литература

• С. Б. Гашков. Задача об аддитивных цепочках и ее обобщения // Математическое просвещение 15.0 (2011): 138-153.