Integers containing all ten digits

Question

It is known that most positive integers contain at least one copy of each of the ten digits.

What is the largest n such that at most 50% of the integers in the set [1,2,3,...,n] contain at least one copy of each of the ten digits?

Answer 1

First we need a way to count two things: the number of $n$-digit pandigital numbers and the number of pandigital numbers with a given prefix not using $r$ digits and a suffix of $f$ "free" digits. The count for the first is $$9\cdot9!S(n,10)$$ where $S(a,b)$ is the second-kind Stirling number, the number of ways to partition $a$ items into $b$ non-empty subsets (we multiply by $9$ for the leading digit choice and by $9!$ for the remaining digit choices). The count for the second is $$\sum_{k=r}^f\binom fkr!S(k,r)(10-r)^{f-k}$$ where $k$ represents the number of "free" digits reserved for non-prefix digits.

Given the two formulas above we can count the number of pandigital numbers $P(n)$ in $[1,n]$ by considering $n$'s prefixes decremented (so as not to overshoot $n$). Then define the non-pandigital abundance $a(n)=n-2P(n)$; it has the Lipschitz property of $|a(n+1)-a(n)|=1$ and we seek the last zero of $a(n)$. Writing code for $P(n)$ is a very delicate task; the code can be found here.

Knowing the Lipschitz property I first computed $a(n)$ for $n=d\cdot10^{26},1\le d\le10$ to get bounds for a zero, specifically the zero's first digit. Then I essentially performed $10$-fold multisection to get additional digits, until I saw all $10$ digits, at which point $a(n)$ was monotone in an interval, positive at the left end and negative at the right. The exact zero followed directly.

The answer is

245836727707164139860503406

How can this be shown as the last zero of $a(n)$? By using the Lipschitz property, but this is tedious and I will not go over it here. Instead I got confirmation from OEIS A260900, which includes this number and equivalents of it in other bases. Note in particular the comment "The $27$-digit number $245836727707164139860503406$, which is $a(134)$, is the only term in the $n=10$ row."

Answer 2

Here's a solution with incomplete logic (and could possibly be wrong).

The largest $n$ is

$1062880$.

Consider the numbers $0$ to $10^m-1$.

If we think of all of them as $n$-digit numbers (e.g., when $m=3$, $1$ is considered as $001$), then there is an equal number of integers containing at least one copy of each of the ten digits by symmetry. But this largely overestimates the number of integers containing $0$, which means that the number of integers containing $0$ is way less than the number of integers containing copies of other nine digits. Thus, $0$ won't be the "limiting digit".

Next, we want to find a rough range of where this largest $n$ lies. We can do that by counting the number of integers containing a specific digit in the range $0$ to $10^m-1$. Take the digit $1$ as an example. To count the number of integers containing $1$, we first count the opposite, i.e., the number of integers that doesn't contain $1$. If every integer is written as an $n$-digit number, then the integers not containing $1$ can have $0,2,3,\cdots 9$ as its digits, so there are $9^m$ such integers. Hence, the number of integers that does contain $1$ is $10^m-9^m$.

When $m$ is too big (in fact, when $m\geq 7$), $\dfrac{10^m-9^m}{10^m}$ becomes larger than $\dfrac{1}{2}$, meaning that over half of the integers in $0$ to $10^m-1$ now contains $1$. Thus, the largest $n$ possible must lie between $10^6$ and $10^7$. (I think the conclusion here is correct, but there is a lot more justification needed to explain why all $n$ values above $10^7$ won't work, as currently we have only proved the cases where $n=10^x$ and $n\geq 10^7$. I wasn't able to come up with a rigid proof for this)

Now that we have a range where the largest $N$ lies, we can start to track down the exact value of the largest $n$.

After $10^m-1$, the next $10^m$ numbers all start with $1$. Thus, the "concentration" of numbers containing $1$ rapidly increases. Between $0$ and $2\cdot 10^m-1$, at least $10^m$ integers contain the digit $1$, which is already larger than $\frac{1}{2}$. But for smaller values of $m$ ($m<6$), we know that the number of integers containing $1$ between $0$ and $10^{m+1}-1$ is less than half. Thus, there must have been some kind of "dilution", reducing the "concentration" of integers containing the digit $1$ below $0.5$. However, the effect of this "dilution" is limited for larger $m$ ($m>7$), where the "concentration" of integers containing the digit $1$ stays above $0.5$.

Here is a draft figure for the concentration of the number of integers containing the digit $1$ for $n$ from $10^6$ to $10^7$.

Now our objective is pretty clear: to find the point of intersection between the blue curve and the horizontal dotted line representing concentration $=0.5$.

How many integers containing $1$ are there from $0$ to $10^6-1$? We've answered that question above, and the answer is $10^6-9^6=468559.$ Let the largest $n$ be $(10^6-1)+x$, where $x<10^6$. Then the number of integers containing the digit $1$ is $468559+x$. Thus the concentration of integers containing the digit $1$ can be expressed as $\dfrac{468559+x}{10^6-1+x}$. When does this concentration equals $0.5$? We just need to solve the equation $\dfrac{468559+x}{10^6-1+x}=\dfrac{1}{2}$. The result is that $x=62881$. Thus, the largest $n$ is $10^6-1+x=1062880$.