Detailed mathematical approach

Problem Summary

A gozinta chain for \(n\) is a sequence

$1=a_0\lt a_1\lt\cdots\lt a_t=n,$

where each term divides the next one. Let \(g(n)\) be the number of such chains, and let

$S(N)=\sum_{\substack{k\le N\\ g(k)=252}} k.$

The task is to find the last nine digits of \(S(10^{36})\). A direct scan up to \(10^{36}\) is hopeless, so the solution first characterizes exactly which prime-exponent patterns produce 252 chains, then sums those integers in a much more structured way.

Mathematical Approach

Write

$n=\prod_{j=1}^{r} p_j^{e_j},\qquad \Omega=e_1+\cdots+e_r.$

The crucial observation is that the number of gozinta chains depends only on the exponent pattern \((e_1,\dots,e_r)\), not on the actual primes \(p_j\).

Step 1: Convert Divisors into Exponent Vectors

Every divisor of \(n\) can be written uniquely as

$d=\prod_{j=1}^{r} p_j^{b_j},\qquad 0\le b_j\le e_j.$

So divisors correspond to lattice points \(b=(b_1,\dots,b_r)\) inside the box \([0,e_1]\times\cdots\times[0,e_r]\). A gozinta chain is therefore a strictly increasing coordinatewise chain

$ (0,\dots,0)=v^{(0)}\lt v^{(1)}\lt\cdots\lt v^{(k)}=(e_1,\dots,e_r), $

where at least one coordinate increases at every step. Since this description uses only the exponents, the chain count is completely determined by the exponent pattern.

Step 2: Count Chains with Exactly \(k\) Steps

Fix a chain length \(k\), meaning \(k\) strict divisibility moves from \(1\) to \(n\). Let the increment in coordinate \(j\) during step \(t\) be \(\delta_{j,t}\). Then

$\delta_{j,t}\ge 0,\qquad \sum_{t=1}^{k}\delta_{j,t}=e_j.$

For one fixed prime \(p_j\), the number of weak compositions of \(e_j\) into \(k\) parts is

$\binom{e_j+k-1}{k-1}.$

Multiplying over all prime coordinates gives the number of increment tables if zero steps are temporarily allowed:

$T_k(e_1,\dots,e_r)=\prod_{j=1}^{r}\binom{e_j+k-1}{k-1}.$

However, \(T_k\) still counts forbidden cases where some step has \(\delta_{1,t}=\cdots=\delta_{r,t}=0\), which would repeat a divisor instead of moving to a strictly larger one.

Step 3: Enforce Strictness by Inclusion-Exclusion

To obtain genuine gozinta chains, every step must increase at least one coordinate. If exactly \(i\) of the \(k\) step positions are declared active, the same stars-and-bars argument gives

$\prod_{j=1}^{r}\binom{e_j+i-1}{i-1}$

possibilities. Choosing the active positions and applying inclusion-exclusion yields

$ F_k(e_1,\dots,e_r)=\sum_{i=1}^{k}(-1)^{k-i}\binom{k}{i}\prod_{j=1}^{r}\binom{e_j+i-1}{i-1}. $

This is the number of chains with exactly \(k\) strict moves. Because each move raises the total exponent sum by at least \(1\), we must have \(1\le k\le \Omega\). Therefore

$ G(e_1,\dots,e_r)=\sum_{k=1}^{\Omega} F_k(e_1,\dots,e_r) $

is the total number of gozinta chains for any integer having exponent pattern \((e_1,\dots,e_r)\).

Step 4: Identify the Unique Pattern Giving 252

The implementations enumerate exponent partitions and evaluate the exact formula above. The outcome is strikingly simple: the only pattern with

$G(e_1,\dots,e_r)=252$

is

$ (e_1,\dots,e_r)=(3,3). $

Hence every qualifying integer has the form

$ n=p^3q^3=(pq)^3,\qquad p\lt q \text{ prime}. $

The primes must be distinct: \(p^6\) has pattern \((6)\), not \((3,3)\), so it does not belong to the target set.

Step 5: Worked Example for the Pattern \((3,3)\)

Take \(n=2^3\cdot 3^3=216\). Here \(\Omega=6\), and for a fixed step count \(k\) we get

$ T_k=\binom{3+k-1}{k-1}^2=\binom{k+2}{2}^2. $

Applying inclusion-exclusion gives

$ F_k=\sum_{i=1}^{k}(-1)^{k-i}\binom{k}{i}\binom{i+2}{2}^2. $

The values are

