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

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

• It is a long story till we get the question, please fix the subject of the question (is there... what... to compute?!) Do we compute using a computer? Do we need to compute this for $n$ (from "below $10^n$") up to $n=10$, or $n=20$, or $n=100$... ? (This kind of "finite ergodic game" is a nice game, but we cannot expect structure or mathematical insight. So let us get the pragmatic view in detail...) – dan_fulea Apr 23 at 11:26
• Yes, it's a long story. I'm also not sure what's unclear. I don't need to compute anything. I am curious about the existence of a straightforward way of doing that which doesn't involve bruteforce approach. I'd be happy to hear about heuristics within "feasible ranges" (e.g. below $10^{1000}$) and I'd also be happy to hear a general proof. – Asaf Karagila Apr 23 at 11:46
• Second generation products need either no even digits or no $5$s in the original number, which puts an upper bound of $O(n^3)$ in the second-generation products – Empy2 Apr 23 at 15:26
• @Empy2: I realized earlier today that actually once can do this recursively in $O(n^2)$, or probably $n\log n$ or so. Start with $D_0=\{1\}$, then let $D_{n+1}$ be $\{d\cdot k\mid d\in\{0,\dots,9\}, k\in D_n\}$. – Asaf Karagila Apr 23 at 21:03
• @AsafKaragila - How would that be $O(n^2)$? The set operations themselves may look like primitives $O(1)$ but in reality they are not. In any case $|D_n| = O(n^4)$ so you cannot compute it in $O(n^2)$, right? – antkam Apr 24 at 12:15

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) {
}
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: • I'm confused about your formula, since it does not fit with the one by Empy2. (Also, Java? Ew. :-)) – Asaf Karagila Apr 23 at 21:16
• @AsafKaragila It's actually the same formula, just check the introdcutory part of my answer again. I have changed it a little bit. Regarding Java... What's wrong with it? :) I did not have Mathematica handy. With streams and lambda functions introduced in Java8, it's easy to use all your CPUs to speed up computations significantly. I see that people prefer Python which I find inferior (terrible execution speeds, limited multithreading capabilities). My language of choice is actually Scala (Java on steroids) but it has much smaller user base. I can also do C++ and Go so by my guest :) – Oldboy Apr 24 at 6:05
• @AsafKaragila I forgot to metion PHP :))))))))) – Oldboy Apr 24 at 8:21
• If you want true speed, then it's assembler or nothing. If you want elegance, then go (Common) Lisp or go home. With lambda functions introduced in 1958... – Asaf Karagila Apr 24 at 8:38
• @Oldboy - while I agree with your points re: programming language, I found it funny (ironic?) that you write in java to INCREASE the set of people who can understand your code, BUT your parallelized version might have severely REDUCED that set! Indeed, I could understand your original code but I no longer understand this new parallelized version. :) – antkam Apr 24 at 12:50

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.

• +1 very nice! what adjustment for $6$s do you have in mind? – antkam Apr 23 at 13:57
• $6^2$ could be replaced by $4×9$ so I only have to worry about one $6$ – Empy2 Apr 23 at 14:01
• But why worry about one $6$? e.g. in the number $6555$ for $n=4$, you have $a=b=1, c=3$ and that still satisfies $a/3 + b/2 + c + d \le n$. Nowhere did you say $a/3$ and $b/2$ have to be integers. – antkam Apr 23 at 14:03
• How did you get from the inequality $a/3+b/2+c+d\le n$ to the closed-form expression $1+{n+2\choose 2}^2$? Can you elaborate on the math techniques involved? – antkam Apr 24 at 11:52
• You've caught me out - I just used Oldboy's results, and found all the differences of the differences of the differences of the differences were the same. – Empy2 Apr 24 at 12:07

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.

• I was just confused. Sorry. It would be easy to count if different multisets gave different products. You have noted one case where that doesn't happen. There are a number of others. You are correct that you give an upper bound. I think it is hard to enumerate the cases where different multisets give the same product. – Ross Millikan Apr 23 at 14:19
• @RossMillikan - I was only halfway into my morning coffee at the time, and feeling unsure myself, so I can fully sympathize. :) – antkam Apr 23 at 14:23