Às vezes, ao escrever um programa, você precisa usar um número primo por algum motivo ou outro (por exemplo, criptografia). Suponho que, às vezes, você também precise usar um número composto. Às vezes, pelo menos aqui no PPCG, seu programa precisa ser capaz de lidar com alterações arbitrárias. E em circunstâncias convenientemente planejadas para fazer uma pergunta interessante sobre o PPCG, talvez até os números que você está usando tenham que ser resistentes à corrupção ...

Definições

Um número composto é um número inteiro ≥ 4 que não é primo, ou seja, é o produto de dois inteiros menores maiores que 1. Um número composto resistente a bitflip é definido da seguinte maneira: é um número inteiro positivo composto para o qual, se você o escrever em binário no número mínimo possível de bits, você pode alterar um ou dois bits do número e o número ainda é composto.

Exemplo

Por exemplo, considere o número 84. Em binário, é isso 1010100. Aqui estão todos os números que diferem em não mais 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

A primeira coluna é o número em binário; a segunda coluna é o número em decimal. Como a terceira coluna indica, todos esses números são compostos. Como tal, 84 é um número composto resistente a bitflip.

A tarefa

Você deve escrever um dos três programas ou funções a seguir, o que fizer mais sentido para o seu idioma:

• Um programa ou função que recebe um número inteiro não negativo n como entrada e gera os primeiros n números compostos resistentes a bitflip.
• Um programa ou função que usa um número inteiro não negativo n como entrada e gera todos os números compostos resistentes a bitflip menores que n (ou se preferir, menores ou iguais a n , ou seja, você pode escolher se n está incluído na saída se bitflip -resistente).
• Um programa ou função que não recebe entrada e gera todos os números compostos resistentes a bitflip. (Isso deve usar um mecanismo de saída capaz de produzir saída enquanto o programa ainda está em execução, como imprimir em stdout, uma lista lenta ou um gerador; você não pode apenas calcular a lista inteira e imprimi-la.)

Casos de teste

Aqui estão os primeiros números compostos resistentes a bitflip:

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

Esclarecimentos

• São apenas os números que você produz que precisam ser resistentes aos bitflips. Esta não é uma tarefa para tornar o programa resistente a bitflips; use os números do programa que você gosta.
• Os números que você produz não precisam ser resistentes a um bitflip nos "zeros iniciais"; imagine que os números serão armazenados no número mínimo possível de bits e apenas esses bits deverão ser imunes a inversão. No entanto, os 1 bits iniciais nos números que você produz precisam estar imunes aos bitflips.
• Use qualquer algoritmo que desejar que produz o resultado certo; você não está sendo marcado em eficiência aqui.
• Se você puder provar que existem muitos números compostos resistentes a bitflip, a) as restrições no formato de saída são levantadas eb) a codificação codificada da lista será permitida (embora provavelmente seja mais detalhada do que apenas calculá-la). Esta regra é principalmente apenas para integridade; Não espero que seja relevante.

Condição de vitória

Isso é código-golfe , então, como de costume, quanto menor, melhor. Também como de costume, o comprimento do programa será medido em bytes.

Geléia , 20? 22 bytes

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

Experimente online!

Rende o primeiro n desses números.

Talvez o ;0possa ser removido (sem ele, não verificamos se o número em si é composto - existem primos com todo o composto de troca de bits?)

Note-se que é não suficiente para realizar o teste not(any(is prime))para o conjunto de números Fritou-bit. Também devemos testar 0se não está no conjunto.

Isso ocorre porque 0não é primo e não é composto ( 1também é, mas veja abaixo).

A necessidade de verificar 0pode ser vista por um contra-exemplo:

• 131136( 2 ¹⁷ +2 ⁶ ) tem o seguinte conjunto de inversão de bits:

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

Todos os quais, exceto 0são compostos, ainda 0não são primos.

1também não é primo e não é composto e pode aparecer no conjunto. No entanto, podemos, se quisermos, deixar isso como se fosse um composto:

• todas as entradas menores ou iguais a 3(se forem consideradas) contêm um de 0qualquer maneira (na verdade, todas são menos do 7que).

• para alcançar 1um pouco, o número original deve ter a forma 2 ^k +2 ⁰ e, se for maior que 3, ou seja, k> 1 , podemos alcançá- 3lo desligando o bit- k e configurando o 1 -bit ( 2 ¹ +2 ⁰ = 3 ).

• para chegar 1em dois pouco vira o número original deve ser da forma 2 ^k e se este é maior do que 3podemos alcançar 2em dois vira em vez disso, e 2é primo.

Como está, o código está manipulando ambos 0e 1juntos usando o átomo "insignificante" Ị,.

Quão?

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

Braquilog , 32 38 bytes

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

Experimente online!

Esta é uma função / predicado ↰₀que retorna um gerador que gera todos esses números. (O link do TIO imprime apenas o primeiro número, para que algo seja observável. A execução localmente produziu muito mais.)

