четверг, 23 февраля 2012 г.

Функция Дейкстры

В блоге Republic of Math я нашёл статью об одной интересной целочисленной неотрицательной функции. Придумал её Эдсгер Дейкстра, обозначив fusc(n).

Значения функции вычисляются по следующему алгоритму:
fusc(0) = 0
fusc(1) = 1
fusc(2n) = fusc(n)
fusc(2n+1) = fusc(n) + fusc(n+1)

Вот как она себя ведёт:

Исследовав первую сотню значений функции:
0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1, 6, 5, 9, 4, 11, 7, 10, 3, 11, 8, 13, 5, 12, 7, 9, 2, 9, 7, 12, 5, 13, 8, 11, 3, 10, 7, 11, 4, 9, 5, 6, 1, 7, 6, 11, 5, 14, 9, 13, 4, 15, 11, 18, 7, 17, 10, 13, 3, 14, 11, 19, 8, 21, 13, 18, 5, 17, 12, 19, 7, 16, 9, 11, 2, 11, 9, 16, 7
можно заметить, что fusc(n) чётное тогда и только тогда, когда n делится на 3. А как это доказать?

5 комментариев:

  1. Как обычно — индукцией. :)

    ОтветитьУдалить
  2. Только в третьей строчке определения опечатка.

    ОтветитьУдалить
  3. Да-да :)

    Опечатку, что-то не нахожу, как ни вчитываюсь...

    ОтветитьУдалить
  4. fusc(2n) = n, а нужно fusc(2n) = fusc(n)

    ОтветитьУдалить
  5. Ааа, точно, спасибо большое!

    ОтветитьУдалить

Популярные сообщения

Темы

число цифра простые геометрия юмор язык дроби степень делимость пи методы история самоописывающее квадрат система счисления время узор задача корень структура тригонометрия е конструкция сайты формулы игра факториал функции приближение программа фрактал последовательность график комбинаторика память вероятность пределы конкурс логарифм треугольник неизвестное интеграл уравнение видео комплексные магический квадрат палиндром правильно-неправильное действие софизм заблуждения процесс ряды цитаты книги окружность прогрессия среднее стереометрия число фи выражения графы проценты логика парабола разрезания символ 2014 Фибоначчи клеточный автомат матрица производная статистика фокус головоломка кривая куб шахматы действия иллюзия новости оказывается оригами построение сложение термин тетраэдр