2 votos

Dada una factorización primaria de un número, encuentra todas sus otras factorizaciones (no factores)

¿Existe un algoritmo para determinar todas las factorizaciones distintas de un número, si se conocen tanto el número como su factorización prima?

Ejemplo

n = 64

f = 2^6

Los factores son:

1, 2, 4, 8, 16, 32, 64

No estoy pidiendo lo anterior. En cambio, ¿hay un método para encontrar lo siguiente:

  • 1 * 64
  • 2 * 32
  • 2 * 2 * 16
  • 2 * 2 * 2 * 8
  • 2 * 2 * 2 * 2 * 4
  • 2 * 2 * 2 * 2 * 2 * 2
  • 4 * 16
  • 4 * 2 * 8
  • 4 * 4 * 4
  • 8 * 8

El ejemplo anterior tiene un factor primo distinto, pero me gustaría una solución generalizada a n factores primos distintos.

1voto

Matthew Scouten Puntos 2518

Recursivamente: para cada factor $f$ de su número $n$ , prepáralo $(f)$ a todas las factorizaciones de $n/f$ donde todos los factores $\ge f$ ...

1voto

Frangello Puntos 21

Como ha señalado @Adrian Keister en un comentario, lo que sigue no responde a la pregunta formulada. Sin embargo, ya que esto responde a lo que probablemente es una pregunta relacionada a menudo, lo dejaré arriba, al menos a menos que empiece a ser asesinado con downvotes $\ldots$

Dejemos que $N$ sea un número entero positivo con factorización prima

$$ N \; = \; p_{1}^{n_1} p_{2}^{n_2} p_{3}^{n_3} \cdots p_{k}^{n_k}$$

Entonces, incluyendo $1$ y $N,$ hay

$$ (n_1 + 1)(n_2 + 1)(n_3 + 1) \cdots (n_k + 1) $$

muchos factores de $N,$ y cada factor tiene la forma

$$ p_{1}^{{\alpha}_1} p_{2}^{{\alpha}_2} p_{3}^{{\alpha}_3} \cdots p_{k}^{{\alpha}_k}$$

donde cada $\alpha_i$ pertenece a $\{0,\,1,\,2,\,3,\, \ldots,\,n_i \}.$

Ejemplo: Dejemos que $N = 45000 = 2^3 \cdot 3^2 \cdot 5^4.$ Entonces el $(3+1)(2+1)(4+1) = 60$ muchos factores son

$$ 2^0 \cdot 3^0 \cdot 5^0 \;\;\;\;\;\;\; 2^0 \cdot 3^0 \cdot 5^1 \;\;\;\;\;\;\; 2^0 \cdot 3^0 \cdot 5^2 \;\;\;\;\;\;\; 2^0 \cdot 3^0 \cdot 5^3 \;\;\;\;\;\;\; 2^0 \cdot 3^0 \cdot 5^4 $$

$$ 2^0 \cdot 3^1 \cdot 5^0 \;\;\;\;\;\;\; 2^0 \cdot 3^1 \cdot 5^1 \;\;\;\;\;\;\; 2^0 \cdot 3^1 \cdot 5^2 \;\;\;\;\;\;\; 2^0 \cdot 3^1 \cdot 5^3 \;\;\;\;\;\;\; 2^0 \cdot 3^1 \cdot 5^4 $$

$$ 2^0 \cdot 3^2 \cdot 5^0 \;\;\;\;\;\;\; 2^0 \cdot 3^2 \cdot 5^1 \;\;\;\;\;\;\; 2^0 \cdot 3^2 \cdot 5^2 \;\;\;\;\;\;\; 2^0 \cdot 3^2 \cdot 5^3 \;\;\;\;\;\;\; 2^0 \cdot 3^2 \cdot 5^4 $$

$$ 2^1 \cdot 3^0 \cdot 5^0 \;\;\;\;\;\;\; 2^1 \cdot 3^0 \cdot 5^1 \;\;\;\;\;\;\; 2^1 \cdot 3^0 \cdot 5^2 \;\;\;\;\;\;\; 2^1 \cdot 3^0 \cdot 5^3 \;\;\;\;\;\;\; 2^1 \cdot 3^0 \cdot 5^4 $$

