Un número es un número de Polignac si y solo si es impar y no se puede representar en la forma p + 2 ⁿ donde n es un número entero no negativo y p es un número entero primo.

Tarea

Escriba un código que tome un número entero positivo y determine si es un número de Polignac. Puede generar dos valores distintos, uno para verdadero y otro para falso. Debe intentar minimizar su recuento de bytes.

Casos de prueba

Para casos positivos aquí está el 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, ...

Aquí hay algunos casos negativos:

22, 57

Japt , 9 14 13 bytes

o!²mnU dj |Uv

¡Pruébelo en línea! o Encuentra todos los enteros de Polignac menores de 1000 .

Salidas 1para entradas falsas y 0para la verdad.

Explicación

 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

Jalea , 11 10 bytes

Guardado 1 byte gracias a @Dennis

Ḷ2*³_ÆPS<Ḃ

Pruébalo en línea!

Cómo 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

Devuelve $0$ o $1$ .

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

Pruébalo en línea!

¿Cómo?

Comenzamos con $p = 1$ . Probamos si$y = n - p$ es compuesto y producimos un booleano en consecuencia. La siguiente prueba se realiza con$p \times 2$ .

Tan pronto como $p$ es mayor que$n$ , detenemos la recursividad y devolvemos $n$ .

Los resultados de todas las iteraciones son AND juntos, coaccionando los valores booleanos a $0$ o $1$ .

Siempre que todos los resultados intermedios sean verdaderos, terminamos con una prueba de bits como:

1 & 1 & 1 & n

Esto da $1$ si y solo si$n$ es impar, que es la última condición requerida para validar la entrada como un 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)

Pruébalo en línea!

Jalea , 10 bytes

Una presentación alternativa de 10 bytes Jelly a la ya publicada.

_ÆRBS€’×ḂẠ

Un enlace monádico regresando 1 para los números de Polignac y 0 en caso contrario.

Pruébalo en línea!o ver los menores de 1000 .

¿Cómo?

_Æ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 gracias a Emigna

Ýo-pZ¹È~

Salidas 0para entradas verdaderas y 1para entradas falsas.

Pruébalo en línea!

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

Pruébalo en línea!

-4 bytes gracias a Leaky Nun

-2 bytes gracias a Wondercricket

+8 bytes para corregir un error

-1 byte gracias al Sr. Xcoder

-3 bytes gracias a Einkorn Enchanter

+12 bytes para corregir un error

Regex (ECMAScript), 97 bytes

Este problema planteó un caso interesante para solucionar el problema de la falta de anticipación no atómica. Y es el único momento hasta el momento en que tengo una buena razón para probar ambas versiones del poder de 2 ((x+)(?=\2$))*x$y (?!(x(xx)+)\1*$), en la misma expresión regular, y el único momento hasta el momento que necesito para proteger la prueba principal contra la coincidencia. 1, como (?!(xx+)\1+$)xx, cuando se usa en una expresión regular más grande.

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

Pruébalo en línea!

# 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 + lookahead 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 versión no solo es mucho más limpia, sino también mucho más rápida, porque en lugar de tener que recorrer todas las formas posibles en que N es la suma de dos números, simplemente puede recorrer en ciclo restando cada potencia de 2 de N y probar la diferencia para ser primo .

El lookahead molecular se puede convertir fácilmente en un lookbehind de longitud variable:

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

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

Pruébalo en línea! (.NET) ¡
Pruébelo en línea! (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 veracidad y 0 para falsedad

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

Pruébalo en línea!

Pruébalo en línea! Polignac enteros menores de 10000

Pari / GP , 34 bytes

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

Pruébalo en línea!

Brachylog , 15 13 bytes

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

Pruébalo en línea!

Salida de números de Polignac hasta 1000.

Devoluciones false.para números de Polignac y true.otros.

Basado en la respuesta eliminada de @ LeakyNun, con algunas correcciones de errores (publicadas con su permiso).

(-2 bytes usando el método de @Jonathan Allan para verificar si el número es una potencia de dos).

El número dado no es un número de Polignac si:

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

Jalea , 13 bytes

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

Pruébalo en línea!

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

Salidas 1para falso y 0para verdadero.

Perl 6 , 55 bytes

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

Pruébalo en línea!

• (1, 2, 4 ... * > $_) es una secuencia de las potencias de dos hasta el argumento de entrada (Perl infiere la serie geométrica de los elementos proporcionados).
• grep &is-prime, ^$_ es la lista de números primos hasta el argumento de entrada.
• [X+] evalúa la suma de todos los elementos del producto cruzado de las dos series.

Podría haber prescindido sode dos bytes menos, pero luego devuelve dos valores falsos distintos ( 0y 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)

prueba y 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]

Explicación

• p es una función que encuentra números primos (¡muy ineficiente!)
• Crear una lista de (+)funciones parciales aplicadas a 2 ^ que se aplica a una lista [0..input]
• Aplicando lo anterior a una lista filtrada 1 para ingresar primos
• Se busca el producto cartesiano resultante de todos los valores posibles para garantizar que no exista una entrada en el producto cartesiano
• Guardado para garantizar que una entrada par sea automáticamente falsa.

ACTUALIZACIÓN: ¡Grite a Einkorn Enchanter por jugar al golf dos bytes!

Lisp común, 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)))))

Regrese NILcuando el argumento sea un número de Polignac, de lo Tcontrario.

Pruébalo en línea!

Sin golf:

(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*…

Pruébalo en línea!

Prefijo anónimo función tácita. Devuelve 1 para la verdad, 0 para la falsedad.

En gran parte basado en la respuesta Japt de ETHProductions .

Gracias a @ Adám por ayudarme con el golf mi respuesta original, y por hacer Dyalog Extended para el caso.

Cómo:

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

Pruébalo en línea!

Pyth , 14 bytes

&%Q2!smP-^2dQl

¡Intentalo!

Julia 0.4 , 31 bytes

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

Pruébalo en línea!

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
∇

La función 0π es la función que devuelve su argumento es primo o no. Para mí, esta función no ha sido recursiva, por lo que es un poco más larga ... Prueba:

  {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 o entrada> = 9E9 devuelve ¯1 (error)

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

C # (compilador interactivo de 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)));}

Pruébalo en línea!

No es el código más eficiente, pero parece funcionar. Mi solución original filtró los primos antes de probarlos en la fórmula y funcionó mucho mejor. La versión actual es 11 bytes más corta.

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