Czasami, pisząc program, musisz użyć liczby pierwszej z jakiegoś powodu (np. Kryptografii). Zakładam, że czasami trzeba również użyć liczby złożonej. Czasami, przynajmniej tutaj na PPCG, twój program musi być w stanie poradzić sobie z dowolnymi zmianami. A w okolicznościach dogodnie zaprojektowanych, by zadać interesujące pytanie PPCG, być może nawet liczby, których używasz, muszą być odporne na korupcję…

Definicje

Liczba złożona jest liczbą całkowitą ≥ 4, która nie jest liczbą pierwszą, tzn. Jest iloczynem dwóch mniejszych liczb całkowitych większych niż 1. Liczbę złożoną odporną na bitflip definiuje się w następujący sposób: jest to dodatnia liczba całkowita dodatnia, dla której, jeśli ją napiszesz binarnie w minimalnej możliwej liczbie bitów, możesz zmienić dowolny jeden lub dwa bity z liczby, a liczba jest nadal złożona.

Przykład

Weźmy na przykład liczbę 84. Binarnie, to jest 1010100. Oto wszystkie liczby, które różnią się o nie więcej niż 2 bity od tego:

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

Pierwsza kolumna to liczba binarna; druga kolumna to liczba dziesiętna. Jak wskazuje trzecia kolumna, wszystkie te liczby są złożone. Jako taki, 84 jest liczbą kompozytową odporną na bitflipy.

Zadanie

Musisz napisać jeden z następujących trzech programów lub funkcji, w zależności od tego, który z nich jest najbardziej odpowiedni dla twojego języka:

• Program lub funkcja, która przyjmuje nieujemną liczbę całkowitą n jako dane wejściowe i wysyła pierwsze n liczb zespolonych odpornych na bitflip.
• Program lub funkcja, która przyjmuje nieujemną liczbę całkowitą n jako dane wejściowe i wysyła wszystkie liczby zespolone odporne na bitflipy mniejsze niż n (lub, jeśli wolisz, mniejsze lub równe n , tzn. Możesz wybrać, czy n ma być dołączone do wyjścia, jeśli bitflip -odporny).
• Program lub funkcja, która nie pobiera danych wejściowych i wyświetla wszystkie liczby zespolone odporne na bitflipy. (Musi to wykorzystywać mechanizm wyjściowy zdolny do generowania danych wyjściowych podczas działania programu, taki jak drukowanie na standardowe wyjście, leniwa lista lub generator; nie można po prostu obliczyć całej listy, a następnie wydrukować ją.)

Przypadki testowe

Oto kilka pierwszych liczb kompozytowych odpornych na bitflip:

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

Wyjaśnienia

• Tylko liczby, które produkujesz, muszą być odporne na bitflipy. Nie jest to zadanie polegające na uczynieniu programu odpornym na bitflipy; użyj dowolnych liczb w samym programie, które ci się podobają.
• Liczby, które podajesz, nie muszą być odporne na bitflip w „wiodących zerach”; wyobraź sobie, że liczby będą przechowywane w minimalnej możliwej liczbie bitów i tylko te bity muszą być odporne na przerzucanie. Jednak początkowe 1 bity liczb, które wyprowadzasz, muszą być odporne na bitflipy.
• Użyj dowolnego algorytmu, który ci się podoba, który daje właściwy wynik; nie jesteś tutaj oceniany pod względem wydajności.
• Jeśli możesz udowodnić, że istnieje wiele liczb kompozytowych odpornych na bitflipy, a) a) ograniczenia formatu wyjściowego zostaną zniesione, i b) dozwolone będzie twarde kodowanie listy (choć prawdopodobnie bardziej szczegółowe niż tylko obliczanie). Ta zasada służy głównie kompletności; Nie oczekuję, że to będzie istotne.

Warunek zwycięstwa

To jest golf golfowy , więc jak zwykle krótszy jest lepszy. Również, jak zwykle, długość programu będzie mierzona w bajtach.

Galaretka , 20 lat? 22 bajty

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

Wypróbuj online!

Daje pierwsze n takich liczb.

Może ;0może być usunięty (bez niego nie sprawdzamy, czy sama liczba jest złożona - czy są jakieś liczby pierwsze z złożonym bit-flips?)

