Liczba jest liczbą pierwszą Mersenne'a, jeśli jest zarówno liczbą pierwszą, jak i może być zapisana w postaci 2 n -1 , gdzie n jest liczbą całkowitą dodatnią.
Twoim zadaniem jest, biorąc pod uwagę dodatnią liczbę całkowitą, ustalić, czy jest to liczba pierwsza Mersenne. Możesz przesłać funkcję, która zwraca wartość prawda / fałsz, lub pełny program, który wykonuje operacje wejścia / wyjścia.
Zasady:
- Ponieważ jest to gra w golfa kodowego , powinieneś dążyć do tego jak najkrótszej możliwej liczby bajtów. Wbudowane są dozwolone.
- Obowiązują standardowe luki w grze w golfa - nie można odczytać liczb pierwszych Mersenne z zewnętrznych plików ani zakodować ich w programie.
- Twój program powinien działać dla wartości w standardowym rozmiarze całkowitym twojego języka.
Przypadki testowe
W celach informacyjnych listę (znanych) Mersenne Primes można znaleźć tutaj . Niektóre przydatne przypadki testowe to:
2 -> False
1 -> False
20 -> False
51 -> False
63 -> False
3 -> True
31 -> True
8191 -> True
Wesołych Świąt wszystkim! Udanych wakacji, bez względu na to, co świętujesz :)
2^n-1
n
jest zawsze liczbą pierwszą, ale wiedząc, że nic nie zmienia, definicja jest nadal poprawna.Odpowiedzi:
Galaretka , 5 bajtów
Wypróbuj online!
Jak to działa
źródło
05AB1E , 5 bajtów
Liczba dodatnia w postaci 2 n - 1 w systemie binarnym składa się tylko z 1 .
Kod:
Wyjaśnienie:
Wykorzystuje kodowanie CP-1252 . Wypróbuj online! lub Zweryfikuj wszystkie przypadki testowe .
źródło
Python , 45 bajtów
Wypróbuj online!
Jak to działa
Trzy warunki porównania łańcuchowego
wykonaj następujące czynności:
-~n&n
oblicza bitowe AND z n + 1 i n . Ponieważ n składa się wyłącznie z 1 bitów, jeśli jest to liczba Mersenne'a, bitowe AND zwróci 0, jeśli (i tylko wtedy).all(n%i for i in range(2,n))
zwraca wartość True wtedy i tylko wtedy, gdy n mod i jest niezerowe dla wszystkich wartości i w [2,…, n - 1] , tj. wtedy i tylko wtedy, gdy n nie ma dodatnich dzielników oprócz 1 i n .Innymi słowy, wszystkie zwracają wartość Prawda wtedy i tylko wtedy, gdy n jest liczbą złożoną, tj. N jest 1 lub liczbą pierwszą.
n
jest oczywiste.Łańcuchowe porównanie zwraca wartość True tylko wtedy, gdy poszczególne porównania robią to samo.
Ponieważ wszystkie zwracają wartość Prawda / 1 lub False / 0 ,
-~n&n<all(n%i for i in range(2,n))
może zwrócić wartość Prawda tylko, jeśli-~n&n
daje 0 (czyli jeśli n jest liczbą Mersenne) i wszystko wraca prawda (czyli jeśli n albo 1 albo prime).Porównanie
all(n%i for i in range(2,n))<n
zachodzi, gdy n> 1 , ale ponieważ wszystkie zwracają wartość Prawda, jeśli n = 1 , nie zachowuje się w tym przypadku.źródło
Brachylog , 7 bajtów
Wypróbuj online!
Program Brachylog jest w zasadzie sekwencją ograniczeń, które tworzą łańcuch: pierwsze ograniczenie jest między danymi wejściowymi a anonimową nieznaną (nazwijmy to A dla celów tej dyskusji), drugie ograniczenie jest między tą anonimową nieznaną a drugą anonimową nieznany (który nazwiemy B ) i tak dalej. Jako taki program rozkłada się w następujący sposób:
Jedynym sposobem, w jaki wszystkie te ograniczenia mogą być spełnione jednocześnie, jest to, gdy B jest potęgą 2, tj. Wejście jest potęgą 2 minus 1, a wejście jest również liczbą pierwszą. (Brachylog wewnętrznie wykorzystuje solver ograniczający, więc program nie będzie tak nieefektywny, jak wygląda kolejność oceny; będzie wiedział, że
C
jest w formie,[2, Y]
zanim spróbuje wyrazićB
jako potęgowanie dwóch liczb).Co ciekawe,
#p+~^
prawie działa, ponieważ liczby pierwsze podobne do Mersenne'a mogą używać tylko 2 jako podstawy w przypadkach nie zdegenerowanych ( dowód ), ale a) nie udaje się dla liczb pierwszych B Mersenne'a B -1, ponieważ można je wyrazić jako B i b ) istniejący interpreter Brachylog wydaje się być zdezorientowany (przechodząc w nieskończoną lub przynajmniej długotrwałą pętlę) przez program, który jest tak słabo ograniczony. Tak więc wydaje się, że 7 bajtów nie zostanie pobitych w Brachylog.źródło
Mathematica 26 bajtów
Zobacz dowód
Działa, o ile nie ma nieparzystych liczb doskonałych i nie wiadomo, aby istniały.
źródło
n(n+1)/2
daje (parzyste) liczby idealne, ilekroćn
jest liczbą pierwszą Mersenne'a (Euclid). Nie wiadomo, czy nieparzysta liczba doskonała może mieć postaćn(n+1)/2
, tj. Być liczbą trójkątną. Wszystkie nawet doskonałe liczby są trójkątne, jeślin
jest to liczba pierwsza Mersenne'a (Euler).Mathematica,
2926 bajtówEdycja: Zapisano 3 bajty dzięki Martinowi Enderowi
PrimeQ@#&&IntegerQ@Log2[#+1]&
Podejrzewam, że byłoby to szybsze, ponieważ pierwsze 42 wykładniki są zakodowane na stałe:
źródło
PrimeQ@#&&1>BitAnd[#,#+1]&
Perl 6 , 29 bajtów
Spróbuj
Rozszerzony:
od Perl 6 ma dowolnie duże wskazówki, to nie pad przód
.base(2)
z0
s.źródło
Python,
8382797673 bajtyPython 2, 71 bajtów
Ta funkcja implementuje test pierwszeństwa Lucasa-Lehmera , więc chociaż nie jest tak krótki, jak niektóre inne oferty Pythona, jest znacznie szybszy w obsłudze dużych danych wejściowych.
Oto kod testowy działający w Python 2 lub Python 3.
wydajność
FWIW, oto nieco bardziej wydajna wersja
f
, która nie sprawdzam
się ponownie w każdej pętli:źródło
R,
4140 bajtówCo dziwne, wbudowane w R.
mersenne
zajmujen
argumentem2^n-1
.To pobiera
x
ze STDIN, sprawdza, czy jest to pierwsze za pomocąmatlab
pakietu i sprawdza, czy log 2x+1
jest liczbą całkowitą, biorąc mod 1 i sprawdzając, czy nie ma „zero-ness”.Ponadto, jeśli użyjesz
mersenne
wbudowanego, będzie on nieco krótszy, ale wydaje się, że oszustwo:Zapisano 1 bajt dzięki @Billywob
źródło
matlab::isprime
zapisanie jednego bajtu. Musisz także użyć<-
do przypisania funkcji.log2(x+1)
zamiast tegolog(x+1,2)
.Pyke, 10 bajtów
Wypróbuj tutaj!
źródło
Właściwie 9 bajtów
Wypróbuj online!
Wyjaśnienie:
Ponieważ każda liczba w postaci 2 n -1 ma wszystkie jedynki w swojej reprezentacji binarnej, liczba pierwsza Mersenne może być zidentyfikowana jako liczba pierwsza o tej jakości.
źródło
Galaretka, 5 bajtów
Alternatywne podejście do istniejącej 5-bajtowej odpowiedzi Jelly @Dennis:
Wypróbuj online!
Jak to działa:
Ponieważ Mersenne Prime jest o jeden mniejszy niż potęga 2, jego reprezentacja binarna to wybitnie 1. Wynik tego wynosi 1 dla liczb pierwszych Mersenne i 0 we wszystkich innych przypadkach.
źródło
Cejlon, 66 bajtów
Sformatowane (i skomentowane):
Dzięki oszukiwaniu (zakodowanie wyników w zakresie liczby całkowitej Ceylona) możemy uzyskać bajt krótszy (65):
(Wygląda na to, że wyróżnik składni źle rozumie cyfry szesnastkowe Ceylona jako początek komentarza.)
Jeśli funkcja anonimowa jest w porządku, ta ma 49 bajtów:
źródło
Wolfram Language (Mathematica) , 23 bajty
Wypróbuj online!
1 jest obsługiwany poprawnie, ponieważ
PrimeQ[BitAnd[1,1+2]*1] == PrimeQ@1 == False
. W przeciwnym razie,BitAnd[#,#+2]#
aby być liczbą pierwszą, potrzebujemy, że#
jest liczbą pierwszą iBitAnd[#,#+2] == 1
, co dzieje się, gdy#
jest liczbą Mersenne.źródło
Wyrażenie regularne ECMAScript,
4231 bajtów^(?!(xx+)\1+$)(x(x*)(?=\3$))+x$
Wypróbuj online!
Edycja: do 31 bajtów dzięki Neilowi.
Podstawowym testem „jest potęga 2 minus 1”
^(x(x*)(?=\2$))*$
. Działa to poprzez zapętlenie operacji „odejmij 1, a następnie podziel równomiernie przez 2”, aż nie będzie można tego zrobić dalej, a następnie upewniając się, że wynik wynosi zero. Można to zmodyfikować, aby dopasować tylko liczby ≥1, zmieniając ostatnią*
na a+
, zmuszając pętlę do iteracji co najmniej raz. Wstawieniex
przed ostatnim$
modyfikuje go tak, aby pasował tylko do liczb ≥3, zapewniając, że końcowy wynik po zapętleniu przynajmniej raz wynosi 1.Powiązany test „to potęga 2” to
^((x+)(?=\2$))*x$
. Istnieje również skrótem pasującymi uprawnień 2 minus 2, odkrytych przez umorusany :^((x+)(?=\2$)x)*$
. Wszystkie trzy wyrażenia regularne mają tę samą długość.Alternatywna 31-bajtowa wersja Grimy :
^(?!(xx+)\1+$|((xx)+)(\2x)*$)xx
Wypróbuj online!
źródło
x(x+)(?=\3$)
nieco bardziej wydajne?Regex (ECMAScript), 29 bajtów
Wypróbuj online!
Zainspirowany przez Grimy na czacie
Wyrażenie regularne potwierdza, że dane wejściowe są większe niż 3 i że nie ma on żadnej postaci:
(xx+)\1+
ani((xx)+)(\1x)+
.Pierwsza odpowiada liczbom złożonym.
Drugi odpowiada liczbie, która jest 1 mniejsza niż wielokrotność liczby nieparzystej większej niż 2.
Pierwszy nie będzie pasował do liczb pierwszych, lub2)n- 1 lub liczby, które są o 1 mniejsze niż nieparzysta liczba pierwsza.
0
lub1
.Drugi nie będzie pasował do numerów formularza
Ponieważ 2 jest jedyną liczbą pierwszą, która jest o 1 mniejsza od liczby nieparzystej, negatywne spojrzenie w przyszłość wraz z twierdzeniem, że dane wejściowe są większe niż 3, będą pasować tylko do liczb pierwszych mersenne.
źródło
Ruby, 47 bajtów
źródło
Julia, 26 bajtów
źródło
Python, 65 bajtów
Wyjścia za pośrednictwem kodu wyjścia. Błąd rekurencji dla False. Brak błędu dla True.
Jak to działa
Ponieważ
2^n-1
w systemie binarnym utworzono całkowicie z 1, kolejną2^n-1
liczbę można wygenerować przeznumber|number+1
.Ta funkcja wykorzystuje to, rekurencyjnie przechodząc przez każdą
2^n-1
liczbę, sprawdzając, czy jest to liczba pierwsza i czy jest odpowiednikiem wejścia. Jeśli liczba nie jest liczbą pierwszą mersenna, python ostatecznie wyśle błąd, ponieważ maksymalna głębokość rekurencji zostałaby przekroczona.źródło
<0
~>0>
.Pushy , 7 bajtów
Wypróbuj online!
Wykorzystuje to fakt, że liczby mersenne mają tylko te w swojej reprezentacji binarnej:
Produkt stosu powstanie tylko
1
wtedy, gdy liczba nie będzie zawierać zer w reprezentacji binarnej, a jego pierwotną wartością jestTrue
.źródło
Pyth , 8 bajtów
Sprawdź wszystkie przypadki testowe.
Pyth , 8 bajtów
Sprawdź wszystkie przypadki testowe.
W jaki sposób?
Podział kodu # 1
Jak to działa?
Liczba w postaci 2 n - 1 zawsze zawiera 1 tylko wtedy, gdy jest zapisana binarnie. Dlatego sprawdzamy, czy wszystkie jego binarne cyfry to 1 i czy jest liczbą pierwszą.
Podział kodu # 2
Jak to działa?
Sprawdza, czy wejście + 1 jest potęgą dwóch (tzn. Czy jest to liczba Mersenne'a), a następnie wykonuje test pierwotności. W Pythonie
bool
jest podklasąint
, więc prawda jest traktowana jako 1, a fałsz jako 0 . Aby uniknąć jednoznacznego sprawdzenia, że jeden to 0, a drugi to 1 , porównujemy ich wartości za pomocą<
(ponieważ mamy tylko 1 taki przypadek).źródło
Java 8,
535249 bajtówNaprawiono błąd i grał w golfa o 4 bajty dzięki @Nevay .
Wyjaśnienie:
Wypróbuj tutaj.
źródło
true
za każdąn->{for(int i=2;i<n;n&=-n%i++>>-1);return(n&n+1)<1&n>2;}
n->{int i=1;for(;++i<n&n%i>0;);return(n&n+1|i^n)<1;}
n->{int i=1;for(;n%++i>0;);return(n&n+1|i^n)==0;}
Python 3, 68 bajtów
Wypróbuj tutaj
Python 2, 63 bajty
Wypróbuj tutaj
Dzięki za sugestię Jonathan
Otwarty na wszelkie sugestie dotyczące zmniejszenia liczby bajtów.
źródło
1 and
~>1and
.Japt, 6 bajtów
Uruchom lub Uruchom wszystkie przypadki testowe
źródło
©
bitowe,&
aby uzyskać spójne wyjście, jeśli chcesz.Python, 93 bajty
Ten kod działałby zarówno w Pythonie 2, jak i Pythonie 3, więc nie podałem wersji.
źródło
Rakieta 76 bajtów
Nie golfowany:
Testowanie:
Wydajność:
źródło
PHP, 53 bajty
przyjmuje argument wiersza poleceń; drukuje
1
dla Mersenne prime, pusty ciąg znaków inny. Uruchom z-r
.awaria
źródło
C, 94 bajty
Zwraca 1, jeśli liczba jest Mersenne Prime, w przeciwnym razie 0.
źródło
~x+g(2,n)
zamiastx^g(2,n)-1
Scala, 59 bajtów
Ta funkcja wymaga wejścia jako
BigInt
. Możesz łatwo przekonwertować ciąg „162259276829213363391578010288127” (2 ** 107-1 to liczba pierwsza Mersenne)BigInt
, wykonując toBigInt("162259276829213363391578010288127")
. Może pójść nie tak, jakisProbablePrime()
sugeruje nazwa metody. Ale prawdopodobieństwo nie jest większe niż0.5^(t.bigLength)*9
.Samodzielna wersja skryptu ma 72 bajty.
Załóżmy, że zapisujemy go jako „t.scala”, wtedy program można uruchomić jako
źródło
Probable
z,isProbablePrime
jeśli Scala maisPrime
funkcję.Perl 5 , 53 bajtów
52 bajty kodu + 1 dla
-p
Wypróbuj online!
źródło
-p
jest on klasyfikowany jako inny język programowania i dlatego nie liczy się w twoim bajcie.