Witam,
Mam takie coś:
Niech \(\displaystyle{ F(1) = 2 \\ F(k+1) = 2^{F(k)}.}\)
Oblicz \(\displaystyle{ F(5)\ \mod\ 2009}\)
Poza tym, że nie bardzo widzę rozwiązanie tego, to jeszcze nie wiem co to jest to "duże ef".
Tak więc proszę o jakąś wskazówkę, ale i powiedzenie co to jest za funkcja.
Obliczenie modulo
- kerajs
- Użytkownik
- Posty: 8581
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3349 razy
Obliczenie modulo
Sądzę że F to zwykła funkcja zadana rekurencyjnie i o argumentach naturalnych.
\(\displaystyle{ F(2)=2 ^{F(1)}=2^2=4}\)
\(\displaystyle{ F(3)=2 ^{F(2)}=2^4=16}\)
\(\displaystyle{ F(4)=2 ^{F(3)}=2^{16}=65536}\)
\(\displaystyle{ F(5)=2 ^{F(4)}=2^{65536}}\)
Pozostaje Ci znaleźć:
\(\displaystyle{ 2^{65536} \mod 2009}\)
\(\displaystyle{ F(2)=2 ^{F(1)}=2^2=4}\)
\(\displaystyle{ F(3)=2 ^{F(2)}=2^4=16}\)
\(\displaystyle{ F(4)=2 ^{F(3)}=2^{16}=65536}\)
\(\displaystyle{ F(5)=2 ^{F(4)}=2^{65536}}\)
Pozostaje Ci znaleźć:
\(\displaystyle{ 2^{65536} \mod 2009}\)
Ostatnio zmieniony 2 lip 2014, o 17:06 przez Ponewor, łącznie zmieniany 1 raz.
Powód: Punkt 2.7 instrukcji LaTeX-a. Funkcje matematyczne należy zapisywać: sinus - \sin, logarytm - \log, logarytm naturalny - \ln itd.
Powód: Punkt 2.7 instrukcji LaTeX-a. Funkcje matematyczne należy zapisywać: sinus - \sin, logarytm - \log, logarytm naturalny - \ln itd.
-
- Użytkownik
- Posty: 1922
- Rejestracja: 26 mar 2012, o 18:52
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 695 razy
- Pomógł: 4 razy
Obliczenie modulo
Może przedstawię metodę jaką udało mi się policzyć (poprawnie).
Czy ktoś wskaże jakąś prostszą, elegantszą ?
Moja:
Z tw. Eulera mamy, że:
\(\displaystyle{ 2^{\phi(2009)} \equiv_{2009} 1}\)
Podniesiemy do \(\displaystyle{ 39}\) potęgi stronami:
\(\displaystyle{ 2^{1680 \cdot 39} \equiv_{2009} 1}\)
\(\displaystyle{ 2^{65520} \equiv_{2009} 1}\)
Widać, że nie brakuje dużo, potrzebujemy jedynie pomnożyć stronami razy \(\displaystyle{ 2^{16}}\).
Ale wiadomo, że (można policzyć "ręcznie"):
\(\displaystyle{ 2^{11} \equiv_{2009} 39}\)
\(\displaystyle{ 2^{16} \equiv_{2009} 39 \cdot 32}\)
Ostatecznie:
\(\displaystyle{ 2^{65536}\equiv_{2009} 1248}\)
Czy ktoś wskaże jakąś prostszą, elegantszą ?
Moja:
Z tw. Eulera mamy, że:
\(\displaystyle{ 2^{\phi(2009)} \equiv_{2009} 1}\)
Podniesiemy do \(\displaystyle{ 39}\) potęgi stronami:
\(\displaystyle{ 2^{1680 \cdot 39} \equiv_{2009} 1}\)
\(\displaystyle{ 2^{65520} \equiv_{2009} 1}\)
Widać, że nie brakuje dużo, potrzebujemy jedynie pomnożyć stronami razy \(\displaystyle{ 2^{16}}\).
Ale wiadomo, że (można policzyć "ręcznie"):
\(\displaystyle{ 2^{11} \equiv_{2009} 39}\)
\(\displaystyle{ 2^{16} \equiv_{2009} 39 \cdot 32}\)
Ostatecznie:
\(\displaystyle{ 2^{65536}\equiv_{2009} 1248}\)
- leszczu450
- Użytkownik
- Posty: 4414
- Rejestracja: 10 paź 2012, o 23:20
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Podziękował: 1589 razy
- Pomógł: 364 razy
Obliczenie modulo
matinf, jak dla mnie Twoje rozwiązanie jest bardzo eleganckie : ) Kilka linijek prostych przejść.