$G(n) = 1 + \sum\limits_{ \substack{d|n\\d != 1\\d\neq n}}G(n /d)$, how to solve for $G(n)=n$.

Question

I have recovered the following recurrence relation: $$G(n) = 1 + \sum\limits_{ \substack{d|n\\d \neq 1\\d\neq n}}G(n /d).$$ I am wondering how to solve $G(n)=n$. More specifically I want to write a little script that does this, so a full characterizations of these solutions is not necessary and likely not even doable. Here is part of the code that I wrote to solve for $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;
}

Now this is probably not as efficient as I can make it but it should be quite alright as far as implementing the recurrence relation in its current form goes. However, I will be needing solutions for large $n$, where this approach has no hope to compute anymore. I need to find a new avenue of attack, or new insights that can used to prune away a bunch of possibilities of $n$.

I have printed the first few solutions to $G(n)$ and included their prime 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 

I checked these numbers to look for a pattern, I suspect that the particulars of the prime factorizations should give a hint as to which numbers are likely to satisfy the desired equality or maybe which ones can never satisfy such equality. From the results I pose the Slugger conjecture: "For $G(n)$ to equal $n$, $n$ needs to have a bunch of $2$'s in its prime factorization".

Other than the apparent high amount of $2$'s in the factorizations I have not really learned much from these results unfortunately.

Does anyone know of a way that we can make the search for $G(n)=n$ more tractable? Thanks in advance!

EDIT: I found the following relation:

$$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$. Then $$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)).$$ Here $\mathbf{0} < \mathbf{u} < \mathbf{e}$ is meant to mean all $k$-tuples $(u_1, \ldots, u_k)$ such that $u_i \neq 0$ for some $i$ and $u_j \neq e_j$ for some $j$.

Answer 1

This sequence is A002033 in the OEIS. For whatever reason most of what is below is not in that entry.

Assuming that $G(1) = 1$ the recurrence relation can be rewritten

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

This means the LHS is a Dirichlet convolution. Taking Dirichlet series, if $F(s) = \sum_{n \ge 1} \frac{G(n)}{n^s}$ then we get that

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

which gives $F(s) (2 - \zeta(s)) = 1$, hence

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

Now, $\zeta(s)^k$ is the Dirichlet series of the function $d_k(n)$, the number of ways to write $n$ as the product of $k$ positive integers. This gives

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

Somewhat more explicitly, if $n = \prod_i p_i^{e_i}$ is the prime factorization of $n$, then

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

and hence

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

This recovers Sil's claim in the comments that $G$ only depends on the exponents in the prime factorization of $n$. For any particular $n$ the expression $d_k(n)$ is a polynomial in $k$ of degree $\sum_i e_i$ and so a closed form for the above sum is available, basically by leveraging the identity

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

and substituting $x = \frac{1}{2}$ to get

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

This result is already enough to compute $G(n)$ in the prime power case and it gives

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

as also noted by Sil in the comments.

In general the problem reduces to expressing $f(k) = \prod_i {k + e_i -1 \choose e_i}$ as a sum of polynomials of the form ${k + e \choose e}$. There is a straightforward algorithm for doing this for fixed $e_i$ by computing finite differences of the $f(k)$ as follows. Define the backwards difference operator

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

Observe that $\Delta {k + e \choose e} = {k + e-1 \choose e-1}$. Suppose that $f(k) = \sum_{e=0}^d c_e {k + e \choose e}$ where $d$ is the degree of $f$ as a polynomial in $k$. Then taking backwards differences $r$ times gives

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

Substituting $k = 0$ gives

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

from which it follows that

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

which gives

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

and hence

$$\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}.$$

---

An alternate approach is the following. We can also write the Dirichlet series as

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

$(\zeta(s) - 1)^k$ is the Dirichlet series for a function I'll call $d_k^{+}(n)$, the number of ways to write $n$ as the product of $k$ positive integers each of which is greater than $1$. This gives

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

which among other things is 1) a finite sum ($d_k^{+}(n) = 0$ as soon as $k$ is greater than the sum $\sum_i e_i$ of the exponents in the prime factorization of $n$) and 2) clearly an integer. This gives that $G(n)$ is the number of ways to write $n$ as a product of any number of positive integers greater than $1$, or equivalently the number of "Gozinta chains" of $n$ as in Project Euler 548, which is presumably where this question comes from.

We can write $d_k^{+}(n)$ in terms of $d_k(n)$ using inclusion-exclusion: doing so should more or less lead to the first formula.

This expression is also enough to conclude that $G(n)$ only depends on the exponents in the prime factorization of $n$, and actually it suggests the following alternate generating function expression for $G$. Write

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

Then $g$ has multivariate generating function

$$\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}}$$

so this multivariate generating function is even rational: it can be rewritten

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

Written this way the calculations for small values of $m$ are more transparent. For $m = 1$ we get

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

recovering $g(e) = 2^{e-1}$, and for $m = 2$ we get

$$\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}$$

from which both the computations of $g(1, e)$ and $g(e, e)$ recorded in Sil's community wiki answer can be recovered. To get a sense of what can be done here, let's for a moment consider the generating function above as a generating function in $x_1$ only, with coefficients which are generating functions in $x_2$. This gives

$$\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}.$$

Factoring out $\frac{1 - 2x_2}{1 - x_2}$ from the denominator gives

$$\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.$$

Extracting the coefficient of $k$ then gives, for $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}$$

or, simplifying slightly,

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

For $k = 1$ this recovers $g(1, e) = (e + 2) 2^{e-1}$ as in Sil's answer. For general $k$ this gives

$$\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

This is not intended as an answer, rather summary of observations that would otherways polute the comments.

• For $n>1$ we can write $G(n)=\sum\limits_{ \substack{d|n\\d<n}}G(d)$
• $G(n)$ depends on prime exponents of $n$ (in other words $G(p_1^{e_1}p_2^{e_2}\dots p_k^{e_k}) = f(e_1, e_2, \dots, e_k)$ for some $f$)
• $G(p^k)=2^{k-1}$ for prime $p$
• $G(p\cdot q^n)=(n+2) 2^{n-1}$ for primes $p,q$
• $G(p^n q^n)$ is https://oeis.org/A052141 - Number of paths from $(0,0)$ to $(n,n)$ that always move closer to $(n,n)$ (and do not pass $(n,n)$ and backtrack).