Dado un entero positivo siempre se puede encontrar una tupla de enteros tal que k_1 \ cdot k_2 \ cdot ... \ cdot k_m = n y k_1 | k_2 \ text {,} k_2 | k_3 \ text {,} \ ldots \ text {,} k_ {m-1} | k_m.
Aquí a | b significa que b es un múltiplo de a , digamos "a divide b". Si n> 1, todas las entradas k_i deben ser al menos 2 . Para n = 1 no tenemos ese factor y, por lo tanto, obtenemos una tupla vacía.
En caso de que tenga curiosidad de dónde proviene esto: esta descomposición se conoce como descomposición de factor invariante en la teoría de números y se utiliza en la clasificación de grupos abelianos finitamente generados.
Desafío
Dado salida a todas esas tuplas para la dada exactamente una vez, en el orden que desee. Se permiten los formatos de salida de secuencia estándar .
Ejemplos
1: () (empty tuple)
2: (2)
3: (3)
4: (2,2), (4)
5: (5)
6: (6)
7: (7)
8: (2,2,2), (2,4), (8)
9: (3,3), (9)
10: (10)
11: (11)
12: (2,6), (12)
108: (2,54), (3,3,12), (3,6,6), (3,36), (6,18), (108)
Relacionado: http://oeis.org/A000688 , Lista todas las particiones multiplicativas de n
12,3,3
)Respuestas:
Haskell,
666260 bytesPruébalo en línea!
fuente
05AB1E , 13 bytes
Pruébalo en línea!
fuente
Òœ€.œP
para obtener las sublistas. De hecho, también tuve problemas para encontrar algo más corto ... Si solo hubiera un producto similar alÅœ
producto pero en lugar de la suma. ;)Jalea , 17 bytes
Pruébalo en línea!
fuente
JavaScript (V8) ,
7370 bytesPrints las tuplas en orden descendente(km,km−1,...,k1) .
Pruébalo en línea!
Comentado
fuente
05AB1E ,
171514 bytesMuy lento para casos de prueba más grandes.
-1 byte gracias a @Grimy .
Pruébalo en línea.
Explicación:
fuente
JavaScript, 115 bytes
Escribiré una explicación más tarde
fuente
Wolfram Language (Mathematica) ,
7876727167 bytesPruébalo en línea!
Árbol de búsqueda recursiva.
Solución de fuerza bruta, 64 bytes :
Modificación trivial de mi solución de Mathematica para enumerar todas las particiones multiplicativas de n .
fuente
Japt , 22 bytes
Intentalo
fuente