Parfois, lors de l'écriture d'un programme, vous devez utiliser un nombre premier pour une raison ou une autre (par exemple, la cryptographie). Je suppose que parfois, vous devez également utiliser un numéro composite. Parfois, au moins ici sur PPCG, votre programme doit être capable de gérer des changements arbitraires. Et dans des circonstances convenablement conçues pour poser une question intéressante sur le PPCG, peut-être même les chiffres que vous utilisez doivent résister à la corruption

Définitions

Un nombre composé est un entier ≥ 4 qui n'est pas premier, c'est-à-dire qu'il est le produit de deux entiers plus petits supérieurs à 1. Un nombre composite résistant au bitflip est défini comme suit: c'est un entier positif composite pour lequel, si vous l'écrivez en binaire dans le nombre minimum de bits possible, vous pouvez changer un ou deux bits du nombre, et le nombre est toujours composite.

Exemple

Par exemple, considérons le nombre 84. En binaire, c'est 1010100. Voici tous les nombres qui ne diffèrent pas de plus de 2 bits:

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

La première colonne est le nombre en binaire; la deuxième colonne est le nombre en décimal. Comme l'indique la troisième colonne, tous ces chiffres sont composites. En tant que tel, 84 est un nombre composite résistant au bitflip.

La tâche

Vous devez écrire l'un des trois programmes ou fonctions suivants, selon celui qui convient le mieux à votre langue:

