Иногда при написании программы вам нужно по какой-либо причине использовать простое число (например, криптографию). Я предполагаю, что иногда вам также нужно использовать составное число. Иногда, по крайней мере, здесь, на PPCG, ваша программа должна иметь дело с произвольными изменениями. И в обстоятельствах, которые удобно создать интересный вопрос PPCG, возможно, даже цифры, которые вы используете, должны быть устойчивы к коррупции ...

Определения

Составное число является целым числом ≥ 4 , что не является простым, то есть это произведение двух меньших чисел больше 1. А bitflip резистентных составное число определяется следующим образом : это составное натуральное число , для которого, если вы пишете в двоичном коде в минимально возможном количестве битов вы можете изменить любой один или два бита из числа, и число все еще является составным.

пример

Например, рассмотрим число 84. В двоичном виде это 1010100. Вот все числа, которые отличаются не более чем на 2 бита от этого:

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

Первый столбец - это число в двоичном формате; второй столбец - это число в десятичном виде. Как показывает третий столбец, все эти числа являются составными. Таким образом, 84 является устойчивым к битфлипу составным числом.

Задание

Вы должны написать одну из следующих трех программ или функций, в зависимости от того, что лучше всего подходит для вашего языка:

• Программа или функция, которая принимает неотрицательное целое число n в качестве входных данных и выводит первые n составных чисел, устойчивых к биту.
• Программа или функция, которая принимает неотрицательное целое число n в качестве входных данных и выводит все составные числа, устойчивые к битовым сдвигам, меньшие, чем n (или, если вы предпочитаете, меньшие или равные n , т.е. вы можете выбрать, будет ли n включен в выходные данные, если bitflip резистентный).
• Программа или функция, которая не требует ввода и выводит все составные числа, устойчивые к бит-флипу. (При этом должен использоваться механизм вывода, способный генерировать выходные данные во время работы программы, например, печать в стандартный вывод, отложенный список или генератор; вы не можете просто вычислить весь список и затем напечатать его.)

Контрольные примеры

Вот первые несколько составных чисел, устойчивых к бит-флипу:

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

Разъяснения

• Только числа, которые вы производите, должны быть устойчивы к бит-флипам. Это не задача создания программы, которая считает их устойчивыми к бит-флипам; используйте любые числа в самой программе, которые вам нравятся.
• Числа, которые вы выводите, не должны быть устойчивыми к бит-флипу в «ведущих нулях»; представьте, что числа будут храниться в минимально возможном количестве битов, и только эти биты должны быть защищены от переворачивания. Тем не менее, начальные 1 бита в числах, которые вы выводите, должны быть невосприимчивы к бит-флипам.
• Используйте любой алгоритм, который вам нравится, который дает правильный результат; Вы не отмечены на эффективность здесь.
• Если вы можете доказать, что существует конечное число составных чисел, устойчивых к битовым флипам, то а) ограничения на формат вывода будут сняты, и б) будет разрешено жесткое кодирование списка (хотя, вероятно, более подробное, чем просто его вычисление). Это правило в основном только для полноты; Я не ожидаю, что это будет актуально.

Состояние победы

Это код-гольф , поэтому, как обычно, чем короче, тем лучше. Также, как обычно, длина программы будет измеряться в байтах.

Желе , 20? 22 байта

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

Попробуйте онлайн!

Выдает первые n таких чисел.

Может быть, ;0можно удалить (без этого мы не проверяем, является ли само число составным - есть ли простые числа со всеми сложными переворотами?)

Обратите внимание , что не достаточно , чтобы провести тест not(any(is prime))на множество битовых-перевернуты числа. Мы также должны проверить, что 0не в наборе.

Это потому, что 0не является простым и не составным ( 1тоже, но см. Ниже).

Необходимость проверки 0может быть замечена контрпримером:

• 131136( 2 ¹⁷ +2 ⁶ ) имеет следующий бит-флип:

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

Все из которых, кроме 0составных, еще не 0является простым.

1также не является простым и не составным и может появиться в наборе. Однако мы можем, если захотим, оставить это, как если бы оно было составным:

• все входные данные, которые меньше или равны 3(если рассматриваются вообще), содержат в 0любом случае (фактически все меньше, чем 7делают).

• чтобы достичь 1за один бит переворачивания, исходное число должно иметь вид 2 ^k +2 ⁰ , и если оно больше, чем 3, то есть k> 1 , то мы можем достичь 3, перевернув k- бит и установив 1- бит ( 2 ¹ +2 ⁰ = 3 ).

• чтобы достичь 1двухбитных переворотов, исходное число должно иметь форму 2 ^k, и если оно больше, чем 3мы можем достичь 2за два переворота, и 2оно простое.

В нынешнем виде код обрабатывает и то, 0и другое 1вместе с использованием «незначительного» атома Ị.

Как?

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

Брахилог , 32 38 байт

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

Попробуйте онлайн!

Это функция / предикат, ↰₀которая возвращает генератор, который генерирует все такие числа. (Ссылка TIO печатает только первое число, так что что-то можно наблюдать. Однако при локальном запуске получилось гораздо больше.)

