Números de la partición de computación

Question

Hoy en día un amigo y yo mismo ocurrió con la cuestión de la computación en las particiones de números, es decir: dado un número$n$, ¿cuál es el número de $p(n)$ era de las diferentes formas de escritura $n$ como una suma no cero enteros (donde los desplazamientos de los dos términos en la suma cuenta como un único camino)?

No sabemos de ninguna de las fórmulas para ello. Actualmente estoy tratando de escribir un bruteforce (computacional) planteamiento del problema, pero yo quería preguntarle sobre otro más sofisticada forma de atacar el problema (todavía con un ordenador).

Es bien conocido que $$\sum_{n=0}^\infty p(n)x^n = \prod_{k=1}^\infty\frac{1}{1-x^k}$$ La idea que tenemos es la de proceder de la siguiente manera:

1. $\log\left(\prod_{k=1}^\infty\frac{1}{1-x^k}\right) = -\sum_{k=1}^\infty\log(1-x^k) = -\sum_{k=1}^N\log(1-x^k) + O(x^{N+1})$ cuando se utilizó la expansión de Taylor de $\log$ $1$ para obtener el término de error.
2. $\prod_{k=1}^\infty\frac{1}{1-x^k}\approx \exp\left(\sum_{k=1}^N\log(1-x^k)\right) =: F(x)$ con algún término de error.
3. Evaluar $F$ algunos $x$ cerca de cero (por lo que los términos de orden superior no son relevantes) y el uso polyfit (mínimos cuadrados) para obtener el coeficiente de $x^n$, es decir,$p(n)$.

Ahora mis preguntas son las siguientes:

1. Sería este método (o algo similar)?
2. ¿Cuál sería el término de error en el punto (2.) parecen?
3. Cómo elegir a $N$ y los puntos de $x$ donde evaluamos $F$ en el paso (3.) de manera que el error es menor que decir $0.1$ en la final? Observe que la pregunta anterior está estrechamente relacionado con éste.
4. ¿Cuál sería la complejidad del algoritmo resultante?
5. ¿Cómo son las $p(n)$ calculado normalmente?

Gracias de antemano por la ayuda.

Answer 1

No quiero invocar cualquiera de los métodos sofisticados que se han encontrado (véase el artículo relacionado en la otra respuesta), ni siquiera el número pentagonal teorema. Yo solo quiero decir que la forma más sencilla de calcular los valores de $p(n)$ todos los $n\leq N$ requiere sólo $O(N^2)$ adiciones de números enteros, que es del mismo orden como una sola multiplicación de potencia de la serie a a $O(x^{N+1})$ (y, de hecho, algo más simple ya que no hay coeficiente de multiplicación). Sin haber estudiado el proyecto en detalle, parece poco probable que el resultado sería algo más eficiente que este, aunque sin duda es mucho más complicado.

Así que aquí está el método directo. Voy a presentar como código C++, ya que es lo que acabo de probar. Si su objetivo es calcular un valor relativamente pequeño de$~N$, $N=416$ cual es la medida de lo $64$bits entero sin signo aritmético va a llegar, no hay necesidad de nada más sofisticados; el tiempo de cálculo es insignificante.

 typedef std::vector<unsigned long int> arr;
 arr part(unsigned int n)
 {
   arr c(n+1,0); // array of coefficients of X^0 ... X^n
   c[0]=1;  // start with 1X^0
   for (unsigned int k=1; k<=n; ++k) // multiply by 1/(1-X^k)
     for (unsigned int i=0; i+k<=n; ++i)
       c[i+k]+=c[i];
   return c;
 }

El bucle interno se realiza la división por $1-X^k$; el uso de un aumento de recorrer $i$ esto es sencillo (aunque quizá no tan conocidos, como debe ser). Me explicó que en esta respuesta. En el contexto de este problema concreto de la interpretación para la operación pueden ser: el número de particiones de $i+k$ en partes de tamaño${}\leq k$ es igual al número de particiones en partes de tamaño${}<k$ (cuando no hay piezas igual a$~k$ ocurren en todos), más la suma del número de particiones de $i$ en partes de tamaño${}\leq k$ (con al menos una parte igual a$~k$ , $i$ a la izquierda a la partición); los dos casos son claramente complementarios y exhaustiva.

Answer 2

Un buen estudio sobre el cálculo de los enteros función de partición está aquí:http://www.math.clemson.edu/~kevja/PAPERS/ComputingPartitions-MathComp.pdf. En el capítulo $3$ los resultados de los cálculos se presentan, y la complejidad está dada por los diferentes algoritmos (los dos primeros capítulos explican qué fórmulas son útiles para el cálculo - todos los enlaces que figuran en los comentarios se incluyen, creo). Se muestra, por ejemplo, que el cálculo de $p(n)$ todos los $n ≤ N$ se puede hacer uso de $O(N^{3/2} log^2(N))$ máquina de multiplicaciones.

Answer 3

La respuesta no puede ser que lo que usted quiere. Pensé que esto podría ser una respuesta a ver a su pregunta.

Usted puede saber la relación de recurrencia $nP(n)=\sum\limits_{k=1}^n\sigma(k)P(n-k)$ donde $\sigma(k)$ es la suma de los divisores de la función. Esto puede ser fácilmente derivan de la utilización de funciones de generación de $P(n)$$\sigma(n)$. También puede utilizar Erdos del método:

$nP(n)=\sum_{m=1}^n \sum_{k=1}^{n/m}mP(n-km)=\sum_{r=1}^nP(n-r)\sum_{m\mid r}m=\sum_{r=1}^nP(n-r)\sigma(r)$.

Ahora tenga en cuenta que, usted va a tener $n\ \text{linear equations}$ con variables $x_n=P(n)$ y los coeficientes de $\sigma(n)$.

Utilizando la regla de Cramer puede encontrar $P(n)=\frac{\det A_n}{\det B_n}$. Esto puede verse fácilmente que el $B_n$ es triangular superior y determinante de la $B_n$$n!$.

Ahora, $A_n(i,1)=\sigma(i)$$A_n(j,j)=n-j+1\\A_n(i.j)=-\sigma(j-i), \text{if}\ i<j\\A_n(i,j)=0, \text{if}\ i>j$$j>1$.

Creo computing $\det A_n$ es 'muy difícil', pero bueno en el sentido de $P(n)$ depende básicamente de la factorización prima de $n$. Si usted desea jugar con el determinante usted puede encontrar algunas buenas relaciones de recurrencia, involucrando $\sigma (n)$'s.

Answer 4

Como se explicó en la última sección de estas notas, si utilizas la repetición de MacMahon (que viene del pentagonal teorema número según lo mencionado arriba), usted puede calcular $p(n)$ sólo conociendo $2 \sqrt{2n/3}$ de los términos anteriores.

http://Math.Berkeley.edu/~mhaiman/math172-spring10/partitions.pdf