Manchmal müssen Sie beim Schreiben eines Programms aus irgendeinem Grund eine Primzahl verwenden (z. B. Kryptografie). Ich gehe davon aus, dass Sie manchmal auch eine zusammengesetzte Nummer verwenden müssen. Manchmal muss Ihr Programm, zumindest hier bei PPCG, in der Lage sein, mit willkürlichen Änderungen umzugehen. Und unter Umständen, die für eine interessante PPCG-Frage geeignet sind, müssen möglicherweise sogar die von Ihnen verwendeten Zahlen beständig gegen Korruption sein ...

Definitionen

Eine zusammengesetzte Zahl ist eine Ganzzahl ≥ 4, die keine Primzahl ist, dh sie ist das Produkt von zwei kleineren Ganzzahlen größer als 1. Eine bitflipresistente zusammengesetzte Zahl ist wie folgt definiert: Es ist eine zusammengesetzte positive Ganzzahl, für die Sie sie schreiben in binär in der minimal möglichen Anzahl von Bits können Sie ein oder zwei beliebige Bits von der Zahl ändern, und die Zahl ist immer noch zusammengesetzt.

Beispiel

Betrachten Sie zum Beispiel die Zahl 84. In der Binärdatei ist das 1010100. Hier sind alle Zahlen, die sich nicht mehr als 2 Bit davon unterscheiden:

0000100 4 2 × 2
0010000 16 4 × 4
0010100 20 4 × 5
0010101 21 3 × 7
0010110 22 2 × 11
0011100 28 4 × 7
0110100 52 4 × 13
1000000 64 8 × 8
1000100 68 4 × 17
1000101 69 3 × 23
1000110 70 7 × 10
1001100 76 4 × 19
1010000 80 8 × 10
1010001 81 9 × 9
1010010 82 2 × 41
1010100 84 7 × 12
1010101 85 5 × 17
1010110 86 2 × 43
1010111 87 3 × 29
1011000 88 8 × 11
1011100 92 4 × 23
1011101 93 3 × 31
1011110 94 2 × 47
1100100 100 10 × 10
1110000 112 8 × 14
1110100 116 4 × 29
1110101 117 9 × 13
1110110 118 2 × 59
1111100 124 4 × 31

Die erste Spalte ist die Zahl in binärer Form; Die zweite Spalte ist die Dezimalzahl. Wie die dritte Spalte angibt, sind alle diese Zahlen zusammengesetzt. Somit ist 84 eine bitflipresistente zusammengesetzte Zahl.

Die Aufgabe

Sie müssen eines der folgenden drei Programme oder Funktionen schreiben, je nachdem, was für Ihre Sprache am sinnvollsten ist:

• Ein Programm oder eine Funktion, die eine nichtnegative Ganzzahl n als Eingabe verwendet und die ersten n bitflipresistenten zusammengesetzten Zahlen ausgibt .
• Ein Programm oder eine Funktion, die eine nichtnegative Ganzzahl n als Eingabe verwendet und alle bitflipresistenten zusammengesetzten Zahlen kleiner als n ausgibt (oder, wenn Sie dies bevorzugen, kleiner oder gleich n , dh Sie können wählen, ob n in der Ausgabe enthalten sein soll, wenn Bitflip verwendet wird -beständig).
• Ein Programm oder eine Funktion, die keine Eingabe akzeptiert und alle bitflipresistenten zusammengesetzten Zahlen ausgibt. (Dies muss einen Ausgabemechanismus verwenden, der in der Lage ist, eine Ausgabe zu erzeugen, während das Programm noch ausgeführt wird, z. B. Drucken auf stdout, eine Lazy List oder einen Generator. Sie können nicht einfach die gesamte Liste berechnen und dann drucken.)

Testfälle

Hier sind die ersten paar bitflipresistenten Composite-Nummern:

84, 184, 246, 252, 324, 342, 424, 468, 588, 636, 664, 670, 712, 730, 934, 958

Klarstellungen