Agora atualizado para lidar com números que estão dentro de dois bitflips de 0 ou 1 (que não são primos nem compostos) corretamente.

Explicação

Predicado auxiliar ↰₂ (retorna uma lista que é igual à entrada, exceto talvez um elemento)

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

Eu adoraria se houvesse uma maneira mais tersa de fazer essa recursão relativamente simples, mas não tenho certeza se ainda existe; existem alguns recursos de aparência promissora na especificação, mas são marcados como não implementados.

Programa 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 bytes

Um programa completo que solicita o número de números inteiros correspondentes e os exibe um por um, usando 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)

A menos que seu navegador esteja configurado para usar a Otimização de chamada de cauda, ​​isso acabará sendo interrompido devido a um estouro de recursão.

Abaixo está uma versão não recursiva (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--)}

Suposição

Esse algoritmo baseia-se na suposição de que todos os números compostos resistentes a bitflip são pares. Isso leva a uma simplificação bastante importante: em vez de inverter todos os pares de bits possíveis, apenas lançamos o bit # 0 e outro (ou nenhum outro bit) e verificamos se todos os números resultantes são compostos.

No entanto, não consigo encontrar nenhuma prova óbvia de que um número composto ímpar resistente a bitflip não exista realmente. Acontece que nunca é o caso de números pequenos (verifiquei até 1.000.000), e parece que a probabilidade de encontrar um está diminuindo à medida que o número de bits aumenta (mas essa é basicamente a minha intuição).

Geléia , 20 17 bytes

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

Experimente online!

Como funciona

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

(A segunda linha é uma função sem nome que retorna uma lista de todos os números compostos resistentes a bitflip que são menores que a entrada para a função.)

A sintaxe all(u%q for q in range(2,u))será avaliada para Truesempre que ufor primo ou menor que ou igual a 2e, caso contrário, será avaliada como False. (É vazio Truese ufor menor ou igual a 2.)

Em outras palavras, all(u%q for q in range(2,u))é igual a 0se e somente se ué composto.

Se a entrada da função for menor que 2, a função retornará uma lista vazia (conforme desejado). Portanto, assuma que a entrada Né pelo menos 2e suponha 1 <= n < N. Para cada um kde 0through n(inclusive), o código verificará se o nXOR'd ké composto e também verifica se khá no máximo dois 1na representação binária. Se n^kfor composto, ou se ktiver mais de dois 1, passa para o próximo valor de k. Se passar por todos os valores de kfrom 0por nesse caminho, será incluído nna lista.

Por outro lado, se houver um valor de kno máximo dois 1, que n^knão seja composto, nnão será incluído na lista.

Perl 6 , 87 85 bytes

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

Retorna todos os números menores ou iguais ao número de entrada.

Como funciona

Para cada número n de 2 à entrada, faz o seguinte:

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

   Gera todos os números inteiros não negativos que possuem o mesmo ou menor tamanho de bit que n .

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

   Filtra os números desta lista com menos de três bits definidos (usando uma regex).

3. $ _ X + ^

   XOR é n com cada um desses números, produzindo todas as "mutações" válidas de n .

4. ! grep {$ _% todos os 2 .. ^ $ _}

   Somente deixa n fazer parte da lista de saída se nenhuma das mutações for não composta (verificada tomando cada mutação x módulo como uma junção total de números entre 2 e x -1).

Mathematica, 115 bytes

1 byte economizado graças a @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&]]]&

Muito ineficiente porque gera todos os números até 2 ^ ceil (lg (n)).

O segundo código usa U + F4A1 ( Functionfunção)

Floróide , 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)]

Retorna uma lista de números resistentes a bitflip até input - 1. Lida com as situações nervosas (0 e 1) também.

Floroid é uma antiga linguagem minha, que eu usei apenas algumas vezes. Não o tocamos há muito tempo, daí o tamanho do programa.

Traduz para o seguinte código Python, que eu acho que poderia ser reduzido com recursão.

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

Cada função usada aqui é predefinida no Floroid. Esta página contém todas as funções e suas definições.

MATL , 30 28 27 26 bytes

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

Experimente online!

Produz todos os números compostos resistentes a bitflip até (e inclusive) n. Usa idéias de ambas as soluções Jelly - considera apenas 0 como um problema não prioritário; e gera uma lista de números dentro de uma distância 2 primeiro e depois faz um xor.

Solução alternativa, fazendo um loop (30 bytes):

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

Produz todos os números compostos resistentes a bitflip até (e inclusive) n.

CJam , 34 33 bytes

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

Calcula todos os compostos resistentes a bitflip estritamente menores que n .

Como Jonathan Allan, não tenho certeza se é realmente necessário verificar 0 bitflips. Se acontecer que nenhum número primo tem todos os seus bitflips resultam em números compostos, o 0+pode ser removido.

Experimente online!

Explicação

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

Obrigado a Jonathan Allan pela correção.

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

Isso leva um número n e gera todos os números compostos resistentes a bitflip até n .

Como funciona

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