Project Euler Problem 606
A gozinta chain for n is a sequence 1,a,b,dots,n where each element properly divides the next.
Solution
Answer: 158452775
The key observation is that the number of gozinta chains of $n$ depends only on the exponent pattern in its prime factorization. A gozinta chain corresponds exactly to an ordered factorization of $n$ into integers $>1$. A systematic search over exponent signatures shows that the only numbers with exactly $252$ gozinta chains are of the form
$$n=p^3q^3=(pq)^3$$
for distinct primes $p\neq q$. This characterization reproduces the given checks:
- $S(10^6)=8462952$
- $S(10^{12})=623291998881978$
exactly.
Thus for $N=10^{36}$,
$$(pq)^3 \le 10^{36} \quad\Longleftrightarrow\quad pq \le 10^{12}.$$
So we need
$$S(10^{36}) = \sum_{\substack{p<q\ pq\le 10^{12}}} (pq)^3,$$
computed modulo $10^9$ (last nine digits). Using a Lucy/Min25-style prime summatory sieve for
$$\sum_{p\le x} p^3$$
gives the final residue efficiently.
Answer: 158452775