• Es sind nur die Zahlen, die Sie produzieren, die Bitflips widerstehen müssen. Hierbei geht es nicht darum, das Programm so zu gestalten, dass es gegenüber Bitflips resistent ist. Verwenden Sie die von Ihnen gewünschten Zahlen im Programm.
• Die von Ihnen ausgegebenen Zahlen müssen nicht gegen Bitflips in den "führenden Nullen" resistent sein. Stellen Sie sich vor, die Zahlen werden in der kleinstmöglichen Anzahl von Bits gespeichert, und nur diese Bits müssen gegen Umdrehen immun sein. Die ersten 1 Bits der ausgegebenen Zahlen müssen jedoch unempfindlich gegen Bitflips sein.
• Verwenden Sie einen beliebigen Algorithmus, der das richtige Ergebnis liefert. Sie werden hier nicht auf Effizienz bewertet.
• Wenn Sie nachweisen können, dass es endlich viele bitflipresistente zusammengesetzte Zahlen gibt, werden a) die Einschränkungen für das Ausgabeformat aufgehoben und b) die Liste kann hartcodiert werden (obwohl dies wahrscheinlich ausführlicher ist als nur die Berechnung). Diese Regel dient hauptsächlich der Vollständigkeit. Ich erwarte nicht, dass es relevant ist.

Siegbedingung

Das ist Code-Golf , also ist wie immer kürzer besser. Die Länge des Programms wird wie gewohnt in Bytes angegeben.

Gelee , 20? 22 Bytes

BµJŒċ;0Ṭ^µḄµÆPoỊṀ¬
⁴Ç#

Probieren Sie es online!

Ergibt die ersten n solcher Zahlen.

Vielleicht ;0kann die entfernt werden (ohne sie prüfen wir nicht, ob die Zahl selbst zusammengesetzt ist - gibt es Primzahlen mit allen zusammengesetzten Bit-Flips?)

Es ist zu beachten, dass es nicht ausreicht, den Test not(any(is prime))mit dem Satz von Bit-gespiegelten Zahlen durchzuführen . Wir müssen auch testen, dass 0das nicht im Set ist.

Dies liegt daran, dass 0es nicht prim und nicht zusammengesetzt ist ( 1ist auch, aber siehe unten).

Die Notwendigkeit, nach etwas zu 0suchen, lässt sich an einem Gegenbeispiel ablesen:

• 131136( 2 ¹⁷ +2 ⁶ ) hat das folgende Bit-Flip-Set:

[0, 64, 65, 66, 68, 72, 80, 96, 192, 320, 576, 1088, 2112, 4160, 8256, 16448, 32832, 65600, 131072, 131073, 131074, 131076, 131080, 131088, 131104, 131136, 131137, 131138, 131139, 131140, 131141, 131142, 131144, 131145, 131146, 131148, 131152, 131153, 131154, 131156, 131160, 131168, 131169, 131170, 131172, 131176, 131184, 131200, 131264, 131265, 131266, 131268, 131272, 131280, 131296, 131328, 131392, 131393, 131394, 131396, 131400, 131408, 131424, 131520, 131584, 131648, 131649, 131650, 131652, 131656, 131664, 131680, 131776, 131904, 132096, 132160, 132161, 132162, 132164, 132168, 132176, 132192, 132288, 132416, 132672, 133120, 133184, 133185, 133186, 133188, 133192, 133200, 133216, 133312, 133440, 133696, 134208, 135168, 135232, 135233, 135234, 135236, 135240, 135248, 135264, 135360, 135488, 135744, 136256, 137280, 139264, 139328, 139329, 139330, 139332, 139336, 139344, 139360, 139456, 139584, 139840, 140352, 141376, 143424, 147456, 147520, 147521, 147522, 147524, 147528, 147536, 147552, 147648, 147776, 148032, 148544, 149568, 151616, 155712, 163840, 163904, 163905, 163906, 163908, 163912, 163920, 163936, 164032, 164160, 164416, 164928, 165952, 168000, 172096, 180288, 196608, 196672, 196673, 196674, 196676, 196680, 196688, 196704, 196800, 196928, 197184, 197696, 198720, 200768, 204864, 213056, 229440]

