Решение Fizz Buzz с помощью косинусов

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

Мы определяем набор из четырех функций ( { s_0, s_1, s_2, s_3 } ) для целых чисел ( n ) следующим образом: begin{align*} s_0(n) &= n, \ s_1(n) &= mathtt{Fizz}, \ s_2(n) &= mathtt{Buzz}, \ s_3(n) &= mathtt{FizzBuzz}. end{align*} Мы называем их символьными функциями, потому что они создают каждый термин, который появляется в последовательности Fizz Buzz. Символьная функция ( s_0 ) возвращает ( n ) сама. Функции ( s_1, ) ( s_2 ) и ( s_3 ) являются постоянными функциями, которые всегда возвращают буквальные слова ( mathtt{Fizz}, ) ( mathtt{Buzz} ) и ( mathtt{FizzBuzz} ) соответственно, независимо от значения ( n ).

Теперь мы можем определить последовательность Fizz Buzz как последовательность [
(s_{f(n)}(n))_{n = 1}^{infty}
]

где [
f(n) = begin{cases}
1 & text{if } 3 mid n text{ and } 5 nmid n, \
2 & text{if } 3 nmid n text{ and } 5 mid n, \
3 & text{if } 3 mid n text{ and } 5 mid n, \
0 & text{otherwise}.
end{cases}
]

Вот функция ( f(n) ) из предыдущего раздела с перестановкой случаев и условий, чтобы было легче обнаружить интересные закономерности: [
f(n) = begin{cases}
0 & text{if } 5 nmid n text{ and } 3 nmid n, \
1 & text{if } 5 nmid n text{ and } 3 mid n, \
2 & text{if } 5 mid n text{ and } 3 nmid n, \
3 & text{if } 5 mid n text{ and } 3 mid n.
end{cases}
]

Эта функция помогает нам выбрать другую функцию ( s_{f(n)}(n) ), которая, в свою очередь, определяет ( n )-й член последовательности Fizz Buzz. Наша цель сейчас — заменить эту кусочную формулу одним выражением в замкнутой форме. Для этого сначала определим индикаторные функции ( I_m(n) ) следующим образом: [
I_m(n) = begin{cases}
1 & text{if } m mid n, \
0 & text{if } m nmid n.
end{cases}
]

Формулу для ( f(n) ) теперь можно записать так: [
f(n) = begin{cases}
0 & text{if } I_5(n) = 0 text{ and } I_3(n) = 0, \
1 & text{if } I_5(n) = 0 text{ and } I_3(n) = 1, \
2 & text{if } I_5(n) = 1 text{ and } I_3(n) = 0, \
3 & text{if } I_5(n) = 1 text{ and } I_3(n) = 1.
end{cases}
]

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

Вы видите это сейчас? Если мы рассматриваем значения в первых двух столбцах как двоичные цифры, а значения в третьем столбце как десятичные числа, то в каждой строке первые два столбца дают двоичное представление числа в третьем столбце. Например, ( 3_{10} = 11_2 ) и действительно в последней строке таблицы мы видим биты ( 1 ) и ( 1 ) в первых двух столбцах и число ( 3 ) в последнем столбце. Другими словами, запись двоичных цифр ( I_5(n) ) и ( I_3(n) ) рядом дает нам двоичное представление ( f(n). ) Следовательно [
f(n) = 2 , I_5(n) + I_3(n).
]

В предыдущем разделе мы получили формулу [
f(n) = I_3(n) + 2 , I_5(n)
]

который мы затем использовали в качестве индекса для поиска текста, который нужно напечатать. Мы также утверждали, что это уже довольно хорошее выражение закрытой формы.

Однако, чтобы усложнить ситуацию, мы должны спросить себя: что, если нам не разрешат использовать индикаторные функции? Что, если мы должны придерживаться общепринятого значения выражения в замкнутой форме, которое допускает только конечные комбинации основных операций, таких как сложение, вычитание, умножение, деление, целые показатели степени и корни с целым индексом, а также такие функции, как экспоненты, логарифмы и тригонометрические функции. Оказывается, приведенную выше формулу можно переписать, используя только сложение, умножение, деление и функцию косинуса. Начнем перевод. Рассмотрим сумму [
S_m(n) = sum_{k = 0}^{m – 1} e^{2 pi i k n / m},
]

где ( i ) — мнимая единица, а ( n ) и ( m ) — целые числа. Это геометрическая прогрессия на комплексной плоскости с отношением ( r = e^{2 pi in / m}. ) Если ( n ) кратно ( m , ) то ( n = cm ) для некоторого целого числа ( c ) и мы получаем [
r
= e^{2 pi i n / m}
= e^{2 pi i c}
= 1.
]

Следовательно, когда ( n ) кратно ( m, ), мы получаем [
S_m(n)
= sum_{k = 0}^{m – 1} e^{2 pi i k n / m}
= sum_{k = 0}^{m – 1} 1^k
= m.
]

