# 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)$?

#### Solutions Collecting From Web of "Number of positive integers $\le n$ with different digits."

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?

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$.

Yes. See this OEIS page or this MathWorld page.

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

• 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.