Русский
Русский
English
Авторизация
Ip-адрес
Восстановление пароля
Регистрация
Статистика
Реклама

Перевод Решение Fizzbuzz при помощи теоремы Эйлера

image

FizzBuzz это известная задачка на программирование, которую обычно дают в технической части собеседований. Она формулируется примерно так:

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

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

  1. Имеющие делитель 3, но не 5
  2. Имеющие делитель 5, но не 3
  3. Имеющие делитель и 3, и 5
  4. Не имеющие делитель 3 и 5

Нам нужна функция, которая будет возвращать:

  • Fizz, если $n \equiv 0 \pmod 3$ и $n$ является взаимно простым с 5
  • Buzz, если $n \equiv 0 \pmod 5$ и $n$ является взаимно простым с 3
  • FizzBuzz, если $n \equiv 0 \pmod 3$ и $n \equiv 0 \pmod 5$
  • $n$ во всех остальных случаях.

Рассмотрим реализацию такой функции на 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$.

Теорема Эйлера в теории чисел
Теорема Эйлера заключается в том, что $a^{(n)} \equiv 1 (\mod n)$, где $a$ является взаимно простым с $n$, а $$ это пси-функция Эйлера; пси-функция $n$ возвращает количество целых чисел меньше $n$, являющихся взаимно простыми с $n$. Для каждого простого числа $p$, $(p)$ равна $p - 1$.


Леонард Эйлер

$\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) мы можем записать

$(625 + 625(c^4 - 1)) \mod 15$


Теорема Эйлера говорит нам, что если $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 с выбранными в качестве кандидатов произвольными числами.
Источник: habr.com
К списку статей
admin
Опубликовано: 22.03.2021 10:20:41
0

Сейчас читают

Комментариев (0)
Имя
Электронная почта

Программирование

Алгоритмы

Математика

Fizzbuzz

Эйлер

Модулярная функция

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru