Formas de calcular el número multiplicando

Question

Estoy tratando de calcular cuántas formas hay de calcular el mismo número multiplicando 3 números menores o iguales. Pero con una sola permutación de los tres números dados.

Por ejemplo, el número 6 se puede calcular mediante

1 * 1 * 6 = 6
2 * 3 * 1 = 6

pero también se puede calcular mediante las siguientes permutaciones de [ 1, 1, 6 ] , pero quiero contarlo sólo como una opción

1 * 6 * 1 = 6
6 * 1 * 1 = 6

Sé cómo lograr esto usando un algoritmo muy lento de 3 incrustados for ciclos, ¿hay algún truco matemático para hacerlo mejor?

Gracias de antemano.

Editar:

Esto es para los números dentro de <1; n> of N donde n es el número dado.

Se agradecería una solución en forma de pseudocódigo.

Answer 1

Descomponiendo el número en factores primos, escribir $n =\prod_{p \in P} p^{v_p(n)} $ donde $P$ es el conjunto de primos y $v_p(n)$ es el exponente para el que $p^v$ divide exactamente $n$ (es decir, $p^{v_p(n)} \mid n$ y $p^{v_p(n)+1} \not\mid n$ .

Si quieres ver de cuántas maneras $n$ puede escribirse como el producto de $m$ factores, que estos factores sean $(n_k)_{k=1}^m$ para que $n =\prod_{k=1}^m n_k $ .

Desde $n_k =\prod_{p \in P} p^{v_p(n_k)} $ , por factorización única tenemos $v_p(n) =\sum_{k=1}^mv_p(n_k) $ .

El problema se reduce ahora a encontrar el número de formas en que de cada exponente de cada primo que divide $n$ puede escribirse como la suma de $m$ valores no negativos.

Tu turno.

Answer 2

Para encontrar el número de manera de crear $x$ puedes hacer lo siguiente:

$$x=\begin{cases}[x,1,1]\\ [p,q,1]\\ [a,b,c]\end{cases}$$

Para el primer caso no necesitas trabajar. Para el segundo caso necesitas hacer alguna búsqueda:

para lo cual $i\in\Bbb N, i\in [2,\sqrt x]$ tienes $x\equiv0\pmod{i}$

todas las formas posibles de crear el número $x$ en la segunda forma será $\left[i,\frac xi,1\right]$

ahora la tercera forma será la más complicada:

en primer lugar hay que tener en cuenta que $[a,b,c]=[a\times b,c,1]$ por lo que se puede repetir en la segunda parte pero en lugar de buscar qué $i$ tienes $x\equiv0\pmod{i}$ buscará que $j$ tienes $i\equiv0\pmod{j}$ y $\frac xi\equiv0\pmod{j}$