Three Pandigitals

A problem in Contest Center asks:

Find the smallest whole number N=ABC such that A, B and C each contain all of the digits 0 to 9 at least once, and N contains all of the digits 0 to 9 at least three times.

Here is a description of my code to solve the problem:

Any solution, N, is at least a 30 digit number, and therefore too large to be represented by 64 bits, but by using a C++ 128 bit unsigned integer class, all numbers up to 38 decimal digits can be represented, which is hopefully large enough to search for solutions.

I used the 128 bit C++ class https://github.com/calccrypto/uint128_t developed by Jason Lee, adding some performance and functional improvements to help solve the three pandigitals puzzle, notably:

• Add  a function decimal_string to construct the decimal representation of a 128 bit number more quickly.
  
• Using the intrinsic _umul128 to improve performance of 128 bit number multiplication
  

The structure of the solution is as follows.

Pre-calculate P_{10 ,}  a sorted list of the 10-digit pandigitals from 1023456789 to 9876543210

Define M to be the smallest triple pandigital, $ M = 100011222333444555666777888999 $

Define $\hat{N}$ to be the best solution found so far. Initially set $\hat{N} = 999888777666555444333222111000 $ (so assuming there is a 30 digit solution)

for A in P₁₀
    for B in P₁₀  in the range A to $ \left \lfloor \sqrt{\frac{\hat{N}}{A}} \right \rfloor  $
        for C in the range $   \left \lceil \frac{M}{AB} \right \rceil  $ to  $ \left \lfloor  \frac{\hat{N}}{AB}\right \rfloor $
            if C is pandigital and ABC is triple-pandigital
                set $ \hat{N} = ABC $

This has been implemented as a Visual Studio C++ solution Three Pandigitals.zip

The code contains a function to quickly determine whether a value of C is pandigital, and a function added to the uint128_t class to more quickly convert a 128 bit number to a decimal string, used in the test to determine whether ABC is a triple pandigital.

As the search takes several hours, the main program can be run with two arguments: the starting value of A and the best value $\hat{N}$ found so far, allowing the program to be stopped and then restarted where it left off.

Running the program without any input arguments, this value of $\hat{N}$

    $\hat{N} = 1023456789 * 7694082153 * 12700546398 = 100011222449737853847658995366 $

is found almost immediately, vastly reducing the range of values of C that need to be subsequently searched. As smaller values of $\hat{N}$ are found, the range of C values is reduced further.

The program avoids performing 128 bit multiplication as much as possible, and avoids 128 bit division completely by pre-calculating the inverse of all 10 digit pandigitals, stored as doubles, which are then used to calculate a double that approximates $    \frac{M}{AB} $. A uint128_t cast of this approximation is then refined by addition or subtraction.