1/x + 1/y = 1/N (факториал)

Вопрос в том, как решить 1/x + 1/y = 1/N! (N факториал). Найдите число значений, удовлетворяющих x и y при больших значениях N.

Я решил проблему для относительно небольших значений N (любой N!, который будет вписываться в длинный). Итак, я знаю, что решаю проблему, получив все делители (N!) ^ 2. Но это начинает терпеть неудачу, когда (N!) ^ 2 не вписывается в длинный. Я также знаю, что могу найти всех делителей N! суммируя все простые множители каждого числа, факторизованные в N!. То, что мне не хватает, - это то, как я могу использовать все числа в факториале, чтобы найти значения x и y.

РЕДАКТИРОВАТЬ: не искать "ответ" только один намек или два.

Ответы

Ответ 1

Вот ваш намек. Предположим, что m = p ₁^{k ₁} & middot; p ₂^{k ₂} & middot;... & middot; р <суб > Jсуб > ^{к <суб > Jсуб >}. Каждый сомножитель m будет иметь от 0 до k ₁ факторов p ₁, от 0 до k ₂ факторов p ₂ и т.д. Таким образом, существуют (1 + k ₁) & middot; (1 + k ₂) & middot;... & middot; (1 + k _j) возможных делителей.

Итак, вам нужно выяснить простую факторизацию n! ².

Обратите внимание, что это будет считаться, например, ¹/₆= ¹/₈ + ¹/₂₄ как другая пара из ¹/₆= ¹/₂₄ + ¹/₈. Если порядок не имеет значения, добавьте 1 и разделите на 2. (Деление на 2 состоит в том, что обычно два делителя приведут к одному и тому же ответу, с добавлением 1 для исключения, что делитель n! Приводит к паре, которая соединяется с самим собой.)

Ответ 2

Задача: найти счетчик факторов (N!) ^ 2.

Советы:

1) Вам действительно не нужно вычислять (N!) ^ 2, чтобы найти его первичные факторы. Зачем? Скажем, вы найдете основную факторизацию N! как (p1 ^ k1) x (p2 ^ k2).... (pi ^ ki) где pj - простые числа, а kj - показатели.

Теперь число факторов N! так же очевидна, как (k1 + 1) x (k2 + 1) x... x (ki + 1).

2) Для (N!) ^ 2 указанное выше выражение будет, (2 * k1 + 1) * (2 * k2 + 1) *.... * (2 * k1 + 1) который, по сути, мы ищем.

Например, давайте возьмем N = 4, N!= 24 и (N)) 2 = 576; 24 = 2 ^ 3 * 3 ^ 1; Следовательно, нет множителей = (3 + 1) * (1 + 1) = 8, viz {1,2,3,4,6,8,12,24} При 576 = 2 ^ 6 * 3 ^ 2 это (2 * 3 + 1) * (2 * 1 + 1) = 21;

3) В принципе вам нужно найти кратность каждого числа n = N здесь.

Пожалуйста, поправьте меня, если я ошибаюсь где-то здесь.

Ответ 3

Это больше для математики, чем для программирования. Ваше уравнение означает xy = n! (X + y).

Пусть c = gcd (x, y), поэтому x = cx ', y = cy' и gcd (x ', y') = 1. Тогда c ^ 2 x 'y' = n! c (x '+ y'), поэтому cx'y '= n! (x' + y ').

Теперь, когда x 'и y' взаимно просты и не могут быть делящимися, x '+ y', c должно быть. Итак, c = a (x '+ y'), что дает ax'y '= n!.

Чтобы решить вашу проблему, вы должны найти все два взаимно простых делителя n!, каждая пара которых даст решение как (n! (x '+ y')/y ', n! (x' + y ' )/х ').

Ответ 4

Пусть F (N) - число комбинаций (x, y), которые удовлетворяют вашим требованиям.

F (N + 1) = F (N) + # (x, y), которые удовлетворяют условию для N + 1 и по крайней мере один из них (x или y) не делится N + 1.

Интуиция здесь для всех комбинаций (x, y), которые работают для N, (x * (N + 1), y * (N + 1)), будет работать для N + 1. Кроме того, если (x, y) является решением для N + 1 и оба делятся на n + 1, то (x/(N + 1), y/(N + 1)) является решением для N.

Теперь я не уверен, как трудно найти # (x, y), которые работают для (N + 1), и по крайней мере один из них не делится на N + 1, но должен быть проще, чем решать исходные проблема.

Ответ 5

Теперь кратность или показатель для Prime p в N! можно найти по следующей формуле: \ Показатель P в (N!) = [N/p] + [N/(P ^ 2)] + [N/(P ^ 3)] + [N/(P ^ 4)] +...............

                 where [x]=Step function  E.g. [1.23]=integer part(1.23)=1

например. Показатель 3 в 24!= [24/3] + [24/9] + [24/27] +... = 8 +2 +0 + 0 +.. = 10 Теперь вся задача сводится к определению простого числа ниже N и нахождения его экспоненты в N!