Calcular cuántos productos digitales distintos hay debajo $10^n$

Question

Dado un número $n$ su producto digital es el producto de su dígito. Así, el producto digital de $15$ es $1\times 5=5$ y el producto digital de $760$ es $0$ etc.

Hace poco vi un bonito vídeo en Numberphile en el que se hablaba de la persistencia, es decir, de cuántas iteraciones de producto digital se necesitan para llegar a un solo dígito (por ejemplo $75\to 35\to 15\to 5$ tiene una persistencia de $3$ ).

Jugando un poco con la idea, se me ocurrió que una forma eficiente de escribir un código para comprobar esto incluiría tener un diccionario. Esto es porque si sé que $35$ requiere dos pasos, no necesito iterar tres pasos de $75$ , sólo puedo notar que es uno más que $35$ .

Por supuesto, no se quiere almacenar esta información para cada número, porque entonces se estaría desperdiciando un montón de memoria al probar esto con números muy grandes.

Así que mi primera búsqueda fue preguntarme cuál sería el tamaño máximo de un diccionario que necesitamos. Bueno, si probamos hasta $10^n$ el mayor producto digital sería $10^n-1$ que es $9^n$ . Esto es genial, ya que $\frac{9^n}{10^n}\to 0$ así que estás siendo relativamente eficiente. Pero en el mundo real, esto sigue siendo un tamaño masivo de asignación de memoria en un ordenador personal.

El siguiente paso, por tanto, es preguntar, cuántos valores distintos podemos obtener de un producto digital ?

He probado esto hasta $10^8$ y la respuesta puede sorprenderle. Resulta que sólo hay $2026$ valores que se obtienen de los productos digitales a continuación $10^8$ . Alrededor de la mitad de ellos son en realidad $0$ ya que cuanto más largo sea el número, más difícil será evitarlo $0$ pero seguimos hablando de $43000000$ números cuyo producto es distinto de cero.

He aquí un estado básico de los resultados:

$$\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}$$

Se trata de un ritmo de crecimiento bastante lento y, de nuevo, tiene sentido. Cuanto más largos sean sus números, más probable es que tengan $0$ dentro, y si no es un $0$ Entonces, al menos $1$ que puede omitirse y no cambiar el valor del producto.

Evidentemente, la primera pregunta es si sólo hay un número finito de productos digitales. Por supuesto que no. $10^n-1$ tiene un producto digital de $9^{n-1}$ , lo que nos proporcionaría infinitos valores distintos.

¿Existe una forma relativamente sencilla de calcular recursivamente cuántos productos digitales distintos hay a continuación? $10^n$ ? ¿O al menos un límite superior razonable?

(Obsérvese que hay cierta intuición de por qué esto puede hacerse recursivamente. Por ejemplo, si $k$ tiene dígitos pequeños ( $1$ a $4$ entonces $10k+2$ tiene el mismo producto digital que $2k$ Así que si $2$ aparece en una serie de longitudes $n$ y todos los dígitos son pequeños, no añade un nuevo valor. Hay un montón de casos para probar, y , por lo que espero que alguien más talentoso que yo en lo que respecta a la combinatoria finita pueda ver a través de ellos).

Answer 1

Esto es básicamente Secuencia OEIS A154323 que representan los coeficientes centrales del triángulo numérico A113582 . La página de la OEIS ofrece la siguiente fórmula:

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

En realidad, se trata de la fórmula proporcionada por Empty2, sólo que con un índice inicial diferente ( $n$ en lugar de $n+1$ ).

Incluso sin una solución de forma cerrada, se puede contar el número de productos distintos con unas pocas líneas de código. He decidido elegir Java porque desde Java8 es muy fácil emplear todos los núcleos de la CPU existentes en cálculos basados en flujos, lo que acorta significativamente los tiempos de cálculo.

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}");
    }
}

Aquí están los resultados hasta $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}$$

...y un gráfico:

...también utilizando la escala logarítmica:

Answer 2

El producto es $2^a3^b5^c7^d$ donde $a/3+b/2+c+d\le n$ con un ajuste para los 6s, ¿cuál es el volumen de un simplex de cuatro dimensiones?
Excepto en el caso de $n=0$ Los números de la respuesta de @Oldboy son los siguientes $$1+{n+2\choose 2}^2$$
No sé por qué.

Answer 3

Un límite superior poco preciso (¿y una posible aproximación al recuento exacto?)

Digamos que un número $< 10^n$ tiene $n$ dígitos, incluyendo posiblemente la cabeza $0$ s. Si algún dígito es $0$ entonces el DP es $0$ . Ignorando estos, tenemos $n$ dígitos que son $1-9$ . El orden de los dígitos no importa, por lo que en realidad sólo nos interesa el multiconjunto de dígitos (multiconjunto porque el número de veces, por ejemplo $5$ aparece importa).

Para contar estos conjuntos múltiples, podemos lanzar $n$ bolas en nueve casillas. El número de formas, por el método de las estrellas y las barras, es ${n+8 \choose 8}$ . Así que esto es un límite superior. Por ejemplo, para $n=4,5,6,7,8$ los límites superiores son $495, 1287, 3003,6435,12870$ respectivamente.

La razón por la que esto no es ajustado es porque, por ejemplo $2\times 3 = 1 \times 6$ etc. Si hay una forma de contabilizar todas esas equivalencias, entonces tendríamos una fórmula para el recuento exacto.