Как вычислить обратное число факториалу

Обратный факториал

Обратный факториал числа N = n! (обозначение: n!?) определяется как число, факториал которого n! и есть исходное число. Название обратный факториал аналогично названию обратная функция, ом. Большой англо-русский и русско-английский словарь мат. inverse factorial

В частности, n!? — это число предметов, количество перестановок которых (способов расположения) равно n!

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

n!? = n! / 1 / 2 / 3. / (n − 1) = n

или число, меньшее очередного делителя. В последнем случае дробная часть числа, инфолиофакториал которого равен исходному любому положительному числу, определяется решением квадратного уравнения от инфолиофакториала числа х, значения х! которого при целых х=n, совпадают с факториалом, а для всех иных значений х отличаются от значений Гамма-функции Г(х), предложенной Эйлером.

Например, число вариантов построения полевых игроков команды (1-й капитан, 2-й вратарь, далее остальные игроки в любой последовательности) 362880, тогда число игроков в команде может быть определено следующим образом: так как 362880/1/2/3/4/5/6/7/8/9=1, то 9+капитан+вратарь=11.

Wikimedia Foundation . 2010 .

Полезное

Смотреть что такое «Обратный факториал» в других словарях:

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

Полупрямое произведение — Полупрямое произведение  конструкция в теории групп, позволяющая строить новую группу по двум группам и , и действию группы на группе автоморфизмами. Полупрямое произведение групп и над … Википедия

\ — Обратная косая черта (англ. backslash, по русски часто упоминается как «обратный слеш» или «бэкслеш») символ «», назван так, чтобы отличаться от прямой косой черты (англ. «slash», по русски «слеш», «прямой слеш», «/»). Обратная косая черта… … Википедия

Бэк слеш — Обратная косая черта (англ. backslash, по русски часто упоминается как «обратный слеш» или «бэкслеш») символ «», назван так, чтобы отличаться от прямой косой черты (англ. «slash», по русски «слеш», «прямой слеш», «/»). Обратная косая черта… … Википедия

Бэкслеш — Обратная косая черта (англ. backslash, по русски часто упоминается как «обратный слеш» или «бэкслеш») символ «», назван так, чтобы отличаться от прямой косой черты (англ. «slash», по русски «слеш», «прямой слеш», «/»). Обратная косая черта… … Википедия

Бэкслэш — Обратная косая черта (англ. backslash, по русски часто упоминается как «обратный слеш» или «бэкслеш») символ «», назван так, чтобы отличаться от прямой косой черты (англ. «slash», по русски «слеш», «прямой слеш», «/»). Обратная косая черта… … Википедия

Штрих (письмо) — У этого термина существуют и другие значения, см. Штрих. ′ Штрих (письмо) Пунктуация … Википедия

Глоссарий теории групп — Группа (математика) Теория групп … Википедия

Парадигма — (Paradigm) Определение парадигмы, история возникновения парадигмы Информация об определении парадигмы, история возникновения парадигмы Содержание Содержание История возникновения Частные случаи (лингвистика) Управленческая парадигма Парадигма… … Энциклопедия инвестора

Name already in use

Часто в задачах требуется посчитать что-то по простому модулю (чаще всего $10^9 + 7$ ). Это делают для того, чтобы участникам не приходилось использовать длинную арифметику, и они могли сосредоточиться на самой задаче.

Обычные арифметические операции выполняются не сильно сложнее — просто нужно брать модули и заботиться о переполнении. Например:

Но вот с делением возникают проблемы — мы не можем просто взять и поделить. Пример: $\frac<8> <2>= 4$ , но $\frac<8 % 5 = 3> <2 % 5 = 2>\neq 4$ .

Способ 1: бинарное возведение в степень

Если модуль $p$ простой, то решением будет $a^ <-1>\equiv a^$ . Это следует из малой теоремы Ферма:

Теорема. $a^p \equiv a \pmod p$ для всех $a$ , не делящихся на $p$ .

Доказательство. (для понимания несущественно, можно пропустить)

Здесь $P(x_1, x_2, \ldots, x_n) = \frac<\prod (x_i!)>$ это мультиномиальный коеффициент — количество раз, которое элемент $a_1^ a_2^ \ldots a_n^$ появится при раскрытии скобки $(a_1 + a_2 + \ldots + a_n)^k$ .

