[Перевод] Решение Fizzbuzz при помощи теоремы Эйлера22.03.2021 10:18

image

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

Можно написать функцию, вообще не использующую условную логику и вместо этого разделяющую целые числа на 4 возможные категории (обычное решение оставим в качестве упражнения заинтересованному читателю):
  1. Имеющие делитель 3, но не 5
  2. Имеющие делитель 5, но не 3
  3. Имеющие делитель и 3, и 5
  4. Не имеющие делитель 3 и 5

Нам нужна функция, которая будет возвращать:
Рассмотрим реализацию такой функции на Python: 
[(lambda n: { 1: n, 6: "Fizz", 10: "Buzz", 0: "FizzBuzz" }[n**4%15])(n+1) for n in range(100)]

Та же функция на Ruby: 
(1..100).map{|n| {1 => n, 6 => "Fizz", 10 => "Buzz", 0 => "FizzBuzz"}[n**4%15] }

Как мы и ожидали, каждая из этих функций возвращает список целых чисел от 1 до 100 с подставленными в нужные места «Fizz», «Buzz» и «FizzBuzz».

Но почему? Откуда взялись постоянные значения 0, 6, 10 и 1? Почему $n^4 \mod 15$ возвращает 6 для чисел, кратных 3, но не 5, 10 для чисел, кратных 5, но не 3, 0 для чисел, кратных 5 и 3 и 1 во всех остальных случаях? И самое важное — справедливо ли это для любого $n$, которое мы выберем?

I. n^4 mod 15 решает FizzBuzz


Доказательство таково:

$n^4 \mod {15} = \begin{cases} 0, & \text{if $n$ is divisible by 3 and 5} \newline 6, & \text{if $n$ is divisible by 3 and coprime to 5} \newline 10, & \text{if $n$ is divisible by 5 and coprime to 3} \newline 1, & \text{if $n$ is coprime to 3 and 5} \end{cases}$


Первый случай тривиален; если n делится и на 3, и на 5, то после возведения n в любую степень возвращаемый $\mod 15$ результат всегда будет равен 0, та как любое целое число с делителями 3 и 5 будет также кратным 15 $(3 * 5)$.

Во втором случае у нас есть 3 как делитель некой константы c:

$3c^4 \equiv 6 \pmod{15}$


или

$3c^4 \mod 15 = 6$


для каждой константы c > 0, если c является взаимно простым с 5. (Если c не является взаимно простым с 5, то у нас возник первый случай, который вернёт 0.)

Для начала предположим, что $c = 1$. Это даёт $3^4 \mod 15$ или $81 \mod 15$, что вернёт 6: $15 * 5 = 75$, с остатком 6 от 81.

Предположим, что c является целым > 1. Применим степень к каждому множителю и воспользуемся равенством $(ab) = (a + a(b - 1))$:

$\begin{aligned} 3^4c^4 & \mod 15 \newline 81c^4 & \mod 15 \newline (81 + 81(c^4 - 1)) & \mod 15 \end{aligned}$


Давайте рассмотрим отдельно выражение $c^4$. Из теоремы Эйлера в теории чисел мы знаем, что поскольку $c$ является взаимно простым с 5, то $c^4 \mod 5$ равно 1; если $c^4 / 5$ имеет остаток 1, то это должен быть случай, когда $c^4 - 1$ровно делится на 5; то есть, вне зависимости от значения $c$, если оно является взаимно простым с 5, то $(c^4 - 1)$ имеет делитель 5. Другой делитель не важен, поэтому давайте перепишем $(c^4 - 1)$ как $5x$.
Теорема Эйлера в теории чисел

$\begin{align} (81 + 81(5x)) &\mod 15 \newline (81 \mod 15 + 81(5x) \mod 15) &\mod 15 \newline (6 + 81(5x) \mod 15) &\mod 15 \newline 6 \mod 15 \end{align}$


Мы можем переписать это во вторую строку благодаря следующему свойству модулярных выражений: $(a + b) \mod n = (a \mod n + b \mod n) \mod n$. В третьей строке выражение $81(5x)$ имеет делители и 3, и 5, поэтому $81(5x) \mod 15 = 0$, что даёт нам $6 \mod 15$, то есть 6.

То есть для любого $c$, являющегося взаимно простым с 5 и > 1, выражение $3c^4 \mod 15$ вернёт 6.

Благодаря тому же процессу мы выясним, что $5c^4 \mod 15$ всегда возвращает 10; при $c = 1$ мы имеем $625 \mod 15$, что равно 10. Для $c > 1$» /> (взаимно простое с 3) мы можем записать</p><p><img src=


Теорема Эйлера говорит нам, что если $c$ является взаимно простым с 3, то $c^2 \equiv 1 \mod 3$;, но у нас есть $c^4$. Однако $c^4$ — это $c^2c^2$, а поскольку $ab \mod n = ((a \mod n)( b \mod n)) \mod n$, то $c^4 \mod 3$ также равно 1.

Опять же, если $c^4 \equiv 1 (\mod 3)$, то $(c^4 - 1)$ нацело делится на 3 и имеет делитель 3. Это снова сокращает второй член до 0, оставляя $625 \mod 15$, что снова равно 10.

У нас остаётся случай, в котором есть некое число $c$, являющееся взаимно простым с 3 и 5. Если $c$ равно 1, то получаем $1 \mod 15$, то есть 1.

