Bitflip-resistant composite numbers

Question

Sometimes, when writing a program, you need to use a prime number for some reason or other (e.g. cryptography). I assume that sometimes, you need to use a composite number, too. Sometimes, at least here on PPCG, your program has to be able to deal with arbitrary changes. And in circumstances conveniently contrived to make an interesting PPCG question, perhaps even the numbers you're using have to be resistant to corruption…

Definitions

A composite number is an integer ≥ 4 that isn't prime, i.e. it is the product of two smaller integers greater than 1. A bitflip-resistant composite number is defined as follows: it's a composite positive integer for which, if you write it in binary in the minimum possible number of bits, you can change any one or two bits from the number, and the number is still composite.

Example

For example, consider the number 84. In binary, that's 1010100. Here are all the numbers which differ by no more than 2 bits from that:

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

The first column is the number in binary; the second column is the number in decimal. As the third column indicates, all of these numbers are composite. As such, 84 is a bitflip-resistant composite number.

The task

You must write one of the following three programs or functions, whichever makes the most sense for your language:

• A program or function that takes a nonnegative integer n as input, and outputs the first n bitflip-resistant composite numbers.
• A program or function that takes a nonnegative integer n as input, and outputs all bitflip-resistant composite numbers less than n (or if you prefer, less than or equal to n, i.e. you can choose whether n is included in the output if bitflip-resistant).
• A program or function that takes no input, and outputs all bitflip-resistant composite numbers. (This must use an output mechanism capable of producing output while the program is still running, such as printing to stdout, a lazy list, or a generator; you can't just calculate the entire list and then print it.)

Test cases

Here are the first few bitflip-resistant composite numbers:

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

Clarifications

• It's only the numbers you produce that have to be resistant to bitflips. This isn't a task about making the program that finds them resistant to bitflips; use whatever numbers in the program itself that you like.
• The numbers you output don't have to be resistant to a bitflip in the "leading zeroes"; imagine that the numbers will be stored in the minimum possible number of bits, and only those bits have to be immune to flipping. However, the initial 1 bits on the numbers you output do have to be immune to bitflips.
• Use any algorithm you like that produces the right result; you aren't being marked on efficiency here.
• If you can prove that there are finitely many bitflip-resistant composite numbers, then a) the restrictions on output format are lifted, and b) hardcoding the list will be allowed (although probably more verbose than just calculating it). This rule is mostly just for completeness; I don't expect it to be relevant.

Victory condition

This is code-golf, so as usual, shorter is better. Also as usual, the length of the program will be measured in bytes.

Answer 1

Jelly, 20? 22 bytes

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

Try it online!

Yields the first n such numbers.

Maybe the ;0 can be removed (without it we don't check if the number itself is composite - are there any primes with all bit-flips composite?)

Note that it is not sufficient to perform the test not(any(is prime)) to the set of bit-flipped numbers. We must also test that 0 is not in the set.

This is because 0 is not prime and not composite (1 is too, but see below).

The need to check for 0 may be seen by a counter-example:

• 131136 (2¹⁷+2⁶) has the following 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]

All of which, except 0 are composite, yet 0 is not prime.

1 is also non-prime and non-composite and could appear in the set. However we can, if we want, leave this as if it were a composite:

• all inputs less than or equal to 3 (if being considered at all) contain a 0 anyway (in fact all less than 7 do).

• to reach 1 in one bit flip the original number must be of the form 2^k+2⁰, and if this is greater than 3, i.e. k>1, then we can reach 3 by flipping off the k-bit and setting the 1-bit (2¹+2⁰=3).

• to reach 1 in two bit flips the original number must be of the form 2^k and if this is greater than 3 we can reach 2 in two flips instead, and 2 is prime.

As it stands the code is handling both 0 and 1 together using the "insignificant" atom, Ị.

How?

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

Answer 2

Brachylog, 32 38 bytes

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

Try it online!