Теперь два раза «поделим» наш результат на $a$ .

$$ a^p \equiv a \implies a^ \equiv 1 \implies a^ \equiv a^ <-1>$$

Получается, что $a^$ ведет себя как $a^<-1>$ , что нам по сути и нужно. Посчитать $a^$ можно за $O(\log p)$ бинарным возведением в степень.

Приведем код, который позволяет считает $C_n^k$ .

Способ 2: диофантово уравнение

Диофантовыми уравнениями называют такие штуки:

Требуется решить их в целых числах, то есть $a$ и $b$ известны, и нужно найти такие целые (возможно, отрицательные) $x$ и $y$ , чтобы равенство выполнялось. Решают такие вещи расширенным алгоритмом Евклида. TODO: описать, как он работает.

Подставим в качестве $a$ и $b$ соответственно $a$ и $m$

Одним из решений уравнения и будет $a^<-1>$ , потому что если взять уравнение по модулю $m$ , то получим

$$ ax + by = 1 \iff ax \equiv 1 \iff x \equiv a^ <-1>\pmod m $$

Преимущества этого метода над возведением в степень:

• Если обратное существует, то оно найдется даже если модуль не простой. Способ с бинарным возведением тоже можно заставить работать с произвольным модулем, но это будет намного труднее.
• Алгоритм проще выполнять руками.

Сам автор почти всегда использует возведение в степень.

1. Это выражение довольно легко вбивать ( 1e9+7 ).
2. Простое число.
3. Достаточно большое.
4. int не переполняется при сложении.
5. long long не переполняется при умножении.

Кстати, $10^9 + 9$ обладает теми же свойствами. Иногда используют и его.

Предподсчёт обратных факториалов за линейное время

Пусть нам нужно зачем-то посчитать все те же $C_n^k$ , но для больших $n$ и $k$ , поэтому асимптотика $O(n \log m)$ нас не устроит. Оказывается, мы можем сразу предподсчитать все обратные ко всем факториалам.

Если у нас уже написан inv , то нам не жалко потратить $O(\log m)$ операций, посчитав $m!^<-1>$ .

Обратный факториал

Обратный факториал числа N = n! (обозначение: n!? или N?) определяется как число, факториал которого n! и есть исходное число. Название обратный факториал аналогично названию обратная функция, ом. Большой англо-русский и русско-английский словарь мат. inverse factorial

В частности, n!? — это число предметов, количество перестановок которых (способов расположения) равно n!. Мнемоническое правило: обозначение обратный факториал «съедает» обозначение факториал.

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

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

1. Python (я буду использовать версию 2.7.5 под Windows 64 bit)
2. Мозги (я буду пользовать свои с примесью google и wikipedia)

• Факториал

Факториалы манили меня еще в школе. Красивое слово, необычный (для того времени) синтаксис. Я всегда с некоторой издевкой мог блеснуть талантом, ”вычисляя” факториал простого числа. Став старше, и особенно влюбившись в python, моя страсть к факториалам не просто не уменьшилась, скорее наоборот, именно поэтому эта статья полностью будет посвящена всевозможным факториалам. Но сначала немного математики. Итак,

Факториалом числа n (обозначается n!) называется произведение всех натуральных чисел от 1 до n.

Физический смысл (если так можно сказать) факториала определяется как число упорядочиваний множества из n элементов. Переводя с непонятного на русский, давайте представим себе колоду из 36 карт. Каждый раз, когда мы тасуем эту колоду мы создаем уникальное упорядочивание, одно из 36! = 371993326789901217467999448150835200000000. Возможно, именно поэтому карточные игры так популярны! ��

Но ближе к делу! Наверняка каждый, кто изучал python, знает как вычислить факториал, причем не одним способом. Когда изучают lambda-функции, пишут так:

… и мало кто что понимает!

Когда изучают рекурсию, пишут так:

Это уже понятней! А те, кто совсем хорошо знают python, вообще не парятся и делают так:

Но мы пойдём своим путём. Мы не будем использовать math, вместо этого мы напишем свой собственный модуль. Откройте свой любимый редактор (я буду пользоваться стандартным IDLE), создайте файл factorials.py и давайте творить! В качестве простейшей задачи сначала давайте определим функцию для вычисления факториала. Я буду делать это с помощью lambda, как в первом примере:

Теперь, если запустить скрипт на выполнение, то можно будет прямо в интерактивном интерпретаторе набрать

Казалось бы супер! И все примеры, которые можно найти в интернете здесь заканчиваются на позитивной ноте, однако как обычно все не так просто. На самом деле наша функция абсолютно некорректна и простейший способ проверить это — передать ей неадекватное значение. И если с совсем бредятинкой типа ”str” python справится сам, то вот значение типа ”float” легко пропустит. Не верите? Попробуйте посчитать факториал 4.125. Не бином Ньютона, что наша новорожденная функция должна работать только с целочисленным типом данных, следовательно нужно переписать её так:

Во-о-о-т! Теперь скормить ересь не получится, так как сразу будет подниматься TypeError . Но и это еще не всё. Если мы попробуем посчитать факториал -5 (минус пяти), то получим в ответ единицу, а это тоже неадекватно. Факториал определяется только для целых и положительных цифр, следовательно нужно ещё раз переписать код.

Для эстетов еще могу порекомендовать обработать значения типа ”float” , которые по сути являются целыми, типа 25.0, 12.0 etc. Я этого делать не буду, так как предпочитаю более жёстко обращаться с типами данных.

• Обратный факториал

Простейшая задача выполнена, но я бы не стал городить всё это только ради простейшей задачи! �� Куда более интересно найти обратный факториал. Легко догадаться, что

Обратным факториалом числа i называется такое число, факториал которого будет равен i.

То есть если 4! = 24, то обратным факториалом 24 будет 4. Функция для обратного факториала несколько сложнее. Для начала нужно понять механизм её работы. Если считая факториал числа мы последовательно умножаем цифры, то, как не сложно догадаться, здесь мы должны последовательно делить. Для себя я написал такой алгоритм работы функции: последовательно делим число на 1, 2, 3, 4 etc., до тех пор, пока не получим 1 и тогда возвращаем последний делитель. Но перед тем как начать писать код небольшое лирическое отступление. С помощью нашей функции вычислите факториал 4000. И получаем мы RuntimeError: maximum recursion depth exceeded . Печально? На самом деле ничего страшного не произошло, просто python ограничивает глубину рекурсии, что на мой взгляд правильно. Для того, чтобы посмотреть глубину рекурсии необходимо либо в интерпретаторе, либо где кому удобно импортировать модуль sys и выполнить функцию sys.getrecursionlimit() . В ответ вы скорее всего получите 1000, но лично у меня питон падает при вычислении факториала 995, хотя глубина рекурсии стоит 1000. Это на самом деле не важно, так как можно легко увеличить (но будьте разумны!) глубину путем вызова функции sys.setrecursionlimit(5000) например до 5000. Собственно, к чему все это? А к тому, что функция sys.getrecursionlimit() пригодится нам для написания своей функции обратного факториала. Итак, первым делом мы должны проверить поступающее значение на валидность. Также как и с факториалом, мы будем работать только с целыми положительными цифрами, следовательно

Теперь наша задача сводится к тому, чтобы последовательно делить x на числа от 1 и до… догадались? До sys.getrecursionlimit()+1 ! Решение вполне простое и изящное. Можно было, конечно, задать какое-нибудь произвольное число, например 500. Однако, давайте представим себе, что пользователь вычислил факториал 900, взял это число и подставил его в нашу функцию. Вы поняли что произойдет, я уверен. Наш антифакториал будет делить и делить до тех пор, пока не дойдет до 500, а затем остановится. Но мы должны были делить последовательно до 900! В общем, для того, чтобы не париться с такой фигнёй и было реализовано такое решение. Смысл его прост — посчитать факториал 3000 можно только увеличив глубину рекурсии допустим до 4000, а это в свою очередь одновременно увеличит и нашу последовательность, следовательно, антифакториал также будет найден! А сейчас, волшебным образом я сразу покажу функцию антифакториала!))