$ \begin{aligned} F_1&=1,\\ F_2&=14,\\ F_3&=55,\\ F_4&=92,\\ F_5&=70,\\ F_6&=20. \end{aligned} $

Summing them shows

$ 1+14+55+92+70+20=252. $

So \(216\) really has exactly 252 gozinta chains, and by the previous step every other qualifying number is obtained by replacing \(2\) and \(3\) with any distinct prime pair.

Step 6: Reduce \(S(N)\) to a Sum over Prime Pairs

Let

$ X=\left\lfloor N^{1/3}\right\rfloor. $

Then \((pq)^3\le N\) is equivalent to \(pq\le X\), so

$ S(N)=\sum_{\substack{p\lt q\\ pq\le X}} (pq)^3. $

For the actual problem, \(N=10^{36}\), hence \(X=10^{12}\).

Now define the prime-cube prefix sum

$ P_3(y)=\sum_{\substack{q\le y\\ q\text{ prime}}} q^3. $

Grouping terms by the smaller prime \(p\) gives

$ S(N)=\sum_{p\le \sqrt{X}} p^3\left(P_3\!\left(\left\lfloor\frac{X}{p}\right\rfloor\right)-P_3(p)\right). $

The subtraction by \(P_3(p)\) enforces \(q>p\), so every unordered prime pair is counted exactly once.

Step 7: Compute \(P_3\) with a Quotient-Based Prime Summatory Sieve

A full sieve up to \(10^{12}\) would be too large, so the implementation works only with the distinct quotient values

$ v=\left\lfloor\frac{X}{i}\right\rfloor, $

of which there are only \(O(\sqrt{X})\). For each such \(v\), it starts from the ordinary cube sum

$ \sum_{m=2}^{v} m^3=\left(\frac{v(v+1)}{2}\right)^2-1. $

Then it performs Min_25-style prime corrections. When sieving by a prime \(p\), every state with \(v\ge p^2\) is updated by subtracting the contribution of numbers whose smallest remaining prime factor is \(p\):

$ H(v)\leftarrow H(v)-p^3\left(H\!\left(\left\lfloor\frac{v}{p}\right\rfloor\right)-\sum_{q<p} q^3\right). $

After all primes up to \(\sqrt{X}\) have been processed, \(H(v)\) equals \(P_3(v)\). Because only the last nine digits are needed, every arithmetic operation is reduced modulo \(10^9\).

How the Code Works

The C++, Python, and Java implementations follow the same mathematical reduction. They first verify the structural claim by evaluating the exact chain-count formula on exponent partitions and confirming that \((3,3)\) is the only pattern with 252 chains.

Next they set \(X=10^{12}\), generate all primes up to \(\sqrt{X}\), and build the table of distinct quotient values \(\lfloor X/i\rfloor\). Each table entry is initialized with the closed form for \(\sum m^3\), then corrected prime by prime until only prime cubes remain in the summatory table.

Finally they loop over the smaller prime \(p\), query the prime-cube prefix sum at \(\lfloor X/p\rfloor\) and at \(p\), and accumulate

$ p^3\left(P_3\!\left(\left\lfloor\frac{X}{p}\right\rfloor\right)-P_3(p)\right) $

modulo \(10^9\). Before attacking \(10^{36}\), the implementation also checks smaller validated cases such as \(S(10^6)=8462952\) and \(S(10^{12})=623291998881978\).

Complexity Analysis

The exponent-pattern verification is tiny compared with the main computation. For the main solver, sieving primes up to \(\sqrt{X}\) costs \(O(\sqrt{X}\log\log X)\) time and \(O(\sqrt{X})\) memory. The quotient table contains only \(O(\sqrt{X})\) states. During the prime-correction phase, a prime \(p\) touches only those states with \(v\ge p^2\), so the number of table updates is

$ \sum_{p\le \sqrt{X}} O\!\left(\min\!\left(\sqrt{X},\frac{X}{p^2}\right)\right), $

which is sublinear in \(X\) and follows the usual complexity profile of Min_25-style prime-summatory methods. The final accumulation over primes up to \(\sqrt{X}\) is linear in \(\pi(\sqrt{X})\). Overall, the implementation uses \(O(\sqrt{X})\) memory and practical sublinear time for \(X=10^{12}\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=606
2. Partially ordered sets and chains: Wikipedia - Partially ordered set
3. Stars and bars for weak compositions: Wikipedia - Stars and bars
4. Inclusion-exclusion principle: Wikipedia - Inclusion-exclusion principle
5. Prime sieving background: Wikipedia - Sieve of Eratosthenes
6. Prime-counting and related summatory methods: Wikipedia - Prime-counting function