This is a function/predicate ↰₀ that returns a generator that generates all such numbers. (The TIO link only prints the first number, so that something's observable. Running it locally has produced many more, though.)

Now updated to handle numbers which are within two bitflips of 0 or 1 (which are neither prime nor composite) correctly.

Explanation

Helper predicate ↰₂ (returns a list that's equal to the input, except for maybe one element)

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

I'd love it if there were a terser way to do this relatively simple recursion, but I'm not sure there is yet; there are some promising-looking features in the specification, but they're marked as unimplemented.

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

Answer 3

JavaScript (ES6), 96 bytes

A full program that prompts for the number of matching integers and displays them one by one, using 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)

Unless your browser is set up to use Tail Call Optimization, this will eventually break because of a recursion overflow.

Below is a non-recursive 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--)}

Assumption

This algorithm relies on the assumption that all bitflip-resistant composite numbers are even. This leads to a rather important simplification: instead of flipping every possible pair of bits, we only flip bit #0 and another one (or no other bit at all) and check that all resulting numbers are composite.

However, I can't figure out any obvious proof that an odd bitflip-resistant composite number doesn't actually exist. It just happens to never be the case for small numbers (I checked up to 1,000,000), and it seems like the probability of finding one is decreasing as the number of bits is increasing (but this is basically just my intuition about it).

Answer 4

Jelly, 20 17 bytes

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

Try it online!

How it works

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.

Answer 5

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

(The second line is an unnamed function which returns a list of all bitflip-resistant composite numbers which are less than the input to the function.)

The syntax all(u%q for q in range(2,u)) will evaluate to True whenever u is either prime or less than or equal to 2, and otherwise will evaluate to False. (It is vacuously True if u is less than or equal to 2.)

In other words, all(u%q for q in range(2,u)) is equal to 0 if and only if u is composite.

If the function's input is less than 2, then function returns an empty list (as desired). So assume the input N is at least 2, and suppose 1 <= n < N. For each k from 0 through n (inclusive), the code will check whether n XOR'd with k is composite, and it also checks whether k has at most two 1's in its binary representation. If n^k is composite, or if k has more than two 1's, then it moves on to the next value of k. If it gets through all the values of k from 0 through n this way, then it includes n in the list.

On the other hand, if there's a value of k with at most two 1's such that n^k is not composite, then n is not included in the list.

Answer 6

Perl 6, 87 85 bytes

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

Returns all such numbers that are smaller or equal to the input number.

How it works

For each number n from 2 to the input, it does the following:

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

   Generates all non-negative integers that have the same or shorter bit length than n.

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

   Filters numbers from this list that have less than three bits set (using a regex).

3. $_ X+^

   XOR's n with each of those numbers, yielding all valid "mutations" of n.

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

   Only lets n be part of the output list if none of the mutations are non-composite (checked by taking each mutation x modulo an all-Junction of numbers between 2 and x-1).

Answer 7

Mathematica, 115 bytes

1 4 byte saved thanks to @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&]]]&

Very inefficient because it generates all numbers up to 2^ceil(lg(n)).

Second code uses U+F4A1 (Function function)

Answer 8

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

Returns a list of bitflip-resistant numbers up to input - 1. Handles the edgy situations (0 and 1) as well.

Floroid is an old language of mine, that I have used only a couple of times. Haven't touched it for a loooong time, hence the size of the program.

Translates to the following Python code, which I think could be reduced with recursion.

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

Each function used here is predefined in Floroid. This page contains all of the functions and their definitions.

Answer 9

MATL, 30 28 27 26 bytes

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

Try it online!

Outputs all bitflip-resistant composite numbers up to (and including) n. Uses ideas from both Jelly solutions - only considers 0 as a problematic non-prime; and generates a list of numbers within a distance 2 first, then takes an xor.

Alternate solution, by looping (30 bytes):

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

Outputs all bitflip-resistant composite numbers up to (and including) n.

Answer 10

CJam, 34 33 bytes

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

Calculates all bitflip-resistant composites strictly less than n.

Like Jonathan Allan, I'm not sure if it's actually necessary to check for 0 bitflips. If it turns out that no prime number has all of its bitflips result in composite numbers, the 0+ can be removed.

Try it online!

Explanation

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

Answer 11

MATL, 29 bytes

Thanks to Jonathan Allan for a correction.

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

This takes a number n and outputs all bitflip-resistant composite numbers up to n.

How it works

Try it at 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)