$G(n) = 1 + \sum\limits_{ \substack{d|n\\d != 1\\d\neq n}}G(n /d)$ , ¿cómo resolver para $G(n)=n$.

Question

He recuperado la siguiente relación de recurrencia: $$G(n) = 1 + \sum\limits_{ \substack{d|n\\d \neq 1\\d\neq n}}G(n /d).$$ Me estoy preguntando cómo solucionar $G(n)=n$. Más específicamente, quiero escribir un pequeño script que hace esto, para una completa caracterización de estas soluciones no es necesario y es probable que ni siquiera factible. Aquí es la parte del código que escribí para resolver por $G(n)$:

size_t         N = 100000000;
vector<size_t> g(N, 0);

size_t G(size_t n)
{
  if (n < N && g[n] != 0)
    return g[n];
  size_t result = 1;
  for (size_t i = 2; i <= sqrt(n); ++i)
    if (n % i == 0)
      if (i * i == n)
        result += G(n / i);
      else
        result += G(n / i) + G(i);

  if (n < N)
    g[n] = result;

  return result;
}

Ahora, esto probablemente no es tan eficiente como lo puedo hacer, pero debe ser bastante bueno tan lejos como la ejecución de la recurrencia de la relación en su forma actual va. Sin embargo, voy a necesitar soluciones para grandes $n$, donde este enfoque no tiene ninguna esperanza para calcular más. Necesito encontrar una nueva vía de ataque, o nuevas ideas que puede utilizar para podar un montón de posibilidades de $n$.

He impreso las primeras soluciones a $G(n)$ e incluyó su primer factorizations:

48        is factorized as  2 2 2 2 3 
1280      is factorized as  2 2 2 2 2 2 2 2 5 
2496      is factorized as  2 2 2 2 2 2 3 13 
28672     is factorized as  2 2 2 2 2 2 2 2 2 2 2 2 7 
29808     is factorized as  2 2 2 2 3 3 3 3 23 
454656    is factorized as  2 2 2 2 2 2 2 2 2 2 2 2 3 37 
2342912   is factorized as  2 2 2 2 2 2 2 2 2 2 2 2 2 2 11 13 
11534336  is factorized as  2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 11 

He comprobado estos números para buscar un patrón, tengo la sospecha de que los datos del primer factorizations debe dar una pista en cuanto a qué números son propensos a satisfacer la deseada igualdad o tal vez que nunca podrá satisfacer dicha igualdad. A partir de los resultados que presentan el Toletero conjetura: "Por $G(n)$ a la igualdad de $n$, $n$ necesita tener un montón de $2$'s en su descomposición en factores primos".

Aparte de la aparente alta cantidad de $2$'s en el factorizations realmente no los he aprendido mucho de estos resultados, lamentablemente.

¿Alguien sabe de una manera que nos puede hacer la búsqueda de $G(n)=n$ más manejable? Gracias de antemano!

EDIT: he encontrado la siguiente relación:

$$G(2n) = 1+ \sum\limits_{\substack{d|2n\\ d\neq 1 \\ d \neq 2n}}G\left(\frac{2n}{d}\right) = 1 + \sum\limits_{\substack{d|n\\ d\neq 1 \\ d \neq n}} \left(G\left(\frac{2n}{d}\right) + G\left(\frac{n}{d}\right)\right) + G(2).$$

This implies that $G(2n) = 2 + G(n) + \sum\limits_{\substack{d|n\\ d\ \ neq 1 \\ d \ \ neq n}} G\left(\frac{2n}{d}\right)$.

Edit2: As noted by Sil, the function depends only on the prime exponents $(e_1,\ldots, e_k)$ of $$ n. Entonces $$G(n) = G((e_1,\ldots, e_k)) = 1+ \sum\limits_{\mathbf{0} < \mathbf{u} < \mathbf{e}} G((e_1 - u_1, \ldots, e_k - u_k)).$$ Aquí $\mathbf{0} < \mathbf{u} < \mathbf{e}$ es destinado a la media de todos los $k$-tuplas $(u_1, \ldots, u_k)$ tal que $u_i \neq 0$ algunos $i$ $u_j \neq e_j$ algunos $j$.

Answer 1

Esta secuencia es A002033 en la OEIS. Por la razón que sea más de lo que está abajo no está en esa entrada.

Suponiendo que $G(1) = 1$ la recurrencia de la relación puede ser reescrita

$$\sum_{d | n} G(d) = \begin{cases} 2 G(n) &\mbox{if } n \ge 2 \\ 1 &\mbox{if } n = 1 \end{cases}.$$

