How can I efficiently find the smallest number whose reverse equals twice itself?

Below is an outline of an answer that describes two main ideas for “avoiding pure brute‐force” when searching for an N satisfying

  reverse(N) = 2 × N

Rather than iterating one by one from 1 up to a huge ceiling, you can use two complementary approaches:

──────────────────────────────

1. Use Digit–Count Constraints

Every number has a number of digits d; also, if N has d digits then its reversal (when interpreted as an integer) will have d digits (that is, if N’s last digit isn’t zero), and the fact that

  reverse(N) = 2 × N

forces 2 × N to have d digits rather than one more. In particular, if N is a d–digit number then

  10^(d–1) ≤ N < 10^d

and because 2×N must also have d digits (so it is less than 10^d), you must have

  2 × N < 10^d ⟹ N < 5×10^(d–1)

So a necessary condition is that N is in the (much shorter) range

  [10^(d–1), 5×10^(d–1) )

For example, if d = 4 then instead of searching from 1000 up to 9999 you can restrict your search to numbers between 1000 and 4999. (You can “guess” the digit–length by noticing that if you try very small d nothing will work.)

Furthermore, there is a “last–digit/first–digit” relation: Write N as

  N = a₁ a₂ … a_d   (with a₁ ≠ 0, a_d ≠ 0)

Then
  reverse(N) = a_d a₍d–1₎ … a₁

and the condition

  reverse(N) = 2×N

implies that the “first” digit of reverse(N) (namely a_d) is related to how 2×N “ends.” In fact, one may show (ignoring the complications from carries at first) that when doubling the last digit a_d the “ones–digit” of 2×N is (2×a_d) mod 10, and that must equal a₁. (In a full treatment you must allow for carries in the doubling algorithm—but at the very least this congruence gives you candidates for the extreme digits.)

──────────────────────────────
2. Use a Recursive / Constraint–Propagation Approach

Because the doubling of N digit–by–digit (when you double and propagate carries from right to left) must “match” exactly the digits of the reversal of N, you can “couple” the digits by writing the multiplication algorithm in reverse. In other words, if you let

  N = a₀ a₁ … a_(d–1)   with a₀ the most–significant digit

then calculating 2 × N by the standard algorithm produces a carry–chain. Define carry_0 = 0 and for i = d–1, d–2, …, 0 you have

  2×a_i + carry_(d–1–i) = a_(d–1–i) + 10×carry_(d–i)

That is, the i–th digit produced (when processing from rightmost to leftmost) of 2×N must equal the digit from the “opposite end” of N. (The indices may be re–indexed as needed to think “from the outside in.”)

You can then use recursion (or even a constraint–programming tool such as Z3) to “build up” the digit list while enforcing these relations. In a DFS you would choose the outermost pair of digits (remembering a₀ must be nonzero and 2×a_(d–1) plus any carry must produce a₀ in its ones–place) and then “propagate” the constraints inward. This approach “prunes” enormous parts of the search space since many choices of outer digits will simply not permit a solution for the inner ones.

──────────────────────────────
A Simple (but still digit–length–restricted) Python Example

Below is an example that shows how you might restrict the search by digit–count. (This version still uses a “loop over numbers,” but the range is dramatically reduced.) Note that if the solution happens to have many digits you may have to increase max_d.

PYTHONCopied
def reverse_num(n):
    return int(str(n)[::-1])

def find_number_by_digits(max_d):
    for d in range(2, max_d+1):
        low = 10**(d-1)
        high = min(10**d, 5 * 10**(d-1))
        print(f"Trying {d}-digit numbers in range [{low}, {high})")
        for n in range(low, high):
            if reverse_num(n) == 2 * n:
                return n, d
    return None, None

result, d = find_number_by_digits(20)
if result:
    print(f"Found solution: N = {result} (with {d} digits)")
else:
    print("No solution found in the digit range searched.")

This code first determines that an eligible d–digit number must be in the range [10^(d–1), 5×10^(d–1)) (so that 2×N does not “gain” an extra digit). Then it tests numbers in that range.

──────────────────────────────
In Summary

• Rather than brute–forcing N from 1 to a huge limit, use the fact that N (and 2×N) must have the same number of digits. This immediately restricts the possible values of N.

• Go one step further by deducing conditions on the first and last digits. (When doubling a number these edge–digits are “linked” by the carry–mechanism.)

• Finally, consider a recursive or digit–dynamic–programming strategy—where you “build” N from the outside in and only continue when the doubling–and–reversal condition is locally satisfied.

While a closed–form solution does not seem to be available, these ideas dramatically reduce the search space and may allow a computer (or even a constraint–solver) to find the smallest solution in a reasonable time.

──────────────────────────────
Note

In some “reversal–multiplication” puzzles (for example, the well–known 2178 reversal that gives 8712 = 4×2178) the multiplier is different from 2. The available literature suggests that the 2× case is “tight” (that is, if any solution exists it may have many digits) so a DFS approach that respects the digit–by–digit constraints is likely the best way forward.

Happy coding, and let me know if you’d like further details on the recursive method!