Ist meine Nummer eine Polignac-Nummer?

21

Eine Zahl ist genau dann eine de Polignac-Zahl, wenn sie ungerade ist und nicht in der Form p + 2 n dargestellt werden kann, wobei n eine nicht negative ganze Zahl und p eine ganze Primzahl ist.

Aufgabe

Schreiben Sie einen Code, der eine positive ganze Zahl enthält und feststellt, ob es sich um eine de Polignac-Zahl handelt. Sie können zwei unterschiedliche Werte ausgeben, einen für wahr und einen für falsch. Sie sollten darauf abzielen, Ihre Byteanzahl zu minimieren.

Testfälle

Für positive Fälle ist hier der 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, ...

Hier sind einige negative Fälle:

22, 57
Weizen-Assistent
quelle
Können wir wahrheitsgemäße und falsche Ausgaben anstelle von zwei unterschiedlichen Ausgaben haben?
Ok,
@Okx Ich werde nein sagen.
Wheat Wizard
Lassen Sie uns diese Diskussion im Chat fortsetzen .
Wheat Wizard
Ähm ... für die negativen Fälle ist es im Grunde eine beliebige Zahl, die nicht im OEIS enthalten ist, oder? Stellen Sie sicher, dass ich nichts Offensichtliches verpasst habe.
Magic Octopus Urn
@MagicOctopusUrn Ja.
Weizen-Zauberer

Antworten:

11

Japt , 9 14 13 Bytes

o!²mnU dj |Uv

Online testen! oder Finden Sie alle de Polignac-Ganzzahlen unter 1000 .

Ausgänge 1für falsche Eingaben und 0für Wahrheiten.

Erläuterung

 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
ETHproductions
quelle
Dies scheint die falschen Ergebnisse für 2 & 3 zu liefern; Es kehrt zurück, falseaber es sind keine Polignac-Zahlen.
Shaggy
@Shaggy 3ist behoben, aber wir mussten zunächst nicht einmal Fälle behandeln. Festsetzung.
ETHproductions
@ Shaggy Jetzt behoben.
ETHproductions
Ich wollte gerade sagen, dass es eine gute Sache ist, dass der Fix für 3keine Bytes gekostet hat, als ich den Fix für 2- Autsch!
Shaggy
: O + 1 für wettbewerbsfähiges Programm, das nicht wie Codierungsfehler
aussieht
8

Jelly , 11 bis 10 Bytes

1 Byte dank @Dennis gespeichert

Ḷ2*³_ÆPS<Ḃ

Probieren Sie es online!

Wie es funktioniert

Ḷ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.
ETHproductions
quelle
Ḷ2*⁸_ÆPS<Ḃ Speichert ein Byte. tio.run/##ASQA2/9qZWxsef//4bi2Mirigbhfw4ZQUzzhuIL/…
Dennis
@Dennis Danke, ich wusste, dass es eine 3-Byte-Alternative zu geben musste ¬;ḂẠ. S<Ḃist weit außerhalb der Box, zumindest für mich :-)
ETHproductions
8

JavaScript (ES6),  56 54  53 Byte

Gibt 0 oder 1 .

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

Probieren Sie es online!

Wie?

Wir beginnen mit p=1 . Wir testen, ob y=n-p ist und ergeben dementsprechend einen Booleschen Wert. Der nächste Test wird mit p×2 .

Sobald p größer als n , stoppen wir die Rekursion und geben n .

Die Ergebnisse aller Iterationen werden UND-verknüpft, wodurch die Booleschen Werte entweder auf 0 oder 1 .

Vorausgesetzt, dass alle Zwischenergebnisse wahr sind, erhalten wir einen bitweisen Test wie:

1 & 1 & 1 & n

Dies ergibt 1 genau dann, wenn n ungerade ist. Dies ist die letzte Bedingung, die erforderlich ist, um die Eingabe als De-Polignac-Zahl zu validieren.

