четверг, 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 Фибоначчи клеточный автомат кривая производная фокус головоломка действия иллюзия куб шахматы многоугольник новости оказывается оригами подобие построение сложение термин тетраэдр топология