Последовательность Гульда — это целочисленная последовательность, названная в честь , которая подсчитывает количество нечётных чисел в каждой строке треугольника Паскаля. Она состоит только из степеней двойки и начинается с: 1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 8, 4, 8, 8, 16, 2, 4, ... () Например, шестое число в последовательности равно 4, поскольку имеется четыре нечётных числа в треугольнике Паскаля (выделены жирным в последовательности 1, 5, 10, 10, 5, 1). Последовательность Гульда является фрактальной.
Дополнительные интерпретации В последовательности (начиная с ) -е значение даёт наибольшую степень двойки, которая делит центральный биномиальный коэффициент , и числитель дроби (представленной в несократимом виде).
Последовательность Гульда даёт также количество активных ячеек в -м поколении клеточного автомата по правилу 90, начиная с одной активной ячейки. Она имеет характерную растущую пилообразную форму, которая может быть использована для распознавания физических процессов, ведущих себя аналогично правилу 90.
Связанные последовательности Двоичные логарифмы последовательности Гульда сами по себе образуют целочисленную последовательность 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, ... в которой -е значение даёт число ненулевых бит в двоичном представлении числа , иногда записываемое в математической нотации как . Эквивалентно, -е значение в последовательности Гульда равно
Взятие показателей последовательности (т.е., ) по модулю два даёт Последовательность Морса — Туэ.
Частичные суммы последовательности Гульда, 0, 1, 3, 5, 9, 11, 15, 19, 27, 29, 33, 37, 45, ... подсчитывают все нечётные числа в первых строках треугольника Паскаля. Эти числа растут пропорционально , но с коэффициентом пропорциональности, который колеблется между 0,812556... и 1 периодически как функция от .
Рекурсивное построение и самоподобность Первые последовательности Гульда можно построить, рекурсивно вычисляя первые значений, а затем добавив к ним удвоенные значения первых элементов. Например, если к первым чётырём значениям 1, 2, 2, 4 приписать их удвоенные значения 2, 4, 4, 8, получаем первые восемь значений. Ввиду такого способа построения, каждая впервые встречающаяся степень двойки в последовательности находится на позиции .
Последовательность Гульда, последовательность её показателей степени и последовательность Туэ — Морса обладают свойством самоподобия: подпоследовательность значений на чётных позициях в полной последовательности совпадает с исходной последовательностью. Этим свойством обладают и некоторые другие последовательности, например, диатомическая последовательность Стерна. В последовательности Гульда значения на нечётных позициях вдвое больше предыдущих, а в последовательности показателей степени — на единицу больше предыдущих.
История Последовательность названа именем Генри Гульда, который изучал её в начале 1960-х годов. Однако тот факт, что эти числа являются степенями двойки, причём показатель степени -го числа равен количеству единиц в двоичном предсталении числа , был известен ещё Д. У. Л. Глейшеру в 1899.
Доказательство того, что числа в последовательности Гульда являются степенями двойки, было предложено в качестве задачи на математической олимпиаде Патнема в 1956 году.
Примечания
Литература
. Как процитировано у Gilleland.
. См., в частности последний параграф на стр. 156.
Категория:Целочисленные последовательности Категория:Факториалы и биномиальные коэффициенты Категория:Фракталы