Builds the set of algebraically inequivalent expressions on your device (up to 6 numbers), then searches for ways to hit a goal with +, −, ×, ÷ and parentheses.
To begin, consider a puzzle: you are given seven numbers — 300, 200, 100, 20, 10, 2, 1 — with the goal to make 1000, using each number exactly once, the four basic operations, and parentheses (no unary minus or multiplicative inversion).
Before that, try the easier classic: make 24 with
2, 4, 7, 10 (the 24 game). One answer is
((4 − 2) * 7) + 10. Others include (10 − 7) * 4 * 2 and
(10 − 2) * (7 − 4).
A brute-force approach would build every ordering of the numbers, every choice of operations, and every placement of parentheses, then check whether each expression hits the goal. For n numbers that space has size
n! × 4(n−1) × (n−1)!
For 4 numbers that is 9,216 expressions — doable. For 7 it is on the order of 14 billion — not reasonable to check exhaustively.
So the real question is: how many algebraically inequivalent expressions are there under these constraints, and how do we store them so we can search efficiently?
Expressions are stored in reverse Polish notation (RPN) and evaluated with a stack. Brute force solves hard 24-game boards like 3,3,7,7 — but it double-counts equivalents and gets slow.
The filter that removes duplicates uses truncators: several lists of randomly generated floats. Each candidate expression is evaluated on each truncator. The result is looked up in a hash set of values already seen for that truncator. If the expression looks new on enough truncators, it is kept as inequivalent.
The sizes of these sets begin 1, 6, 68, 1170, … — the number of inequivalent expressions in n variables with the four operations. That sequence is OEIS A140606.
Brute force still builds far more candidates than the final inequivalent count, and that gap grows with n. The better approach is dynamic: build f(x1,…,xn), the set of inequivalent expressions on those variables, from smaller sets.
Define a naive product ⊕ on two such sets: combine every expression from the left with every expression from the right using
{ ex + ey, ex − ey, ey − ex, ex × ey, ex / ey, ey / ex }
(commutative ops once; non-commutative ops in both orders). Duplicates are removed afterward by the truncator filter.
For two variables a and b:
f(a) ⊕ f(b) =
{ a+b, a−b, b−a, ab, a/b, b/a }, since f(a) = {a} and
f(b) = {b}.
For four variables a,b,c,d, combine 1+3 and 2+2 partitions over all ways to assign variables to the groups, for example:
That candidate space is much smaller than full brute force. After filtering, the inequivalent counts are:
| n | Inequivalent expressions |
|---|---|
| 1 | 1 |
| 2 | 6 |
| 3 | 68 |
| 4 | 1,170 |
| 5 | 27,142 |
| 6 | 793,002 |
| 7 | 27,914,126 |
| 8 | 1,150,212,810 |
OEIS A140606 / Counter sizes. This site generates through n=6 in the browser; n=7–8 are shown for scale — the desktop Java project targets those larger sets.
For large n, storing every expression as a full object is expensive. The desktop
project packs each expression into a bitfield inside a long, then packs those
bitfields back-to-back into an array of longs so unused bits are not wasted. For seven
variables that cut the saved file from about 1.7 GB down to about
100 MB, and load time from roughly 20 seconds to about 100 ms.
This browser demo regenerates sets up to n=6 in memory and caches a compact binary form in IndexedDB; the same packing idea is what makes the Java solver practical at n=7.
Once the set for n exists, Specific Values plugs your numbers into every inequivalent form and keeps those that equal the goal (up to your max). Find Values picks random boards in a range and repeats that scan until the number of hits falls in the range you asked for.
Same idea that found things like
((((4/7)+(16*9))*14)+3) = 2027 from 3, 4, 7, 9, 14, 16 — only here the
generation for n≤6 runs locally in the page.
These are the 68 inequivalent forms for three variables. Change a, b, c, and the goal — results are ordered by how close each evaluation is to the goal. The full solver does the same kind of scan over the much larger sets for n = 4…6.