Alle, außer 0zusammengesetzt, sind noch 0nicht prim.

1ist auch nicht primär und nicht zusammengesetzt und könnte im Set erscheinen. Wenn wir möchten, können wir dies jedoch so belassen, als wäre es ein Komposit:

• Alle Eingaben kleiner oder gleich 3(wenn überhaupt berücksichtigt) enthalten 0sowieso (in der Tat alle kleiner als 7).

• um 1in einem Bit Flip zu erreichen, muss die ursprüngliche Zahl die Form 2 ^k + 2 ^{0 haben} , und wenn diese größer ist als 3, dh k> 1 , dann können wir erreichen, 3indem wir das k- Bit abklappen und das 1- Bit setzen ( 2 ¹ + 2 ⁰ = 3 ).

• Um 1in zwei Bit-Flips zu erreichen, muss die ursprüngliche Zahl die Form 2 ^{k haben.} Wenn diese größer ist 3, können wir sie 2stattdessen in zwei Flips erreichen , und sie 2ist eine Primzahl.

Gegenwärtig behandelt der Code beide 0und 1zusammen unter Verwendung des "unbedeutenden" Atoms Ị.

Wie?

⁴Ç# - Main link: n
⁴   - 16
  # - count up from 16 finding the first n matches of
 Ç  -     last link (1) as a monad

BµJŒċ;0Ṭ^µḄµÆPoỊṀ¬ - Link 1, test a number: i
B                  - convert to a binary list
 µ                 - start a new monadic chain
  J                - range(length): [1,2,...,nBits]
   Œċ              - pairs with replacement: [[1,1],[1,2],...,[1,nBits],[2,2],[2,3],...,[2,nBits],...,[nBits-1,nBits]]
     ;0            - concatenate a zero
       Ṭ           - untruth (makes lists with ones at those indexes - the [1,1], [2,2], etc make the one-flips, the zero makes the no-flip, the rest make the two-flips)
        ^          - exclusive or with the binary list version of i (flip the bits)
         µ         - start a new monadic chain
          Ḅ        - un-binary (get the integer values of each of the flipped versions)
           µ       - start a new monadic chain
            ÆP     - is prime? (make a list of 1s for primes and 0 for non-primes)
               Ị   - is insignificant (abs(v)<=1)
              o    - logical or (now we have true for any primes, 0 or 1 - hence non-composites)
                Ṁ  - maximum (1 if any non-composite was found)
                 ¬ - not (1 if all were composite)

Brachylog , 32 38 Bytes

2<≜.¬(ḃ↰₂↰₂~ḃ≜{ṗ|ℕ<2}∧)
k~k|tgT∧?k↰:Tc

Probieren Sie es online!

Dies ist eine Funktion / ein Prädikat ↰₀, das einen Generator zurückgibt, der alle diese Zahlen generiert. (Der TIO-Link gibt nur die erste Zahl aus, sodass etwas beobachtet werden kann. Die lokale Ausführung hat jedoch viel mehr produziert.)

Jetzt aktualisiert, um Zahlen, die innerhalb von zwei Bitflips von 0 oder 1 liegen (die weder Primzahlen noch zusammengesetzte Zahlen sind), korrekt zu behandeln.

Erläuterung

Hilfsprädikat ↰₂ (gibt eine Liste zurück, die bis auf ein Element der Eingabe entspricht)

k~k|tgT∧?k↰:Tc
   |            Either:
 ~k               the output is produced by appending an arbitrary element
k                 to the input minus its last element
                Or:
        ?k        take the input minus its last element,
          ↰       call this predicate recursively on that,
      T    :Tc    then append
     g            the singleton list consisting of
    t             the last element of the input

Ich würde es lieben, wenn es eine schnellere Möglichkeit gäbe, diese relativ einfache Rekursion durchzuführen, aber ich bin mir nicht sicher, ob es noch eine gibt. Die Spezifikation enthält einige vielversprechend aussehende Funktionen, die jedoch als nicht implementiert gekennzeichnet sind.