Теперь обновлено, чтобы обрабатывать числа, которые находятся в пределах двух бит-флипов от 0 или 1 (которые не являются ни простыми, ни составными) правильно.

объяснение

Предикат помощника ↰₂ (возвращает список, равный входному значению, за исключением, может быть, одного элемента)

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

Мне бы понравилось, если бы был более краткий способ сделать эту относительно простую рекурсию, но я не уверен, что она еще есть; В спецификации есть многообещающие функции, но они помечены как невыполненные.

Основная программа ↰₀

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 байт

Полная программа, которая запрашивает количество совпадающих целых чисел и отображает их одно за другим, используя 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)

Если ваш браузер не настроен на использование Tail Call Optimization, это в конечном итоге сломается из-за переполнения рекурсии.

Ниже приведена нерекурсивная версия (102 байта).

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

предположение

Этот алгоритм основан на предположении, что все составные числа, устойчивые к битовым флипам, являются четными. Это приводит к довольно важному упрощению: вместо того, чтобы переворачивать каждую возможную пару битов, мы переворачиваем только бит № 0 и еще один бит (или вообще никакого другого бита) и проверяем, что все полученные числа являются составными.

Тем не менее, я не могу найти никакого очевидного доказательства того, что нечетного составного числа, устойчивого к бит-флипу, на самом деле не существует. Просто так случается, что для маленьких чисел никогда не бывает (я проверил до 1 000 000), и похоже, что вероятность найти единицу уменьшается с увеличением количества бит (но это в основном только моя интуиция).

Желе , 20 17 байт

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

Попробуйте онлайн!

Как это работает

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 байт

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

(Вторая строка - это безымянная функция, которая возвращает список всех составных чисел, устойчивых к бит-флипу, которые меньше, чем входные данные для функции.)

Синтаксис all(u%q for q in range(2,u))будет оцениваться, Trueкогда uон либо прост, либо меньше или равен 2, а в противном случае будет оцениваться False. (Пусто, Trueесли uменьше или равно 2.)

Другими словами, all(u%q for q in range(2,u))равен 0тогда и только тогда, когда uявляется составным.

Если ввод функции меньше чем 2, то функция возвращает пустой список (по желанию). Итак, предположим, что вход Nпо крайней мере 2, и предположим 1 <= n < N. Для каждого kиз 0сквозных n(включительно) код будет проверять, является ли nXOR'd с kсоставным, и также проверяет, kимеет ли не более двух 1в своем двоичном представлении. Если n^kсоставной, или если kимеет более двух 1, то он переходит к следующему значению k. Если он получает через все значения kот 0через nтаким образом, то она включает в себя nв списке.

С другой стороны, если есть значение kс не более чем двумя значениями 1, которое n^kне является составным, то nоно не включается в список.

Perl 6 , 87 85 байт

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

Возвращает все такие числа, которые меньше или равны введенному номеру.

Как это работает

Для каждого числа n от 2 до ввода выполняется следующее:

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

   Создает все неотрицательные целые числа, которые имеют одинаковую или меньшую длину в битах, чем n .

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

   Фильтрует числа из этого списка, у которых установлено менее трех битов (с использованием регулярного выражения).

3. $ _ X + ^

   XOR n с каждым из этих чисел, давая все действительные "мутации" n .

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

   Позволяет n быть частью выходного списка только в том случае, если ни одна из мутаций не является составной (проверяется путем выбора каждой мутации x по модулю all-Junction чисел от 2 до x -1).

Mathematica, 115 байт

1 4 байта сохранено благодаря @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&]]]&

Очень неэффективно, потому что генерирует все числа до 2 ^ ceil (lg (n)).

Второй код использует U + F4A1 ( Functionфункция)

Floroid , 95 109 байт

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

Возвращает список устойчивых к битфлипу чисел до input - 1. Также обрабатывает острые ситуации (0 и 1).

Floroid - мой старый язык, который я использовал только пару раз. Давно не трогал его, отсюда и размер программы.

Переводит на следующий код Python, который, я думаю, может быть уменьшен с помощью рекурсии.

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

Каждая используемая здесь функция предопределена в Floroid. Эта страница содержит все функции и их определения.

MATL , 30 28 27 26 байтов

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

Попробуйте онлайн!

Выводит все устойчивые к битфлипу составные числа до (включая) n. Использует идеи из обоих решений Jelly - рассматривает только 0 как проблемное не простое число; и сначала генерирует список чисел на расстоянии 2, затем принимает xor.

Альтернативное решение с помощью цикла (30 байт):

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

Выводит все устойчивые к битфлипу составные числа до (включая) n.

CJam , 34 33 байта

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

Вычисляет все бит-флип-устойчивые композиты строго меньше, чем n .

Как и Джонатан Аллан, я не уверен, действительно ли необходимо проверять наличие 0 бит-клипов. Если выясняется, что ни одно простое число не имеет всех своих бит-флипов, приводящих к составным числам, их 0+можно удалить.

Попробуйте онлайн!

объяснение

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 байт

Спасибо Джонатану Аллану за исправление.

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

Он принимает число n и выводит все составные числа, устойчивые к бит-флипу, вплоть до n .

Как это работает

Попробуйте это в 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)