Liczba jest liczbą pierwszą Mersenne'a, jeśli jest zarówno liczbą pierwszą, jak i może być zapisana w postaci 2 ⁿ -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 :)}

Galaretka , 5 bajtów

&‘<ÆP

Wypróbuj online!

Jak to działa

&‘<ÆP  Main link. Argument: x

 ‘     Yield x+1.
&      Take the bitwise AND of x and x+1.
       This yields 0 iff x is a Mersenne number, i.e., iff x+1 is a power of 2.
   ÆP  Yield 1 if x is a prime, 0 if not.
  <    Compare the results to both sides,
       This yields 1 iff x is both a Mersenne number and a prime.

05AB1E , 5 bajtów

Liczba dodatnia w postaci 2 ⁿ - 1 w systemie binarnym składa się tylko z 1 .

Kod:

b`¹pP

Wyjaśnienie:

b`      # Push each digit of the binary representation of the number onto the stack
  ¹p    # Check if the input is prime
    P   # Take the product of all these digits

Wykorzystuje kodowanie CP-1252 . Wypróbuj online! lub Zweryfikuj wszystkie przypadki testowe .

Python , 45 bajtów

lambda n:-~n&n<all(n%i for i in range(2,n))<n

Wypróbuj online!

Jak to działa

Trzy warunki porównania łańcuchowego

-~n&n<all(n%i for i in range(2,n))<n

wykonaj następujące czynności:

• -~n&noblicza 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&ndaje 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))<nzachodzi, gdy n> 1 , ale ponieważ wszystkie zwracają wartość Prawda, jeśli n = 1 , nie zachowuje się w tym przypadku.

Brachylog , 7 bajtów

#p+~^h2

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:

#p      Input = A, and is prime
+       B = A + 1
~^      B = X to the power Y, C = the list [X, Y]
h       D = the head of list C (= X)
2       D = 2

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

Mathematica 26 bajtów

