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

Question

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

Answer 1

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++;
                i = i.add(one);
            } 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?

Answer 2

Yes. See this OEIS page or this MathWorld page.

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

Answer 3

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

Answer 4

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