Computing how many distinct digital products are below $10^n$

Question

Given a number $n$, its digital product is the product of its digit. So the digital product of $15$ is $1\times 5=5$, and the digital product of $760$ is $0$, etc.

I recently saw a nice video on Numberphile where they discussed persistence, namely how many iterations of digital product do you need in order to reach a single digit (e.g. $75\to 35\to 15\to 5$ has persistence of $3$).

Playing a bit with the idea, it occurred to me that an efficient way of writing a code to check for this would include having a dictionary. This is because if I know that $35$ requires two steps, I don't need to iterate three steps from $75$, I can just notice that it's one more than $35$.

Of course, you don't want to store this information for every number, because then you'd be wasting a lot of memory when testing this with very large numbers.

So my first quest was to wonder what would be the maximal size of a dictionary we need. Well, If we test all the way to $10^n$, the largest digital product would be $10^n-1$, which is $9^n$. This is great, since $\frac{9^n}{10^n}\to 0$, so you're being relatively efficient. But in the real world, this is still a massive size of memory allocation on a personal computer.

The next step, therefore, is to ask, how many distinct values can we get from a digital product?

I tested this up to $10^8$, and the answer may surprise you. It turns out that there are only $2026$ values that you get from digital products below $10^8$. About half of those are actually $0$, since the longer the number the harder it is to avoid $0$, but we are still talking about $43000000$ numbers whose product is non-zero.

Here is a basic state of the results:

$$\begin{array}{c|l} \text{Below} & \text{Distinct digital products}\\\hline 10^0 & 1\\ 10^1 & 10\\ 10^2 & 37\\ 10^3 & 101\\ 10^4 & 226\\ 10^5 & 442\\ 10^6 & 785\\ 10^7 & 1297\\ 10^8 & 2026 \end{array}$$

This is quite a slow growth rate, and again, it makes sense. The longer your numbers are, the more likely they are to have $0$ inside, and if not a $0$, then at least $1$ which can then be omitted and not change the value of the product.

Obviously, the first question is whether or not there are only finitely many digital products. Of course not. $10^n-1$ has a digital product of $9^{n-1}$, which would provide us with infinitely many distinct values.

Is there a relatively straightforward to recursively compute how many distinct digital products are there below $10^n$? Or at least a reasonable upper bound?