• Un programme ou une fonction qui prend en entrée un entier non négatif n et génère les n premiers nombres composites résistants au flip bit.
• Un programme ou une fonction qui prend un entier non négatif n en entrée, et sort tous les nombres composites résistants au bitflip inférieurs à n (ou si vous préférez, inférieurs ou égaux à n , c'est-à-dire que vous pouvez choisir si n est inclus dans la sortie si bitflip -résistant).
• Un programme ou une fonction qui ne prend aucune entrée et génère tous les nombres composites résistants au bitflip. (Cela doit utiliser un mécanisme de sortie capable de produire une sortie pendant que le programme est en cours d'exécution, comme l'impression sur stdout, une liste paresseuse ou un générateur; vous ne pouvez pas simplement calculer la liste entière puis l'imprimer.)

Cas de test

Voici les premiers nombres composites résistants au bitflip:

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

Clarifications

• Ce ne sont que les chiffres que vous produisez qui doivent être résistants aux bitflips. Il ne s'agit pas de rendre le programme qui les trouve résistants aux bitflips; utilisez les numéros que vous aimez dans le programme lui-même.
• Les nombres que vous sortez ne doivent pas nécessairement résister à un bitflip dans les "zéros de tête"; imaginez que les nombres seront stockés dans le nombre minimum possible de bits, et seuls ces bits doivent être à l'abri du retournement. Cependant, les 1 bits initiaux des nombres que vous sortez doivent être à l'abri des bitflips.
• Utilisez n'importe quel algorithme que vous aimez qui produit le bon résultat; vous n'êtes pas marqué sur l'efficacité ici.
• Si vous pouvez prouver qu'il existe un nombre fini de nombres composites résistants au bitflip, alors a) les restrictions sur le format de sortie sont levées, et b) le codage en dur de la liste sera autorisé (bien que probablement plus verbeux que le simple calcul). Cette règle est surtout juste pour être complet; Je ne m'attends pas à ce que ce soit pertinent.

Condition de victoire

C'est du code-golf , donc comme d'habitude, plus c'est court, mieux c'est. Toujours comme d'habitude, la longueur du programme sera mesurée en octets.

Gelée , 20? 22 octets

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

Essayez-le en ligne!

Donne les n premiers de ces nombres.

Peut-être que le ;0peut être supprimé (sans lui, nous ne vérifions pas si le nombre lui-même est composite - y a-t-il des nombres premiers avec tous les bit-flips composites?)

Notez qu'il ne suffit pas d'effectuer le test not(any(is prime))sur l'ensemble de nombres à bits inversés. Il faut aussi tester qui 0n'est pas dans le set.

C'est parce que 0n'est pas premier et non composite (l' 1est aussi, mais voir ci-dessous).

La nécessité de vérifier 0peut être vue par un contre-exemple:

• 131136( 2 ¹⁷ +2 ⁶ ) a le jeu de flip-bit suivant:

[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]

Tous, sauf 0sont composites, ne 0sont pas encore premiers.

1est également non premier et non composite et pourrait apparaître dans l'ensemble. Cependant, nous pouvons, si nous voulons, laisser cela comme s'il s'agissait d'un composite:

• toutes les entrées inférieures ou égales 3(si elles sont prises en compte) contiennent de 0toute façon (en fait toutes sont inférieures à 7).

• pour atteindre 1en un bit flip le nombre d'origine doit être de la forme 2 ^k +2 ⁰ , et si celui-ci est supérieur à 3, c'est-à-dire k> 1 , alors nous pouvons atteindre 3en retournant le k- bit et en réglant le 1- bit ( 2 ¹ +2 ⁰ = 3 ).

• pour atteindre 1en deux flips, le nombre d'origine doit être de la forme 2 ^k et s'il est supérieur à 3ce que nous pouvons atteindre 2en deux flips à la place, et 2est premier.

En l'état actuel du code est à la fois la manipulation 0et 1ensemble en utilisant l'atome « insignifiante », Ị.

Comment?

⁴Ç# - 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 octets

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

Essayez-le en ligne!

Il s'agit d'une fonction / prédicat ↰₀qui renvoie un générateur qui génère tous ces nombres. (Le lien TIO imprime uniquement le premier nombre, de sorte que quelque chose soit observable. L'exécuter localement en a produit beaucoup plus, cependant.)

Maintenant mis à jour pour gérer correctement les nombres qui se trouvent dans deux bitflips de 0 ou 1 (qui ne sont ni premiers ni composites).

Explication

Prédicat d'aide ↰₂ (renvoie une liste qui est égale à l'entrée, à l'exception peut-être d'un élément)

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

J'adorerais qu'il y ait un moyen plus simple de faire cette récursivité relativement simple, mais je ne suis pas sûr qu'il y en ait encore; il y a quelques fonctionnalités prometteuses dans la spécification, mais elles sont marquées comme non implémentées.

Programme principal ↰₀

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 octets

Un programme complet qui demande le nombre d'entiers correspondants et les affiche un par un, en utilisant 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)

Sauf si votre navigateur est configuré pour utiliser Tail Call Optimization, cela finira par se casser en raison d'un débordement de récursivité.

Ci-dessous, une version non récursive (102 octets).

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

supposition

Cet algorithme repose sur l'hypothèse que tous les nombres composites résistants au bitflip sont pairs. Cela conduit à une simplification assez importante: au lieu de retourner toutes les paires de bits possibles, nous retournons uniquement le bit # 0 et un autre (ou aucun autre bit du tout) et vérifions que tous les nombres résultants sont composites.

Cependant, je ne peux pas trouver de preuve évidente qu'un nombre composite impair résistant au bitflip n'existe pas réellement. Il se trouve que ce n'est jamais le cas pour les petits nombres (j'ai vérifié jusqu'à 1000000), et il semble que la probabilité d'en trouver un diminue à mesure que le nombre de bits augmente (mais ce n'est fondamentalement que mon intuition à ce sujet).

Gelée , 20 17 octets

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

Essayez-le en ligne!

Comment ça marche

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 octets

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

(La deuxième ligne est une fonction sans nom qui renvoie une liste de tous les nombres composites résistants au bitflip qui sont inférieurs à l'entrée de la fonction.)

La syntaxe all(u%q for q in range(2,u))évaluera à Truechaque fois qu'il uest premier ou inférieur ou égal à 2, et sinon évaluera à False. (Il est vide Truesi uest inférieur ou égal à 2.)

En d'autres termes, all(u%q for q in range(2,u))est égal à 0si et seulement si uest composite.

Si l'entrée de la fonction est inférieure à 2, la fonction renvoie une liste vide (comme vous le souhaitez). Supposez donc que l'entrée Nest au moins 2, et supposez 1 <= n < N. Pour chacun kde à 0travers n(inclus), le code vérifiera si nXOR'd avec kest composite, et il vérifie également s'il ka au plus deux 1dans sa représentation binaire. Si n^kest composite ou s'il en ka plus de deux 1, il passe à la valeur suivante de k. S'il passe à travers toutes les valeurs de kfrom 0de ncette manière, il les inclut ndans la liste.

D'un autre côté, s'il y a une valeur kavec au plus deux 1comme tel qui n^kn'est pas composite, alors il nn'est pas inclus dans la liste.

Perl 6 , 87 85 octets

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

Renvoie tous ces nombres inférieurs ou égaux au nombre entré.

Comment ça marche

Pour chaque nombre n de 2 à l'entrée, il procède comme suit:

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

   Génère tous les entiers non négatifs qui ont la même longueur de bit ou plus courte que n .

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

   Filtre les nombres de cette liste qui ont moins de trois bits définis (à l'aide d'une expression régulière).

3. $ _ X + ^

   XOR n avec chacun de ces nombres, donnant toutes les «mutations» valides de n .

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

   Ne permet à n de faire partie de la liste de sortie que si aucune des mutations n'est non composite (vérifiée en prenant chaque mutation x modulo une jonction de nombres entre 2 et x -1).

Mathematica, 115 octets

1 4 octets enregistrés grâce à @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&]]]&

Très inefficace car il génère tous les nombres jusqu'à 2 ^ ceil (lg (n)).

Le deuxième code utilise U + F4A1 ( Functionfonction)

Floroid , 95 109 octets

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

Renvoie une liste de nombres résistants au bitflip jusqu'à input - 1. Gère également les situations énervées (0 et 1).

Floroid est une vieille langue que je n'ai utilisée que quelques fois. Je ne l'ai pas touché depuis longtemps, d'où la taille du programme.

Se traduit par le code Python suivant, qui je pense pourrait être réduit avec la récursivité.

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

Chaque fonction utilisée ici est prédéfinie dans Floroid. Cette page contient toutes les fonctions et leurs définitions.

MATL , 30 28 27 26 octets

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

Essayez-le en ligne!

Génère tous les nombres composites résistants au bitflip jusqu'à (et y compris) n. Utilise les idées des deux solutions Jelly - considère uniquement 0 comme un non-prime problématique; et génère d'abord une liste de nombres sur une distance 2, puis prend un xor.

Solution alternative, en boucle (30 octets):

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

Génère tous les nombres composites résistants au bitflip jusqu'à (et y compris) n.

CJam , 34 33 octets

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

Calcule tous les composites bitflip-résistants strictement inférieurs à n .

Comme Jonathan Allan, je ne sais pas s'il est réellement nécessaire de vérifier 0 bitflips. S'il s'avère qu'aucun nombre premier n'a tous ses bitflips résultants en nombres composites, le 0+peut être supprimé.

Essayez-le en ligne!

Explication

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 octets

Merci à Jonathan Allan pour une correction.

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

Cela prend un nombre n et génère tous les nombres composites résistants au bitflip jusqu'à n .

Comment ça marche

Essayez-le sur 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)