Если $c$ > 1, мы снова можем записать это как $(1 + (c^4 - 1)) \mod 15$. Так как мы знаем, что если $c$ является взаимно простым с 3 и 5, $c^4 \equiv 1 (\mod 3)$ и $c^4 \equiv 1 (\mod 5)$, то $(c^4 - 1)$ имеет делители 3 и 5.

Поэтому снова:

$\begin{aligned} (1 + (c^4 - 1)) &\mod 15 \newline (1 \mod 15 + (c^4 - 1) \mod 15) &\mod 15 \newline (1 + 0) &\mod 15 \newline 1 &\mod 15 \newline 1 \end{aligned}$


То есть $n^4 \mod 15$ всегда будет возвращать 0, если и 3, и 5 являются делителями $n$, возвращать 6, если делителем является 3, но не 5, возвращать 10, если делителем является 5, но не 3, и 1, если $n$ является взаимно простым и с 3, и с 5, а функция вида ->(n){ {1 => n, 6 => "Fizz", 10 => "Buzz", 0 => "FizzBuzz"}[n**4%15] } всегда будет возвращать правильный результат FizzBuzz для каждого $n$ (до того, как $n^4$ не переполнит тип integer, используемый в компьютере).

II. Решение любой задачи категории FizzBuzz


Схожую функцию можно создать для любой похожей задачи, которые я буду называть задачами категории FizzBuzz. (Задачи категории FizzBuzz: например, выводить «Foo» вместо чисел, кратных 2, «Bar» вместо чисел, кратных трём, «Baz» вместо чисел, кратных 5 и выполнить конкатенацию каждого слова для чисел, имеющих больше одного из делителей 2,3 и 5). Выбираемые в качестве делителей числа не обязаны быть простыми, но если одно из них имеет в качестве делителя другое, то некоторые группы не существуют. Например, если мы решили изменить FizzBuzz так, чтобы кратные 2 возвращали «Fizz», а кратные 4 возвращали «Buzz» (вместо традиционных 3 и 5), то увидим «Fizz» для каждого кратного 2, «FizzBuzz» для кратного 2 и 4, но никогда не увидим «Buzz», потому что не существует числа, кратного 4, являющегося взаимно простым с 2.

Представленное ниже обобщённое решение не такое уж и общее, как я сказал: существует множество пар чисел, для которого оно не сработает; поэтому делители нужно выбирать гораздо тщательнее. Оно сработает для уникальных простых чисел, но не всегда хорошо для составных чисел. Хочу поблагодарить автора этого очень подробного поста, объясняющего подробности того, почему общая формула не будет работать для составных чисел.

Написанное выше уравнение для решения FizzBuzz можно также записать в виде

$n^{LCM(ϕ(3),ϕ(5))} \mod (3 \cdot 5)$


где $ϕ$ — это пси-функция Эйлера, а $LCM$ — наименьшее общее кратное.

В общем виде для любого множества из $k$ делителей $n_1,n_2,..n_k$, для которого нам нужна функция типа FizzBuzz, можно использовать формулу:

$n^{LCM(ϕ(n_1),ϕ(n_2),..ϕ(n_k))} \mod \prod_{i=1}^k n_i$


Для функции типа FizzBuzz, возвращающей «Foo» вместо чисел, кратных 7, и «Bar» вместо чисел, кратных 11, найдём:

$n^{LCM(ϕ(7),ϕ(11))} \mod (7 \cdot 11)$


$ϕ(7)$ равно 6, а $ϕ(11)$ равно 10, и $LCM$ (наименьшее общее кратное) для 6 и 10 равно 30. То есть уравнение примет вид:

$n^{30} \mod 77$


Реализация на Python: 
[(lambda n: { 1: n, 7**30%77: "Foo", 11**30%77: "Bar", 0: "FooBar" }[n**30%77])(n+1) for n in range(100)]

Это даст нам ожидаемый результат:
[1, 2, 3, 4, 5, 6, 'Foo', 8, 9, 10, 'Bar', 12, 13, 'Foo', 15, 16, 17, 18, 19, 20, 'Foo', 'Bar', 23, 24, 25, 26, 27, 'Foo', 29, 30, 31, 32, 'Bar', 34, 'Foo', 36, 37, 38, 39, 40, 41, 'Foo', 43, 'Bar', 45, 46, 47, 48, 'Foo', 50, 51, 52, 53, 54, 'Bar', 'Foo', 57, 58, 59, 60, 61, 62, 'Foo', 64, 65, 'Bar', 67, 68, 69, 'Foo', 71, 72, 73, 74, 75, 76, 'FooBar', 78, 79, 80, 81, 82, 83, 'Foo', 85, 86, 87, 'Bar', 89, 90, 'Foo', 92, 93, 94, 95, 96, 97, 'Foo', 'Bar', 100]

Вывод


Итак,

$$display$$a^{LCM (ϕ (n_1), ϕ (n_2),…ϕ (n_k))} \equiv \begin{cases} 0\pmod {\prod_{i=1}^k n_i}, & \text{if $n$ is divisible by every $n_1, n_2,…n_k$} \newline r_1, r_2,…r_k\pmod {\prod_{i=1}^k n_i}, & \text{a distinct result for every other combination of factors in $n_1, n_2,…n_k$} \newline 1\pmod {\prod_{i=1}^k n_i}, & \text{if $n$ is coprime to every $n_1, n_2,…n_k$} \end{cases}$$display$$


… если числа $n_1, n_2,.. n_k$ являются уникальными простыми числами. Снова благодарю автора этого поста за столь наглядную иллюстрацию этого.

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

© Habrahabr.ru