Hauptprogramm ↰₀

2<≜.¬(ḃ↰₂↰₂~ḃ≜{ṗ|ℕ<2}∧)
2<≜                      For each integer greater than 2
   .                     generate it if
    ¬(                )  it does not have the following property:
      ḃ                  converting it to binary,
       ↰₂↰₂              running the helper predicate twice,
           ~ḃ            and converting back to decimal
             ≜           does not allow us to find a specific value
              {     }    that is:
               ṗ           prime;
                |        or:
                 ℕ<2       nonnegative and less than 2
                     ∧   (disable an unwanted implicit constraint)

JavaScript (ES6), 96 Byte

Ein vollständiges Programm, das nach der Anzahl der übereinstimmenden Ganzzahlen fragt und diese nacheinander mit anzeigt alert().

for(i=prompt(n=2);i;n+=2)(g=b=>b>n?alert(n,i--):(C=(n,x=n)=>n%--x?C(n,x):x>1)(n^b|1)&&g(b*2))(1)

Sofern Ihr Browser nicht für die Verwendung von Tail Call Optimization konfiguriert ist, wird dies möglicherweise aufgrund eines Rekursionsüberlaufs unterbrochen.

Unten finden Sie eine nicht rekursive Version (102 Bytes).

for(i=prompt(n=2);i;n+=2){for(c=b=1;b<n;b*=2,c&=C)for(C=k=2,x=n^b|1;k<x;k++)C|=!(x%k);c&&alert(n,i--)}

Annahme

Dieser Algorithmus basiert auf der Annahme, dass alle bitflipresistenten zusammengesetzten Zahlen gerade sind. Dies führt zu einer ziemlich wichtigen Vereinfachung: Anstatt jedes mögliche Bitpaar zu spiegeln, spiegeln wir nur Bit # 0 und ein anderes (oder überhaupt kein anderes Bit) und überprüfen, ob alle resultierenden Zahlen zusammengesetzt sind.

Ich kann jedoch keinen offensichtlichen Beweis dafür finden, dass es tatsächlich keine ungerade bitflipresistente zusammengesetzte Zahl gibt. Zufällig ist dies bei kleinen Zahlen nie der Fall (ich habe bis zu 1.000.000 überprüft), und es scheint, als würde die Wahrscheinlichkeit, eine zu finden, mit zunehmender Anzahl von Bits abnehmen (aber dies ist im Grunde nur meine Intuition darüber).

Jelly , 20 17 Bytes

BJŒċṬUḄ^;⁸ÆḍṂỊµÐḟ

Probieren Sie es online!

Wie es funktioniert

BJŒċṬUḄ^;⁸ÆḍṂỊµÐḟ  Main link. Argument: n

              µ    Combine all links to the left into a chain.
               Ðḟ  Filter-false; keep only integers k from [1, ..., n] for which
                   the chain returns 0.
B                    Convert k to binary.
 J                   Get the indices of all digits.
  Œċ                 Take all combination of two indices, with replacement.
    Ṭ                Untruth; map each index pair [i, j] to the Boolean array of
                     length j that has 1's at (and only at) indices i and j.
     U               Upend; reverse each Boolean array.
      Ḅ              Unbinary; convert each array from base 2 to integer.
       ^             XOR the resulting numbers with k.
        ;⁸           Append k to the resulting list.
          Æḍ         Count the number of proper divisors of each result.
            Ṃ        Take the minimum.
             Ị       Insignificant; test if the minimum is 0 or 1.

Python 2, 113 Bytes

r=range
lambda N:[n for n in r(1,N)if 1-any((bin(k).count('1')<3)*all((n^k)%q for q in r(2,n^k))for k in r(n+1))]

(Die zweite Zeile ist eine unbenannte Funktion, die eine Liste aller bitflipresistenten zusammengesetzten Zahlen zurückgibt, die kleiner sind als die Eingabe für die Funktion.)

