Fizz Buzz — это игра с числами, которая стала неожиданно популярной в мире компьютерного программирования в качестве простой проверки базовых навыков. Правила игры просты: игроки вслух произносят по порядку числа, начиная с единицы. Если число делится на 3, игрок должен сказать вместо него «Fizz». Если число делится на 5, он должен сказать «Buzz». Если оно делится и на 3, и на 5, игрок говорит «FizzBuzz». Вот типичная программа на Python, выводящая нужную последовательность:

for n in range(1, 101):
    if n % 15 == 0:
        print('FizzBuzz')
    elif n % 3 == 0:
        print('Fizz')
    elif n % 5 == 0:
        print('Buzz')
    else:
        print(n)

А вот её вывод: fizz-buzz.txt. Можно ли усложнить эту программу? Слова «Fizz», «Buzz» и «FizzBuzz» повторяются в этой последовательности периодически. А что ещё у нас есть периодического? Тригонометрические функции! Возможно, нам удастся при помощи этих функций закодировать все четыре правила последовательности в выражении в аналитическом виде. Именно эту задачу мы и исследуем в статье, получив в конце дискретный ряд Фурье, который может получить любое целочисленное n и выбрать для печати соответствующий текст.

Определения

Прежде, чем двигаться дальше, сформулируем чёткое математическое определение последовательности Fizz Buzz. Начнём мы с нескольких функций, которые позже помогут нам определить последовательность Fizz Buzz.

Символьные функции

Мы определим множество из четырёх функций для целочисленных следующим образом:

Мы называем их символьными, потому что они генерируют все элементы, встречающиеся в последовательности Fizz Buzz. Символьная функция возвращает само . Функции ,
и — функции-константы, всегда возвращающие слова , и , каким бы ни было значение .

Последовательность Fizz Buzz

Теперь мы можем определить последовательность Fizz Buzz, как последовательность , где

Запись означает, что целое делит целое , то есть кратно . Эквивалентно, существует такое целочисленное , что . Аналогично, означает, что не делит , то есть не кратно . С учётом вышеприведённых определений мы можем разложить первые несколько членов последовательности в явном виде следующим образом:

Обратите внимание, что функция возвращает индекс , который мы потом используем для выбора символьной функции, чтобы сгенерировать -ный член последовательности. Поэтому можно назвать индексной функцией.

Индикаторные функции

Изменим порядок случаев и условий индексной функции , чтобы легче находить интересные паттерны:

Эта функция помогает нам выбрать другую функцию , которая, в свою очередь, определяет -ный член последовательности Fizz Buzz. Теперь наша цель заключается в том. чтобы заменить эту кусочную функцию единым выражением в аналитическом виде. Для этого мы сначала определим индикаторные функции :

Формулу теперь можно переписать так:

Замечаете паттерн? Вот та же функция, записанная в виде таблицы:

Видите? Если считать значения в первых двух столбцах двоичными, а значения в третьем — десятичными значениями, то в каждой строке первые два столбца дают нам двоичное представление числа в третьем столбце. Например, , и в последней строке таблицы мы действительно видим в первых двух столбцах биты и , а в последнем — число . Иными словами, запись рядом двоичных цифр и даёт нам двоичное представление . Следовательно, . Теперь можно написать небольшую программу для демонстрации этой формулы:

for n in range(1, 101):
    s = [n, 'Fizz', 'Buzz', 'FizzBuzz']
    i = (n % 3 == 0) + 2 * (n % 5 == 0)
    print(s[i])

Можно ещё сильнее укоротить её, немного снизив её понятность:

for n in range(1, 101):
    print([n, 'Fizz', 'Buzz', 'FizzBuzz'][(n % 3 == 0) + 2 * (n % 5 == 0)])

Итак, мы добились неплохих результатов. Хоть у нас пока нет универсального определения выражения в аналитическом виде, думаю, многие согласятся, что определённые выше индикаторные функции достаточно просты, чтобы допустить их в выражении в аналитическом виде.

Сложные показательные функции

В предыдущем разделе мы получили формулу , которую затем использовали в качестве индекса для поиска выводимого текста. Также мы заявили, что это уже достаточно хорошее выражение в аналитическом виде.

Однако в интересах усложнения задачи мы должны задаться вопросом: что, если использование индикаторных функций запрещено? Что, если мы должны придерживаться общепринятого определения выражения в аналитическом виде, допускающего только конечные сочетания таких базовых операций, как сложение, вычитание, умножение, деление, целочисленные степени и корни с целочисленными индексами, а также функции наподобие показательных, логарифмов и тригонометрических? Оказывается, что приведённую выше формулу можно переписать с использованием исключительно сложения, умножения и косинуса. Давайте приступим к преобразованию. Рассмотрим сумму