Zauważ, że nie wystarczy wykonać test not(any(is prime))na zestawie liczb z odwróconą liczbą bitów. Musimy także przetestować, że 0nie ma go w zestawie.

Wynika to z faktu, że 0nie jest liczbą pierwszą i nie jest złożona ( 1jest też, ale patrz poniżej).

Konieczność sprawdzenia 0może być widoczna na przykładzie:

• 131136( 2 ¹⁷ +2 ⁶ ) ma następujący zestaw bit-flip:

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

Wszystkie, z wyjątkiem 0złożonych, ale 0nie są pierwszorzędne.

1jest również niepierwszorzędny i niekompozytowy i może pojawić się w zestawie. Możemy jednak, jeśli chcemy, pozostawić to tak, jakby to był złożony:

• wszystkie dane wejściowe mniejsze niż lub równe 3(jeśli są w ogóle brane pod uwagę) zawierają 0mimo to (w rzeczywistości wszystkie mniej niż 7do)

• aby osiągnąć 1w jednym bicie odwróć, pierwotna liczba musi mieć postać 2 ^k +2 ⁰ , a jeśli jest ona większa niż 3, tj. k> 1 , wówczas możemy osiągnąć 3, wyłączając wartość k- bit i ustawiając wartość 1- bit ( 2 ¹ + 2 ⁰ = 3 ).

• aby dotrzeć 1w dwóch bitach, pierwotna liczba musi mieć postać 2 ^k, a jeśli jest większa niż 3możemy 2w zamian sięgnąć w dwóch rzutach i 2jest liczbą pierwszą.

W obecnej formie kod jest obsługa zarówno 0i 1razem za pomocą „nieznaczne” atomu Ị.

W jaki sposób?

⁴Ç# - 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 bajtów

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

Wypróbuj online!

Jest to funkcja / predykat, ↰₀która zwraca generator, który generuje wszystkie takie liczby. (Łącze TIO drukuje tylko pierwszy numer, dzięki czemu coś można zaobserwować. Lokalne uruchomienie spowodowało jednak znacznie więcej.)

Teraz zaktualizowano, aby poprawnie obsługiwał liczby, które znajdują się w dwóch bitflipach od 0 lub 1 (które nie są liczbami pierwszymi ani złożonymi).

Wyjaśnienie

Predykat pomocnika ↰₂ (zwraca listę równą wartości wejściowej, z wyjątkiem może jednego elementu)

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

Bardzo by mi się podobało, gdyby istniał szybszy sposób na wykonanie tej stosunkowo prostej rekurencji, ale nie jestem pewien, czy jest jeszcze taka możliwość; w specyfikacji znajduje się kilka obiecujących funkcji, ale są one oznaczone jako niewdrożone.

Główny program ↰₀

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 bajtów

Pełny program, który monituje o liczbę pasujących liczb całkowitych i wyświetla je jeden po drugim, używając 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)

O ile Twoja przeglądarka nie jest skonfigurowana do korzystania z funkcji optymalizacji połączenia z ogonem, w końcu ulegnie ona awarii z powodu przepełnienia rekurencji.

Poniżej znajduje się wersja nierekurencyjna (102 bajty).

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

Założenie

Algorytm ten opiera się na założeniu, że wszystkie liczby zespolone odporne na bitflip są parzyste. Prowadzi to do dość ważnego uproszczenia: zamiast przerzucać każdą możliwą parę bitów, odwracamy tylko bit nr 0 i kolejny (lub żaden inny bit) i sprawdzamy, czy wszystkie wynikowe liczby są złożone.

Jednak nie mogę znaleźć żadnego oczywistego dowodu, że nieparzysta liczba kompozytowa odporna na bitflip tak naprawdę nie istnieje. Tak się nie dzieje w przypadku małych liczb (sprawdziłem do 1 000 000) i wydaje się, że prawdopodobieństwo znalezienia jednego maleje wraz ze wzrostem liczby bitów (ale to w zasadzie moja intuicja na ten temat).

Galaretka , 20 17 bajtów

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

Wypróbuj online!

Jak to działa

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 bajtów

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

(Drugi wiersz to nienazwana funkcja, która zwraca listę wszystkich liczb zespolonych odpornych na bitflip, które są mniejsze niż dane wejściowe do funkcji.)

