Innullifiability

This project is an attempt to learn more about a very specific mathsy- feeling problem I came across playing an arithmetic game with a friend. I'm not sure if it really has much to do with maths, and it could very well be thoroughly in the 'computing' side of things. But I'm trying to find a bunch of solutions, essentially, and try and find patterns and interesting things.

Here's the problem written out very concisely: Find a set of positive integers from which it is impossible to construct an arithmetic expression, using each value only once, that evaluates to zero. Here, an arithmetic expression can utilize bracketing, addition, subtraction, multiplication, and division in the case where no remainder is generated. Such a set is 'innullifiable'. If, on the other hand, it is possible to construct a null-evaluating expression, a set is 'nullifiable'.

For example, the set $[1, 2, 3]$ is trivially nullifiable, since $1 + 2 - 3 = 0$, but the set $[1, 2, 4]$ is innullifiable, as there is no way to construct a null-evaluating expression. Try it, and you'll see.

Reasoning

Through some basic reasoning, we can know that a set is nullifiable if and only if there exist two non-overlapping expressions evaluating to the same number: since we're using positive integers, the only way to have zero be the result of a computation is to subtract a value from itself, and once you get zero anywhere, you simply multiply by the remaining values to nullify the set. With this simplified test for nullifiability, we can easily say any set that contains the same value twice is nullifiable, so we'll only look at sets without repetition. We also know that any superset of a nullifiable set is also nullifiable.

Another way of thinking about this null-evaluating arithmetic expression is to imagine binary operations being done on pairs of values in the set, one at a time, with the result taking those values' place, 'reducing' the set. If there are ever two of the same value, those create a zero (by subtraction) and then the zero absorbs any spare values (by multiplication). This means it's also perfectly legal to reduce a set by simply removing values. Here we see a set being continuously reduced to prove its nullifiability:

1. $[2, 3, 4, 10, 14]$
2. $[2, 7, 10, 14], 3 + 4 = 7$
3. $[10, 14, 14], 2 * 7 = 14$
4. $[0, 10], 14 - 14 = 0$
5. $[0]$

Program Logic

This program is for finding all the innullifiable sets in a given search space. Running an exhaustive test for every set in a search space would be quite costly, so the approach actually used here is to generate new nullifiable sets from smaller ones. There are two 'expansion phases' for generating new sets from already-computed smaller ones: making supersets, and introducing 'mutations' to the values.

Superset expansion is pretty straightforward: any values that can be inserted will be, and the set remains nullifiable. For example, the set $[2, 3, 5]$ is nullifiable, as $2 + 3 - 5 = 0$. When any value $X$ is inserted, it is still nullifiable, as $(2 + 3 - 5) * X = 0$.

Mutations essentially make a small change to the values. They replace a value with pairs of different values, from which a simple expression evaluating to the original value can be made, thus creating a completely new set that is still nullifiable. For example, given the same example set as before, we can substitute $5$ with $[7, 12]$, since $12 - 7 = 5$, and $2 + 3 - (12 - 7) = 0$. Mutations need not be introduced to sets generated through a superset phase, as the original set would've undergone all those same mutations too, making additional ones redundant.

When we think in terms of 'reducing' a set, mutations cover every way a set could reduce to one of the input sets by operation, and supersets cover all spare values. Thus, we know that everything that can be reduced to one of the input sets will definitely be output. If we input every nullifiable set in the range of values up to $X$, then any remaining nullifiable sets cannot reduce to any of them, and so the first step in their reduction is to compute a value greater than $X$.

Workflow

Set Records

Set Records are the actual containers that hold information about sets. They also define the search space to be used by programs. They hold a status for each set, which can be 'marked', signifying the set is nullifiable. It can also indicate whether a set was generated by supersets, and thus wouldn't need to undergo mutation.

The sets held in a Record can be thought of as made up of two segments: a Variable segment, and a Fixed segment. The Variable segment makes up most of the set, and it's what actually changes throughout the Record; the maximum value in this segment can take on values in the M-range. Beyond that, it may be desirable to have a small number of higher values 'fixed' in place, so as to not create such an enormous Record, so the Fixed segment holds those values and effectively 'appends' them to the values in the variable segment. Sets are represented as values in ascending order (no repeated values), and the record is itself sorted by set values, greater ones taking precedence.¹

For example, you might have a record with size 4 and M-Value ranging from 11 to 16. The record would store information about sets starting at $[1, 2, 3, 11]$ and ending at $[13, 14, 15, 16]$. The order would be as follows:

0. $[1, 2, 3, 11]$
1. $[1, 2, 4, 11]$
2. $[1, 3, 4, 11]$
3. $[2, 3, 4, 11]$
4. $[1, 2, 5, 11]$
5. $[1, 3, 5, 11]$

...

1607. $[11, 14, 15, 16]$
1608. $[12, 14, 15, 16]$
1609. $[13, 14, 15, 16]$

Programs

There are four programs. Each program works on a record at least, and so must take in the record's set size and the filename to import from. Running a program with no arguments will show its usage message.

gen, Produce New Generation

This program implements the actual nullifiable set generation algorithm described earlier, with the two expansion phases: supersets and mutations. It takes in two records, a source and a destination, the destination's set size being one greater than the source. The set size provided should match the source record. It can run in a multithreaded mode.

By default, the destination is loaded in, both expansion phases are run, and the destination is exported back out. Expansion phases are optional and it can be specified that only one should run with command-line options s and m. Destination import can be skipped with option c, in which case the destination is created with the same M-value range as the source.

weed, Exhaustively Test Unmarked Sets

This program 'weeds out' any remaining nullifiable sets in a given set record, by applying the exhaustive test to every unmarked set and marking the fails. It can run in a multithreaded mode.

eval, Evaluate Record

This program will scan a record and print the representations of the remaining unmarked sets, as well as the number of them. Alternately, a short display of only the number of sets will be output if the s option is passed.

create, Create Blank Record

This program will create a new record with everything unmarked. It must be provided with the set size, as well as the min and max M-values, and the filename.

Scripts

autoinnull, Automatic

This script takes in a set size and a max M-value, and will generate all innullifiable sets in that search space, all from scratch. It does this using a shared memory file for record storage, for fast I/O speeds between commands. It does sequential generations of all the same value range, with a weeding phase at the end, before displaying the resulting innullifiable sets. The weeding phase is necessary because the source sets are all within the M-value range, and so there may be sets which can't reduce to one of those and have to utilize higher values.

Footnotes

1. See 'Combinatorial number system' on the English Wikipedia ↩