(Note that there is some intuition as to why this can be done recursively. For example, if $k$ has small digits ($1$ to $4$, then $10k+2$ has the same digital product as $2k$, so if $2$ appears in a number of length $n$, and all the digits are small, it does not add a new value. There are a lot of cases to test, and , which is why I hope someone more talented than me when it comes to finite combinatorics can see through them.)

Answer 1

This is basically OEIS sequence A154323 representing central coefficients of number triangle A113582. The OEIS page gives the following formula:

$$a_n = \frac{n^4 + 2n^3 + n^2 + 4}4=1+\binom{n+1}{2}^2$$

The is actually the formula provided by Empty2, just with a different starting index ($n$ instead of $n+1$).

Even without a closed form solution, you can count the number of distinct products with just a few lines of code. I have decided to choose Java because since Java8 it's very easy to employ all existing CPU cores in stream-based computations which shortens computation times significantly.

import java.math.BigInteger;
import java.util.HashSet;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Application {
    public static final int N = 100;

    static Set<BigInteger> getUniqueProducts(int generation) {
        Set<BigInteger> result = new HashSet<>();
        if(generation == 0) {
            result.add(BigInteger.ONE);
        }
        else {
            Set<BigInteger> products = getUniqueProducts(generation - 1);
            result = products.stream().parallel().flatMap(
                    product -> IntStream
                        .range(0, 10)
                        .mapToObj(String::valueOf)
                        .map(s -> new BigInteger(s))
                        .map(num -> num.multiply(product))
            ).collect(Collectors.toSet());
        }
        System.out.println("10^{" + generation + "} & " + result.size() + "\\\\");
        return result;
    }   

    public static void main(String[] args) {
        System.out.println("\\begin{array}{c|l}");
        System.out.println("\\text{Below} & \\text{Distinct digital products}\\\\\\hline");
        getUniqueProducts(N);
        System.out.println("\\end{array}");
    }
}

Here are the results up to $n=80$:

$$\begin{array}{c|l} \text{Below} & \text{Distinct digital products}\\\hline 10^{0} & 1\\ 10^{1} & 10\\ 10^{2} & 37\\ 10^{3} & 101\\ 10^{4} & 226\\ 10^{5} & 442\\ 10^{6} & 785\\ 10^{7} & 1297\\ 10^{8} & 2026\\ 10^{9} & 3026\\ 10^{10} & 4357\\ 10^{11} & 6085\\ 10^{12} & 8282\\ 10^{13} & 11026\\ 10^{14} & 14401\\ 10^{15} & 18497\\ 10^{16} & 23410\\ 10^{17} & 29242\\ 10^{18} & 36101\\ 10^{19} & 44101\\ 10^{20} & 53362\\ 10^{21} & 64010\\ 10^{22} & 76177\\ 10^{23} & 90001\\ 10^{24} & 105626\\ 10^{25} & 123202\\ 10^{26} & 142885\\ 10^{27} & 164837\\ 10^{28} & 189226\\ 10^{29} & 216226\\ 10^{30} & 246017\\ 10^{31} & 278785\\ 10^{32} & 314722\\ 10^{33} & 354026\\ 10^{34} & 396901\\ 10^{35} & 443557\\ 10^{36} & 494210\\ 10^{37} & 549082\\ 10^{38} & 608401\\ 10^{39} & 672401\\ 10^{40} & 741322\\ 10^{41} & 815410\\ 10^{42} & 894917\\ 10^{43} & 980101\\ 10^{44} & 1071226\\ 10^{45} & 1168562\\ 10^{46} & 1272385\\ 10^{47} & 1382977\\ 10^{48} & 1500626\\ 10^{49} & 1625626\\ 10^{50} & 1758277\\ 10^{51} & 1898885\\ 10^{52} & 2047762\\ 10^{53} & 2205226\\ 10^{54} & 2371601\\ 10^{55} & 2547217\\ 10^{56} & 2732410\\ 10^{57} & 2927522\\ 10^{58} & 3132901\\ 10^{59} & 3348901\\ 10^{60} & 3575882\\ 10^{61} & 3814210\\ 10^{62} & 4064257\\ 10^{63} & 4326401\\ 10^{64} & 4601026\\ 10^{65} & 4888522\\ 10^{66} & 5189285\\ 10^{67} & 5503717\\ 10^{68} & 5832226\\ 10^{69} & 6175226\\ 10^{70} & 6533137\\ 10^{71} & 6906385\\ 10^{72} & 7295402\\ 10^{73} & 7700626\\ 10^{74} & 8122501\\ 10^{75} & 8561477\\ 10^{76} & 9018010\\ 10^{77} & 9492562\\ 10^{78} & 9985601\\ 10^{79} & 10497601\\ 10^{80} & 11029042\\ \end{array}$$

...and a chart:

...also using logarithmic scaling:

Answer 2

A loose upperbound (and possible approach for exact count?)

Lets say a number $< 10^n$ has $n$ digits, including possibly leading $0$s. If any digit is $0$ then the DP is $0$. Ignoring those, we have $n$ digits which are $1-9$. The ordering of the digits don't matter, so we're really just interested in the multiset of digits (multiset because the number of times e.g. $5$ appears matters).

To count such multisets, we can throw $n$ balls into nine boxes. The number of ways, by stars and bars method, is ${n+8 \choose 8}$. So this is an upperbound. E.g. for $n=4,5,6,7,8$ the upperbounds are $495, 1287, 3003,6435,12870$ respectively.

The reason this is not tight is because e.g. $2\times 3 = 1 \times 6$, etc. If there is a way to account for all such equivalences then we'd have a formula for the exact count.

Answer 3

The product is $2^a3^b5^c7^d$ where $a/3+b/2+c+d\le n$, with an adjustment for 6s, so what is the volume of a four-dimensional simplex?
Except for $n=0$, the numbers in @Oldboy's answer follow $$1+{n+2\choose 2}^2$$
I don't know why.