Project Euler Problem 548
A gozinta chain for n is a sequence 1,a,b,dots,n where each element properly divides the next.
Solution
Answer: 12144044603581281
Let $g(n)$ denote the number of gozinta chains ending at $n$, i.e. chains
$$1=a_0 \mid a_1 \mid a_2 \mid \cdots \mid a_k=n$$
where each term properly divides the next.
The key recurrence is:
$$g(n)=\sum_{\substack{d\mid n\ d<n}} g(d), \qquad g(1)=1$$
because every chain ending at $n$ must come from a proper divisor $d$ immediately before $n$.
For example:
$$g(12)=g(1)+g(2)+g(3)+g(4)+g(6) =1+1+1+2+3=8$$
matching the statement.
A crucial observation is that $g(n)$ depends only on the prime exponent signature of $n$.
If
$$n=\prod p_i^{e_i},$$
then every divisor corresponds to choosing exponents $f_i\le e_i$, so the recurrence depends only on the exponent tuple $(e_1,e_2,\dots)$, not on the primes themselves.
Thus we memoize $G(\mathbf e)$, where $\mathbf e$ is the sorted exponent signature.
We then:
- Enumerate all exponent signatures whose smallest realization is $\le 10^{16}$.
- Compute $G(\mathbf e)$.
- Check whether:
- $G(\mathbf e)\le 10^{16}$, and
- the prime signature of $G(\mathbf e)$ is exactly $\mathbf e$.
Those are precisely the fixed points $g(n)=n$.
The resulting values are:
$$\begin{aligned} &1,\ 48,\ 1280,\ 2496,\ 28672,\ 29808,\ 454656,\ 2342912,\ 11534336,\ &57409536,\ 218103808,\ 34753216512,\ 73014444032,\ 583041810432,\ &1305670057984,\ 2624225017856,\ 404620279021568,\ &467515780104192,\ 1014849232437248,\ &4446425022726144,\ 5806013294837760 \end{aligned}$$
Their sum is:
Answer: 12144044603581281