Detailed mathematical approach

Problem Summary

For each integer \(n\) with \(2\le n\le 31\), form the double factorial

$n!!=\prod_{\substack{1\le k\le n \\ k\equiv n\pmod{2}}} k.$

The problem associates every positive integer with a canonical binary factor tree: primes are leaves, while a composite number is split at the divisor closest to \(\sqrt m\) from below and then treated recursively. If \(T(m)\) denotes that tree shape, we must find, for every \(n\), the smallest integer \(M(n)\ge 2\) with \(T(M(n))=T(n!!)\), and finally compute

$\sum_{n=2}^{31} M(n).$

The challenge is that many different integers can share the same tree, so the solution generates integers by shape class instead of scanning all integers one by one.

Mathematical Approach

The canonical decomposition is deterministic, so each positive integer belongs to exactly one shape class. The solver therefore turns the problem into a sequence-generation task: for each target shape coming from \(n!!\), list all integers with that shape in increasing order and take the first one.

Step 1: Define the canonical shape

For a prime \(p\), set

$T(p)=\bullet.$

For a composite integer \(m\), define

$\delta(m)=\max\{d:d\mid m,\ d\le \sqrt m\},\qquad a=\delta(m),\qquad b=\frac{m}{a},$

so \(a\le b\), and then set

$T(m)=\langle T(a),T(b)\rangle.$

The factor \(a\) is the largest divisor not exceeding \(\sqrt m\), so \((a,b)\) is the most balanced divisor pair of \(m\). This makes the top split unique, and recursion makes the whole tree unique.

Step 2: Reformulate the target quantity

For each \(n\in\{2,3,\dots,31\}\), let

$t_n=T(n!!),\qquad M(n)=\min\{m\ge 2:T(m)=t_n\}.$

The minimum exists because \(n!!\) itself has shape \(t_n\). In particular,

$M(n)\le n!!\le 31!!,$

so every required answer lies below a finite global bound.

For each shape \(s\), define \(S_s\) to be the increasing sequence of all integers \(m\le 31!!\) with \(T(m)=s\). Then the desired value is simply the first term of \(S_{t_n}\).

Step 3: Build each shape from its children

The leaf shape is easy:

$S_{\bullet}=(2,3,5,7,11,\dots),$

because primes are exactly the integers whose canonical tree is a single leaf.

Now suppose \(s=\langle u,v\rangle\) is an internal shape. Any integer \(m\) with \(T(m)=s\) has a canonical top split \(m=xy\) with

$T(x)=u,\qquad T(y)=v,\qquad x\le y.$

Therefore every element of \(S_s\) must occur among candidate products of the form

$x\in S_u,\qquad y\in S_v,\qquad x\le y,\qquad m=xy.$

This gives a complete candidate source for the parent shape.

Step 4: Revalidate the candidate products

Not every such product really belongs to \(S_s\). Even if \(x\) has shape \(u\) and \(y\) has shape \(v\), the product \(xy\) might admit a more balanced divisor pair than \((x,y)\), so its canonical split can move to a different tree.

The correct characterization is therefore

$S_s=\{xy:x\in S_u,\ y\in S_v,\ x\le y,\ T(xy)=s\}.$

The extra test \(T(xy)=s\) is essential: it filters out products whose top split or deeper recursive structure changes after recomputing the canonical tree.

Step 5: Merge the product streams lazily

Write

$S_u=(x_0,x_1,x_2,\dots),\qquad S_v=(y_0,y_1,y_2,\dots)$

in increasing order. For fixed \(i\), only indices \(j\) with \(y_j\ge x_i\) are allowed, so each row

$x_i y_j\qquad (j\ge j_0(i))$

is itself increasing, where \(j_0(i)\) is the first index satisfying \(y_{j_0(i)}\ge x_i\).

A priority queue can merge these rows without generating the full Cartesian product. Whenever the smallest available product is removed, the algorithm advances only that row and opens a new row only when its first possible product can compete with the current minimum. Duplicate products are skipped, and every surviving product is rechecked against the canonical-shape rule.

Worked Example: \(n=9\)

We have

$9!!=9\cdot 7\cdot 5\cdot 3\cdot 1=945.$

The largest divisor of \(945\) not exceeding \(\sqrt{945}\) is \(27\), so the top split is

$945=27\cdot 35.$

Continuing recursively,

$27=3\cdot 9,\qquad 9=3\cdot 3,\qquad 35=5\cdot 7.$

Hence

$T(945)=\langle \langle \bullet,\langle \bullet,\bullet\rangle\rangle,\langle \bullet,\bullet\rangle\rangle.$

Now look at \(72\). Its largest divisor not exceeding \(\sqrt{72}\) is \(8\), so

$72=8\cdot 9,\qquad 8=2\cdot 4,\qquad 4=2\cdot 2,\qquad 9=3\cdot 3.$

This gives exactly the same tree shape, so \(T(72)=T(945)\). The increasing sequence for that shape begins with \(72\), and the implementations confirm the checkpoint

$M(9)=72.$

How the Code Works

The C++, Python, and Java implementations first compute the target shapes \(T(n!!)\) for \(2\le n\le 31\). They then mark only the shapes needed by those targets and by their descendants, which keeps the later sequence generation focused on the relevant part of the tree space.

To evaluate \(T(m)\), the implementation uses deterministic primality testing for 64-bit integers, Pollard's rho factorization for composites, and divisor generation from the prime factorization to identify the largest divisor not exceeding \(\sqrt m\). Results are memoized so repeated shape queries become cheap.

Each needed shape owns a lazy increasing sequence. The leaf sequence emits primes in order. Every internal sequence performs a best-first merge of child products with a priority queue, enforces the order \(x\le y\), ignores duplicates, rejects products above \(31!!\), and keeps only those products whose recomputed canonical tree matches the target shape. Once the first term of every target sequence has been obtained, the program adds those minima.

Complexity Analysis

The runtime is output-sensitive: it depends on how many candidate products must be examined before the required values for each shape appear. If a needed shape \(s\) inspects \(K_s\) candidate products, its heap work is \(O(K_s\log K_s)\) in the standard best-first merge model.

The expensive subroutine is canonical-shape validation, because that requires primality testing, factorization, divisor enumeration, and recursive tree reconstruction. Memoization removes much of the repeated cost in practice, so the method is efficient for the required range, but the cleanest description is “heap-driven lazy generation with number-theoretic validation” rather than a single closed-form complexity bound. Memory usage is dominated by cached factorizations, primality results, canonical shapes, and stored prefixes of the generated sequences.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=829
2. Double factorial: Wikipedia — Double factorial
3. Pollard's rho algorithm: Wikipedia — Pollard's rho algorithm
4. Miller-Rabin primality test: Wikipedia — Miller-Rabin primality test
5. Priority queue: Wikipedia — Priority queue