Антифакториал

[ewert]

Spook писал(а):

ewert писал(а):

Более того, тупой перебор натурального ряда статистически в любом случае эффективнее, т.к. в большинстве случаев проверка будет очень быстро обрываться.

Вы имеете ввиду просто последовательное деление?

почему именно я, с этого вроде ещё ИСН начал в самом что ни на есть втором посте этой ветки, ну и потом другие товарищи

[Spook]

Ну я к этому тоже подхожу, просто заинтересовали и другие идеи.

[Бодигрим]

ИМХО в случае равномерно распределенных входных данных последовательное деление - наилучший метод.

[Батороев]

Spook писал(а):

Батороев писал(а):

... при помощи указанного выше факториала можно проверить все числа от $ 200000$ до $600000$.
Если данный факториал имеет остаток по модулю заданного числа, отличный от нуля, то это число - простое.
Если Вы отдельно введете проверку, делится ли число на $3$, то диапазон можно увеличить до $ 1000000$ и т.д.

Интересная идея, оценить бы временную сложность и объем памяти.

А никакой собственно идеи здесь и нет.
Просто, рассматривается дробь в числителе которой все числа до $ 200000 $, а в знаменателе - либо составное, делители которого меньше $ 200000 $ и которые сократятся с числителем, либо простые, превосходящие $ 200000 $, которые, естественно, дадут ненулевой остаток.
Удобно то, что готовый факториал используется для проверки большого количества чисел.

[PAV]

Я все-таки не понимаю - Вы планируете программно реализовывать арифметику работы с большими числами или нет? Если да, то умножать (т.е. искать факториал или сокращенный факториал) будет значительно проще, чем делить.

Если нет (т.е. заранее закладываемся на не очень большие числа) - тогда практически любой метод хорош. Количество чисел $n$, факториалы которых укладываются в 64-битное целое число, сравнительно невелико, их можно просто заранее посчитать и сравнивать проверяемое число с таблицей.

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

Добавлено спустя 8 минут 3 секунды:

Spook в сообщении #136740 писал(а):

В принципе получается, что мы вибираем меньшего кандидата и все-таки считаем полностью его факториал?

Нет. Мы определили степень двойки, которая входит в проверяемое нами число (обозначим ее $z$). Мы также умеем по заданному числу $n$ вычислять степень двойки, которая входит в $n!$. Мы также знаем, что эта степень не больше самого числа $n$. Т.е. берем $n=z$ и считаем не факториал $n$, а степень двойки в $n!$. Пока эта степень меньше наблюдаемой $z$, увеличиваем $n$. Если мы в точности числа $z$ не получили, то точно не факториал. Если же при некотором $n$ степень совпала (это может быть только на четном), то остается два кандидата - $n$ и $n+1$.

Можно также попробовать совместить это со следующей идеей: с помощью формулы Стирлинга оценить порядок числа $n!$ (например, количество цифр в его двоичном представлении). Для полученных двух кандидатов проверить порядок с тем, который наблюдается. По моим представлениям, признак степени двойки и признак порядка всего числа довольно ортогональны, поэтому эти два (достаточно простых) критерия помогут отсеивать много не-факториалов.

[Spook]

PAV, да, планируется работа с длинными числами. Основные арифметические операции реализовал. По поводу двоичного представления. Использование большего основания системы счисления тоже позволяет увеличить эффективность, уменьшая число цифр, необходимых для представления каждого числа. Хотя я не уверен пока, что же лучше. Как Вы правильно заметили, для двоичного представление

PAV писал(а):

... достаточно элементарно и быстро определяется число нулей, на которые оканчивается число, т.е. макисмальная степень двойки.

PAV писал(а):

Мы определили степень двойки, которая входит в проверяемое нами число (обозначим ее $z$). Мы также умеем по заданному числу $n$ вычислять степень двойки, которая входит в $n!$. Мы также знаем, что эта степень не больше самого числа $n$. Т.е. берем $n=z$ и считаем не факториал $n$, а степень двойки в $n!$. Пока эта степень меньше наблюдаемой $z$, увеличиваем $n$. Если мы в точности числа $z$ не получили, то точно не факториал. Если же при некотором $n$ степень совпала (это может быть только на четном), то остается два кандидата - $n$ и $n+1$.

Возможно, это оптимальный метод.

PAV писал(а):

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

ортогональные числа = независимые? (На всякий случай, теории чисел не изучал)

[Бодигрим]

Цитата:

ортогональные числа = независимые?

Так некорректно говорить: числа не бывают зависимыми или независимыми. Видимо PAV хотел сказать, что признак степени двойки и признак порядка всего числа как случайные величины над вероятностным пространством натуральных чисел независимы.

[PAV]

Термин "ортогональные признаки" здесь не имеет определенного математического смысла. Это жаргон, который означает, что эти признаки существенно "разные". Совместное их использование может быть на порядок эффективнее, чем использование только одного, для задачи отсечения "ложных" факториалов.

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

А по поводу основания системы счисления - разумеется, при грамотной реализации, фактически арифметические действия производятся не в двоичной системе, а в системе с основанием, например, $2^{16}$ или $2^{32}$.

[Spook]

Ну тогда вроде все. Спасибо всем за советы, буду пробовать.

[Евгений Машеров]

Spook
Последовательно вычислять факториалы 1,2,3... N.