Liczba jest liczbą de Polignaca wtedy i tylko wtedy, gdy jest nieparzysta i nie może być reprezentowana w postaci p + 2 ^n, gdzie n jest liczbą całkowitą nieujemną, a p jest liczbą całkowitą pierwszą.

Zadanie

Napisz kod, który przyjmuje dodatnią liczbę całkowitą i określa, czy jest to liczba de Polignaca. Możesz wyprowadzić dwie różne wartości: jedną dla wartości true i jedną dla wartości false. Powinieneś dążyć do zminimalizowania liczby bajtów.

Przypadki testowe

Dla pozytywnych przypadków oto OEIS

1, 127, 149, 251, 331, 337, 373, 509, 599, 701, 757, 809, 877, 905, 907, 959, 977, 997, 1019, 1087, 1199, 1207, 1211, 1243, 1259, 1271, 1477, 1529, 1541, 1549, 1589, 1597, 1619, 1649, 1657, 1719, 1759, 1777, 1783, 1807, 1829, 1859, 1867, 1927, 1969, 1973, ...

Oto kilka negatywnych przypadków:

22, 57

Japt , 9 14 13 bajtów

o!²mnU dj |Uv

Przetestuj online! lub Znajdź wszystkie liczby całkowite de Polignac poniżej 1000 .

Wyjścia 1dla danych wejściowych 0dla fałszowania i dla prawdy.

Wyjaśnienie

 o!²  mnU dj |Uv
Uo!p2 mnU dj |Uv  : Ungolfed
                  : Implicit: U = input integer (e.g. 9)
Uo                : Create the range [0..U), and map each item X to
  !p2             :   2 ** X.               [1, 2, 4, 8, 16, 32, 64, 128, 256]
      m           : Map each of these powers of 2 by
       nU         :   subtracting from U.   [8, 7, 5, 1, -7, -23, -57, -119, -247]
          d       : Return whether any item in the result is
           j      :   prime.                (5 and 7 are, so `true`)
             |    : Take the bitwise OR of this and
              Uv  :   U is divisble by (missing argument = 2).
                  : This gives 1 if U cannot be represented as p + 2^n or if U is even.
                  : Implicit: output result of last expression

Galaretka , 11 10 bajtów

Zapisano 1 bajt dzięki @Dennis

Ḷ2*³_ÆPS<Ḃ

Wypróbuj online!

Jak to działa

Ḷ2*³_ÆPS<Ḃ   Main link. Argument: n (integer)
Ḷ            Lowered range; yield [0, 1, 2, ..., n-1].
 2*          Reversed exponentiation with 2; yield [1, 2, 4, ..., 2**(n-1)].
   ³_        Reversed subtraction with the input; yield [n-1, n-2, n-4, ..., n-2**(n-1)].
     ÆP      Replace each item with 1 if it is prime, 0 otherwise.
       S     Sum; yield a positive integer if any item was prime, 0 otherwise.
         Ḃ   Yield n % 2.
        <    Yield 1 if the sum is less than n % 2, 0 otherwise.
             This yields 1 if and only if the sum is 0 and n is odd.

JavaScript (ES6),  56 54  53 bajtów

Zwraca $0$ lub $1$ .

f=(n,p=1,x=y=n-p)=>n>p?y%--x?f(n,p,x):x!=1&f(n,p*2):n

Wypróbuj online!

W jaki sposób?

Zaczynamy od $p = 1$ . Sprawdzamy, czy $y = n - p$ jest złożone i daje odpowiednio wartość logiczną. Następny test przeprowadzany jest przy $p \times 2$ .

Gdy tylko $p$ jest większe niż $n$ , zatrzymujemy rekurencję i zwracamy $n$ .

Wyniki wszystkich iteracji są AND połączone razem, co zmusza wartości boolowskie do $0$ lub $1$ .

Pod warunkiem, że wszystkie wyniki pośrednie były zgodne z prawdą, kończymy testem bitowym, takim jak:

1 & 1 & 1 & n

Daje to $1$ wtedy i tylko wtedy, gdy $n$ jest nieparzysty, co jest ostatnim warunkiem wymaganym do zatwierdzenia danych wejściowych jako liczby de Polignaca.

Python 2 , 60 57 56 bajtów

f=lambda n,k=1,p=-1:k/n or(n-k&n-k-p%k>0)&n&f(n,k+1,p*k)

Wypróbuj online!

Galaretka , 10 bajtów

