Book of programming problems

Complexity (1-100): 45

A K-digit motley number (K≤10) is a number all decimal digits of which are different. Zero cannot be the first digit.

Write a program which, given a K, will find all the longest sequences of K-digit motley numbers such that each successive number is twice as large as preceding, Output the first numbers of all sequences. The program is allowed to execute no longer then 3 seconds.

A simple backtracking algorithm would take too much time to find the numbers. First, note that all the sequences are exactly of length 4, because of the limit for the number of digits. The first number should be less than 1.25*10^K and greater than or equal to 10^K.

We will use the predicate isMotley(n) iff n is motley. A double-motley number n is such that isMotley(n) and isMotley(2*n). A triple-motley is isMotley(n) and isMotley(2*n) and isMotley(4*n). A quadruple-motley is isMotley(n) and isMotley(2*n) and isMotley(4*n) and isMotley(8*n).

All sequences, therefore, should start with a quadruple-motley number. Generating a sequence of quadruple-motley numbers may be difficult, hence we generate all the triple-motley numbers and check each if it is quadruple-motley.

Let's start with a simple observation: each part of a motley number N of a motley number. Thus, if N=N₁N₂ (concatenation), then both N₁ and N₂ are motley. That is not always true for double-motley numbers: if  N=N₁N₂ is double-motley, than N₁ should be double-motley only if N₂ starts with a digit 0 .. 4. N₂ should be double-motley, too. Indeed, by multiplying N₂ by 2 we get a motley number and a carrier, which is 0, if the first digit of N₂ is in the range 0 .. 4, or 1, if the first digit of N₂ is in the range 5 .. 9. we should extend the predicate 'double-motley' by a parameter 'carry bit':


Similarly, for a triple-motley number N=N₁N₂ we have four cases:

1. N₂ starts with digits 00 .. 24
2. N₂ starts with digits 25 .. 49
3. N₂ starts with digits 50 .. 74
4. N₂ starts with digits 75 .. 99

This fact is ensued by two multiplications, thus two carry bits:


We will generate numbers by adding a digit d to the 'current' number N₁: and checking condition triple-motley(N₁d, c₁, c₂)  for each combination of c₁ and c₂. The combination will tell us the range for values of dN₂, thus reducing the number of combinations required to enumerate the triple-motley numbers.

See output for K=10.