Esto significa que el lado izquierdo es una de Dirichlet de convolución. Tomando de Dirichlet de la serie, si $F(s) = \sum_{n \ge 1} \frac{G(n)}{n^s}$ entonces tenemos que

$$F(s) \zeta(s) = 2 F(s) - 1$$

que da $F(s) (2 - \zeta(s)) = 1$, por lo tanto

$$F(s) = \frac{1}{2 - \zeta(s)} = \frac{1}{2} \sum_{k \ge 0} \left( \frac{\zeta(s)}{2} \right)^k.$$

Ahora, $\zeta(s)^k$ es la de Dirichlet de la serie de la función $d_k(n)$, el número de maneras de escribir $n$ como el producto de la $k$ enteros positivos. Esto le da

$$G(n) = \frac{1}{2} \sum_{k \ge 0} \frac{d_k(n)}{2^k}.$$

Algo más explícito, si $n = \prod_i p_i^{e_i}$ es la factorización prima de $n$, luego

$$d_k(n) = \prod_i {e_i + k - 1 \choose k-1}$$

y por lo tanto

$$\boxed{ G(n) = \frac{1}{2} \sum_{k \ge 0} \frac{1}{2^k} \prod_i {e_i + k - 1 \choose k-1} }.$$

Así se recupera el Sil de la demanda en los comentarios que $G$ sólo depende de los exponentes en la factorización prima de $n$. Para cualquier particular $n$ la expresión de $d_k(n)$ es un polinomio en a $k$ grado $\sum_i e_i$, por lo que una forma cerrada para la anterior suma está disponible, básicamente mediante el aprovechamiento de la identidad

$$\frac{1}{(1 - x)^{e+1}} = \sum_{k \ge 0} {e + k \choose k} x^k$$

y sustituyendo $x = \frac{1}{2}$ para obtener

$$2^{e+1} = \sum_{k \ge 0} \frac{1}{2^k} {e + k \choose k}.$$

Este resultado ya es suficiente para calcular los $G(n)$ en el primer caso power y se da

$$G(p^e) = 2^{e - 1}$$

como también se indicó por Sil en los comentarios.

En general, el problema se reduce a la expresión de las $f(k) = \prod_i {k + e_i -1 \choose e_i}$ como una suma de polinomios de la forma ${k + e \choose e}$. Hay un sencillo algoritmo para hacer esto para fijo $e_i$ mediante el cálculo de diferencias finitas de la $f(k)$ como sigue. Definir el operador diferencia hacia atrás

$$(\Delta f)(k) = f(k) - f(k-1).$$

Observar que $\Delta {k + e \choose e} = {k + e-1 \choose e-1}$. Supongamos que $f(k) = \sum_{e=0}^d c_e {k + e \choose e}$ donde $d$ es el grado de $f$ como un polinomio en $k$. Luego tomar hacia atrás diferencias $r$ veces da

$$(\Delta^r f)(k) = \sum_{e=r}^d c_e {k + e - r \choose e - r}.$$

Sustituyendo $k = 0$ da

$$(\Delta^r f)(0) = c_r + c_{r+1} + \dots + c_d$$

a partir de la cual se deduce que

$$c_e = (\Delta^{e+1} f)(0) - (\Delta^e f)(0)$$

lo que da

$$f(k) = \sum_{e=0}^d \left( (\Delta^{e+1} f)(0) - (\Delta^e f)(0) \right) {k+e \choose e}$$

y por lo tanto

$$\sum_{k \ge 0} \frac{f(k)}{2^k} = \sum_{e=0}^d \left( (\Delta^{e+1} f)(0) - (\Delta^e f)(0) \right) 2^{e+1}.$$

---

Un enfoque alternativo es el siguiente. También podemos escribir la Dirichlet, como la serie de

$$F(s) = \frac{1}{1 - (\zeta(s) - 1)} = \sum_{k \ge 0} (\zeta(s) - 1)^k.$$

$(\zeta(s) - 1)^k$ es la de Dirichlet de la serie para una función que voy a llamar a $d_k^{+}(n)$, el número de maneras de escribir $n$ como el producto de la $k$ enteros positivos cada uno de los cuales es mayor que $1$. Esto le da

$$\boxed{ G(n) = \sum_{k \ge 0} d_k^{+}(n) }.$$

que entre otras cosas es 1) una suma finita ($d_k^{+}(n) = 0$ tan pronto como $k$ es mayor que la suma de $\sum_i e_i$ de los exponentes en la factorización prima de $n$) y 2) claramente un entero. Esto le da a ese $G(n)$ es el número de maneras de escribir $n$ como un producto de cualquier número de enteros positivos mayores que $1$, o, equivalentemente, el número de "Gozinta cadenas" de $n$ como en el Proyecto de Euler 548, que es probablemente donde esta pregunta viene de.

