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.

IBM Ponder This, January 2017

The IBM Ponder This puzzle for January 2017 asked for a rational solution for x^y=y^x, where the last eight digits of x are different from each other, and for a bonus asked for a solution where the last eight digits of x are a permutation of 1,2,3,4,5,6,7,8.

It is possible to do better than this, and construct a solution where the last nine digits of x are are a permutation of 1,2,3,4,5,6,7,8,9 , and a solution where the last ten digits of x are are a permutation of  0,1,2,3,4,5,6,7,8,9.

Original Problem and Bonus

Goldbach and Euler proved that a set of 2 rationals {x,y} satisfies x^y=y^x    iff   $ \{x,y\} = \{ (\frac{n+1}{n})^n , (\frac{n+1}{n})^{n+1} \} $  for integer n. [1], [2]

If these numbers are to have last digits, n must be of the form $ n = 2^t 5^f $

$ \frac{n+1}{n}$ has $ d = max(t,f) $ decimal places.

$ \frac{(n+1)10^d}{n} $ is an integer whose last digits are the last decimal digits of $ \frac{n+1}{n}$

The last $D$ digits of $x,y$ are 

$ (\frac{(n+1)10^d}{n})^{n+k} $ mod $ 10^D $,  for $k = 0,1 $                  

Which can be calculated as

$ ((n+1)2^{d-t}5^{d-f})^{n+k} $ mod $ 10^D$,  for $k = 0,1 $

or

$ (10^d +2^{d-t}5^{d-f})^{n+k} $ mod $ 10^D$,  for $k = 0,1 $                            ...... (1)

For modest values of n, it is easy to calculate these residues using modular exponentiation, for example in C or Python.  This Python program searches for solutions to both problems.

The first problem has a solution for $n=2^4 \cdot 5^1 =80$, $x =( \frac{81}{80})^{80} $

The bonus problem has a solution for $n= 5^5 = 3125$, $x =( \frac{3126}{3125})^{3126} $

Extending the Problems

Now the more interesting problems: find a solution where the last nine digits of x are are a permutation of 1,2,3,4,5,6,7,8,9 , and a solution where the last ten digits of x are are a permutation of  0,1,2,3,4,5,6,7,8,9.

Here we need to examine larger values of $n$,  so expression (1) becomes impractical to use and we have to find a better way of determining the last digits of $ (\frac{(n+1)10^d}{n})^{n+k} $

If $d \ge  D$, then (1) can be reduced to

$ (2^{d-t}5^{d-f})^{n+k} $ mod $ 10^D$,  for $k = 0,1 $ 

There are two cases to consider:

$f>t$

$ (2^{d-t}5^{d-f})^{n+k} $ mod $ 10^D  = ( 2^{f-t})^{n+k} $ mod $ 10^D =  2^{(f-t)(n+k)} $ mod $ 10^D $

Now [3] shows that powers of 2 mod $10^D$ cycle with a period of $P = 4 \cdot 5^{D-1}$, starting at $2^D$

so if $ (f-t)(n+k) = (f-t)(2^t 5^f+k) \ge D $,

$2^{(f-t)(n+k)} $ mod $ 10^D $ =  $ 2^{ D + ((f-t)(2^t 5^f+k) - D) \: mod  \: P } $ mod $ 10^D $                ..... (2)

$t >f$

$ (2^{d-t}5^{d-f})^{n+k} $ mod $ 10^D = ( 5^{t-f})^{n+k} $ mod $ 10^D =  5^{(t-f)(n+k)} $ mod $ 10^D $

 [4] shows that powers of 5 mod $10^D$ cycle with a period of $P=2^{D-2}$, starting at $5^D$ 

so if $ (t-f)(n+k) = (t-f)(2^t 5^f+k) \ge D $,

$5^{(t-f)(n+k)} $ mod $ 10^D $ =  $ 5^{ D + ((t-f)(2^t 5^f+k) - D)   \: mod  \: P } $ mod $ 10^D $                ..... (3)

The residues in (2) and (3) can be calculated using modular exponentiation without the need to handle excessively large numbers. This Python program searches for solutions to both problems, finding the following solutions:

For $n = 5^{267}$, the last ten digits of $( \frac{n+1}{n})^{n+1} $ are 3628975104

For $n = 2^2 \cdot 5^{957}$, the last nine digits of $( \frac{n+1}{n})^{n+1} $ are 247315968

[1] Cut The Knot, Rational Solutions to x^y = y^x

[2] Sved, Marta. “On the Rational Solutions of x^y = y^x.” Mathematics Magazine, vol. 63, no. 1, 1990, pp. 30–33., http://www.jstor.org/stable/2691508.

[3] Exploring Binary, Cycle Length of Powers of Two Mod Powers of Ten, Rick Regan, November 6th, 2009

[4]  Exploring Binary, Cycle Length of Powers of Five Mod Powers of Ten,  Rick Regan, December 22nd, 2009