Znalezc ilosc rozwiazan rownania diofantycznego.

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
nivwusquorum
Użytkownik
Użytkownik
Posty: 93
Rejestracja: 31 maja 2007, o 17:53
Płeć: Mężczyzna
Lokalizacja: Chojnice
Podziękował: 1 raz
Pomógł: 3 razy

Znalezc ilosc rozwiazan rownania diofantycznego.

Post autor: nivwusquorum »

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:

Kod: Zaznacz cały

http://oeis.org/A073947


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.
Awatar użytkownika
fon_nojman
Użytkownik
Użytkownik
Posty: 1599
Rejestracja: 13 cze 2009, o 22:26
Płeć: Mężczyzna
Lokalizacja: Łódź
Podziękował: 68 razy
Pomógł: 255 razy

Znalezc ilosc rozwiazan rownania diofantycznego.

Post autor: fon_nojman »

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.}\)
Awatar użytkownika
Zordon
Użytkownik
Użytkownik
Posty: 4977
Rejestracja: 12 lut 2008, o 21:42
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 75 razy
Pomógł: 910 razy

Znalezc ilosc rozwiazan rownania diofantycznego.

Post autor: Zordon »

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.
ODPOWIEDZ