Addendums acaba de añadir que moderadamente refinar la enumeración de (por ejemplo) todas las soluciones enteras positivas de $(xyz) \leq 180$ .
Las soluciones enteras positivas de $(xyz) \leq 180$ puede dividirse en $180$ conjuntos mutuamente excluyentes $(xyz) = a$ donde $a \in \{1,2,\dots, 180\}.$
A continuación, utilizando el mismo método que empleó en su consulta, examinará cada valor de $a$ por separado, examinando su factorización prima. Aunque este enfoque prescinde de cualquier intento de elegancia, el planteamiento es ciertamente sencillo.
Addendum-1 : Visión general
Las adiciones a la respuesta se proporcionan en secciones, Addendum-1, Addendum-2, ... que discuten un enfoque alternativo al problema general y luego tratan de conectar los dos enfoques.
El problema general es:
Enumerar el número de soluciones enteras positivas de $(xyz) \leq M \in \mathbb{Z^+}$ .
Ideas a tener en cuenta:
-
Sea $S_M$ denotan el número de soluciones enteras positivas de $(xyz) \leq M \in \mathbb{Z^+}$ .
-
Sea $T_M$ denotan el número de soluciones enteras positivas de $(xyz) = M \in \mathbb{Z^+}$ . Entonces, claramente, $T_M = [S_M - S_{(M-1)}].$
-
El triple ordenado $(a,b,c)$ se utilizará para denotar la solución $(x=a, y=b, z=c).$
-
Cuando (por ejemplo) la informática $T_{(179)}$ las soluciones $(1,1,179), (1,179,1),$ y $(179,1,1)$ se no considerarse distintos. Para evitar el recuento excesivo, la restricción de $x \leq y \leq z$ se hará cumplir.
-
Para $r \in \mathbb{R}, \lfloor r\rfloor$ se utilizará para denotar el suelo de $r$ (es decir, el mayor número entero $\leq r)$ .
-
El algoritmo alternativo descarta cualquier idea que implique factorizaciones primos, y por lo tanto supuestamente hace que el análisis de la OP resulte obsoleto. De hecho, el final de estos apéndices será un enfoque alternativo (posiblemente irrisorio) para calcular factorizaciones de primos.
Addendum-2 : Informática $S_{(180)}$
Creo que la demostración más clara del enfoque alternativo es empezar con un ejemplo. Dada la restricción de que $x \leq y \leq z$ la primera consideración es que
$$\left\lfloor \left(\frac{180}{1}\right)^{(1/3)} \right\rfloor = 5.\tag1$$
Por lo tanto, $x$ debe ser un elemento de $\{1,2,3,4,5\}.$ Como ilustración adicional del algoritmo, supongamos que estamos enumerando todas las soluciones enteras positivas $(x,y,z)$ donde $x=3$ . Considere que
$$\left\lfloor \left(\frac{180}{3}\right)^{(1/2)} \right\rfloor = 7.\tag2$$
Por lo tanto, cuando $x=3, y$ debe ser un elemento de $\{3,4,5,6,7\}.$ Siguiendo con la ilustración del algoritmo, supongamos que estamos enumerando todas las soluciones enteras positivas $(x,y,z)$ donde $x=3$ y $y=5$ . Considere que
$$\left\lfloor \left(\frac{180}{3 \times 5}\right)^{(1/1)} \right\rfloor = 12.\tag3$$
Por lo tanto, cuando $x=3$ y $y = 5,$ $z$ debe ser un elemento de $\{5,6,7, \cdots, 12\}.$ Por lo tanto $[(12 + 1) - 5] = 8$ soluciones distintas asociadas a $x=3$ y $y=5$ .
Sea $f_k(M,a) : ~k,M,a \in \mathbb{Z^+}, ~a \leq M~$ denotar :
$$\left\lfloor \left(\frac{M}{a}\right)^{(1/k)} \right\rfloor.$$
Entonces $$S_{(180)} = \sum_{x=1}^{f_3(180,1)}~ \sum_{y=x}^{f_2(180,x)}~ \sum_{z=y}^{f_1(180,[xy])}~\{1\} $$ $$=~ \sum_{x=1}^{f_3(180,1)}~ \sum_{y=x}^{f_2(180,x)}~\{1 + f_1(180,[xy]) - y\}.\tag4$$
Addendum-3 : Informática $S_{M}$
El análisis inherente a las ecuaciones (1) a (4) de la sección anterior se sin cambios . Por lo tanto: $$S_{M} ~=~ \sum_{x=1}^{f_3(M,1)}~ \sum_{y=x}^{f_2(M,x)}~\{1 + f_1(M,[xy]) - y\}.\tag5$$
En la respuesta original, yo especulado que emplear un programa informático en un PC para calcular (por ejemplo) $S_{(100,000)}$ a través de factorizaciones primos debería funcionar bien. Ahora especular que empleando un programa informático en un PC para calcular (por ejemplo) $S_{1,000,000,000}$ a través del algoritmo alternativo también debería estar bien.
Además, si $L$ es cualquier número aleatorio tal que $(10)^{(9)} \leq L < (10)^{(10)}$ y, a continuación, utilizando un PC para calcular $T_L = S_L - S_{L-1}$ también debería estar bien. Se desconoce el tamaño de $L$ puede ser permitir $T_L$ para ser fácilmente computable en un superordenador moderno.
En el resto de los apéndices se analiza la utilización del cómputo de $T_L$ para determinar la factorización en primos de $L$ .
Addendum-4 : Utilización de la enumeración de $T_{180}$ para calcular la factorización en primos de $(180)$ .
De hecho, $T_{180} = 20$ en lugar de $18$ calculado por la OP. Esto se explica de la siguiente manera.
$180 = 2^2 \times 3^2 \times 5^1.$
Entorno:
$X = 2^{x_1} \times 3^{x_2} \times 5^{x_3}$
$Y = 2^{y_1} \times 3^{y_2} \times 5^{y_3}$
$Z = 2^{z_1} \times 3^{z_2} \times 5^{z_3}$
y utilizando Análisis de estrellas y barras para calcular el número de soluciones enteras no negativas de
$(x_1 + y_1 + z_1 = 2) ~: \binom{4}{2} = 6.$
$(x_2 + y_2 + z_2 = 2) ~: \binom{4}{2} = 6.$
$(x_3 + y_3 + z_3 = 1) ~: \binom{3}{1} = 3.$
Entonces la estimación inicial de $T_{180}$ es $6 \times 6 \times 3 = 108.$
La segunda estimación de $T_{180}$ como $\frac{108}{3!} = 18$ está más cerca, pero también equivocado. Esta segunda estimación supone que cada solución generada por el párrafo anterior ocurre $(3!)$ veces, entre las soluciones $(x,y,z)$ . Esto es incorrecto, porque $180$ es divisible por $4$ cuadrados perfectos, $\{1,4,9,36\}.$ Por tanto, la estimación inicial de 108 soluciones debe dividirse en dos grupos:
Las 12 soluciones que constituyen las 3 permutaciones cada una de $(1,1,180), (2,2,45), (3,3,20), (6,6,5)$ y las otras 96 soluciones. Estas otras 96 soluciones implican cada una 3 factores distintos, lo que genera (¡3!) repeticiones cada una.
Por lo tanto, la enumeración correcta es $$\frac{96}{3!} + \frac{12}{3} = 20.$$
Así que el ( risible ) la pregunta es: ¿cómo se puede utilizar el cálculo de $T_{180} = 20$ para calcular la factorización en primos de $(180)$ .
Supongamos que $(180) = (p_1)^{a_1} \times (p_2)^{a_2} \times \cdots (p_r)^{a_r}$ donde
$p_1, \cdots, p_r$ son primos distintos en orden ascendente y $a_1, \cdots, a_r \in \mathbb{Z^+}$ .
Entonces quieres enumerar todas las soluciones distintas $(X,Y,Z)$ donde $(XYZ) = 180$ y
$X$ tiene forma $p_1^{x_1} \times \cdots \times p_r^{x_r}$
$Y$ tiene forma $p_1^{y_1} \times \cdots \times p_r^{y_r}$
$Z$ tiene forma $p_1^{z_1} \times \cdots \times p_r^{z_r}.$
Lo primero que hay que hacer es calcular el número de soluciones distintas de $$S_1 : x_1 + y_1 + z_1 = a_1 : \binom{a_1 + [3-1]}{3-1} = \binom{a_1 + 2}{2}$$ $$S_2 : x_2 + y_2 + z_2 = a_2 : \binom{a_2 + [3-1]}{3-1} = \binom{a_2 + 2}{2}$$ $$~\cdots~$$ $$S_r : x_r + y_r + z_r = a_r : \binom{a_r + [3-1]}{3-1} = \binom{a_r + 2}{2}.$$
A continuación, debe calcular el número de soluciones de $(xyz) = (180)$ donde los tres números son iguales : $[0]$ y el número de soluciones de $(xyz) = (180)$ donde dos de los tres números son iguales $[4]$ .
Además, puesto que $180 < (2 \times 3 \times 5 \times 7)$ sabrá inmediatamente que $r < 4.$ Por lo tanto, tiene las siguientes limitaciones:
- $r \in \{1,2,3\}.$
- $S_1 \times \cdots \times S_r = [(3!)d + (3)e]$ donde $e = 4,$ y
$d + e = T_{180} = 20 \implies d = 16 \implies$
$(S_1 \times \cdots \times S_r) = [(3!)(16) + (3)(4) = 108].$
En este punto, está buscando no más de 3 factores $S_1, \cdots, S_r$ tal que $S_1 \times \cdots \times S_r = 108$ y $S_1, \cdots, S_r$ son elementos (no necesariamente distintos) de
$$\left\{\binom{1 + 2}{2} = 3, \binom{2 + 2}{2} = 6, \binom{3 + 2}{2} = 10, \cdots\right\}.$$
Dado que el objetivo de ilustrar esta sección es facilitar el cálculo de la factorización en primos de $L$ para un gran $L$ cuando $T_L$ es conocido, este es un punto de parada razonable para esta sección.
Addendum-5 : Utilización de la enumeración de $T_{L}$ para calcular la factorización en primos de $L$ para muy grande $L$ .
Este es un lugar conveniente para enfatizar que mi comprensión de la Teoría de Números está en el nivel de licenciatura nivel universitario (por ejemplo, mi implicación con la reciprocidad cuadrática ha telarañas en él), y (por ejemplo) tengo cero conocimiento de los recursos informáticos necesarios para calcular todos los números primos menores que (grande) $L$ .
Por lo que sé, todas las ideas que mencionaré en esta sección ya se han tenido en cuenta.
En primer lugar, para los grandes $n$ ,
$$n ~\text{is prime}~ \iff T_n = 1.$$
A continuación, en lugar de definir $S_n = $ el número de soluciones enteras positivas distintas de $(xyz) \leq n$ se podría definir como ${}_3S_n$ . Del mismo modo, se podría redefinir $T_n$ como ${}_3T_n.$ Esto sugiere (quizás erróneamente) que para ( pertinentemente ) grande $L$ podría ser factible y útil calcular (por ejemplo)
$$\{{}_{(10)}T_L, {}_9T_L, \cdots {}_2T_L\}.$$
He pasado por alto un punto que puede ser crítico:
para grandes $L$ para $n,m \in \{1,2,\cdots, 10\} ~: m \leq n,$ no está claro hasta qué punto será factible calcular cuántos ( no diferenciado ) soluciones a $(f_1 \times \cdots \times f_n) = L$ tendrá exactamente $m$ factores idénticos.