PerfectNumberQ[# (#+1)/2]&

Zobacz dowód

Działa, o ile nie ma nieparzystych liczb doskonałych i nie wiadomo, aby istniały.

Mathematica, 29 26 bajtów

Edycja: Zapisano 3 bajty dzięki Martinowi Enderowi

PrimeQ@#&&IntegerQ@Log2[#+1]&

PrimeQ@#&&1>BitAnd[#,#+1]&

Podejrzewam, że byłoby to szybsze, ponieważ pierwsze 42 wykładniki są zakodowane na stałe:

MersennePrimeExponentQ@Log2[#+1]&

Perl 6 , 29 bajtów

{.base(2)~~/^1*$/&&.is-prime}

Spróbuj

Rozszerzony:

{             # bare block lambda with implicit parameter ｢$_｣

  .base(2)    # is its binary representation ( implicit method call on ｢$_｣ )
   ~~
  /^ 1* $/    # made entirely of ｢1｣s

  &&          # and

  .is-prime   # is it prime

}

od Perl 6 ma dowolnie duże wskazówki, to nie pad przód .base(2)z 0s.

Python, 83 82 79 76 73 bajty

def f(m):
 s,n=(m!=3)*4,m>>2
 while-~m&m<n:s,n=(s*s-2)%m,n>>1
 return s<1

Python 2, 71 bajtów

def f(m):
 s,n=(m!=3)*4,m/4
 while-~m&m<n:s,n=(s*s-2)%m,n/2
 return s<1

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.

from __future__ import print_function

def primes(n):
    """ Return a list of primes < n """
    # From http://stackoverflow.com/a/3035188/4014959
    sieve = [True] * (n//2)
    for i in range(3, int(n**0.5) + 1, 2):
        if sieve[i//2]:
            sieve[i*i//2::i] = [False] * ((n - i*i - 1) // (2*i) + 1)
    return [2] + [2*i + 1 for i in range(1, n//2) if sieve[i]]

def lucas_lehmer_old(p):
    m = (1 << p) - 1
    s = 4
    for i in range(p - 2):
        s = (s * s - 2) % m
    return s == 0 and m or 0

# much faster
def lucas_lehmer(p):
    m = (1 << p) - 1
    s = 4
    for i in range(p - 2):
        s = s * s - 2
        while s > m:
            s = (s & m) + (s >> p)
    return s == 0 or s == m and m or 0

def f(m):
 s,n=(m!=3)*4,m>>2
 while-~m&m<n:s,n=(s*s-2)%m,n>>1
 return s<1

# Make a list of some Mersenne primes
a = [3]
for p in primes(608):
    m = lucas_lehmer(p)
    if m:
        print(p, m)
        a.append(m)
print()

# Test that `f` works on all the numbers in `a`
print(all(map(f, a))) 

# Test `f` on numbers that may not be Mersenne primes
for i in range(1, 525000):
    u = f(i)
    v = i in a
    if u or v:
        print(i, u, v)
    if u != v:
        print('Error:', i, u, v)

wydajność

3 7
5 31
7 127
13 8191
17 131071
19 524287
31 2147483647
61 2305843009213693951
89 618970019642690137449562111
107 162259276829213363391578010288127
127 170141183460469231731687303715884105727
521 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151
607 531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127

True
3 True True
7 True True
31 True True
127 True True
8191 True True
131071 True True
524287 True True

FWIW, oto nieco bardziej wydajna wersja f, która nie sprawdza msię ponownie w każdej pętli:

def f(m):
 s,n=m!=3and 4,m>>2
 if-~m&m<1:
  while n:
   s=(s*s-2)%m
   n>>=1
 return s<1

R, 41 40 bajtów

matlab::isprime(x<-scan())&!log2(x+1)%%1

Co dziwne, wbudowane w R. mersennezajmujen argumentem 2^n-1.

To pobiera xze STDIN, sprawdza, czy jest to pierwsze za pomocąmatlab pakietu i sprawdza, czy log 2 x+1jest liczbą całkowitą, biorąc mod 1 i sprawdzając, czy nie ma „zero-ness”.

Ponadto, jeśli użyjesz mersennewbudowanego, będzie on nieco krótszy, ale wydaje się, że oszustwo:

numbers::mersenne(log2(scan()+1))

Zapisano 1 bajt dzięki @Billywob

Pyke, 10 bajtów

_PQb2+}\1q

Wypróbuj tutaj!

_P         -    is_prime(input)
     +     -   ^ + V
  Qb2      -    base_2(input)
      }    -  uniquify(^)
       \1q - ^ == "1"

Właściwie 9 bajtów

;├╔'1=@p*

Wypróbuj online!

Wyjaśnienie:

Ponieważ każda liczba w postaci 2 ⁿ -1 ma wszystkie jedynki w swojej reprezentacji binarnej, liczba pierwsza Mersenne może być zidentyfikowana jako liczba pierwsza o tej jakości.

;├╔'1=@p*
 ├╔'1=     only unique binary digit is 1
        *  and
;     @p   is prime

Galaretka, 5 bajtów

Alternatywne podejście do istniejącej 5-bajtowej odpowiedzi Jelly @Dennis:

B;ÆPP

Wypróbuj online!

Jak to działa:

B      Returns the binary representation of the input as a list [1, 0, 1, 1, ...]
 ;     And attach to this list 
  ÆP   a 1 if the input is a prime, 0 otherwise
    P  Calculates the product of this list of 1's and 0's

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.

Cejlon, 66 bajtów

Boolean m(Integer c)=>c>2&&c.and(c+1)<1&&!(2:c-2).any((d)=>c%d<1);

Sformatowane (i skomentowane):

// Check whether a (positive integer) number is a mersenne prime number.
//
// Question:  http://codegolf.stackexchange.com/q/104508/2338
// My Answer: http://codegolf.stackexchange.com/a/104805/2338

Boolean m(Integer c) =>
        // check whether c+1 is a power of two
        c.and(c+1)<1 &&
        // the standard primality check by trial division
         !(2 : c-2).any((d) => c%d < 1) &&
        // we need to exclude 1, which is unfortunately
        // matched by both criteria above, but is no prime.
        c>1;

Dzięki oszukiwaniu (zakodowanie wyników w zakresie liczby całkowitej Ceylona) możemy uzyskać bajt krótszy (65):

Boolean h(Integer c) =>
        c.and(c+1)<1 && #20000000800a20ac.and(c+1)>0;

(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:

[2,3,5,7,13,17,19,31,61].map((p)=>2^p-1).contains

Wolfram Language (Mathematica) , 23 bajty

PrimeQ[BitAnd[#,#+2]#]&

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ą i BitAnd[#,#+2] == 1, co dzieje się, gdy #jest liczbą Mersenne.

Wyrażenie regularne ECMAScript, 42 31 bajtów

^(?!(xx+)\1+$)(x(x*)(?=\3$))+x$

^
(?!(xx+)\1+$)      # Assert that N is prime or 0 or 1.
(x(x*)(?=\3$))+x$  # Assert that N is a power of 2 minus 1 and is >= 3.
                   # The >=3 part of this prevents the match of 0 and 1.

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. Wstawienie xprzed 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!

# Match Mersenne primes in the domain ^x*$
^                   # N = input number
(?!                 # "(?!p|q)" is equivalent to "(?!p)(?!q)"; evaluate the
                    # logical AND of the following negative lookaheads:
    (xx+)\1+$       # Assert that N is prime or 0 or 1
|
    ((xx)+)(\2x)*$  # Assert that N is a power of 2 minus 1; this is based
                    # on "(?!(x(xx)+)\1*$)" which matches powers of 2.
)
xx                  # Assert that N >= 2, to prevent the unwanted match of
                    # 0 and 1 by both of the negative lookahead statements.

Regex (ECMAScript), 29 bajtów

^(?!(xx+|(x(x))+)(\1\3)+$)xxx

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, lub 0lub 1.
Drugi nie będzie pasował do numerów formularza$2^n-1$lub liczby, które są o 1 mniejsze niż nieparzysta liczba pierwsza.

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.

Ruby, 47 bajtów

->b{!("%b"%(b/2)=~/0/||(2...b).find{|a|b%a<1})}

Julia, 26 bajtów

n->isprime(n)&&ispow2(n+1)

Python, 65 bajtów

f=lambda n,i=3:(n^i)-all(n%i for i in range(2,n))<0 or f(n,-~i|i)

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-1w systemie binarnym utworzono całkowicie z 1, kolejną 2^n-1liczbę można wygenerować przeznumber|number+1 .

Ta funkcja wykorzystuje to, rekurencyjnie przechodząc przez każdą 2^n-1liczbę, 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.

Pushy , 7 bajtów

oBoIpP#

Wypróbuj online!

Wykorzystuje to fakt, że liczby mersenne mają tylko te w swojej reprezentacji binarnej:

oB      \ Pop input, push its binary digits.
  oI    \ Re-push the input
    p   \ Test its primality (0/1)
     P# \ Print the product of the stack

Produkt stosu powstanie tylko 1wtedy, gdy liczba nie będzie zawierać zer w reprezentacji binarnej, a jego pierwotną wartością jest True.

Pyth , 8 bajtów

&.AjQ2P_

Sprawdź wszystkie przypadki testowe.

Pyth , 8 bajtów

<.&QhQP_

Sprawdź wszystkie przypadki testowe.

W jaki sposób?

Podział kodu # 1

&.AjQ2P_    Full program with implicit input.

      P_    Is Prime?
   jQ2      Convert the input to binary as a list of digits.
 .A         All the elements are truthy (i.e. all are 1).
&           Logical AND.
            Output implicitly.

Jak to działa?

Liczba w postaci 2 ⁿ - 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

<.&QhQP_    Full program with implicit input.

      P_    Is Prime?
    hQ      Input + 1.
 .&Q        Bitwise AND between the input and ^.
<           Is smaller than? I.e. The bitwise AND results in 0 and the primality test results in 1.
            Output implicitly.

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 booljest 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).

Java 8, 53 52 49 bajtów

n->{int i=1;for(;n%++i>0;);return(n&n+1|i^n)==0;}

Naprawiono błąd i grał w golfa o 4 bajty dzięki @Nevay .

Wyjaśnienie:

Wypróbuj tutaj.

n->{                // Method with integer parameter and boolean return-type
  int i=1;          //  Temp integer `i`, starting at 1
  for(;n%++i>0;);   //  Loop and increase `i` as long as `n` is divisible by `i`
  return(n&n+1|i^n) //  Then return if `n` bitwise-AND `n+1` bitwise-OR `i` bitwise-XOR `n`
          ==0;      //  is exactly 0
}                   // End of method

Python 3, 68 bajtów

a=int(input());print(a&-~a<1and a>1and all(a%b for b in range(2,a)))

Wypróbuj tutaj

Python 2, 63 bajty

a=input();print(a&-~a<1)and a>1and all(a%b for b in range(2,a))

Wypróbuj tutaj

Dzięki za sugestię Jonathan

Otwarty na wszelkie sugestie dotyczące zmniejszenia liczby bajtów.

Japt, 6 bajtów

¢¬×&Uj

Uruchom lub Uruchom wszystkie przypadki testowe

Python, 93 bajty

def f(a):
 for b in range(a):
  if(a+1==2**b and not[i for i in range(2,a)if a%i<1]):return 1

Ten kod działałby zarówno w Pythonie 2, jak i Pythonie 3, więc nie podałem wersji.

Rakieta 76 bajtów

(define(g m)(for/or((i m))(= m(-(expt 2 i)1))))(if(and(prime? n)(g n))#t #f)

Nie golfowany:

(require math)
(define(f n)
  (define (ispowerminus1 m)
    (for/or ((i m))
      (= m (-(expt 2 i)1))))
  (if (and (prime? n)
           (ispowerminus1 n))
      #t #f))

Testowanie:

(f 1)
(f 2)
(f 20)
(f 51)
(f 63)
(f 3)
(f 31)
(f 8191)

Wydajność:

#f
#f
#f
#f
#f
#t
#t
#t

PHP, 53 bajty

for($i=$n=$argv[1];--$i&&$n%$i;);echo!($i-1|$n+1&$n);

przyjmuje argument wiersza poleceń; drukuje 1dla Mersenne prime, pusty ciąg znaków inny. Uruchom z -r.

awaria

for($i=$n=$argv[1];--$i&&$n%$i;);   // loop $i down from $n-1 until $i divides $n
                        // If $n is prime, loop ends with $i=1. ($n=1 -> $i=0)
echo!($i-1|$n+1&$n);    // If $i!=1, $n is not prime. If ($n+1&$n)>0, $n is not Mersenne.
                        // If either $i-1 or $n+1&$n is truthy, the negation will be false.

C, 94 bajty

g(n,i){return--i?g(2*n,i):n;}n,r;f(x){for(n=r=1;++n<x;)r=x%n?x^g(2,n)-1?r:r|2:r&2;return r>2;}

Zwraca 1, jeśli liczba jest Mersenne Prime, w przeciwnym razie 0.

Scala, 59 bajtów

def f(t:BigInt)=t.isProbablePrime(t.bitLength*9)&(1+t)%2==0

Ta funkcja wymaga wejścia jako BigInt. Możesz łatwo przekonwertować ciąg „162259276829213363391578010288127” (2 ** 107-1 to liczba pierwsza Mersenne) BigInt, wykonując to BigInt("162259276829213363391578010288127"). Może pójść nie tak, jak isProbablePrime()sugeruje nazwa metody. Ale prawdopodobieństwo nie jest większe niż0.5^(t.bigLength)*9 .

Samodzielna wersja skryptu ma 72 bajty.

val t=BigInt(args(0));print(t.isProbablePrime(t.bitLength*9)&(1+t)%2==0)

Załóżmy, że zapisujemy go jako „t.scala”, wtedy program można uruchomić jako

>scala t.scala 162259276829213363391578010288127
>true

Perl 5 , 53 bajtów

52 bajty kodu + 1 dla -p

$f=0|sqrt;1while$_%$f--;$_=!$f*(sprintf'%b',$_)!~/0/

Wypróbuj online!