Arnauld
quelle
3
Tolle Technik. Wahrscheinlich die einzig gültige Antwort, die nicht explizit n%2oder ähnlich
lautet
Dies hat falsche Negative für de Polignac-Zahlen der Form 2 ^ M + 1, wie 262145 und 2097153 (nachfolgende sind 4722366482869645213697, 38685626227668133590597633, 5192296858534827628530496329220097 usw.). Es ist nicht die Größe der Zahlen, die ein Problem darstellt, da beispielsweise 262139, 262259, 2097131 und 2097187 korrekt identifiziert werden. Natürlich musste ich aufgrund der Rekursion die Stapelgröße auf etwas sehr Großes vergrößern, um dies zu testen, und testete nur die Bereiche um die ersten beiden oben aufgeführten 2 ^ M + 1 de Polignac-Zahlen.
Deadcode
1
@Deadcode Vielen Dank für den Hinweis. Jetzt behoben.
Arnauld
1
@Arnauld Ah, du hast recht :) Nur um sicherzugehen , ich habe das getan und es ist behoben.
Deadcode
1
@Deadcode Ordentlich! :)
Arnauld
7

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)

Probieren Sie es online!

Dennis
quelle
Wow, das ist beeindruckend ineffizient. Primetest nach Wilsons Theorem . Auf der positiven Seite funktioniert es korrekt für 262145 und 2097153 (unter der Annahme unbegrenzter Stapel- und Bignum-Größe); Einige der anderen Einreichungen tun dies nicht. Sein Is-Prime-Algorithmus liefert "truthy" für 4, da (-6)% 4 = 2 ist, aber dies ist kein Problem, da gerade Zahlen von der abgelehnt werden &n&. Die Zahl 5 wäre falsch negativ, wenn es sich um eine de Polignac-Zahl handeln würde, da 1 + 4 = 5, aber dies ist kein Problem, da 2 + 3 = 5.
Deadcode
7

Gelee , 10 Bytes

Eine alternative 10-Byte-Jelly-Vorlage zu der bereits veröffentlichten.

_ÆRBS€’×ḂẠ

Eine monadische Verbindung, die 1 für de Polignac-Zahlen und 0 für andere zurückgibt.

Probieren Sie es online! oder sieh die unter 1000 .

Wie?

_Æ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
Jonathan Allan
quelle
Ich brauchte ungefähr 10 Minuten, um zu verstehen, wie das funktioniert ... großartige Technik, ich konnte mir keinen guten Weg
vorstellen
7

05AB1E , 9 8 Bytes

-1 Byte danke an Emigna

Ýo-pZ¹È~

Ausgänge 0für wahrheitsgemäße Eingaben und 1für falsche Eingaben.

Probieren Sie es online!

Okx
quelle
könnte sein Z.
Emigna
@Emigna Ah. Ich wusste, dass es eine 1-Byte-Alternative dazu gibt!
Okx
6

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

Probieren Sie es online!

-4 Bytes dank Leaky Nun

-2 Bytes dank Wondercricket

+8 Bytes, um einen Fehler zu beheben

-1 Byte danke an Herrn Xcoder

-3 Bytes dank Einkorn Enchanter

+12 Bytes, um einen Fehler zu beheben

HyperNeutrino
quelle
Ich denke das ist auch eine Python 3 kompatible Antwort?
Ari Cooper-Davis
Dies hat ein falsches Negativ für 1 und für alle de Polignac-Zahlen der Form 2 ^ M + 1, wie z. B. 262145 und 2097153 (nachfolgende sind 4722366482869645213697, 38685626227668133590597633, 5192296858534827628530496329220097 usw.). Es ist nicht die Größe der Zahlen, die ein Problem darstellt, da beispielsweise 262139, 262259, 2097131 und 2097187 korrekt identifiziert werden.
Deadcode
1
@Deadcode explizite Prüfung, um sicherzustellen, dass die "Primzahl" nicht 1 ist; sollte jetzt funktionieren
HyperNeutrino
6

Regex (ECMAScript), 97 Bytes

Dieses Problem war ein interessanter Fall, um das Problem des Fehlens eines nichtatomaren Vorausschauers zu umgehen. Und es ist das einzige Mal, dass ich einen guten Grund hatte, beide Versionen der Potenz von 2 zu testen, ((x+)(?=\2$))*x$und es ist das einzige Mal, dass ich (?!(x(xx)+)\1*$)den Primetest gegen Matching schützen musste 1, wie (?!(xx+)\1+$)xxbei Verwendung in einem größeren Regex.

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

