# 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