Your problem sets out to solve the following system of modular equations:
x1 + 2*x2 + 2*x3 + 2*x4 + 2*x5 + x6 + x7 = A (mod 100)
x4 + x5 = B (mod 10)
x2 + x3 = C (mod 10)
The first equivalence comes from steps 1-3 above, the second from step 4 and the third from step 5. The basic math that you need to solve a system of equivalences is the Chinese Remainder Theorem.
This system will not have a unique solution. To see how redundant it is, count the possibilities for the sequence (x1,x2,x3,x4,x5,x6,x7)
and (C,B,A)
separately. For the former, x1,x6,x7
are interchangeable as are x4,x5
and x2,x3
, so we count them separately. There are (45+3-1 choose 3)
ways to choose x1,x6,x7
each between 01
and 45
(remember to choose with repetition), and (45+2-1 choose 2)
ways to choose each of the other pairs. This gives a total of
(47 choose 3)*(46 choose 2)^2 = 16 782 525
ways of choosing the x
s. For the 4-digit sequence, there are 10 000
possibilities. The number above is far larger, so certainly there is a lot of repetition.
If you want to pin down just one x
sequence that yields a given CBA
sequence, then you can simplify the problem by choosing arbitrary values for x6,x7,x5,x3
and then using the CRT to solve for x1,x4,x2
(which may or may not exist).
For example, suppose you take
x3 = 19, x5 = 22, x6 = 31, x7 = 13
Then you solve for the remaining x
s by solving this system
x4 + 22 = 3 (mod 10)
x2 + 19 = 4 (mod 10)
x1 + 2*x2 + 38 + 2*x4 + 44 + 31 + 13 = 82 (mod 100)
The first two equations are easy, though the solutions are not unique
x4 = 1 (mod 10) => x4 = 1, 11, 21, 31, or 41
x2 = 5 (mod 10) => x2 = 5, 15, 25, 35, or 45
Adding in the final equation to solve for x1
and pin down x2,x4
gives
x1 + 2*(x2 + x4) = 56 (mod 100)
which has many solutions, among them x1 = 4, x2 = 5, x4 = 21
, but also x1 = 44, x2 = 5, x4 = 1
as well as many others.
I'm one of the authors of the paper referenced by David Bevan in his comment. The four-fours was one inspiration for that problem, although others have thought about it also. The specific version of the problem there looks at the minimum number of $1$s needed to represent $n$ where one is allowed only addition and multiplication but any number of parentheses. Call this $g(n)$. For example, $g(6) \le 5$, since $6=(1+1)(1+1+1)$, and it isn't hard to show that $g(6)=5$. Even in this limited version of the problem, the question is generally difficult even to get asymptotics.
In some sense most natural questions of asymptotic growth are somewhat contained in this question, since one can write any given $k$ as $1+1+1...+1$ $k$ times, and $1=k/k$. Thus starting with some $k$ other than $1$ (such as $k=4$), the asymptotics stay bounded within a constant factor, assuming that addition and division are allowed.
However, actually calculating this sort of thing for any set of operations is generally difficult. In the case of integer complexity one has a straightforward way of doing so, since if one calculates $g(i)$ for all $i < n$, calculating $g(n)$ is then doable. This doesn't apply when one has other operations generally, with division and substraction already making an algorithm difficult. In this case, one can make such an algorithm but exactly how to do so is more subtle. In fact, as long as one is restricted to binary operations this is doable (proof sketch: do what you did to look at all distinct expressions).
Adding in non-binary operations makes everything even tougher. Adding in square roots won't make things that much harder, nor will adding factorial by itself. The pair of them together makes calculating specific values much more difficult. My guess would be that even with factorial, square root and the four binary operations there are numbers which require arbitrarily large numbers of $1$s, but I also suspect that this would be extremely difficult to prove. Note that this is already substantially weaker than what you are asking- whether the order of growth is of $\log n$. Here though square roots probably don't alter things at all; in order for it to matter one needs to have a lot numbers of the form n^2^k with surprisingly low complexity. This seems unlikely.
Best Answer
For a non-Diophantine approach:
There are well-known divisibility tests for $5, 9, 11$ based on the digits.
$7$ also has a divisibility test, though not as nice: $10x + y$ is divisible by $7$ if $x - 2y$ is divisible by $7$, where $y$ is a single digit.
So for example, $17325$ is
Now you have either $abc0$ or $abc5$. But if we have $abc0$, then $ac0$ being divisible by $11$ requires $a - c$ to be divisible by $11$, which can only be true if $a = c$. But that breaks the "all digits are different" rule. So there is no solution with last digit $0$.
For $abc5$,
We can combine the various possibilities for $9$ and $11$ divisibility to give relationships between $a, b$: $$\begin{align}(b + c = 4)\;\&\;(c = a + 5) &\implies a + b = -1\quad ⨳\\ (b + c = 4)\;\&\;(a = c + 6) &\implies a + b = 10\\ (b + c = 13)\;\&\;(c = a + 5) &\implies a + b = 8\\ (b + c = 13)\;\&\;(a = c + 6) &\implies a + b = 19\quad ⨳\end{align}$$ So either $a+b = 10$ or $a+b = 8$. Now $10a+b - 10 = 9a + (a+b) - 10$. So
So the two possible solutions are: $$\begin{align}1765 &= 5\times353\\765 &= 9\times 85\\165 &= 11 \times 15\\175 &= 7 \times 25\end{align}$$ and $$\begin{align}7315 &= 5 \times 1463\\315 &= 9 \times 35\\715 &= 11\times 65\\735 &= 7 \times 105\end{align}$$
Without the distinct digits requirement, $6360$ is also a solution (the only solution with $0$ as the last digit).