Probieren Sie es 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 + Molecular Lookahead), 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.
)

Diese Version ist nicht nur viel sauberer, sondern auch viel schneller, denn anstatt alle möglichen Wege durchlaufen zu müssen, in denen N die Summe von zwei Zahlen ist, kann man einfach jede Potenz von 2 von N subtrahieren und die Differenz auf Primzahl testen .

Der molekulare Lookahead kann einfach in einen Look mit variabler Länge umgewandelt werden:

Regex (.NET oder ECMAScript 2018), 55 54 Byte

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

Probieren Sie es online! (.NET)
Probieren Sie es 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
    )
)
Deadcode
quelle
Ihre Regex kann ^(?!(x+)((?!(xx+)\3+$)x*(?!(x(xx)+)\4*$)|x(?!(x(xx)+)\6*$)x*(?!(xx+)\8+$)x)?\1$)ohne allzu große Schwierigkeiten optimiert werden. Dann kann mit einigen sorgfältigen Überlegungen weiter nach Golf gespielt werden ^(?!(x+)((x?)(?!(x(x\3)+)\4+$)x*(?!(x(xx)+|\3\3+)\6+$)\3)?\1$). Kürzere können noch möglich sein
H.PWiz
Mein kürzester ist allerdings sehr langsam
H.PWiz
oh, (x(xx)+|\3\3+)->(x\3?(xx)+)
H.PWiz
4

Mathematica, 41 Bytes

OddQ@#&&!Or@@PrimeQ[#-2^Range[0,Log2@#]]&
Alephalpha
quelle
1
Es gibt kein eingebautes dafür? Wow, ich bin überrascht.
HyperNeutrino
1
Es ist so ärgerlich , dass hier Mathematica negative Primzahlen hält prim sein, sonst könnten Sie durch das Ersetzen sparen Bytes PrimeQ[#-2^Range[0,Log2@#]]mit PrimeQ[#-2^Range[0,#]]und dann durch PrimeQ[#-2^Range@#/2].
Greg Martin
4

Brachylog , 15 bis 13 Bytes

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

Probieren Sie es online!

Polignac-Zahlen bis 1000 ausgeben.

Rückgabe false.für de Polignac-Nummern und true.andere.

Basierend auf der gelöschten Antwort von @ LeakyNun mit einigen Bugfixes (mit deren Erlaubnis veröffentlicht).

(-2 Bytes mit der @ Jonathan Allan-Methode, um zu überprüfen, ob die Zahl eine Zweierpotenz ist.)

Die angegebene Nummer ist keine Polignac-Nummer, wenn:

/₂ℕ              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
Sundar - Setzen Sie Monica wieder ein
quelle
=h2wäre 1 Byte kürzer, aber es funktioniert auch nicht 3.
Fatalize
Hinweis für (nicht mobiles) Selbst: 14 Bytes Online testen! . Inspiriert von Jonathan Allans Jelly-Antwort.
Sundar - Reinstate Monica
13 Probieren Sie es online!
Sundar - Reinstate Monica
Erinnerung für Ihre Notizen, denke ich?
Kroppeb
1
@Deadcode Früher hat es funktioniert, als dies gepostet wurde, und in der Zwischenzeit scheint sich etwas an der Aufteilung geändert zu haben - zum Beispiel. Probieren Sie es online! gibt false statt 64 zurück. Die Änderung ist wahrscheinlich von diesem Commit in die Sprache, aber ich war hier eine Weile nicht aktiv, also weiß nicht, ob es beabsichtigt oder ein Fehler ist.
Sundar - Setzen Sie Monica
3

Jelly , 13 Bytes

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

Probieren Sie es 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).

Ausgaben 1für false und 0für true.

