Сколько делителей у числа 100!+1?

[Ktina]

Сколько делителей у числа

$$100!+1\quad \text{?}$$

(вот источник, задача 31)

Это как раз тот случай, когда так и подмывает написать "много".

(Оффтоп)

Как сказал один киногерой, всё, что мы делаем, возвращается к нам.
Три с половиной года тому назад я помогала делать уроки одному третьекласснику (а заодно и его маме). Желая, по всей видимости, ознакомить читателя с понятием "бесконечность", автор учебника предложил задачу, в которой спрашивалось что-то вроде "сколько вообще существует острых углов?".
Ну так мама этого третьеклассника и говорит ему, мол, напиши "много". Тут я вскипела и говорю "ты ещё напиши "до%%%", очень математичный ответ получится!". Мы тогда вдрызг поссорились с мамой этого третьеклассника, упрямо продолжавшей утверждать, что для такого маленького ребёнка ответ "много" -- это нормально.

Или я в упор не вижу очевидного решения?

[Sonic86]

pdf-ка писал(а):

Решите в натуральных числах уравнение $xy=31$

Стопудово опечатка. PARI/GP уже 5 минут думает.
Число составное.

[Ktina]

Sonic86 в сообщении #756134 писал(а):

pdf-ка писал(а):

Решите в натуральных числах уравнение $xy=31$

Стопудово опечатка. PARI/GP уже 5 минут думает.
Число составное.

А 1 не натуральное уже число?

[vorvalm]

$100!+1\equiv 0 \pmod {101}$

[Shadow]

Ktina, давайте предположим, что Sonic86 знает является ли 1 натуральным. Тогда его коментар:

Sonic86 в сообщении #756134 писал(а):

Стопудово опечатка. PARI/GP уже 5 минут думает.
Число составное.

скорее всего относится к зад.31

Мне тоже кажется, что в условии что-то пропущено. Скорее всего имелось ввиду двуцифренных делителей или что-то такое. Общий уровень сложности остальных задач (приведенный пример Sonic86 особо умиляет) другое не предполагает, вкл. знание теоремы Вильсона.

[Sonic86]

PARI/GP писал(а):

$$100!+1= 101\cdot 14303\cdot 149239\cdot 350433007170616328107072379\cdot P_5 $$

Shadow в сообщении #756140 писал(а):

Тогда его коментар:... скорее всего относится к зад.31

да, я не очень понятно выразился

[Ktina]

Shadow в сообщении #756140 писал(а):

... Скорее всего имелось ввиду двуцифренных делителей или что-то такое. ...

Это Вы так красиво пошутили?
$100!$ делится на каждое из двузначных чисел. Значит, $100!+1$ не делится ни на одно из них.

[Ms-dos4]

Sonic86 в сообщении #756134 писал(а):

Стопудово опечатка. PARI/GP уже 5 минут думает.
Число составное.

Ну не знаю, математика находит кол-во делителей довольно быстро. Но вот как найти их без компа вопрос...

[Ktina]

Ms-dos4 в сообщении #756147 писал(а):

Ну не знаю, математика находит кол-во делителей довольно быстро. Но вот как найти их без компа вопрос...

Даже Альфа не справилась.

[Sonic86]

Ms-dos4 в сообщении #756147 писал(а):

Ну не знаю, математика находит кол-во делителей довольно быстро.

Не понял. Разве существует способ расчета числа делителей быстрее, чем через факторизацию числа?

Ms-dos4 в сообщении #756147 писал(а):

Но вот как найти их без компа вопрос...

Ага, классический в то же время и вполне современный

[Ms-dos4]

Sonic86

Цитата:

Не понял. Разве существует способ расчета числа делителей быстрее, чем через факторизацию числа?

Нет, но алгоритмы факторизации есть разные + конечно время зависит от проца.

Цитата:

Ага, классический в то же время и вполне современный

Я имел ввиду только применительно к этому заданию.

Ktina

Цитата:

Даже Альфа не справилась.

Отправил в ЛС

[Shadow]

Ktina в сообщении #756145 писал(а):

Это Вы так красиво пошутили?
$100!$ делится на каждое из двузначных чисел. Значит, $100!+1$ не делится ни на одно из них.

Вполне прилично для 6-го класса. Олимпиада находится в разделе ЦОД-2010/2012-Задачи-6 класс. Кстати, что означает "по дорожкам"? Там стрелочки какие-то. Возможно, ребенок решает не все задачи, а сам себе выбирает путь? Тогда цель - обойти задачу 31

[Ktina]

Shadow в сообщении #756157 писал(а):

Кстати, что означает "по дорожкам"? Там стрелочки какие-то. Возможно, ребенок решает не все задачи, а сам себе выбирает путь? Тогда цель - обойти задачу 31

Вы будете смеяться, но я тоже об этом подумала. Возможно, задача 31 изначальна задумывалась в виде неподъёмной.

[Aritaborian]

Мне Альфа тоже кукиш показала, но не в том смысле, что не справилась, а что «standard computational time exceeded». Mathematica же считает уже десять минут.

[tbutton]

Ktina

Цитата:

Даже Альфа не справилась.

Почему же? Всё нормально
$ factor(100! + 1) = 9.33262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000... × 10^157$ и можно ещё цифр попросить :)