Angka adalah angka de Polignac jika dan hanya jika itu ganjil dan tidak dapat direpresentasikan dalam bentuk p + 2 ^{n di} mana n adalah bilangan bulat non-negatif dan p adalah bilangan bulat utama.

Tugas

Tulis beberapa kode yang mengambil bilangan bulat positif dan tentukan apakah itu nomor de Polignac. Anda dapat menampilkan dua nilai berbeda satu untuk true dan satu untuk false. Anda harus meminimalkan jumlah byte Anda.

Uji Kasus

Untuk kasus positif inilah 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, ...

Berikut ini beberapa kasus negatif:

22, 57

Japt , 9 14 13 byte

o!²mnU dj |Uv

Uji secara online! atau Temukan semua bilangan bulat de Polignac di bawah 1000 .

Keluaran 1untuk input palsu dan 0untuk kebenaran.

Penjelasan

 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

Jelly , 11 10 byte

Disimpan 1 byte berkat @Dennis

Ḷ2*³_ÆPS<Ḃ

Cobalah online!

Bagaimana itu bekerja

Ḷ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 byte

Mengembalikan $0$ atau $1$ .

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

Cobalah online!

Bagaimana?

Kita mulai dengan $p = 1$ . Kami menguji apakah $y = n - p$ adalah komposit dan menghasilkan boolean yang sesuai. Tes selanjutnya dilakukan dengan $p \times 2$ .

Begitu $p$ lebih besar dari $n$ , kita menghentikan rekursi dan mengembalikan $n$ .

Hasil dari semua iterasi adalah AND'd bersama-sama, memaksa nilai boolean menjadi $0$ atau $1$ .

Asalkan semua hasil antara benar, kami berakhir dengan uji bitwise seperti:

1 & 1 & 1 & n

Ini memberikan $1$ jika dan hanya jika $n$ ganjil, yang merupakan kondisi terakhir yang diperlukan untuk memvalidasi input sebagai nomor de Polignac.

Python 2 , 60 57 56 byte

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

Cobalah online!

Jelly , 10 byte

Alternatif pengiriman 10 byte Jelly ke yang sudah diposkan.

_ÆRBS€’×ḂẠ

Tautan monadik yang mengembalikan 1 untuk nomor de Polignac dan 0 jika tidak.

Cobalah online! atau lihat yang di bawah 1000 .

Bagaimana?

_Æ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 byte

-1 byte terima kasih kepada Emigna

Ýo-pZ¹È~

Output 0untuk input yang benar dan 1untuk input yang salah.

Cobalah online!

Python 2 , 99 byte

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

Cobalah online!

-4 bytes berkat Leaky Nun

-2 byte berkat Wondercricket

+8 byte untuk memperbaiki kesalahan

-1 byte terima kasih kepada Tn. Xcoder

-3 byte terima kasih kepada Einkorn Enchanter

+12 byte untuk memperbaiki kesalahan

Regex (ECMAScript), 97 byte

Masalah ini menimbulkan kasus menarik untuk mengatasi masalah kurangnya pencarian non-atom. Dan ini satu-satunya waktu sejauh ini sehingga saya memiliki alasan yang bagus untuk menempatkan kedua versi uji 2, ((x+)(?=\2$))*x$dan (?!(x(xx)+)\1*$), di regex yang sama, dan satu-satunya waktu sejauh ini yang saya perlukan untuk melindungi uji utama terhadap pencocokan 1, seperti (?!(xx+)\1+$)xx, ketika digunakan dalam regex yang lebih besar.

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

Cobalah 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 + molekul lookahead), 53 52 byte