Теперь логика �� Сначала мы проверяем валидность данных, потом начинаем последовательно делить число, причем важно, что мы делим именно преобразованные во ”float” значения. Для того, чтобы понять смысл этого преобразования прямо в интерпретаторе разделить 8 на 3. Почему вы получаете 2 я расскажу как нибудь потом, для нас же важно точное значение. Разделите 8.0 на 3.0 и увидите разницу. На самом деле цикл работает довольно просто. Мы делим значение на 1, проверяем равно ли получившееся 1.0 или больше 1.0. Если значение не равно 1.0 и больше 1.0, то инструкция continue продолжает цикл, мы делим значение на 2 , проверяем etc. Если вдруг значение не равно 1.0, и при этом уже меньше 1.0, значит данное число не было факториалом и нам нужно выйти из цикла, возбудив ValueError . Мы выходим из цикла для того, чтобы попусту не заставлять python тратить ресурсы на прогон по всему циклу, что логично. Если же значение строго рано 1.0, то мы опять же выходим из цикла и возвращаем тот делитель, на котором этот выход произошел. Строго говоря, можно (и нужно!) еще сократить цикл — смысла делить на 1 тоже нет. Теперь можно потестировать наш antifactorial . К примеру:

Таким образом мы написали пару функций — прямую и обратную, которые помогут нам как посчитать факториал числа, так и выяснить факториалом какого числа является (если вообще является) другое число. Дальше будет проще, но интересней!

• Суперфакториал

Суперфакториал придумали в 1995 году Нейл Слоан и Саймон Плоуф (англ.) и определили они его как произведение факториалов. Иными словами,

Функция для нахождения суперфакториала элементарна до безобразия, я даже не буду особо распинаться:

Знакомо, не правда ли? По сути, это та же самая функция, что и факториал, но только умножение происходит не на x , а на factorial(x) !

• Обратный суперфакториал

Также элементарен и обратный суперфакториал:

Здесь мы делим в свою очередь не на число, а на факториал числа.

• Гиперфакториалы

Энтузиасты не остановились на суперфакториалах и в 2000 году Генри Боттомли (англ.) создал гиперфакториалы, которые являются произведением суперфакториалов. Я не буду впадать в маразм и функцию мне писать лень, но о произведении гиперфакториалов, произведении произведения гиперфакториалов etc. я умолчу ��

Функция гиперфакториала повторяет суперфакториал, только вместо умножения на factorial(x) мы умножаем на superfactorial(x) . Обратный гиперфакториал я предлагаю вам написать самостоятельно, это не составит вообще никакой сложности.

• Двойной факториал

Не намного более сложной задачей является написание функции двойного факториала. Сначала разберемся, что это собственно такое.

Двойным факториалом числа n (n!!) называется произведение всех натуральных чисел от 1 до n, имеющих ту де чётность, что и n.

Соответственно можно написать такую функцию:

Смысл такой же как и у обычного факториала, только с одной особенностью — шаг рекурсии не 1, а 2 (так как нам нужно идти строго по чётным или нечётным числам).

• Обратный двойной факториал

Обратный двойной факториал — это ненамного сложнее, чем обычный обратный факториал. Я реализовал её на мой взгляд не самым изящным способом, но пока нет желания как-то сокращать код. Основное отличие от обычных обратных факториалов в том, что мы должны делить не последовательно на 2, 3, 4,5 etc., но последовательно с шагом 2 и начинать деление либо с 2, либо с 3 в зависимости от чётности. Собственно реализация:

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

Тест на внимательность!

Если вы дочитали до сюда, то наверняка уже не раз нашли ошибки в коде. Нет? Что же, давайте тогда вычислим 0! и 1!. А теперь antifactorial(1) ! Именно! Мы совсем забыли об этой единице. Но давайте обратим на неё внимание теперь. Факториал, суперфакториал, гиперфакториал и двойной факториал нуля и единицы равен одному. Разумеется, нам необходимо научить наши функции возвращать значения, причем сразу два. Новичок начнет сразу переписывать все обратные функции, вводить эти конструкции ”если-то”. Мы — не новички!:-) Мы возьмем и напишем декоратор! Я сейчас не буду вдаваться в подробности о декораторах, этим на примере этого же модуля займусь завтра, когда у меня будет время, а сейчас просто напишу этот декоратор. Просто без комментариев:

Теперь перед всеми обратными функциями достаточно прописать инструкцию @constant и все будет в порядке!

На этом разрешите пока остановиться. В следующей части мы познакомимся с праймориалами и факторионами, а также научимся (если вдруг кто не умел) генерировать последовательности всех этих кракозябр. После же того, как мы закончим с математикой, мы преобразим наш код в нечто декорированное! ��