Liczba 113
jest pierwszą liczbą pierwszą, której długość 3
jest liczbą pierwszą, suma cyfrowa 5 = 1 + 1 + 3
jest liczbą pierwszą, a produkt cyfrowy 3 = 1 * 1 * 3
jest liczbą pierwszą.
Liczba pierwsza, która ma te 3 właściwości, będzie nazywana najwyższą liczbą pierwszą . Liczby pierwsze 11117
i 1111151
inne przykłady.
Cel
Napisz program, który może znaleźć największą możliwą liczbę pierwszą w niespełna godzinę na przyzwoitym nowoczesnym komputerze osobistym (takim jak preferowana specyfikacja tutaj ).
Nie powinieneś po prostu dać nam dużej najwyższej liczby. Musisz pokazać nam swój proces wyszukiwania za pomocą kodu, który faktycznie działa. Możesz opierać się na rozwiązaniach swoich lub innych osób, ale pamiętaj, aby dać im uznanie. Wspólnie staramy się znaleźć największą najwyższą liczbę pierwszą na zwykłym komputerze w ciągu godziny.
Punktacja
Wygrana, która znajdzie największą najwyższą liczbę pierwszą. Jeśli okaże się, że istnieje ostatecznie wiele najwyższych liczb pierwszych, wygrywa pierwsze podporządkowanie, które generuje najwyższą liczbę pierwszą.
(Jeśli możesz matematycznie udowodnić, że istnieje albo nie ma nieskończenie wiele najwyższych liczb pierwszych, dam ci 200 nagród za to tylko dlatego :)))
Detale
- Możesz użyć dowolnego źródła do wygenerowania liczb pierwszych (np. Internetu).
- Możesz użyć probabilistycznych metod testowych.
- Wszystko jest w bazie 10.
- Zero i jeden NIE są uważane za pierwsze.
- Liczby pierwsze zawierające
0
mają tak cyfrowy produkt,0
że oczywiście nie mogą być najwyższe. Aby strona była mniej zaśmiecona, umieść duże (ponad 100 cyfr) najwyższe liczby pierwsze w postaci:
{[number of 1's before the prime digit]}[prime digit]{[number of 1's after the prime digit]}
Więc
1111151
może być wyrażona jako{5}5{1}
.
źródło
Odpowiedzi:
Perl, 15101 cyfr, {83} 7 {15017}, 8 minut. Max znaleziono: 72227 cyfr
Korzystanie z mojego modułu Math :: Prime :: Util i jego zaplecza GMP . Posiada szereg testów złożoności, w tym is_prob_prime () z testem ES BPSW (nieco bardziej rygorystycznym niż ispseudoprime Pari), is_prime (), który dodaje jeden losowy MR, i is_provable_prime (), który uruchomi BLS75 T5 lub ECPP. Przy tych rozmiarach i typach wykonanie dowodu zajmie dużo czasu. Wrzuciłem kolejny test MR w sub weryfikatorze pedantycznym. Czasy na Core2 E7500, który zdecydowanie nie jest moim najszybszym komputerem (zajmuje to 2,5 minuty na moim i7-4770K).
Jak zauważa Tim S., moglibyśmy szukać większych wartości, aż do momentu, gdy pojedynczy test zajmie godzinę. Przy ~ 15000 cyfr na tym E7500 potrzeba około 26 sekund na test MR i 2 minuty na pełny is_prime (podział próbny plus podstawowa 2 MR plus ES Lucas plus jedna losowa podstawowa MR). Mój i7-4770K jest ponad 3 razy szybszy. Próbowałem kilku rozmiarów, głównie widząc, jak to zrobiło na wynikach innych ludzi. Próbowałem 8k, 20k i 16k, zabijając każde po ~ 5 minutach. Następnie próbowałem 15k w progresji na ~ 10m każdy i miałem szczęście na czwartym.
Testy PRP OpenPFGW są z pewnością szybsze po około 4000 cyfr i znacznie szybsze w zakresie 50k +. Jego test ma jednak sporo fałszywych wyników pozytywnych, co czyni go doskonałym testem wstępnym, ale nadal chcielibyśmy zweryfikować wyniki za pomocą czegoś innego.
Można to zrównoleglić za pomocą wątków perla lub przy użyciu MCE podobnego do równoległych przykładów Fibonacciego w module.
Czas i wyniki na bezczynnym komputerze i7-4770K z pojedynczym rdzeniem:
Aby uzyskać wynik 32 000 cyfr, uruchomiłem 6 skryptów działających jednocześnie z każdym kolejnym argumentem zaczynającym się od 32 000. Po 26,5 minutach jeden skończył się z wyświetlonym wynikiem 32063 cyfr. Za 57k pozwalam kolejnym skryptom uruchamiać 6 jednocześnie na godzinę z przyrostem wejściowym 500, aż wynik 57k powróci za 57 minut. 72-cyfrowy wynik został znaleziony przez wykonanie kolejnych liczb pierwszych od 70k w górę, więc na pewno nie został znaleziony w ciągu godziny (chociaż kiedy już wiesz, od czego zacząć, to jest).
Scenariusz:
źródło
gmpy2
i PyPy zmy_math
): codepad.org/aSzc0esTforprimes { ...do stuff... } 1e7;
10-krotnie szybsze (podziękowania dla Pari / GP za wiele świetnych pomysłów). Zawsze doceniam opinie, więc daj mi znać, jeśli coś nie działa tak, jak chcesz.Python 2.7 na PyPy, {2404} 3 {1596} (~ 10 ^ 4000)
Znalazłem go około 50 minut po uruchomieniu od 4000. Dlatego oszacowałbym, że jest to górna granica tego podejścia do kodu.
Zmiana: zauważyłem, że niektóre długości wydają się bardziej owocne dla generowania tego rodzaju liczby pierwszej niż inne, dlatego postanowiłem sprawdzić tylko 50 losowych lokalizacji cyfry, która nie jest 1 zamiast wszystkich możliwych lokalizacji, przed przeniesieniem na. Nie jestem do końca pewien, czy poprawi to wydajność lub czy 50 jest poprawne, ale zobaczymy.
Lista możliwości jest generowana na podstawie faktu, że aby spełniony był wymóg dotyczący produktu, liczba musi być równa wszystkim oprócz liczby pierwszej. Ponadto liczba pierwsza nie może być równa 2 ze względu na stosunek sumy i długości, a suma cyfrowa nie może być podzielna przez trzy, co daje wymaganie% 3.
is_prime pochodzi z http://codepad.org/KtXsydxK , napisane przez @primo
Uwaga: ta funkcja is_prime jest tak naprawdę pseudopierwszym testem Baillie-PSW, ale nie ma znanych przeciw-przykładów, więc nie będę się martwił o to rozróżnienie.
źródło
is_very_very_very_very_very_very_very_probably_prime()
...PARI / GP, 4127 cyfr
(10 4127 -1) / 9 + 2 * 10515
Jest to dość proste wyszukiwanie: sprawdź tylko długości liczb pierwszych, a następnie oblicz możliwe liczby pierwsze do użycia, a następnie powtórz wszystkie możliwości. Specjalnie opisałem typowe przypadki, w których do użycia jest 0 lub 1 odpowiednia liczba pierwsza.
Obliczenie zajęło 36 minut na jednym rdzeniu dość starej maszyny. Jestem pewien, że nie byłoby problemu ze znalezieniem takiej liczby ponad 5000 cyfr w ciągu godziny, ale jestem też niecierpliwy.
Lepszym rozwiązaniem byłoby użycie dowolnego rozsądnego języka do zrobienia wszystkiego poza najbardziej wewnętrzną pętlą, a następnie zbudowanie pliku abc dla pierwszej formy, który jest zoptymalizowany dla tego rodzaju obliczeń. Powinno to umożliwić zwiększenie obliczeń do co najmniej 10 000 cyfr.
Edycja : wdrożyłem opisane powyżej rozwiązanie hybrydowe, ale na mojej starej maszynie nie mogę znaleźć pierwszego terminu z> = 10 000 cyfr w mniej niż godzinę. O ile nie uruchomię tego na czymś szybszym, będę musiał zmienić cel na mniej wzniosły.
źródło
Mathematica 3181 cyfr
Aktualizacja: W moim pierwszym zgłoszeniu wystąpiły poważne błędy. Byłem w stanie poświęcić trochę czasu na sprawdzenie wyników dla tego. Dane wyjściowe są sformatowane jako lista cyfr. Dzięki temu można łatwo sprawdzić każdy z warunków.
Przykład
To był mój pierwszy test, poszukiwanie rozwiązania z 3181 cyframi. Pierwszy przypadek znaleziono w 26 sekund.
Przejdźmy do rozumowania. Następnie przejdziemy do samego programu.
Zacznijmy, tak jak ja, „jaka jest czwarta liczba pierwsza?” Czy możemy znaleźć rozwiązanie z tyloma cyframi (3181)?
Numer można znaleźć, łącząc cyfry.
Zamiast wyświetlać, zamiast tego możemy zapytać, jakie są cyfry i gdzie się znajdują.
Oznacza to, że było 3180 wystąpień cyfry 1 i jedno wystąpienie cyfry 7.
Na której pozycji jest cyfra 7?
Cyfra 7 to 142. cyfra. Wszystkie pozostałe to 1.
Oczywiście iloczyn cyfr musi być liczbą pierwszą, a mianowicie 7.
A suma cyfr jest również liczbą pierwszą.
I wiemy, że liczba cyfr jest liczbą pierwszą. Pamiętaj, że wybraliśmy 450. pierwszą, a mianowicie 3118.
Tak więc wszystkie warunki zostały spełnione.
źródło
4002 * 1 + 7 = 4009
a nie 4003 zgodnie ze specyfikacją.Python 2.7, 6217 cyfr: {23} 5 {6193} 6 minut 51 sekund
Pracowałem nad własną wersją i byłem rozczarowany, widząc, że @issacg pobił mnie do sedna bardzo podobnym podejściem, aczkolwiek z is_ (bardzo_prawdopodobnie) _prime (). Widzę jednak, że mam pewne znaczące różnice, które skutkują lepszą odpowiedzią w krótszym czasie (gdy używam również is_prime). Aby to wyjaśnić, kiedy zaczynam od 4000, uzyskuję lepszą 4001-cyfrową odpowiedź ({393} 7 {3607}) w zaledwie 26 minut i 37 sekund przy użyciu standardowego interpretera Pythona (również w wersji 2.7), a nie PyPy wersja. Poza tym nie sprawdzam liczb na miejscu. Wszyscy kandydaci są sprawdzani.
Oto główne ulepszenia:
Użyj generatora liczb pierwszych ( https://stackoverflow.com/questions/567222/simple-prime-generator-in-python/568618#568618 ), aby utworzyć listę liczb pierwszych do sprawdzenia i (jego wersja „małych liczb pierwszych”) i do generowania dopuszczalnych długości liczb.
Chcemy spędzać czas na szukaniu największej liczby pierwszej o danej długości, a nie najmniejszej, dlatego najpierw sprawdzam możliwie największe liczby, a nie najmniejsze. Następnie, gdy zostanie znaleziony, możemy natychmiast przejść do następnej długości.
EDYCJA: Teraz z wieloprocesowym przetwarzaniem
Jest to znacząca zmiana w stosunku do poprzednich wersji. Wcześniej zauważyłem, że moja 8-rdzeniowa maszyna prawie nie działa, więc postanowiłem spróbować swoich sił w wieloprocesowym przetwarzaniu w Pythonie (pierwszy raz). Wyniki są bardzo miłe!
W tej wersji odradza się 7 procesów potomnych, które chwytają „zadanie” z kolejki potencjalnych możliwości (num_length + odpowiednie cyfry). Przebijają się, próbując różnych [7,5,3] pozycji, aż znajdzie jedną. Jeśli tak, informuje proces główny o nowej najdłuższej znalezionej długości. Jeśli dzieci pracują na długości num_l, która jest krótsza, po prostu za kaucją idą do następnej długości.
Rozpocząłem ten bieg z 6000 i nadal działa, ale jak dotąd jestem bardzo zadowolony z wyników.
Program nie zatrzymuje się jeszcze poprawnie, ale dla mnie nie jest to wielka sprawa.
Teraz kod:
źródło
my_math
może również służyć do generowania listy liczb pierwszych, à lawhile prime < 20006: prime = next_prime(prime)
. Wydaje się być około 3 razy szybszygen_primes
i znacznie wydajniejszy.C, GMP - {7224} 5 {564} = 7789
Uznanie dla @issacg i was wszystkich za inspiracje i triki.
A także mistrzowskie pytanie zadające @ Calvin's Hobbies dla tego pytania.
Skompilować:
gcc -I/usr/local/include -o p_out p.c -pthread -L/usr/local/lib -lgmp
Jeśli masz ochotę przekazać swoją moc obliczeniową lub jesteś ciekawy wydajności, skopiuj kod i skompiluj. ;) Będziesz musiał zainstalować GMP.
źródło
PFGW, 6067 cyfr, {5956} 7 {110}
Uruchom program PFGW z następującym plikiem wejściowym i
-f100
wprowadź liczby wstępne. Po około 2-3 minutach procesora na moim komputerze (i5 Haswell) znajduje PRP (10 ^ (6073-6) -1) / 9 + 6 * 10 ^ 110 lub {5956} 7 {110} . Jako punkt początkowy wybrałem 6000 cyfr jako liczbę „nic w mojej kieszeni”, która jest nieco wyższa niż we wszystkich poprzednich zgłoszeniach.Na podstawie tego, jak szybko udało mi się go znaleźć, mogłem z łatwością zwiększyć liczbę cyfr i nadal znaleźć PRP w ciągu godziny. Dzięki temu, jak napisane są reguły, mogę nawet znaleźć rozmiar, w którym mój procesor, działający na wszystkich 4 rdzeniach, może ukończyć jeden test PRP w ciągu godziny, poświęcić dużo czasu na znalezienie PRP i mieć moje „wyszukiwanie” wyłącznie jednego PRP.
PS W pewnym sensie nie jest to rozwiązanie „kodowe”, ponieważ nie napisałem niczego poza plikiem wejściowym ... ale wiele rozwiązań Mathematica dla problemów matematycznych w jednym wierszu można opisać w ten sam sposób, jak można używając biblioteki, która wykonuje dla Ciebie ciężką pracę. W rzeczywistości myślę, że trudno jest narysować dobrą linię między nimi. Jeśli chcesz, mogę napisać skrypt, który tworzy plik wejściowy PFGW i wywołuje PFGW. Skrypt może nawet wyszukiwać równolegle, aby użyć wszystkich 4 rdzeni i przyspieszyć wyszukiwanie ~ 4 razy (na moim CPU).
PPS Myślę, że LLR może wykonać testy PRP dla tych liczb i spodziewałbym się, że będzie to znacznie szybsze niż PFGW . Dedykowany program przesiewania mógłby również lepiej uwzględniać te liczby niż jednorazowy PFGW. Jeśli je połączysz, jestem pewien, że możesz przekroczyć granice znacznie wyżej niż obecne rozwiązania.
źródło
Python 2.7, 17-19 cyfr
Znaleziono 5111111111111 (13 cyfr) w 3 sekundy, a ta 17-cyfrowa najwyższa liczba pierwsza w 3 minuty. Domyślam się, że maszyna docelowa może to uruchomić i uzyskać 19-cyfrową najwyższą liczbę pierwszą w niecałą godzinę. Podejście to nie skaluje się dobrze, ponieważ utrzymuje liczby pierwsze w pamięci do połowy liczby cyfr docelowych. Wyszukiwanie 17-cyfrowe wymaga przechowywania tablicy 100 milionów boolanów. 19 cyfr wymagałoby tablicy elementów 1B, a pamięć byłaby wyczerpana przed przejściem do 23 cyfr. Prawdopodobnie też będzie to środowisko uruchomieniowe.
Podejścia oparte na testach pierwszeństwa, które nie obejmują absurdalnie dużej liczby liczb pierwszych dzielników, wypadną znacznie lepiej.
źródło
Mathematica
42114259 cyfrZ numerem:
{1042} 7 {3168}{388} 3 {3870}Który został wygenerowany przez następujący kod:
Rzuty powodują, że przestaje on testować inne liczby z tymi samymi cyframi, co aktualnie znalezione. ponieważ rozpoczyna testowanie od najbardziej znaczącej cyfry, będzie to oznaczać, że zawsze zwraca największą liczbę, chyba że liczba cyfr jest członkiem pierwszej trójki.
Po prostu zacząłem testować tuż poniżej wartości jednej z poprzednich odpowiedzi :)
Po zakończeniu liczba jest przechowywana w zmiennej najbardziej aktualnej
źródło
JavaScript, 3019 cyfr, {2 273} 5 {745}
To wykorzystuje test MillerRabin zawarty w BigInteger.js przez Toma Wu.
Począwszy od 0 => 2,046 cyfr = {1799} 7 {263} w ciągu godziny .
Począwszy od 3000 => 3019 cyfr = {2273} 5 {745} w ciągu godziny, mniej niż 3 sekundy .
Gdy zaczął się od zera, program przeskoczył do przodu i zaczął ponownie szukać na długości 1,5 x długości ostatniej znalezionej s-prime. Potem, gdy zobaczyłem, jak szybko działa, pomyślałem, że w ciągu godziny znajdzie taki, który zaczyna się od 3000 - co wystarczyło na zaledwie 3 sekundy.
Możesz go wypróbować tutaj: http://goo.gl/t3TmTk
(Ustaw, aby obliczyć wszystkie s-liczby pierwsze lub przejść do przodu.)
Program działa poprzez konstruowanie ciągów wszystkich „1”, ale z jednym „3”, „5” lub „7”. Dodałem szybkie sprawdzenie w funkcji IsStrPrime, aby odrzucić liczby kończące się na „5”.
To była niezła zabawa. Przypomina mi zagadkę, którą zrobiłem wiele lat temu, aby obliczyć, co nazywa się cyfrą pierwszą usuniętą . Jest to liczba pierwsza, która po usunięciu dowolnej cyfry pozostanie liczbą pierwszą. Na przykład 1037 jest liczbą pierwszą usuniętą, ponieważ 1037, 037, 137, 107 i 103 są liczbą pierwszą. Znalazłem jedną 84 cyfry, a najdłuższa, jaką znam, ma 332 cyfry. Jestem pewien, że moglibyśmy znaleźć go znacznie dłużej dzięki technikom stosowanym w tej układance. (Ale wybór numerów próbnych jest nieco trudniejszy - może?)
źródło
Axiom, 3019 cyfr {318} 5 {2700}
wynik z wartości początkowej 3000 w 529 sek
źródło