Podemos escribir $d_k^{+}(n)$ en términos de $d_k(n)$ mediante la inclusión-exclusión: hacerlo más o menos de conducir a la primera fórmula.

Esta expresión también es suficiente para concluir que el $G(n)$ sólo depende de los exponentes en la factorización prima de $n$, y de hecho se sugiere las siguientes alternativas de generación de expresión de función para $G$. Escribir

$$G \left( \prod_{i=1}^m p_i^{e_i} \right) = g(e_1, e_2, \dots e_m).$$

A continuación, $g$ ha multivariante de generación de función

$$\sum_{e_i \ge 0} g(e_1, e_2, \dots e_m) x_1^{e_1} x_2^{e_2} \dots x_m^{e_m} = \frac{1}{2 - (\sum_{e_i \ge 0} x_1^{e_1} x_2^{e_2} \dots x_m^{e_m})} = \frac{1}{2 - \prod_{i=1}^m \frac{1}{1 - x_i}}$$

así que este multivariante de la generación de la función es aún racional: puede ser reescrita

$$\displaystyle \frac{\prod_{i=1}^m (1 - x_i)}{2 \prod_{i=1}^m (1 - x_i) - 1}.$$

Escrito de este modo los cálculos para los valores pequeños de a $m$ son más transparentes. Para $m = 1$ tenemos

$$\sum_{e \ge 0} g(e) x^e = \frac{1 - x}{1 - 2x}$$

la recuperación de $g(e) = 2^{e-1}$, y para $m = 2$ tenemos

$$\sum_{e_1, e_2 \ge 0} g(e_1, e_2) x_1^{e_1} x_2^{e_2} = \frac{1}{2 - \frac{1}{(1 - x_1)(1 - x_2)}} = \frac{(1 - x_1)(1 - x_2)}{1 - 2x_1 - 2x_2 + 2x_1 x_2}$$

a partir de la cual tanto los cálculos de $g(1, e)$ $g(e, e)$ registrado en el Sil de la wiki de la comunidad de respuesta puede ser recuperado. Para tener una idea de lo que se puede hacer aquí, vamos por un momento a considerar la generación de la función anterior como la generación de la función en $x_1$, con coeficientes que son funciones de generación en $x_2$. Esto le da

$$\frac{1 - x_1}{2 - 2x_1 - \frac{1}{1 - x_2}} = \frac{1 - x_1}{\frac{1 - 2x_2}{1 - x_2} - 2x_1}.$$

Factorizando $\frac{1 - 2x_2}{1 - x_2}$ desde el denominador da

$$\frac{1 - x_2}{1 - 2x_2} \frac{1 - x_1}{1 - \frac{2 - 2x_2}{1 - 2x_2} x_1} = (1 - x_1) \sum_{k \ge 0} 2^k \frac{(1 - x_2)^{k+1}}{(1 - 2x_2)^{k+1}} x_1^k.$$

Extraer el coeficiente de $k$ a continuación se da, por $k \ge 1$,

$$\sum_{e \ge 0} g(k, e) x^e = 2^k \frac{(1 - x)^{k+1}}{(1 - 2x)^{k+1}} - 2^{k-1} \frac{(1 - x)^k}{(1 - 2x)^k}$$

o, simplificando un poco,

$$\boxed{ \sum_{e \ge 0} g(k, e) x^e = 2^{k-1} \frac{(1 - x)^k}{(1 - 2x)^{k+1}} }.$$

Para $k = 1$ se recupera $g(1, e) = (e + 2) 2^{e-1}$ como en el Sil de la respuesta. Para general $k$ esto da

$$\boxed{ g(k, e) = 2^{k-1} \sum_{i=0}^k (-1)^i 2^{e-i} {k \choose i} {k + e - i \choose k} }.$$

Answer 2

Esto no es una respuesta, en lugar de resumen de observaciones que le otherways polute los comentarios.

• Para $n>1$ podemos escribir $G(n)=\sum\limits_{ \substack{d|n\\d<n}}G(d)$
• $G(n)$ depende en primer exponentes de la $n$ (en otras palabras $G(p_1^{e_1}p_2^{e_2}\dots p_k^{e_k}) = f(e_1, e_2, \dots, e_k)$ algunos $f$)
• $G(p^k)=2^{k-1}$ primer $p$
• $G(p\cdot q^n)=(n+2) 2^{n-1}$ para los números primos $p,q$
• $G(p^n q^n)$ es https://oeis.org/A052141 - Número de rutas de $(0,0)$ $(n,n)$que siempre se mueven más cerca de $(n,n)$ (y no pasan a $(n,n)$ y la marcha atrás).