^(?!(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.
)

Versi ini tidak hanya jauh lebih bersih, tetapi jauh lebih cepat, karena alih-alih harus memutar melalui semua cara yang mungkin bahwa N adalah jumlah dari dua angka, itu hanya dapat siklus melalui pengurangan setiap kekuatan 2 dari N dan menguji perbedaan untuk menjadi prima .

Tampilan molekul dapat dengan mudah dikonversi ke tampilan panjang variabel di belakang:

Regex (.NET atau ECMAScript 2018), 55 54 byte

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

Cobalah online! (.NET)
Cobalah secara 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 byte

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

PHP , 75 bytes

mencetak 1 untuk truey dan 0 untuk falsy

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

Cobalah online!

Cobalah online! Integer Polignac di bawah 10.000

Pari / GP , 34 byte

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

Cobalah online!

Brachylog , 15 13 byte

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

Cobalah online!

Output nomor Polignac hingga 1000.

Pengembalian false.untuk nomor de Polignac dan true.lainnya.

Berdasarkan jawaban yang dihapus @ LeakyNun, dengan beberapa perbaikan bug (diposkan dengan izin mereka).

(-2 byte dengan menggunakan metode @Jonathan Allan untuk memeriksa apakah angka tersebut adalah kekuatan dua.)

Nomor yang diberikan bukan nomor de Polignac jika:

/₂ℕ              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

Jelly , 13 byte

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

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

Output 1untuk false dan 0true.

Perl 6 , 55 byte

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

Cobalah online!

• (1, 2, 4 ... * > $_) adalah urutan kekuatan dua hingga argumen input (Perl menyimpulkan deret geometri dari elemen yang disediakan).
• grep &is-prime, ^$_ adalah daftar bilangan prima hingga argumen input.
• [X+] mengevaluasi jumlah semua elemen produk silang dari dua seri.

Saya bisa melakukannya tanpa kurang dari sodua byte, tetapi kemudian mengembalikan dua nilai falsy yang berbeda ( 0dan False).

Aksioma, 86 byte

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

tes dan hasil

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

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]

Penjelasan

• p adalah fungsi yang menemukan bilangan prima (sangat tidak efisien!)
• Membuat daftar (+)fungsi 2 parsial yang diterapkan ke daftar [0..input]
• Menerapkan hal di atas ke daftar memfilter 1 untuk memasukkan bilangan prima
• Produk kartesius yang dihasilkan dari setiap nilai yang mungkin dicari untuk memastikan input tidak ada dalam produk kartesius
• Diproteksi untuk memastikan bahwa input genap secara otomatis salah.

PEMBARUAN: Berteriaklah kepada Einkorn Enchanter karena bermain golf dua byte!

Common Lisp, 134 byte

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

Kembali NILketika argumennya adalah nomor Polignac, Tjika tidak.

Cobalah online!

Tidak Disatukan:

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

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

Cobalah online!

Fungsi tacit awalan anonim. Mengembalikan 1 untuk truey, 0 untuk falsy.

Sebagian besar didasarkan pada jawaban Japt ETHProductions ' .

Terima kasih kepada @ Adám karena telah membantu golf jawaban asli saya, dan untuk membuat Dyalog Extended dalam hal ini.

Bagaimana:

⍱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 byte

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

Cobalah online!

Pyth , 14 byte

&%Q2!smP-^2dQl

Cobalah!

Julia 0,4 , 31 byte

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

Cobalah online!

APL (NARS) 80 karakter, 160 byte

∇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
∇

Fungsi 0π adalah fungsi yang mengembalikan argumennya prima atau tidak. Bagi saya fungsi ini belum rekursif sehingga sedikit lebih panjang ... Uji:

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

untuk input <= 0 atau input> = 9E9 itu mengembalikan ¯1 (kesalahan)

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

C # (Visual C # Interactive Compiler) , 107 byte

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)));}

Cobalah online!

Bukan kode yang paling efisien, tetapi tampaknya berhasil. Solusi asli saya memfilter bilangan prima sebelum mengujinya dalam rumus dan kinerjanya jauh lebih baik. Versi saat ini lebih pendek 11 byte.

// 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))
     );
}