Algoritmo para la partición de n en distintos números primos

Question

Estoy buscando un algoritmo que va a crear una partición de un número entero positivo en distintos números primos. El número de particiones está dada por este OEIS secuencia: https://oeis.org/A000586

Para ser más específicos, sólo estoy interesado en conjuntos de 5 números primos que se agregan al número original, y me gustaría obtener todas las posibles particiones para cada número.

Es alguien consciente de un algoritmo a lo largo de estas líneas?

Answer 1

El primer paso es considerar si los 2 se incluye. Desde otro de los números primos son impares, 2 se incluye si usted está tratando de finad particiones de un número en un número impar de distrito de los números primos o un número impar en un número de diferentes números primos; 2 es excluidas de otra manera.

El siguiente paso es considerar la partición de $n$ a $k$ distintos impares, números primos menores o iguales a $m$ (no hay ningún punto de mirar a $m$ mayor que la diferencia entre el $n$ y la suma de los primeros $k-1$ impares, números primos). Si $k=1$, a continuación, comprobar si $n$ es primo. Si $k>1$, a continuación, la parte más grande es mayor que $\frac{n}{k}$ pero inferior o igual a $m$. Así que usted puede elegir de un conjunto de números primos en este rango como posibles partes; si una de estas es$p$, entonces usted, a continuación, junto necesidad de encontrar particiones de $n-p$ a $k-1$ distintos impares, números primos menores o iguales a $p-2$, lo que lo lleva de vuelta al principio de este paso.

Puede haber etapas en las que la misma pregunta se le pide varias veces, y por lo tanto puede ser más eficiente para calcular previamente las soluciones

Como una ilustración, tomar la partición de 40 en cinco de los números primos. 40 es aún y cinco es un número impar por lo que 2 debe ser una parte.

Ahora queremos particiones de 38 en cuatro distintos impares, números primos. La mayor parte debe ser más de $\frac{38}{4}$ e inferior o igual a $38-3-5-7$, por lo que debe ser en $\{ 11,13,17,19,23\}$. Considerar estos a su vez.

• Queremos particiones de 27 en tres distintos impares, números primos menores o iguales a 9. Que no es posible, ya que también debe ser mayor que $\frac{27}{3}$.

• Queremos particiones de 25 en tres distintos impares, números primos menores o iguales a 11. La mayor parte, también debe ser mayor que $\frac{25}{3}$, por lo que la única posibilidad de que la mayor parte es de 11, lo que nos deja a buscar particiones de 14 en dos impares, números primos menores o iguales a 9, que en la próxima etapa no ser posible ya que no hay números primos mayores de 7 y menos de o igual a 9.

• Queremos particiones de 21 en tres distintos impares, números primos menores o iguales a 15, aunque podemos reducir este de 15 a $21-3-5=13$. La mayor parte, también debe ser mayor que $\frac{21}{3}$,por lo que debe ser en $\{ 11,13\}$, lo que nos deja a buscar lo que nos deja para buscar las particiones de 10 en dos impares, números primos menores o iguales a 9 (reducir a $10-3=7$) [que en el siguiente paso nos dará $3+7$], y para las particiones de 8 en dos impares, números primos menores o iguales a 11 (reducir a $8-3=5$) [que en el siguiente paso nos dará $3+5$]. Para la reconstrucción de regreso al inicio, esto nos da las particiones $2+3+7+11+17$ e $2+3+5+13+17$.

• Queremos particiones de 19 en tres distintos impares, números primos menores o iguales a 17, aunque se puede reducir de 17 a $19-3-5=11$. La mayor parte, también debe ser mayor que $\frac{19}{3}$, por lo que debe ser en $\{7,11\}$, lo que nos deja a buscar particiones de 12 en dos impares, números primos menores o iguales a 5 (no es posible), y para las particiones de 8 en dos impares, números primos menores o iguales a 9 (reducir a $8-3=5$) [ya hemos encontrado $3+5$]. Para la reconstrucción de regreso al inicio, esto nos da la partición $2+3+5+11+19$.

• Queremos particiones de 15 en tres distintos impares, números primos menores o iguales a 23, aunque podemos reducir este 23 de a $15-3-5=7$. La mayor parte, también debe ser mayor que $\frac{15}{3}$, por lo que debe ser en $\{7\}$, lo que nos deja a buscar particiones de 8 en dos impares, números primos menores o iguales a 5 [ya hemos encontrado $3+5$]. Para la reconstrucción de regreso al inicio, esto nos da la partición $2+3+5+7+23$.

Lo que hace este método, de hecho, los cuatro deseado particiones de 40.