Un nombre est un nombre de Polignac si et seulement s'il est impair et ne peut pas être représenté sous la forme p + 2 ⁿ où n est un entier non négatif et p est un entier premier.

Tâche

Écrivez un code qui prend un entier positif et détermine s'il s'agit d'un nombre de Polignac. Vous pouvez afficher deux valeurs distinctes, une pour vrai et une pour faux. Vous devez viser à minimiser votre nombre d'octets.

Cas de test

Pour les cas positifs, voici l'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, ...

Voici quelques cas négatifs:

22, 57

Japt , 9 14 13 octets

o!²mnU dj |Uv

Testez-le en ligne! ou Trouver tous les nombres entiers de Polignac inférieurs à 1000 .

Sorties 1pour entrées fausses et 0pour véridiques.

Explication

 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ée , 11 10 octets

1 octet enregistré grâce à @Dennis

Ḷ2*³_ÆPS<Ḃ

Essayez-le en ligne!

Comment ça marche

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

Renvoie $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

Essayez-le en ligne!

Comment?

Nous commençons avec $p = 1$ . Nous testons si $y = n - p$ est composite et donnons un booléen en conséquence. Le test suivant est effectué avec $p \times 2$ .

Dès que $p$ est supérieur à $n$ , nous arrêtons la récursivité et retournons $n$ .

Les résultats de toutes les itérations sont ET ensemble, contraignant les valeurs booléennes à $0$ ou $1$ .

À condition que tous les résultats intermédiaires soient véridiques, nous nous retrouvons avec un test au niveau du bit tel que:

1 & 1 & 1 & n

Cela donne $1$ si et seulement si $n$ est impair, qui est la dernière condition requise pour valider l'entrée en tant que nombre de Polignac.

Python 2 , 60 57 56 octets

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

Essayez-le en ligne!

Gelée , 10 octets

Une soumission Jelly de 10 octets alternative à celle déjà publiée.

_ÆRBS€’×ḂẠ

Un lien monadique renvoyant 1 pour les nombres de Polignac et 0 sinon.

Essayez-le en ligne! ou voir ceux de moins de 1000 .

Comment?

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

-1 octet grâce à Emigna

Ýo-pZ¹È~

Sorties 0pour entrées véridiques et 1pour entrées fausses.

Essayez-le en ligne!

Python 2 , 99 octets

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

Essayez-le en ligne!

-4 octets grâce à Leaky Nun

-2 octets grâce à Wondercricket

+8 octets pour corriger une erreur

-1 octet merci à M. Xcoder

-3 octets grâce à Einkorn Enchanter

+12 octets pour corriger une erreur

Regex (ECMAScript), 97 octets

Ce problème a posé un cas intéressant pour contourner le problème du manque d'anticipation non atomique. Et c'est la seule fois jusqu'à présent que j'ai eu une bonne raison de mettre les deux versions du test de puissance de 2, ((x+)(?=\2$))*x$et (?!(x(xx)+)\1*$), dans le même regex, et la seule fois jusqu'à présent, j'ai eu besoin de protéger le test principal contre la correspondance 1, comme (?!(xx+)\1+$)xx, lorsqu'il est utilisé dans une expression régulière plus grande.

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

Essayez-le en ligne!

# 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 + antenne moléculaire), 53 52 octets

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

Cette version est non seulement beaucoup plus propre, mais beaucoup plus rapide, car au lieu d'avoir à parcourir toutes les façons possibles que N est la somme de deux nombres, elle peut simplement parcourir en soustrayant chaque puissance de 2 de N et tester la différence pour être premier .

La tête de lecture moléculaire peut être facilement convertie en vue arrière de longueur variable:

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

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

Essayez-le en ligne! (.NET)
Essayez-le en ligne! (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 octets

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

PHP , 75 octets

imprime 1 pour la vérité et 0 pour la fausse

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

Essayez-le en ligne!

Essayez-le en ligne! Polignac Entiers sous 10000

Pari / GP , 34 octets

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

Essayez-le en ligne!

Brachylog , 15 13 octets

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

Essayez-le en ligne!

Sortie de Polignac jusqu'à 1000.

Retourne false.pour les nombres de Polignac et true.autrement.

Basé sur la réponse supprimée de @ LeakyNun, avec quelques corrections de bugs (publiés avec leur permission).

(-2 octets en utilisant la méthode de @Jonathan Allan pour vérifier si le nombre est une puissance de deux.)

Le numéro donné n'est pas un numéro 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

Gelée , 13 octets

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

Essayez-le en ligne!

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

Sorties 1pour faux et 0pour vrai.

Perl 6 , 55 octets

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

Essayez-le en ligne!

• (1, 2, 4 ... * > $_) est une séquence des puissances de deux jusqu'à l'argument d'entrée (Perl déduit la série géométrique des éléments fournis).
• grep &is-prime, ^$_ est la liste des nombres premiers jusqu'à l'argument d'entrée.
• [X+] évalue la somme de tous les éléments du produit croisé des deux séries.

J'aurais pu me passer sode deux octets de moins, mais cela renvoie deux valeurs de falsification distinctes ( 0et False).

Axiome, 86 octets

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

test et résultats

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

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]

Explication

• p est une fonction qui trouve des nombres premiers (très inefficace!)
• Création d'une liste de (+) fonction partielle appliquée à 2 ^ qui est appliquée à une liste [0..input]
• Appliquer ce qui précède à une liste filtrée 1 pour entrer des nombres premiers
• Le produit cartésien résultant de chaque valeur possible est recherché pour s'assurer que l'entrée n'existe pas dans le produit cartésien
• Protégé pour garantir qu'une entrée paire est automatiquement fausse.

MISE À JOUR: Criez à Einkorn Enchanter pour jouer au golf sur deux octets!

Lisp commun, 134 octets

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

Retourne NILquand l'argument est un nombre de Polignac, Tsinon.

Essayez-le en ligne!

Non 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 octets

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

Essayez-le en ligne!

Fonction tacite de préfixe anonyme. Renvoie 1 pour la vérité, 0 pour la fausse.

Largement basé sur la réponse Japt d'ETHProductions .

Merci à @ Adám d'avoir aidé à jouer au golf ma réponse originale et d'avoir fait Dyalog Extended d'ailleurs.

Comment:

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

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

Essayez-le en ligne!

Pyth , 14 octets

&%Q2!smP-^2dQl

Essayez!

Julia 0.4 , 31 octets

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

Essayez-le en ligne!

APL (NARS) 80 caractères, 160 octets

∇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 fonction 0π est la fonction qui renvoie son argument premier ou non. Pour moi cette fonction n'est pas récursive donc elle est un peu plus longue ... Test:

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

pour entrée <= 0 ou entrée> = 9E9, il renvoie ¯1 (erreur)

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

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

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

Essayez-le en ligne!

Pas le code le plus efficace, mais semble fonctionner. Ma solution d'origine a filtré les nombres premiers avant de les tester dans la formule et elle a fonctionné beaucoup mieux. La version actuelle est plus courte de 11 octets.

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