Ciekawe zadanie

Treść: Znaleźć najmniejszą liczbę złożoną n taką, że n dzieli (2^{n)-2 oraz n dzieli (3}n)-3.

Poniewaz jest to zadanie z jeszcze trwajacego konkursu, nie zamieszczamy kodu tutaj :] Ale moze ktos chcialby sie z nim zmierzyc ;)

A jesli nikt nie ma ochoty to moze znacie odpowiedzi na kilka pytan:
Sprawdzilem wszystkie liczby zlozone do 99 999 999, nic. Tylko liczby pierwsze spelniaja to rownosc, czy jest to mozliwe ze taka liczba istenieje? Czy mozna dowiesc matematycznie ze to jest nie mozliwe? Jesli tak prosze o wskazowke :]

Jesli ktos ma jakies pomysly na optymalizacje wyszukiwania to tez bardoz chetnie :]

W niecałe 7 minut sprawdziłem ten sam przedział i znalazłem 492 takie liczby.
Z małego twierdzenia Fermata wynika, że jeżeli N jest liczbą pierwszą to dla dowolnego całkowitego P,
P^{N=P (mod N) czyli N jest dzielnikiem P}N-P.
Niestety, dla P<N własność tą mają nie tylko liczby pierwsze (liczby Carmichael'a)
Wniosek? Sprawdź swój program.

Tj. (2^n)-2 i (3</sup>n)-3

skeisym napisał(a)

Tj. (2^n)-2 i (3</sup>n)-3
Przecież nawiasy są zbędne (potęgowanie ma wyższy priorytet niż odejmowanie).

Do 100 mln. jest tylko 255 liczb Carmichael'a,
my znajdziemy ich więcej ponieważ sprawdzamy tylko dla p równego 2 i 3.

Sprawdź liczbę 2701 (jest to pierwsza liczba spełniająca Twoje warunki nie będąca liczbą Carmichael'a).
(Nie jest to najmniejsza liczba spełniająca warunki.)

W ciągu sekundy znalazłem 68 liczb spełniających założenia, największa to 873181.

Korzystajac z Twojej zyczliwosci mozesz mi powiedziec jak realizujesz operacje na takich duzych liczbach ? 3^2701 w c++ wykracza juz poza typ unsigned long long int :/ Czy konieczne jest napisanie samemu obslugi tak duzych liczb?
Wielki dzeki za zainteresowanie :)

tak - musialbys to napisac sam, albo skorzystac z jakiejs gotowej zewnetrznej biblioteki od bardzo duzych liczb calkowitych. ale dowcip w tym, ze zeby sprawdzic czy N dzieli 3^{N-3 wcale nie trzeba wykonywac faktycznego obliczenia wartosci 3}N :)

Jest właśnie tak jak pisze Pierzasty Wąż :)
Interesuje nas sprawdzenie czy (P^N) % N == P. "%" to reszta z dzielenia (modulo).
Normalnie potęgujemy pętlą (N-1 "obrotów") a wynik okropnie szybko rośnie.
Lecz przy takich modularnych obliczeniach po każdym mnożeniu wynik bierzemy modulo.
Należy pamiętać, że jeżeli N jest liczbą 32-bitową, wynik mnożenia ma 64 bity!
W naszym przykładzie mnożymy maksymalnie przez 3, jeżeli N<100'000'000 wystarczą 32 bity.

long unsigned int w=1;
for (k=1; k<=n; ++k)
          w= (w*p) % n;
if (w==p) .....

To jest prosty sposób potęgowania, lecz da się go ogromnie usprawnić,
tu pętla kręci się N razy, a wystarczy tylko log2(N), zamiast np. miliard razy wystarczy kilkadziesiąt.

Ok, a wiec 561, bedace Liczba Carmichaela spelnia warunki, i teraz tylko wystarcyz ze sprawdze czy od 341 do 561 istenieje jeszcze jakeis inne liczby zlozone spelniace warunki zadania? Od 341 poniewaz jest najmniejsza liczba pseudopierwsza fermata o podstawie 2 ? Bardzo dziekuje za pomoc :)

Interesuje nas najmniejsza liczba występująca na obu listach (Sloane's A005935, oraz A001567)

No to wlasciwie prawda jest taka ze nie ma co pisac... ;] Heh problem zostal teraz juz rozwiazany, a c++ do tego mi sie nie przyda no przeciez nie wysle kodu ktory szuka najmniejszego wspolnego elementu tablic ;P
W kazdym razie dziekuje za pomoc :) Ciekawi mnie tylko czemu wg. kalkulatora (programu komputerowego) 561|3^561-3 pewnie liczby sa juz za duze :]

Jeszce raz dziekuje za wlozony czas :)

int main(){
cout << "Szukana liczba jest 1105...";
system("pause");
}
:P no skrobne jakies uzasadnienie, chyba zeby sztucznie szukac tych liczb i tak znajac wynik ;/

Ale że zadanie jest z informatyki a nie matematyki czy Googlowania trzeba to zrobić tak jakby się o tym nie wiedziało.
Należy sensownie zapisać:

• testowanie pierwszości, (może lepiej sito Eratostenesa)
• potęgowanie,
  Wiedzieć, że:
• (P^{N-P) % N==0 to prawie to samo co P}N % N==P
• w potęgowaniu można resztę z dzielenia wykonywać w każdym kroku (ab)%n == [(a%n)(b%n)] % n
  </u></u>

Xitami mozesz mi powiedziec jeszce tylko jedna rzecz, dlaczego 561 wg. mojej funkcji ktora jak sadze dziala poprawnia tak jak zasugerowales na podstawie kongruencji, tj. 561 spelnia warunki zadania chociaz nie jest wymienione wsrod liczb pseudopierwszych w opracowaniu: http://www.research.att.com/~njas/sequences/A001567

A funkcja reszta wyglada nastepujaco:
int reszta(int liczba, int wykladnik, int dzielnik){
wynik=1;
for(int i=0; i < wykladnik; i++){
wynik=(wynik*liczba)%dzielnik;
}
return wynik;
}

Rozwiązaniem twojego zadania jest oczywiście 561.
A zamieszanie powstało z winy mojej i pewnej niekonsekwencji w źródłach. Sorki.
Pseudopierwsze to takie nieparzyste liczby złożone, które spełniają małe twierdzenie Fermata,
czyli P^N-P=0 (mod N), ale... dla takich P które nie są dzielnikiem N (P i N są względnie pierwsze)
co prowadzi do formuły P^(N-1)=1 (mod N). I tak to teraz jest określane i takie liczby znajdują się na podanych listach.
Łatwo widać, że 3 jest dzielnikiem 561 (5+6+1 jest podzielne przez 3), więc liczba ta nie znajduje się na A001567.

Co do funkcji reszta, wynik=liczba; for(int i=1; i < wykladnik... tak chyba trochę ładniej,
ale warto popracować jeszcze nad tym, zobacz np. tu:
http://pl.wikipedia.org/wiki/Algorytm_szybkiego_pot%C4%99gowania

Heh dziekuje bardzo :) popracuje troszke jeszce nad tym programem :] A zeby bylo smieszniej spalil mi sie zasilacz ( mam nadzieje ze tylko on ), na szczescie istnieje 2 komputer ale pisze od nowa :) Cale szczescie ze to malutki program z zrodlem na mniej niz 80 linijek :]
Jeszcze raz dziekuje bardzo za pomoc i pozdrawiam :)