HyperNeutrino
quelle
Ḷ2*ạfÆRṆdann auf Parität prüfen
Leaky Nun
@LeakyNun Ḷ2*ạfÆRṆo‘Ḃgibt 1für beide 127und zurück 22; das ist nicht richtig. Es sei denn, Sie haben das nicht vorgeschlagen.
HyperNeutrino
Sie müssen und verwenden, nicht oder. (oder Sie können meine letzte Verneinung entfernen und dann fortfahren, es in 9/10 Bytes zu tun)
Undichte Nonne
@LeakyNun Dein Snippet gibt es 0für 149.
ETHproductions
@ETHproductions richtig. Ändern, um _@es zu beheben.
Undichte Nonne
2

Perl 6 , 55 Bytes

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

Probieren Sie es online!

  • (1, 2, 4 ... * > $_) ist eine Folge der Zweierpotenzen bis zum Eingabeargument (Perl leitet die geometrische Reihe aus den bereitgestellten Elementen ab).
  • grep &is-prime, ^$_ ist die Liste der Primzahlen bis zum Eingabeargument.
  • [X+] Wertet die Summe aller Elemente des Kreuzprodukts der beiden Reihen aus.

Ich hätte auf die sozwei Bytes weniger verzichten können, aber dann werden zwei verschiedene falsche Werte ( 0und False) zurückgegeben.

Sean
quelle
2

Axiom, 86 Bytes

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

Test und Ergebnisse

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

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]

Erläuterung

  • p ist eine Funktion, die Primzahlen findet (sehr ineffizient!)
  • Erstellen einer Liste der (+)auf 2 ^ angewendeten Teilfunktionen, die auf eine Liste angewendet werden [0..Eingabe]
  • Anwenden des Obigen auf eine Liste, die mit 1 gefiltert ist, um Primzahlen einzugeben
  • Das resultierende kartesische Produkt mit jedem möglichen Wert wird durchsucht, um sicherzustellen, dass im kartesischen Produkt keine Eingabe vorhanden ist
  • Wird überwacht, um sicherzustellen, dass eine gerade Eingabe automatisch falsch ist.

UPDATE: Schreien Sie Einkorn Enchanter für das Golfen von zwei Bytes!

maple_shaft
quelle
1
p x=[x]==[i|i<-[2..x],x`mod`i<1]ist ein kürzerer Primalitätstest.
Wheat Wizard
@EinkornEnchanter Toller Fang! Du hast mich zwei Bytes Golf gespielt!
maple_shaft
1
Sie können auch filter p[1..k]anstelle vonfilter(p)[1..k]
Weizen-Assistent
1

Common Lisp, 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)))))

Gibt zurück, NILwenn das Argument eine Polignac-Zahl ist, Tandernfalls.

Probieren Sie es 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
Renzo
quelle
1

APL (Dyalog Extended) , 12 Byte

2∘|⍲0⍭⊢-2*…

Probieren Sie es online!

Anonymes Präfix implizite Funktion. Gibt 1 für wahr, 0 für falsch zurück.

Hauptsächlich basierend auf der Japt-Antwort von ETHProductions .

Vielen Dank an @ Adám für die Unterstützung beim Golfen meiner ursprünglichen Antwort und für die Erstellung von Dyalog Extended.

Wie:

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)
J. Sallé
quelle
0

Pyth , 14 Bytes

&%Q2!smP-^2dQl

Versuch es!

KarlKastor
quelle
0

APL (NARS) 80 Zeichen, 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
∇

Die Funktion 0π ist die Funktion, die zurückgibt, ob ihr Argument prim ist oder nicht. Für mich ist diese Funktion nicht rekursiv, daher ist sie etwas länger ... Test:

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

für Eingabe <= 0 oder Eingabe> = 9E9 wird ¯1 zurückgegeben (Fehler)

  f¨0 ¯1 ¯2 900000000001
¯1 ¯1 ¯1 ¯1 
RosLuP
quelle
0

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

Probieren Sie es online!

Nicht der effizienteste Code, scheint aber zu funktionieren. Meine ursprüngliche Lösung hat nach Primzahlen gefiltert, bevor sie in der Formel getestet wurde, und es lief viel besser. Die aktuelle Version ist 11 Bytes kürzer.

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