Składnia all(u%q for q in range(2,u))będzie oceniać, Trueilekroć ujest albo pierwsza, albo mniejsza, albo równa 2, a w przeciwnym razie - False. (Jest pusta, Truejeśli ujest mniejsza lub równa 2.)

Innymi słowy, all(u%q for q in range(2,u))jest równy 0wtedy i tylko wtedy, gdy ujest złożony.

Jeśli wartość wejściowa funkcji jest mniejsza niż 2, wówczas funkcja zwraca pustą listę (zgodnie z życzeniem). Załóżmy więc, że dane wejściowe Nsą co najmniej 2i załóżmy 1 <= n < N. Dla każdego kz 0przez n(włącznie), kod sprawdzi czy nXOR'd ze kjest złożona, a także sprawdza, czy kma co najwyżej dwa 1„s w reprezentacji binarnej. Jeśli n^kjest złożony lub kma więcej niż dwa 1, wówczas przechodzi do następnej wartości k. Jeśli przejdzie przez wszystkie wartości kz 0w nten sposób, to znajdzie się nna liście.

Z drugiej strony, jeśli istnieje wartość kz co najwyżej dwóch 1takich, która n^knie jest złożona, nto nie jest uwzględniona na liście.

Perl 6 , 87 85 bajtów

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

Zwraca wszystkie liczby, które są mniejsze lub równe liczbie wejściowej.

Jak to działa

Dla każdej liczby n od 2 do wejścia wykonuje następujące czynności:

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

   Generuje wszystkie nieujemne liczby całkowite, które mają taką samą lub krótszą długość bitu niż n .

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

   Filtruje liczby z tej listy, które mają ustawione mniej niż trzy bity (za pomocą wyrażenia regularnego).

3. $ _ X + ^

   XOR n dla każdej z tych liczb, dając wszystkie ważne „mutacje” n .

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

   Pozwala n znajdować się na liście wyników tylko wtedy, gdy żadna mutacja nie jest złożona (sprawdzane przez przyjęcie każdej mutacji x modulo połączenia wszystkich liczb między 2 a x -1).

Mathematica, 115 bajtów

1 4 bajty zapisane dzięki @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&]]]&

Bardzo nieefektywny, ponieważ generuje wszystkie liczby do 2 ^ ceil (lg (n)).

Drugi kod używa U + F4A1 ( Functionfunkcja)

Floroid , 95 109 bajtów

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

Zwraca listę liczb odpornych na bitflip do input - 1. Obsługuje również trudne sytuacje (0 i 1).

Floroid to mój stary język, którego używałem tylko kilka razy. Nie dotykałem go przez długi czas, stąd rozmiar programu.

Przekłada się na następujący kod Python, który moim zdaniem można zmniejszyć za pomocą rekurencji.

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

Każda użyta tutaj funkcja jest wstępnie zdefiniowana w Floroid. Ta strona zawiera wszystkie funkcje i ich definicje.

MATL , 30 28 27 26 bajtów

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

Wypróbuj online!

Wysyła wszystkie liczby kompozytowe odporne na bitflip do n (włącznie) n. Korzysta z pomysłów obu rozwiązań Jelly - tylko 0 uważa za problematyczne niepierwszorzędne; i generuje najpierw listę liczb w odległości 2, a następnie przyjmuje xor.

Alternatywne rozwiązanie, zapętlając (30 bajtów):

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

Wysyła wszystkie liczby kompozytowe odporne na bitflip do n (włącznie) n.

CJam , 34 33 bajty

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

Oblicza wszystkie kompozyty odporne na bitflipa dokładnie mniej niż n .

Podobnie jak Jonathan Allan, nie jestem pewien, czy rzeczywiście konieczne jest sprawdzenie 0 bitflipów. Jeśli okaże się, że żadna liczba pierwsza nie ma wszystkich wyników bitflip w liczbach zespolonych, 0+można ją usunąć.

Wypróbuj online!

Wyjaśnienie

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 bajtów

Dzięki Jonathanowi Allanowi za korektę.

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

Pobiera to liczbę n i wysyła wszystkie liczby kompozytowe odporne na bitflip do n .

Jak to działa

Wypróbuj w 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)