Matematyka.pl

Znaleźć ilość rozwiazań równania:
\(\displaystyle{ \frac{1}{x} + \frac{1}{y} = \frac{1}{n!}}\)
w zaleznosci od \(\displaystyle{ n}\). (x,y) są dodatnie calkowite.

Jakby ktos chociaz znalazl ciekawa obserwacje, albo relacje rekurencyjna, to bede bardzo wdzieczny.

Ja do tej pory zdazylem tylko ustalic ze:
- bardzo czesto zdaza sie ze jezeli (x,y) jest rozwiazaniem i x<y to \(\displaystyle{ x|y}\), ale nie jest to regula. Jesli juz \(\displaystyle{ nwd(x,y) \neq x}\) to z reguly bardzo maly czynnik je rozni.
- wydaje mi sie, ze to moze byc ten ciag: ale nie jestem pewien:


Z góry dzięki za wszelką pomoc!-- 28 sierpnia 2011, 08:42 --OK oto odpowiedz:
Jezeli \(\displaystyle{ n! = p_1^{\alpha_1}p_2^{\alpha_2}...p_n^{\alpha_n}}\) (rozklad na czynniki pierwsze). To odpowiedz to \(\displaystyle{ (2 \alpha_1 +1)(2 \alpha_2 +1)...(2 \alpha_n +1)}\). Jezeli kogos interesuje dokladne rozwiazanie to pisac. Jezeli kogos interesuje algorytmiczna strona implementacji tej odpowiedzi dla \(\displaystyle{ 1 \leq n \leq 10^6}\) (odpowiedz liczona mod 1000007), tez pisac. Jest calkiem ladna matematycznie.

Kombinował bym tak:
Przekształcamy do postaci \(\displaystyle{ x=\frac{n!y}{y-n!}}\) czyli licznik i mianownik mają wspólny dzielnik, można go przedstawić jako \(\displaystyle{ ab}\) gdzie \(\displaystyle{ a|n!, b|y}\) skąd także dostajemy, że \(\displaystyle{ b|n!, a|y.}\)

nivwusquorum pisze: Jezeli kogos interesuje algorytmiczna strona implementacji tej odpowiedzi dla \(\displaystyle{ 1 \leq n \leq 10^6}\) (odpowiedz liczona mod 1000007), tez pisac. Jest calkiem ladna matematycznie.

jesli da sie szybciej niz \(\displaystyle{ O(n\log(\log n))}\) to chętnie poczytam.