$$ 2^1 \cdot 3^1 \cdot 5^0 \;\;\;\;\;\;\; 2^1 \cdot 3^1 \cdot 5^1 \;\;\;\;\;\;\; 2^1 \cdot 3^1 \cdot 5^2 \;\;\;\;\;\;\; 2^1 \cdot 3^1 \cdot 5^3 \;\;\;\;\;\;\; 2^1 \cdot 3^1 \cdot 5^4 $$

$$ 2^1 \cdot 3^2 \cdot 5^0 \;\;\;\;\;\;\; 2^1 \cdot 3^2 \cdot 5^1 \;\;\;\;\;\;\; 2^1 \cdot 3^2 \cdot 5^2 \;\;\;\;\;\;\; 2^1 \cdot 3^2 \cdot 5^3 \;\;\;\;\;\;\; 2^1 \cdot 3^2 \cdot 5^4 $$

$$ 2^2 \cdot 3^0 \cdot 5^0 \;\;\;\;\;\;\; 2^2 \cdot 3^0 \cdot 5^1 \;\;\;\;\;\;\; 2^2 \cdot 3^0 \cdot 5^2 \;\;\;\;\;\;\; 2^2 \cdot 3^0 \cdot 5^3 \;\;\;\;\;\;\; 2^2 \cdot 3^0 \cdot 5^4 $$

$$ 2^2 \cdot 3^1 \cdot 5^0 \;\;\;\;\;\;\; 2^2 \cdot 3^1 \cdot 5^1 \;\;\;\;\;\;\; 2^2 \cdot 3^1 \cdot 5^2 \;\;\;\;\;\;\; 2^2 \cdot 3^1 \cdot 5^3 \;\;\;\;\;\;\; 2^2 \cdot 3^1 \cdot 5^4 $$

$$ 2^2 \cdot 3^2 \cdot 5^0 \;\;\;\;\;\;\; 2^2 \cdot 3^2 \cdot 5^1 \;\;\;\;\;\;\; 2^2 \cdot 3^2 \cdot 5^2 \;\;\;\;\;\;\; 2^2 \cdot 3^2 \cdot 5^3 \;\;\;\;\;\;\; 2^2 \cdot 3^2 \cdot 5^4 $$

$$ 2^3 \cdot 3^0 \cdot 5^0 \;\;\;\;\;\;\; 2^3 \cdot 3^0 \cdot 5^1 \;\;\;\;\;\;\; 2^3 \cdot 3^0 \cdot 5^2 \;\;\;\;\;\;\; 2^3 \cdot 3^0 \cdot 5^3 \;\;\;\;\;\;\; 2^3 \cdot 3^0 \cdot 5^4 $$

$$ 2^3 \cdot 3^1 \cdot 5^0 \;\;\;\;\;\;\; 2^3 \cdot 3^1 \cdot 5^1 \;\;\;\;\;\;\; 2^3 \cdot 3^1 \cdot 5^2 \;\;\;\;\;\;\; 2^3 \cdot 3^1 \cdot 5^3 \;\;\;\;\;\;\; 2^3 \cdot 3^1 \cdot 5^4 $$

$$ 2^3 \cdot 3^2 \cdot 5^0 \;\;\;\;\;\;\; 2^3 \cdot 3^2 \cdot 5^1 \;\;\;\;\;\;\; 2^3 \cdot 3^2 \cdot 5^2 \;\;\;\;\;\;\; 2^3 \cdot 3^2 \cdot 5^3 \;\;\;\;\;\;\; 2^3 \cdot 3^2 \cdot 5^4 $$

En este ejemplo, observe que los exponentes en $2$ vienen de $\{0,\,1,\,2,\,3\}$ y los exponentes en $3$ vienen de $\{0,\,1,\,2\}$ y los exponentes en $5$ vienen de $\{0,\,1,\,2,\,3,\, 4\}.$ Una forma de organizar las posibles opciones de elección de los exponentes es la misma que cuando se prueban todas las combinaciones para un cerradura de combinación cuya secuencia de desbloqueo de dígitos has olvidado o perdido, algo que he tenido que hacer al menos dos veces, y no por diversión, cuando era niño.

0voto

SmileyCraft Puntos 48

Puedes iterar por todos los divisores $d$ de $n$ y luego enumerar recursivamente todas las factorizaciones de $n/d$ donde cada factor es como máximo $d$ . Si quieres saber cómo implementar esto de manera eficiente, puedo codificar algo en c++.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X