![image](https://habrastorage.org/webt/ql/1f/ke/ql1fkebr2bf_oviayhfo9hynyjm.jpeg)
FizzBuzz — это известная задачка на программирование, которую обычно дают в технической части собеседований. Она формулируется примерно так:
Напишите функцию, выводящую список целых чисел от 1 до 100, но вместо каждого числа, кратного 3, она должна выводить «Fizz», а вместо каждого числа, кратного 5, выводить «Buzz». Вместо чисел, кратных и 3, 5, программа должна выводить «FizzBuzz»; все остальные числа должны выводиться без изменений.
Можно написать функцию, вообще не использующую условную логику и вместо этого разделяющую целые числа на 4 возможные категории (обычное решение оставим в качестве упражнения заинтересованному читателю):
- Имеющие делитель 3, но не 5
- Имеющие делитель 5, но не 3
- Имеющие делитель и 3, и 5
- Не имеющие делитель 3 и 5
Нам нужна функция, которая будет возвращать:
- «Fizz», если
и
является взаимно простым с 5
- «Buzz», если
и
является взаимно простым с 3
- «FizzBuzz», если
и
во всех остальных случаях.
Рассмотрим реализацию такой функции на 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? Почему
I. n^4 mod 15 решает FizzBuzz
Доказательство таково:
Первый случай тривиален; если n делится и на 3, и на 5, то после возведения n в любую степень возвращаемый
Во втором случае у нас есть 3 как делитель некой константы c:
или
для каждой константы c > 0, если c является взаимно простым с 5. (Если c не является взаимно простым с 5, то у нас возник первый случай, который вернёт 0.)
Для начала предположим, что
Предположим, что c является целым > 1. Применим степень к каждому множителю и воспользуемся равенством
Давайте рассмотрим отдельно выражение
Теорема Эйлера в теории чисел
Теорема Эйлера заключается в том, что
, где
является взаимно простым с
, а
— это пси-функция Эйлера; пси-функция
возвращает количество целых чисел меньше
, являющихся взаимно простыми с
. Для каждого простого числа
,
равна
.
![](https://habrastorage.org/r/w780q1/webt/ql/1f/ke/ql1fkebr2bf_oviayhfo9hynyjm.jpeg)
Леонард Эйлер
![](https://habrastorage.org/webt/ql/1f/ke/ql1fkebr2bf_oviayhfo9hynyjm.jpeg)
Леонард Эйлер
Мы можем переписать это во вторую строку благодаря следующему свойству модулярных выражений:
То есть для любого
Благодаря тому же процессу мы выясним, что
Теорема Эйлера говорит нам, что если
Опять же, если
У нас остаётся случай, в котором есть некое число
Если
Поэтому снова:
То есть
->(n){ {1 => n, 6 => "Fizz", 10 => "Buzz", 0 => "FizzBuzz"}[n**4%15] }
всегда будет возвращать правильный результат FizzBuzz для каждого 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 можно также записать в виде
где
В общем виде для любого множества из
Для функции типа FizzBuzz, возвращающей «Foo» вместо чисел, кратных 7, и «Bar» вместо чисел, кратных 11, найдём:
Реализация на 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]
Вывод
Итак,
… если числа
Я не делаю никаких предположений о том, что существует какое-то иное практическое применение этой формулы, кроме как для решения задач категории FizzBuzz с выбранными в качестве кандидатов произвольными числами.