Die Syntax all(u%q for q in range(2,u))wird Trueimmer dann ausgewertet, wenn sie uentweder Primzahl oder kleiner oder gleich ist 2, und ansonsten wird sie ausgewertet False. (Es ist leer, Truewenn ukleiner oder gleich ist 2.)

Mit anderen Worten, all(u%q for q in range(2,u))ist 0genau dann gleich, wenn zusammengesetzt uist.

Wenn die Eingabe der Funktion kleiner als ist 2, gibt die Funktion eine leere Liste zurück (wie gewünscht). Nehmen wir also an, die Eingabe Nist mindestens 2, und nehmen wir an 1 <= n < N. Für jedes kvon 0bis n(einschließlich) prüft der Code, ob nXOR mit zusammengesetzt kist, und er prüft auch, ob khöchstens zwei 1in seiner Binärdarstellung sind. Wenn n^kes zusammengesetzt ist oder wenn kes mehr als zwei hat 1, geht es weiter zum nächsten Wert von k. Wenn es auf diese Weise alle Werte von kvon 0durchläuft n, wird es nin die Liste aufgenommen.

Auf der anderen Seite, wenn ein Wert von ihm kmit höchstens zwei 1ist , so dass n^knicht Verbund ist, dann nist nicht in der Liste enthält.

Perl 6 , 87 85 Bytes

{grep {!grep {$_%all 2..^$_},($_ X+^grep {.base(2)~~m:g/1/ <3},^(2+<.log(2)))},2..$_}

Gibt alle Zahlen zurück, die kleiner oder gleich der eingegebenen Nummer sind.

Wie es funktioniert

Für jede Zahl n von 2 bis zur Eingabe wird Folgendes ausgeführt:

1. ^ (2 + <.log (2))

   Erzeugt alle nicht negativen Ganzzahlen, die dieselbe oder eine kürzere Bitlänge als n haben .

2. grep {.base (2) ~~ m: g / 1 / <3},

   Filtert Zahlen aus dieser Liste, für die weniger als drei Bits festgelegt sind (unter Verwendung eines regulären Ausdrucks).

3. $ _ X + ^

   XORs n mit jeder dieser Zahlen ergeben alle gültigen "Mutationen" von n .

4. ! grep {$ _% all 2 .. ^ $ _}

   Lässt n nur dann Teil der Ausgabeliste sein, wenn keine der Mutationen nicht zusammengesetzt ist (überprüfen Sie dies, indem Sie für jede Mutation x modulo eine All-Junction von Zahlen zwischen 2 und x -1 verwenden).

Mathematica, 115 Bytes

1 4 Byte gespeichert dank @MartinEnder