Alternatywne 10-bajtowe przesłanie galaretki do już opublikowanego.

_ÆRBS€’×ḂẠ

Łącze monadyczne zwracające 1 dla liczb de Polignac i 0 w przeciwnym razie.

Wypróbuj online! lub zobacz te poniżej 1000 .

W jaki sposób?

_ÆRBS€’×ḂẠ - Link: number, n  e.g.  1    3      5                  6                   127
 ÆR        - prime range            []   [2]    [2,3,5]            [2,3,5]             [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127]
_          - subtract from n        []   [1]    [3,2,0]            [4,3,1]             [125,124,122,120,116,114,110,108,104,98,96,90,86,84,80,74,68,66,60,56,54,48,44,38,30,26,24,20,18,14,0]
   B       - convert to binary      []   [[1]]  [[1,1],[1,0],[0]]  [[1,0,0],[1,1],[1]  [[1,1,1,1,1,0,1],[1,1,1,1,1,0,0],[1,1,1,1,0,1,0],[1,1,1,1,0,0,0],[1,1,1,0,1,0,0],[1,1,1,0,0,1,0],[1,1,0,1,1,1,0],[1,1,0,1,1,0,0],[1,1,0,1,0,0,0],[1,1,0,0,0,1,0],[1,1,0,0,0,0,0],[1,0,1,1,0,1,0],[1,0,1,0,1,1,0],[1,0,1,0,1,0,0],[1,0,1,0,0,0,0],[1,0,0,1,0,1,0],[1,0,0,0,1,0,0],[1,0,0,0,0,1,0],[1,1,1,1,0,0],[1,1,1,0,0,0],[1,1,0,1,1,0],[1,1,0,0,0,0],[1,0,1,1,0,0],[1,0,0,1,1,0],[1,1,1,1,0],[1,1,0,1,0],[1,1,0,0,0],[1,0,1,0,0],[1,0,0,1,0],[1,1,1,0],0]
    S€     - sum €ach               []   [1]    [2,1,0]            [1,2,1]             [6,5,5,4,4,4,5,4,3,3,2,4,4,3,2,3,2,2,4,3,4,2,3,3,4,3,2,2,2,3,0]
      ’    - decrement              []   [0]    [1,0,-1]           [0,1,0]             [5,4,4,3,3,3,4,3,2,2,1,3,3,2,1,2,1,1,3,2,3,1,2,2,3,2,1,1,1,2,-1]
        Ḃ  - n mod 2                1    1      1                  0                   1
       ×   - multiply               []   [0]    [1,0,-1]           [0,0,0]             [5,4,4,3,3,3,4,3,2,2,1,3,3,2,1,2,1,1,3,2,3,1,2,2,3,2,1,1,1,2,-1]
         Ạ - all truthy?            1    0      0                  0                   1

05AB1E , 9 8 bajtów

-1 bajt dzięki Emignie

Ýo-pZ¹È~

Wyjścia 0dla prawdziwych danych wejściowych i 1dla fałszywych danych wejściowych.

Wypróbuj online!

Python 2 , 99 bajtów

lambda n:n&1-any(n-2**k>1and all((n-2**k)%j for j in range(2,n-2**k))for k in range(len(bin(n))-2))

Wypróbuj online!

-4 bajty dzięki Dziurawej Zakonnicy

-2 bajty dzięki Wondercricket

+8 bajtów, aby naprawić błąd

-1 bajt dzięki Mr. Xcoder

-3 bajty dzięki Einkorn Enchanter

+12 bajtów, aby naprawić błąd

Regex (ECMAScript), 97 bajtów

Problem ten stanowił interesujący przypadek do obejścia problemu braku nieatomowej perspektywy. I to jak dotąd jedyny raz, kiedy miałem dobry powód, aby przetestować obie wersje potęgi 2, ((x+)(?=\2$))*x$i (?!(x(xx)+)\1*$), w tym samym wyrażeniu regularnym, i jak dotąd jedyny potrzebny mi czas, aby zabezpieczyć test główny przed dopasowaniem 1, ponieważ (?!(xx+)\1+$)xxw przypadku użycia w większym wyrażeniu regularnym.

^(?!(xx)*$|(x+)((?!(xx+)\4+$).*(?=\2$)((x+)(?=\6$))*x$|(?!(x(xx)+)\7*$).*(?=\2$)(?!(xx+)\9+$)xx))

Wypróbuj online!

# For the purposes of these comments, the input number = N.
^
# Assert that N is not the sum of a prime number and a power of 2.
(?!
    (xx)*$                 # Assert that N is odd.
|
    # Since we must cycle through all values for a number X and a corresponding number
    # N-X, this cannot be in an atomic lookahead. The problem then becomes that it
    # consumes characters. Thus we must let X be the larger of the two and N-X be the
    # smaller, and do tests on X followed by tests on N-X. We can't just test X for
    # being prime and N-X for being a power of 2, nor vice versa, because either one
    # could be smaller or larger. Thus, we must test X for being either prime or a
    # power of 2, and if it matches as being one of those two, do the opposite test on
    # N-X.
    # Note that the prime test used below, of the form (?!(xx+)\2+$), has a false match
    # for 0 and 1 being prime. The 0 match is harmless for our purposes, because it
    # will only result in a match for N being a power of 2 itself, thus rejecting
    # powers of 2 as being de Polignac numbers, but since we already require that N is
    # odd, we're already rejecting powers of 2 implicitly. However, the 1 match would
    # break the robustness of this test. There can be de Polignac numbers of the form
    # 2^M+1, for example 262145 and 2097153. So we must discard the 1 match by changing
    # the prime test to "(?!(xx+)\2+$)xx". We only need to do this on the N-X test,
    # though, because as X is the larger number, it is already guaranteed not to be 1.
    (x+)           # \2 = N-X = Smaller number to test for being prime or a power of 2;
                   # tail = X = larger number to test for being prime or a power of 2.
    (
        (?!(xx+)\4+$)      # Test X for being prime.
        .*(?=\2$)          # tail = N-X
        ((x+)(?=\6$))*x$   # Test N-X for being a power of 2. Use the positive version
                           # since it's faster and doesn't have a false match of 0.
    |
        (?!(x(xx)+)\7*$)   # Test X for being a power of 2. Use the negative version
                           # because the testing of X has to be in a lookahead, and
                           # putting the positive version in a positive lookahead would
                           # be worse golf. It doesn't matter that this can have a false
                           # match of 0, because X is guaranteed never to be 0.
        .*(?=\2$)          # tail = N-X
        (?!(xx+)\9+$)xx    # Test N-X for being prime. We must prevent a false match of
                           # 1 for the reason described above.
    )
)

Regex (ECMAScript + przegląd molekularny), 53 52 bajty

^(?!(xx)*$|(?*xx+(((x+)(?=\4$))*x$))\2(?!(xx+)\5+$))

# For the purposes of these comments, the input number = N.
^
# Assert that N is not the sum of a prime number and a power of 2.
(?!
    (xx)*$                   # Assert that N is odd.
|
    (?*
        xx+                  # Force N - \2 to be > 1, because the prime test used
                             # below has a false match of 1, which would otherwise
                             # give us false negatives on de Polignac numbers of the
                             # form 2^M+1, such as 262145 and 2097153.
        (((x+)(?=\4$))*x$)   # Cycle through subtracting all possible powers of 2 from
                             # tail, so we can then test {N - {power of 2}} for being
                             # prime.
                             # \2 = the power of 2
    )
    \2                       # tail = N - \2
    (?!(xx+)\5+$)            # Test tail for being prime. If it matches, this will fail
                             # the outside negative lookahead, showing that N is not a
                             # de Polignac number.
)

Ta wersja jest nie tylko o wiele czystsza, ale także znacznie szybsza, ponieważ zamiast cyklicznie przewijać wszystkie możliwe sposoby, że N jest sumą dwóch liczb, może po prostu cyklicznie odejmować każdą potęgę 2 od N i sprawdzać różnicę pod względem bycia liczbą pierwszą .

Molekularny lookahead można łatwo przekształcić w look-look o zmiennej długości:

Regex (.NET lub ECMAScript 2018), 55 54 bajtów

^(?!(xx)*$|xx+(((x+)(?=\4$))*x$)(?<=(?<!^\5+(x+x))\2))

Wypróbuj online! (.NET)
Wypróbuj online! (ECMAScript 2018)

# For the purposes of these comments, the input number = N.
^
# Assert that N is not the sum of a prime number and a power of 2.
(?!
    (xx)*$                 # Assert that N is odd.
|
    xx+                    # Force N - \2 to be > 1, because the prime test used
                           # below has a false match of 1, which would otherwise
                           # give us false negatives on de Polignac numbers of the
                           # form 2^M+1, such as 262145 and 2097153.
    (((x+)(?=\4$))*x$)     # Cycle through subtracting all possible powers of 2 from
                           # tail, so we can then test {N - {power of 2}} for being
                           # prime.
                           # \2 = the power of 2
    (?<=
        (?<!^\5+(x+x))     # Test tail for being prime. If it matches, this will fail
                           # the outside negative lookahead, showing that N is not a
                           # de Polignac number.
        \2                 # tail = N - \2
    )
)

Mathematica, 41 bajtów

OddQ@#&&!Or@@PrimeQ[#-2^Range[0,Log2@#]]&

PHP , 75 bajtów

drukuje 1 dla prawdy i 0 dla fałszu

for($t=1&$argn;0<$d=$n=$argn-2**$i++;$d-1?:$t&=0)for(;--$d&&$n%$d;);echo$t;

Wypróbuj online!

Wypróbuj online! Liczby całkowite Polignac poniżej 10000

Pari / GP , 34 bajty

n->n%2*prod(i=0,n,!isprime(n-2^i))

Wypróbuj online!

Brachylog , 15 13 bajtów

/₂ℕ|>ṗ;?-₍ḃ+1

Wypróbuj online!

Dane wyjściowe liczb Polignaca do 1000.

Zwraca false.numery de Polignac i true.inne.

Na podstawie usuniętej odpowiedzi @ LeakyNun, z kilkoma poprawkami błędów (opublikowanymi za ich zgodą).

(-2 bajty za pomocą metody @Jonathan Allan, aby sprawdzić, czy liczba jest potęgą dwóch).

Podany numer nie jest liczbą de Polignac, jeśli:

/₂ℕ              It's an even number
   |>ṗ           Or there exists a prime number less than the input
      ;?-₍       which when subtracted from the input
          ḃ      gives a result that has a binary form
           +     such that the sum of the bits 
            1    is 1

Galaretka , 13 bajtów

ÆRạl2=Ḟ$o/o‘Ḃ

Wypróbuj online!

ÆRạl2=Ḟ$o/     Main link; argument is z
ÆR             Generate all primes in the range [2..z]
  ạ            Absolute difference with z for each prime
   l2          Logarithm Base 2
     =Ḟ$       For each one, check if it's equal to its floored value (i.e. if it is an integer)
        o/     Reduce by Logical OR to check if any prime plus a power of two equals the z
          o‘Ḃ  Or it's not an odd number. If it's not an odd number, then automatically return 1 (false).

Dane wyjściowe 1dla false i 0true.

Perl 6 , 55 bajtów

{so$_%2&&$_∉((1,2,4...*>$_) [X+] grep &is-prime,^$_)}

Wypróbuj online!

• (1, 2, 4 ... * > $_) jest sekwencją potęg dwóch do momentu argumentu wejściowego (Perl wyprowadza szereg geometryczny z podanych elementów).
• grep &is-prime, ^$_ jest listą liczb pierwszych aż do argumentu wejściowego.
• [X+] ocenia sumę wszystkich elementów iloczynu krzyżowego dwóch serii.

Mógłbym zrobić bez sodwóch bajtów mniej, ale wtedy zwraca dwie różne wartości fałszowania ( 0i False).

Aksjomat, 86 bajtów

f(n:PI):Boolean==(~odd?(n)=>false;d:=1;repeat(n<=d or prime?(n-d)=>break;d:=d*2);n<=d)

test i wyniki

(21) -> for i in 1..600 repeat if f(i) then output i
   1
   127
   149
   251
   331
   337
   373
   509
   599

Haskell, 104 102 bajtów

p x=[x]==[i|i<-[2..x],x`mod`i<1]
h k|even k=1>2|2>1=notElem k$((+)<$>(2^)<$>[0..k])<*>filter(p)[1..k]

Wyjaśnienie

• p jest funkcją znajdującą liczby pierwsze (bardzo nieefektywne!)
• Tworzenie listy (+)zastosowanej do funkcji cząstkowej 2 ^, która zostanie zastosowana do listy [0..input]
• Zastosowanie powyższego do listy przefiltrowano 1, aby wprowadzić liczby pierwsze
• Wynikowy produkt kartezjański o każdej możliwej wartości jest przeszukiwany, aby upewnić się, że dane wejściowe nie istnieją w produkcie kartezjańskim
• Chroniony, aby zapewnić, że parzyste wejście jest automatycznie fałszywe.

AKTUALIZACJA: Krzycz do Einkorn Enchanter za grę w golfa dwa bajty!

Common Lisp, 134 bajty

(lambda(x)(flet((p(x)(loop for i from 2 below x always(>(mod x i)0))))(or(evenp x)(do((j 1(* j 2))(m()(p(- x j))))((or(>= j x)m)m)))))

Zwraca, NILgdy argument jest liczbą Polignac, w Tprzeciwnym razie.

Wypróbuj online!

Nie golfowany:

(lambda (n)
  (flet ((prime? (x)                 ; x is prime
           loop for i from 2 below x ; if for i in [2..n-1]
           always (> (mod x i) 0)))  ; is x is not divisible by i
    (or (evenp n)                    ; if n is even is not a Polignac number
        (do ((j 1( * j 2))           ; loop with j = 2^i, i = 0, 1,... 
             (m () (prime? (- n j)))); m = n - 2^i is prime?
            ((or (>= j n)            ; terminate if 2^i ≥ n
                 m)                  ; or if n - 2^i is prime
             m)))))                  ; not a polignac if n - 2^i is prime

APL (Dyalog Extended) , 12 bajtów

⍱2∘|⍲0⍭⊢-2*…

Wypróbuj online!

Anonimowa funkcja ukrytego przedrostka. Zwraca 1 za prawdę, 0 za fałsz.

W dużej mierze na podstawie odpowiedzi Japt ETHProductions .

Dzięki @ Adám za pomoc w grze w golfa moją oryginalną odpowiedź i za zrobienie Dyalog Extended w tym zakresie.

W jaki sposób:

⍱2∘|⍲0⍭⊢-2*…   ⍝ Tacit prefix function; input will be called ⍵
           …    ⍝ Inclusive Range [0..⍵]
         2*     ⍝ 2 to the power of each number in the range
       ⊢-       ⍝ Subtract each from ⍵
     0⍭         ⍝ Non-primality check on each resulting number
    ⍲           ⍝ Logical NAND
 2∘|            ⍝ Mod 2
⍱               ⍝ Not any (bitwise OR reduction, then negated)

Python 2 , 98 bajtów

lambda x:not(x%2<1or any((lambda x:x>1and all(x%j for j in range(2,x)))(x-2**i)for i in range(x)))

Wypróbuj online!

Pyth , 14 bajtów

&%Q2!smP-^2dQl

Spróbuj!

Julia 0.4 , 31 bajtów

n->n%2*!any(ispow2,n-primes(n))

Wypróbuj online!

APL (NARS) 80 znaków, 160 bajtów

∇r←f w;n
r←¯1⋄→0×⍳(w≤0)∨w≥9E9⋄r←0⋄→0×⍳0=2∣w⋄n←r←1
→0×⍳w≤n⋄→3×⍳0πw-n⋄n×←2⋄→2
r←0
∇

Funkcja 0π jest funkcją, która zwraca argument, że jest liczbą pierwszą lub nie. Dla mnie ta funkcja nie jest rekurencyjna, więc jest trochę dłuższa ... Test:

  {1=f ⍵:⍵⋄⍬}¨1..1000
1  127  149  251  331  337  373  509  599  701  757  809  877  905  907  959  977  997 

dla wejścia <= 0 lub wejścia> = 9E9 zwraca ¯1 (błąd)

  f¨0 ¯1 ¯2 900000000001
¯1 ¯1 ¯1 ¯1 

C # (interaktywny kompilator Visual C #) , 107 bajtów

x=>{var r=Enumerable.Range(2,x);return x%2>0&r.All(p=>r.Any(d=>d<p&p%d<1)|r.All(n=>x!=p+Math.Pow(2,n-2)));}

Wypróbuj online!

Nie jest to najbardziej wydajny kod, ale wydaje się działać. Moje oryginalne rozwiązanie filtrowało liczby pierwsze przed przetestowaniem ich w formule i działało znacznie lepiej. Obecna wersja jest o 11 bajtów krótsza.

// input x is an integer
x=>{
  // we need to generate several
  // ranges. since this is verbose,
  // generate 1 and keep a reference
  var r=Enumerable.Range(2,x);
  // this is the main condition
  return
     // input must be odd
     x%2>0&
     // generate all possible p's
     // over our range and ensure that
     // they satisfy the following
     r.All(p=>
       // either p is not prime
       r.Any(d=>d<p&p%d<1)
       |
       // or there is no n that satisfies
       // the formula: x=p+2^n
       r.All(n=>x!=p+Math.Pow(2,n-2))
     );
}