Начнем с формулы Эйлера [
e^{i x} = cos x + i sin x
]

где ( x ) — действительное число. Из этой формулы получаем[
e^{i x} + e^{-i x} = 2 cos x.
]

Поэтому begin{align*} I_3(n) &= frac{1}{3} sum_{k = 0}^2 e^{2 pi ikn / 3} \ &= frac{1}{3} left( 1 + e^{2 pi in / 3} + e^{4 pi in / 3} right) \ &= frac{1}{3} left( 1 + e^{2 pi in / 3} + e^{-2 pi in / 3} right) \ &= frac{1}{3} + frac{2}{3} cos left( frac{2 pi n}{3} right). end{align*} Третье равенство выше следует из того факта, что ( e^{4 pi in / 3} = e^{6 pi in / 3} e^{-2 pi in / 3} = e^{2 pi in} e^{-2 pi in/3} = e^{-2 pi in / 3}. )

Приведенная выше функция определена для целочисленных значений ( n ), но мы можем расширить ее формулу до вещественного значения ( x ) и построить ее график, чтобы наблюдать ее форму между целыми числами. Как и ожидалось, функция принимает значение ( 1 ) всякий раз, когда ( x ) является целым числом, кратным ( 3 ) и ( 0 ), когда ( x ) является целым числом, не делящимся на ( 3. )

Аналогично, begin{align*} I_5(n) &= frac{1}{5} sum_{k = 0}^4 e^{2 pi ikn / 5} \ &= frac{1}{5} left( 1 + e^{2 pi in / 5} + e^{4 pi in / 5} + e^{6 pi in / 5} + e^{8 pi in / 5} right) \ &= frac{1}{5} left( 1 + e^{2 pi in / 5} + e^{4 pi in / 5} + e^{-4 pi in / 5} + e^{-2 pi in / 5} right) \ &= frac{1}{5} + frac{2}{5} cos left( frac{2 pi n}{5} right) + frac{2}{5} cos left( frac{4 pi n}{5} right). end{align*} Распространение этого выражения на реальные значения ( x ) позволяет нам также построить его форму. Еще раз, функция принимает значение ( 1 ) для целых чисел, кратных ( 5 ) и ( 0 ) для целых чисел, не кратных ( 5. )

Напомним, что мы выразили ( f(n) ) как [
f(n) = I_3(n) + 2 , I_5(n).
]

Подстановка этих тригонометрических выражений дает [
f(n)
= frac{1}{3} + frac{2}{3} cos left( frac{2 pi n}{3} right) +
2 cdot left( frac{1}{5} + frac{2}{5} cos left( frac{2 pi n}{5} right) +
frac{2}{5} cos left( frac{4 pi n}{5} right) right).
]

Простое упрощение дает [
f(n)
= frac{11}{15} +
frac{2}{3} cos left( frac{2 pi n}{3} right) +
frac{4}{5} cos left( frac{2 pi n}{5} right) +
frac{4}{5} cos left( frac{4 pi n}{5} right).
]

Мы можем расширить это выражение до действительного ( x ) и также построить его график. Полученная кривая принимает значения ( 0, 1, 2 ) и ( 3 ) в целочисленных точках по желанию.

Теперь мы можем написать нашу программу на 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 как [
(s_{f(n)}(n))_{n = 1}^{infty}
]

где [
f(n)
= frac{11}{15} +
frac{2}{3} cos left( frac{2 pi n}{3} right) +
frac{4}{5} cos left( frac{2 pi n}{5} right) +
frac{4}{5} cos left( frac{4 pi n}{5} right)
in { 0, 1, 2, 3 }
]

и ( s_0(n) = n, ) ( s_1(n) = mathtt{Fizz}, ) ( s_2(n) = mathtt{Buzz} ) и ( s_3(n) = mathtt{FizzBuzz}. ) Программа 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)))])

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

printf 'from math import cos, pinfor 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

Внимательный может заметить, что полученное нами выражение для ( f(n) ) представляет собой конечный ряд Фурье. Это неудивительно, поскольку результат работы программы Fizz Buzz зависит только от ( n bmod 15. ) Любую функцию на конечной циклической группе можно записать в точности как конечное разложение Фурье.

Мы взяли простую игру со счетом и превратили ее в тригонометрическую конструкцию: конечный ряд Фурье с постоянным членом ( 11/15 ) и тремя косинусами с коэффициентами ( 2/3, ) ( 4/5 ) и ( 4/5. ). Конечно, ничто из этого не делает Fizz Buzz проще, но это показывает, что каждые ( mathtt{Fizz} ) и ( mathtt{Buzz} ) теперь обязан своим существованием определенному набору коэффициентов Фурье. Мы начали со скромной цели усложнить эту простую задачу. Думаю, можно с уверенностью сказать, что мы не ошиблись.