где — мнимая единица, а и — целые. Это геометрический ряд на комплексной плоскости с коэффициентом . Если кратно , то для некого целочисленного , и мы получаем . Следовательно, когда кратно , мы получаем

Если не кратно m, то , и геометрический ряд принимает вид

Следовательно,

Разделив обе части на , получим

Но правая часть — это . Следовательно

Косинусы

Начнём с формулы Эйлера , где — вещественное число. Из этой формулы мы получаем . Следовательно

Третье равенство следует из того, что

когда целое.

Представленная выше функция определена для целочисленных значений , но можно разложить эту формулу на вещественные и составить график, чтобы наблюдать его форму в целых числах. Как и ожидается, функция имеет значение , когда — кратное трём целое, и значение , когда — целое, не кратное трём.

Аналогично

Разложив это выражение на вещественные значения , мы тоже можем создать её график. В этом случае функция тоже получает значение при целых , кратных , и , если x не кратно .

Вспомним, что мы выразили , как . Подставив эти тригонометрические выражения, получим

Это можно упростить до

Это выражение тоже можно разложить на вещественные и составить её график. Получившаяся кривая принимает в целочисленных точках значения , , и , как нам и было нужно.

Теперь мы можем написать следующую программу на Python:

from math import cos, pi
for n in range(1, 101):
    s = [n, 'Fizz', 'Buzz', 'FizzBuzz']
    i = round(11 / 15 + (2 / 3) * cos(2 * pi * n / 3)
                      + (4 / 5) * cos(2 * pi * n / 5)
                      + (4 / 5) * cos(4 * pi * n / 5))
    print(s[i])

Дискретное преобразование Фурье

Внимательный читатель может заметить, что выражение, полученное нами для — это дискретный ряд Фурье. Это неудивительно, ведь вывод программы Fizz Buzz зависит только от . Любую функцию для конечной циклической группы можно точным образом записать, как конечное разложение в ряд Фурье. В этом разделе мы получим при помощи дискретного преобразования Фурье. Стоит отметить, что представленные здесь вычисления вручную выполнять довольно скучно. Тем не менее, мы вкратце разберём, как они выполняются. В конце мы придём к точно такой же , что и выше. Мы просто получим тот же результат более прямым, но и более трудоёмким образом. Если вам это не кажется интересным, можете пропустить этот раздел.

Мы знаем, что — периодическая функция с периодом . Чтобы применить дискретное преобразование Фурье, мы рассмотрим один полный период функции со значениями . В рамках этого периода мы получаем:

Дискретный ряд Фурье — это

где коэффициенты Фурье задаются дискретным преобразованием Фурье

для . Формула для называется дискретным преобразованием Фурье (discrete Fourier transform, DFT). Формула для называется обратным дискретным преобразованием Фурье (inverse discrete Fourier transform, IDFT).

Пусть . Тогда при использовании значений из представленной выше таблицы DFT принимает следующий вид:

Подставив в это выражение, получим следующие коэффициенты Фурье:

Вычисление этих коэффициентов Фурье вручную может быть довольно монотонным процессом. На практике они почти всегда вычисляются математическим ПО, системами компьютерной алгебры или даже простым кодом наподобие такого: fizz-buzz-fourier.py. После вычисления коэффициентов мы можем подставить их в обратное преобразование и получить

Это то же самое выражение , которое мы получили в предыдущем разделе. Мы видим, что индексную функцию Fizz Buzz можно точным образом выразить через механизмы анализа Фурье.

Заключение

Подведём итог: мы определили последовательность Fizz Buzz как

где

Программа на Python для вывода последовательности Fizz Buzz, основанная на этом определении, представлена выше. В более сжатом виде программу можно записать так:

from math import cos, pi
for n in range(1, 101):
    print([n, 'Fizz', 'Buzz', 'FizzBuzz'][round(11 / 15 + (2 / 3) * cos(2 * pi * n / 3) + (4 / 5) * (cos(2 * pi * n / 5) + cos(4 * pi * n / 5)))])

Также можно изящно обернуть это в однострочник оболочки на случай, если вы захотите поделиться этой программой с друзьями, чтобы удивить их:

python3 -c 'from math import cos, pi; [print([n, "Fizz", "Buzz", "FizzBuzz"][round(11/15 + (2/3) * cos(2*pi*n/3) + (4/5) * (cos(2*pi*n/5) + cos(4*pi*n/5)))]) for n in range(1, 101)]'

В этой статье мы превратили простую числовую игру в тригонометрическую конструкцию, состоящую из дискретного ряда Фурье с тремя косинусами и четырьмя коэффициентами. Ничто из этого не упрощает Fizz Buzz, наоборот, делает его только сложнее. Но это решение показывает, что каждое и теперь обязано своим существованием определённому множеству коэффициентов Фурье. Мы начали статью со скромной цели: усложнения этой простой задачи, и мне кажется, нам это вполне удалось.