Number of positive integers $\le n$ with different digits.

An integer $m$ is acceptable iff in it's decimal representation all digits are different. For example $9876543210$ is the largest acceptable integer. For each $n\in \Bbb N$, $\theta(n)$ is the number of all acceptable positive integers not greater than $n$.

Is there a simple formula for $\theta(n)$?

-
I know a formula exists for $n = 10^k$, $k \in \mathbb{N}$. Would this be sufficient for you? (I'm not sure if there is one for the general case.) – George V. Williams Mar 16 '13 at 23:57
Yes, I encountered this question in a computer program. I think this special case simplifies the problem to some extent. – user59671 Mar 17 '13 at 0:00
Something else that might help you is ignoring repeated digits if one digit is shown to be repeating. For example, after $3300$, there's no need to consider $3301, 3302, \ldots$. – George V. Williams Mar 17 '13 at 0:02
This question is a special case of math.stackexchange.com/q/226821/6876 – Martin Thoma Mar 17 '13 at 11:17

This is not a math answer, but if you're only interested in the results I guess my approach is much simpler to understand. I simply let the computer calculate the numbers.

Simple Python solution

This one works, but is slow:

def isAcceptable(number):
s = str(number)
for i in range(len(s)-1):
for j in range(i+1,len(s)):
if s[i] == s[j]:
return False
return True

def getNumberOfAcceptableNumbers(n):
acceptable = 0
i = 1
while i <= n:
if isAcceptable(i):
acceptable += 1
i += 1
return acceptable

print(getNumberOfAcceptableNumbers(98765432))


It took over 5 minutes on my machine for 98765432. The result was 2,345,850.

I'm currently implementing this in Java. For 98765432 it takes only 32 seconds and I'm currently improving it.

Java solution

import java.math.BigInteger;

public class DiffDigits {
/**
* All numbers that are not acceptable have at least one pair of two
* indices that have the same digit. Take the pair where the lower
* index is maximal. Return the lower index.
*
* @param number
* @return -1 iff number is acceptable, otherwise index as described above
*/
public static int getHighestIndexThatHasToChange(BigInteger number) {
String s = number.toString();
// i == 0 is the most significant digit
for (int i = 0; i < s.length() - 1; i++) {
for (int j = i + 1; j < s.length(); j++) {
if (s.charAt(i) == s.charAt(j)) {
return j;
}
}
}
return -1;
}

/**
* Get the amount of positive integers that are acceptable in range [i, end]
*
* @param i the first number to check
* @param end the last one to check
* @return
*/
public static int getNumberOfAcceptableNumbers(BigInteger i, BigInteger end) {
BigInteger one = new BigInteger("1");
BigInteger ten = new BigInteger("10");
int acceptable = 0;
while (i.compareTo(end) <= 0) {
int highestIndex = getHighestIndexThatHasToChange(i);
if (highestIndex == -1) {
acceptable++;
} else {
i = i.add(ten.pow(i.toString().length() - 1 - highestIndex));
}
}
return acceptable;
}

public static void main(String[] args) {
System.out.println("Start");
long startTime = System.nanoTime();
System.out.println(getNumberOfAcceptableNumbers(new BigInteger("1"),
new BigInteger("9876543210")));
long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println("Execution took " + duration / 1000000000.0
+ " seconds.");
System.out.println("End");
}
}


For $n = 9876543210$ there are 8,877,690 acceptable numbers. For this range, it took 56 seconds to execute. For every other range it will be less.

By the way, this sounds like a Project Euler task. Is it one? Which task is it?

-
thanks. but I may need to translate to Java solution to C#. – user59671 Mar 17 '13 at 14:47

Quite often, counting questions that are trivial for $n \le 10^d$ can be solved very efficiently in general by decomposing into decimal blocks of size $m\cdot 10^d$.

Define $\psi(n) = \theta(n-1)$ for convenience, and say you want to know $\psi(4537)$: decompose this into $$\psi(1000) + [\psi(4000)-\psi(1000)] + [\psi(4500)-\psi(4000)] + [\psi(4530)-\psi(4500) ] + [\psi(4537) - \psi(4530)].$$

Previous answers have already shown how to calculate $\psi(1000)$, but each of the remaining blocks is equally simple. For instance, $[\psi(4500)-\psi(4000)]$ is just the number of acceptable numbers between $4000$ and $4499$, inclusive. In this block the first digit is fixed, and the second digit is any of $0,1,2,3$ ($4$ being forbidden). The third digit has $8$ choices, and the fourth digit has $7$, so $\psi(4500)-\psi(4000) = 4\cdot8\cdot 7$.

The other blocks follow a quite similar pattern, they can all be computed using nothing more than "count how many digits of $x$ are at most $y$" and testing for distinctness, all very efficient operations even for bases much, much larger than $10$.

-

$$\theta(10^n - 1) = \sum_{k=1}^n \frac{9 \cdot 9!}{(10 - k)!}$$

-
Not true for $n=0,1$ since $\theta(1) = 1$ and $\theta(10)=10$ (originally this comment overlooked the latter). This is really a formula for $\theta(10^n - 1)$, but for all $n>1$ it makes no difference. – Erick Wong Mar 17 '13 at 1:00
@ErickWong, thanks for the catch. (The summands are actually for the number of $n$ digit acceptable numbers.) – George V. Williams Mar 17 '13 at 1:02
Indeed, this is why I always find it more natural (in a programming context) to work with the "$< n$" version of such functions rather than "$\le n$". – Erick Wong Mar 17 '13 at 1:04
• The first digit may be any of {1,2,...,9}, so 9 choices.
• The second digit may be any digit of {0,1,...,9}, except the first one. So 9 choices.
• The third digit may be any digit of {0,1,...,9}, except the first and the second one. So 8 choices.
• ...
• The tenth digit may be any digit of {0,1,...,9}, except the nine previous,. So 1 choice.
• It is not possible to have 11 distinct digits.

So $θ(n)=9 \times 9 \times 8\times 7 ... \times (10-n) = 9 \times \frac 9! {(-n)!}$

Apart for the $θ(n)=0$ for $n>10$ already mentioned, you also have an exception for 0, $θ(0)=10$ since $0$ is acceptable.

-
Note all integers must be less then $n$. n is not the number of digits. – user59671 Mar 17 '13 at 0:16