Cases[4~Range~#,x_/;And@@CompositeQ[Fold[#+##&]/@Select[{0,1}~Tuples~BitLength@x,Tr@Abs[#-x~IntegerDigits~2]<3&]]]&

(* or *)

(s=Select)[4~Range~#,xAnd@@CompositeQ[Fold[#+##&]/@s[{0,1}~Tuples~BitLength@x,Tr@Abs[#-x~IntegerDigits~2]<3&]]]&

Sehr ineffizient, da alle Zahlen bis zu 2 ^ ceil (lg (n)) generiert werden.

Zweiter Code verwendet U + F4A1 ( FunctionFunktion)

Floroid , 95 109 Bytes

Bj:[n KnIw(j)Fp(Cao(hm("".y(k)))Mhm("".y(k))>1KkIcd("10"*Z(hi(n)),Z(hi(n)))FT(a!=b Ka,bIq(hi(n),"".y(k)))<3)]

Gibt eine Liste von bitflipresistenten Zahlen bis zurück input - 1. Behandelt auch die nervösen Situationen (0 und 1).

Floroid ist eine alte Sprache von mir, die ich nur ein paar Mal benutzt habe. Ich habe es eine ganze Weile nicht angerührt, daher die Größe des Programms.

Übersetzt in den folgenden Python-Code, der meiner Meinung nach durch Rekursion reduziert werden könnte.

lambda j:[n for n in  range(j) if  all( not  functions.isPrime( functions.fromBinStr("".join(k))) and  functions.fromBinStr("".join(k))>1for k in  functions.combinations_with_replacement("10"*len( functions.pureBin(n)),len( functions.pureBin(n))) if sum (a!=b for a,b in  zip( functions.pureBin(n),"".join(k)))<3)]

Jede hier verwendete Funktion ist in Floroid vordefiniert. Diese Seite enthält alle Funktionen und deren Definitionen.

MATL , 30 28 27 26 Bytes

:GBnW:qtB!s3<)!Z~tZpw~+a~f

Probieren Sie es online!

Gibt alle bitflipresistenten zusammengesetzten Zahlen bis (und einschließlich) n aus. Verwendet Ideen aus beiden Jelly-Lösungen - betrachtet 0 nur als problematische Nicht-Primzahl; und erzeugt zuerst eine Liste von Zahlen in einem Abstand von 2, nimmt dann ein xor an.

Alternative Lösung durch Schleifen (30 Byte):

:"@BnW:qt@Z~B!s3<)Zp1M~ha~?@D]

Gibt alle bitflipresistenten zusammengesetzten Zahlen bis (und einschließlich) n aus.

CJam , 34 33 Bytes

ri{_2b,,2\f#_m*::|0+f^:mp:+!},2>p

Berechnet alle bitflipresistenten Verbundwerkstoffe mit einer Genauigkeit von weniger als n .

Wie bei Jonathan Allan bin ich mir nicht sicher, ob es tatsächlich notwendig ist, auf 0 Bitflips zu prüfen. Wenn sich herausstellt, dass bei keiner Primzahl alle Bitflips zusammengesetzte Zahlen ergeben, 0+kann die entfernt werden.

Probieren Sie es online!

Erläuterung

ri                                 Take an integer from input (n)
  {                                Filter out all numbers in the range 0...n-1 for which
                                    the following block is false
   _                                 Duplicate the number
    2b,                              Convert to binary, get the length
       ,                             Range from 0 to length-1
        2\f#                         Map each number in that range as a power of 2
                                      results in all powers of 2 less than or equal to n
            _m*                      Cartesian product with itself
               ::|                   Reduce each Cartesian pair with btiwse OR
                                      results in all numbers that have 1-2 1 bits in binary
                  0+                 Add 0 to that list
                    f^               Bitwise XOR the number we're checking with each of these
                                      This computes all the bitflips
                      :mp            Map each result to 0 if it's prime, 1 if it's composite
                         :+!         Take the sum of the list, check if it's 0
                                      If it is, then none of the results were prime
                            },     (end of filter block)
                              2>   Discard the first 2 numbers, since 0 and 1 always pass
                                p  Print the list nicely

MATL , 29 Bytes

Vielen Dank an Jonathan Allan für die Korrektur.

q:Q"@BtnFTZ^=~!s3<fqt2>)Zp~?@

Dies nimmt eine Zahl n und gibt alle bitflipresistenten zusammengesetzten Zahlen bis zu n aus .

Wie es funktioniert

Probieren Sie es bei MATL Online!

q:Q       % Input n implicitly. Push range [2 3 ... n]
"         % For each k in [2 3 ... n]
  @       %   Push k
  B       %   Convert to binary. Gives a row vector of zeros and ones, say v
  tn      %   Duplicate. Number of elements, say m
  FT      %   Push [0 1]
  Z^      %   Cartesian power of [0 1] raised to m. This gives a matrix,
          %   where each row is a binary number of length m
  =~      %   Compare with v, with broadcast
  !s      %   Sum of each row. Gives a row vector. This is the number of
          %   bit flips
  3<      %   True for numbers that are less than 3 bit flips away from k
  fq      %   Find their indices and subtract 1 to convert to decimal form.
          %   This gives a vector of numbers that are less than 3 bit flips
          %   away from k
  t2>)    %   Remove 0 or 1
  Zp~     %   Test each entry for non-primeness
?         % If all entries are true
  @       %   Push k
          % End (implicit)
          % Display stack (implicit)