We analyze a small binary that asks to satisfy a seemingly unsolvable equation.

The challenge consists of one 32-bit binary named `impossible`

with a size of
about 4k. Putting it into hex rays decompiles the program smoothly. The
relevant parts (with slight adjustments to improve readability) are shown below:

```
#include <stdio.h>
unsigned int nums[21];
int is_in_range(int a1)
{
int result;
if ( a1 <= 1 || a1 > 1000000 )
result = -1;
else
result = a1;
return result;
}
int main(int argc, const char **argv, const char **envp)
{
long long tmp1;
int tmp2;
unsigned long long tmp3;
unsigned long long product;
unsigned long long sum;
int i, j, last_idx;
alarm(15);
last_idx = 0;
nums[0] = 1;
for (i = 1; i < 21; i++) {
scanf("%d", &nums[i]);
nums[i] = nums[i - 1] < nums[i] ? is_in_range(nums[i]) : -1;
last_idx = i;
if (nums[i] == -1)
break;
}
sum = 0;
product = 1;
for (j = 1; j < last_idx; j++) {
sum += nums[j];
tmp1 = nums[j];
tmp2 = tmp1 * HIDWORD(product) + HIDWORD(tmp1) * product;
tmp3 = (unsigned int)product * (unsigned long long)(unsigned int)tmp1;
LODWORD(product) = tmp3;
HIDWORD(product) = HIDWORD(tmp3) + tmp2;
}
if (last_idx <= 1 || product != sum) {
puts("Wrong...");
} else {
puts("Correct!");
}
return 0;
}
```

The program reads in up to 20 **distinct** numbers in ascending order, checks
whether they are in the range $[2,10^6]$, computes the sum and the product of the
numbers and checks if the sum equals the product. Don’t let yourself be
confused by the `HIDWORD`

and `LODWORD`

macros, that’s just IDA’s way of telling
us that 64bit arithmetic is being done on 32 bit numbers. If the values of `sum`

and `product`

match **and** we gave the program more than one number, we win.

So, remember are looking for $m\in[2,20]$ **distinct** $n_i\in[2,10^6]$ such that
\[
\sum_{i=0}^{m-1} n_i = \prod_{i=0}^{m-1} n_i \text.
\]

Mathematicians proved that the only solutions to the problem above ${(0, 0), (1, 1), (2, 2)}$ do not meet our requirements, so solving the problem above is provably impossible.

… well, then, how the heck could the solve counter for the challenge be $>0$
at the time we started working on the task? Fair enough: The above equation
omits the fact we’re not working on numbers of arbitrary precision. What we’re
actually looking for is a solution to the **congruence**

\[ \sum_{i=0}^m n_i \equiv \prod_{i=0}^m n_i \pmod{2^{64}} \text. \]

So the integer wrap-around is right there to rescue us. At this point, a long and cruel session of mindtorturing emerged and many ideas turned out to be totally useless until we had the final inspiration. Some observations:

- The product always grows faster than the sum, so probably the only possibility to satisfy the equation is abusing the wrap-around
- The sum will never wrap as even the largest constructable number ($\sum_{i=0}^{20}10^6-i)$ is still magnitudes below $2^{64}$.
- The product is invariant under moving a prime factor from one number to another, whereas the sum changes under this operation. Clearly, numbers with many small prime factors give us some flexibility.

The following idea finally led to a solution: Once the wrap-around occurs, we
want the resulting number to be as small as possible (see observation 1 above).
This means that we need to construct a number with a very large gap between the
first and the second `1`

bits. Clearly, all numbers $2^x+2^y$ with $x$ large
(as close as possible to and below of $64$) and $y$ small (as close as possible
to and above $0$) satisfy this requirement. We thus started looking at numbers
$2^n + 1$ with $n\in[0,63]$ to find the largest one consisting of prime factors
all below $10^6$:

```
(n, prime factors of 2^n+1)
(0, 2)
(1, 3)
(2, 5)
(3, 3^2)
(4, 17)
(5, 3 * 11)
(6, 5 * 13)
(7, 3 * 43)
(8, 257)
(9, 3^3 * 19)
(10, 5^2 * 41)
(11, 3 * 683)
(12, 17 * 241)
(13, 3 * 2731)
(14, 5 * 29 * 113)
(15, 3^2 * 11 * 331)
(16, 65537)
(17, 3 * 43691)
(18, 5 * 13 * 37 * 109)
(19, 3 * 174763)
(20, 17 * 61681)
(21, 3^2 * 43 * 5419)
(22, 5 * 397 * 2113)
(23, 3 * 2796203)
(24, 97 * 257 * 673)
(25, 3 * 11 * 251 * 4051)
(26, 5 * 53 * 157 * 1613)
(27, 3^4 * 19 * 87211)
(28, 17 * 15790321)
(29, 3 * 59 * 3033169)
(30, 5^2 * 13 * 41 * 61 * 1321)
(31, 3 * 715827883)
(32, 641 * 6700417)
(33, 3^2 * 67 * 683 * 20857)
(34, 5 * 137 * 953 * 26317)
(35, 3 * 11 * 43 * 281 * 86171)
(36, 17 * 241 * 433 * 38737)
(37, 3 * 1777 * 25781083)
(38, 5 * 229 * 457 * 525313)
(39, 3^2 * 2731 * 22366891)
(40, 257 * 4278255361)
(41, 3 * 83 * 8831418697)
(42, 5 * 13 * 29 * 113 * 1429 * 14449)
(43, 3 * 2932031007403)
(44, 17 * 353 * 2931542417)
(45, 3^3 * 11 * 19 * 331 * 18837001)
(46, 5 * 277 * 1013 * 1657 * 30269)
(47, 3 * 283 * 165768537521)
(48, 193 * 65537 * 22253377)
(49, 3 * 43 * 4363953127297)
(50, 5^3 * 41 * 101 * 8101 * 268501)
(51, 3^2 * 307 * 2857 * 6529 * 43691)
(52, 17 * 858001 * 308761441)
(53, 3 * 107 * 28059810762433)
(54, 5 * 13 * 37 * 109 * 246241 * 279073)
(55, 3 * 11^2 * 683 * 2971 * 48912491)
(56, 257 * 5153 * 54410972897)
(57, 3^2 * 571 * 174763 * 160465489)
(58, 5 * 107367629 * 536903681)
(59, 3 * 2833 * 37171 * 1824726041)
(60, 17 * 241 * 61681 * 4562284561)
(61, 3 * 768614336404564651)
(62, 5 * 5581 * 8681 * 49477 * 384773)
(63, 3^3 * 19 * 43 * 5419 * 77158673929)
```

Gotcha! $2^{62}+1 = 5 \cdot 5581 \cdot 8681 \cdot 49477 \cdot 384773$, all well below $10^6$. To trigger the integer wrap-around, we also need to include a factor of $4$ (left shift by two bit positions) to get $4 \cdot 5 \cdot 5581 \cdot 8681 \cdot 49477 \cdot 384773 \equiv 4 \pmod{2^{64}}$. Now the (quickly growing, see observation 2) product is significantly smaller than the sum $4 + 5 + 5581 + 8681 + 49477 + 384773 = 448521$. Awesome!

The last step is pretty lame: We wrote a small python script that quickly brute-forced a last number $z$ such that the sum would match the product and found $149507$. And indeed:

```
% python3 -q
>>> print(4 + 5 + 5581 + 8681 + 49477 + 149507 + 384773)
598028
>>> print(4 * 5 * 5581 * 8681 * 49477 * 149507 * 384773 % 2**64)
598028
>>>
```