Um número é um número de Polignac se, e somente se, for ímpar e não puder ser representado na forma p + 2 ^{n, em} que n é um número inteiro não negativo ep é um número inteiro primo.

Tarefa

Escreva um código que use um número inteiro positivo e determine se é um número de Polignac. Você pode gerar dois valores distintos, um para verdadeiro e outro para falso. Você deve minimizar sua contagem de bytes.

Casos de teste

Para casos positivos, aqui está o 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, ...

Aqui estão alguns casos negativos:

22, 57

Japonês , 9 14 13 bytes

o!²mnU dj |Uv

Teste online! ou Encontre todos os números inteiros de Polignac abaixo de 1000 .

Saídas 1para entradas falsas e verdadeiras 0.

Explicação

 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

Geléia , 11 10 bytes

Guardado 1 byte graças a @Dennis

Ḷ2*³_ÆPS<Ḃ

Experimente online!

Como funciona

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

Retorna $0$ ou $1$ .

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

Experimente online!

Quão?

Começamos com $p = 1$ . Testamos se $y = n - p$ é composto e produzimos um booleano de acordo. O próximo teste é realizado com $p \times 2$ .

Assim que $p$ for maior que $n$ , paramos a recursão e retornamos $n$ .

Os resultados de todas as iterações são AND 'juntos, coagindo os valores booleanos para $0$ ou $1$ .

Desde que todos os resultados intermediários sejam verdadeiros, terminamos com um teste bit a bit, como:

1 & 1 & 1 & n

Isso fornece $1$ se e somente se $n$ for ímpar, que é a última condição necessária para validar a entrada como um número de Polignac.

Python 2 , 60 57 56 bytes

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

Experimente online!

Gelatina , 10 bytes

Um envio alternativo de geléia de 10 bytes ao já publicado.

_ÆRBS€’×ḂẠ

Um link monádico retornando 1 para os números de Polignac e 0 caso contrário.

Experimente online! ou veja os abaixo de 1000 .

Quão?

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

-1 byte graças a Emigna

Ýo-pZ¹È~

Saídas 0para entradas 1verdadeiras e para entradas falsas.

Experimente online!

Python 2 , 99 bytes

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

Experimente online!

-4 bytes graças a Leaky Nun

-2 bytes graças ao Wondercricket

+8 bytes para corrigir um erro

-1 byte graças ao Sr. Xcoder

-3 bytes graças ao Einkorn Enchanter

+12 bytes para corrigir um erro

Regex (ECMAScript), 97 bytes

Esse problema representava um caso interessante para solucionar o problema de falta de um cabeçote não atômico. E é a única vez até agora que tive um bom motivo para colocar as duas versões do poder do teste 2 ((x+)(?=\2$))*x$e (?!(x(xx)+)\1*$), no mesmo regex, e o único tempo até agora necessário para proteger o teste principal contra a correspondência 1, como (?!(xx+)\1+$)xx, quando usado em uma regex maior.

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

Experimente 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 + pesquisa molecular), 53 52 bytes

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

Esta versão não é apenas muito mais limpa, mas muito mais rápida, porque, em vez de ter que percorrer todas as maneiras possíveis em que N é a soma de dois números, ela pode apenas percorrer subtraindo cada potência de 2 de N e testar a diferença por ser a principal. .

A cabeça molecular lookah pode ser facilmente convertida em uma aparência de comprimento variável:

Regex (.NET ou ECMAScript 2018), 55 54 bytes

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

Experimente online! (.NET)
Experimente 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 bytes

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

PHP , 75 bytes

imprime 1 para verdade e 0 para falsidade

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

Experimente online!

Experimente online! Polignac Inteiros abaixo de 10000

Pari / GP , 34 bytes

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

Experimente online!

Braquilog , 15 13 bytes

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

Experimente online!

Saída de números Polignac até 1000.

Retorna false.para números de Polignac e true.outros.

Com base na resposta excluída do @ LeakyNun, com algumas correções (postadas com sua permissão).

(-2 bytes usando o método de Jonathan Allan para verificar se o número é uma potência de dois.)

O número fornecido não é de Polignac se:

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

Gelatina , 13 bytes

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

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

Saídas 1para false e 0true.

Perl 6 , 55 bytes

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

Experimente online!

• (1, 2, 4 ... * > $_) é uma sequência dos poderes de dois até o argumento de entrada (Perl infere a série geométrica a partir dos elementos fornecidos).
• grep &is-prime, ^$_ é a lista de números primos até o argumento de entrada.
• [X+] avalia a soma de todos os elementos do produto cruzado das duas séries.

Eu poderia ter feito sem o sopor dois bytes a menos, mas, em seguida, ele retorna dois valores distintos de falsidade ( 0e False).

Axioma, 86 bytes

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

teste e resultados

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

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]

Explicação

• p é uma função que encontra números primos (muito ineficiente!)
• Criando uma lista de (+)função parcial aplicada a 2 ^ que é aplicada a uma lista [0..input]
• Aplicando o acima a uma lista filtrada 1 para inserir primos
• O produto cartesiano resultante de todos os valores possíveis é pesquisado para garantir que não exista entrada no produto cartesiano
• Guardado para garantir que uma entrada uniforme seja automaticamente falsa.

ATUALIZAÇÃO: Grite para o Einkorn Enchanter por jogar dois bytes!

Lisp comum, 134 bytes

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

Retorne NILquando o argumento for um número Polignac, Tcaso contrário.

Experimente online!

Ungolfed:

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

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

Experimente online!

Função tácita de prefixo anônimo. Retorna 1 para verdade, 0 para falsidade.

Basicamente baseado na resposta japonesa do ETHProductions .

Agradeço a @ Adám por ajudar no golfe minha resposta original e por fazer o Dyalog Extended nesse sentido.

Quão:

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

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

Experimente online!

Pitão , 14 bytes

&%Q2!smP-^2dQl

Tente!

Julia 0.4 , 31 bytes

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

Experimente online!

APL (NARS) 80 caracteres, 160 bytes

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

A função 0π é a função que retorna seu argumento é primária ou não. Para mim, essa função não é recursiva, por isso é um pouco mais longa ... Teste:

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

para entrada <= 0 ou entrada> = 9E9, retorna ¯1 (erro)

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

C # (compilador interativo do Visual C #) , 107 bytes

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

Experimente online!

Não é o código mais eficiente, mas parece funcionar. Minha solução original filtrou os primos antes de testá-los na fórmula e teve um desempenho muito melhor. A versão atual é 11 bytes menor.

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