Using your Head is Permitted

June 2013 solution

Let A be some large constant. For example, it may be 1040. Let B be another constant, computed as B = 1 - A + A2 + A4.

One program that would solve the question is

1. a = x mod 2233393
2. b = a + A
3. c = B mod b
4. d = c mod 2233393

This solves the problem in only four operations.

The reason this solution works is that if XY in some ring (for example, modulo some number), then for any polynomial, P, we also have P(X) ≡ P(Y) in the same ring.

Here, our ring is the integers taken modulo (a + A). Under this modulus, the number -a and the number A are equivalent. Now, we calculate B in this ring. The value of B was defined as a polynomial over A. In the ring, it is therefore equivalent to the same polynomial at the value -a. This value is 1 - (-a) + (-a)2 + (-a)4 = 1 + a + a2 + a4, which is our target polynomial. We can now think of this as our target polynomial calculated at a.

Our next observation is that the true value of this polynomial (at a) must be nonnegative and less than a+A. It is nonnegative because all its coefficients are nonnegative. It is less than a+A because in our first step (a=x mod 2233393) we bounded a, and therefore also the value of the polynomial. The choice of A as a "large" constant was merely meant to have it larger than this bound. Because the true value to be computed is between 0 and the modulus, we know that the result of the modulo operation at step 3 is the actual value of the polynomial at a, and not some folded value.

Next, consider everything in the ring of the integers modulo 2233393. By construction, x and a are equivalent in this ring. Therefore, so must c and the target value be. For the target value, specifically, we know that by definition it must be between 0 and 2233393 (the value of the modulus), so we take c modulo this value at step 4, giving us the final result.

We note that this is a general technique, and neither special properties of the target polynomial nor special properties of the modulus value were used in the process.

I have recently presented a paper in TAMC 2013 (an extended abstract of which can be found here) showcasing the general fact that the simple availability of a "large enough" number is a huge boon to computational power, far beyond what is apparent in the present solution. The same paper also shows the great computational powers of the modulo operation. By comparison, the paper shows that in many cases multiplication does not bring any added computational power.

Back to riddle

Back to main page