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.
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.
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.
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}\).
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.
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.
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.
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.$$
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.
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.
Für jede ganze Zahl \(n\) mit \(2\le n\le 31\) wird zunächst das Doppelfakultät
$$n!!=\prod_{\substack{1\le k\le n \\ k\equiv n\pmod{2}}} k$$
gebildet. Jedem positiven Integer wird dann ein kanonischer binärer Faktorisierungsbaum zugeordnet: Primzahlen sind Blätter, und eine zusammengesetzte Zahl wird an dem Teiler gespalten, der von unten am nächsten bei \(\sqrt m\) liegt. Bezeichnet \(T(m)\) diese Baumform, so suchen wir für jedes \(n\) die kleinste Zahl \(M(n)\ge 2\) mit \(T(M(n))=T(n!!)\) und berechnen schließlich
$$\sum_{n=2}^{31} M(n).$$
Da viele verschiedene Zahlen dieselbe Form besitzen können, arbeitet die Lösung nicht mit roher Vollsuche, sondern erzeugt Zahlen formweise.
Die kanonische Zerlegung ist eindeutig. Deshalb gehört jede positive Zahl genau zu einer Formklasse, und das Problem reduziert sich darauf, für jede Zielform die zugehörigen Zahlen in aufsteigender Reihenfolge zu erzeugen.
Für eine Primzahl \(p\) setzen wir
$$T(p)=\bullet.$$
Für eine zusammengesetzte Zahl \(m\) definieren wir
$$\delta(m)=\max\{d:d\mid m,\ d\le \sqrt m\},\qquad a=\delta(m),\qquad b=\frac{m}{a},$$
wobei automatisch \(a\le b\) gilt, und dann
$$T(m)=\langle T(a),T(b)\rangle.$$
Der Faktor \(a\) ist also der größte Teiler von \(m\), der \(\sqrt m\) nicht überschreitet. Damit ist das ausgewogenste Teilerpaar eindeutig festgelegt, und durch Rekursion ist die gesamte Baumform eindeutig.
Für \(n=2,3,\dots,31\) definieren wir
$$t_n=T(n!!),\qquad M(n)=\min\{m\ge 2:T(m)=t_n\}.$$
Dieses Minimum existiert, weil \(n!!\) selbst bereits die Form \(t_n\) besitzt. Insbesondere gilt
$$M(n)\le n!!\le 31!!.$$
Damit gibt es eine globale endliche Obergrenze für alle gesuchten Minimalwerte.
Für jede Form \(s\) betrachten wir die aufsteigende Folge aller Zahlen \(m\le 31!!\) mit \(T(m)=s\). Der gesuchte Wert \(M(n)\) ist dann einfach das erste Element der Folge zur Form \(t_n\).
Für die Blattform ist die Folge unmittelbar klar:
$$S_{\bullet}=(2,3,5,7,11,\dots),$$
denn genau die Primzahlen besitzen einen Baum mit nur einem Blatt.
Sei nun \(s=\langle u,v\rangle\) eine innere Form. Hat eine Zahl \(m\) die Form \(s\), dann zerfällt sie an der obersten kanonischen Stelle als \(m=xy\) mit
$$T(x)=u,\qquad T(y)=v,\qquad x\le y.$$
Also muss jedes Element der Folge \(S_s\) unter Produkten der Form
$$x\in S_u,\qquad y\in S_v,\qquad x\le y,\qquad m=xy$$
auftreten.
Nicht jedes Produkt \(xy\) aus den Kindfolgen gehört tatsächlich zu \(S_s\). Nach der Multiplikation kann es sein, dass \(xy\) ein noch ausgewogeneres Teilerpaar besitzt als \((x,y)\). Dann ändert sich die kanonische Zerlegung, und das Produkt landet in einer anderen Formklasse.
Deshalb lautet die korrekte Beschreibung
$$S_s=\{xy:x\in S_u,\ y\in S_v,\ x\le y,\ T(xy)=s\}.$$
Die Bedingung \(T(xy)=s\) ist der entscheidende Filter, der aus einer bloßen Kandidatenmenge eine exakte mathematische Beschreibung macht.
Schreiben wir
$$S_u=(x_0,x_1,x_2,\dots),\qquad S_v=(y_0,y_1,y_2,\dots)$$
in aufsteigender Reihenfolge. Für festes \(i\) sind nur diejenigen \(j\) erlaubt, für die \(y_j\ge x_i\) gilt. Damit ist jede Zeile
$$x_i y_j\qquad (j\ge j_0(i))$$
eine sortierte Folge, wobei \(j_0(i)\) der erste zulässige Index ist.
Eine Prioritätswarteschlange kann diese Zeilen faul mergen: Es wird immer das kleinste aktuell verfügbare Produkt entnommen, danach nur die betreffende Zeile fortgesetzt. Neue Zeilen werden erst geöffnet, wenn ihr erstes mögliches Produkt mit dem aktuellen Minimum konkurrieren kann. Doppelte Werte werden übersprungen, und jedes Produkt wird nochmals auf seine kanonische Form geprüft.
Es gilt
$$9!!=9\cdot 7\cdot 5\cdot 3\cdot 1=945.$$
Der größte Teiler von \(945\), der \(\sqrt{945}\) nicht überschreitet, ist \(27\). Also lautet die oberste Zerlegung
$$945=27\cdot 35.$$
Rekursiv weiter ergibt sich
$$27=3\cdot 9,\qquad 9=3\cdot 3,\qquad 35=5\cdot 7.$$
Somit ist
$$T(945)=\langle \langle \bullet,\langle \bullet,\bullet\rangle\rangle,\langle \bullet,\bullet\rangle\rangle.$$
Betrachten wir nun \(72\). Hier ist der größte Teiler unterhalb von \(\sqrt{72}\) gleich \(8\), also
$$72=8\cdot 9,\qquad 8=2\cdot 4,\qquad 4=2\cdot 2,\qquad 9=3\cdot 3.$$
Damit besitzt \(72\) exakt dieselbe Form. Die erzeugte Folge für diese Form beginnt mit \(72\), und die Implementierungen bestätigen daher den Prüfwert
$$M(9)=72.$$
Die C++-, Python- und Java-Implementierungen berechnen zuerst die Zielformen \(T(n!!)\) für \(2\le n\le 31\). Danach markieren sie nur diejenigen Formen, die tatsächlich von diesen Zielen und ihren Unterformen benötigt werden.
Zur Auswertung von \(T(m)\) verwendet die Implementierung einen deterministischen Primzahltest für 64-Bit-Zahlen, Pollard-Rho zur Faktorisierung zusammengesetzter Zahlen sowie eine Divisor-Erzeugung aus der Primfaktorzerlegung, um den größten Teiler \(\le \sqrt m\) zu finden. Ergebnisse werden zwischengespeichert, damit wiederholte Formabfragen schnell werden.
Jede benötigte Form besitzt eine faule aufsteigende Folge. Die Blattfolge liefert Primzahlen. Jede innere Folge führt die Produktkandidaten der Kindfolgen mit einer Prioritätswarteschlange zusammen, erzwingt \(x\le y\), verwirft Dubletten, ignoriert Produkte oberhalb von \(31!!\) und akzeptiert nur Kandidaten, deren neu berechnete kanonische Form mit der Zielform übereinstimmt. Sobald für jede Zielform das erste Element vorliegt, werden diese Minimalwerte addiert.
Die Laufzeit ist ausgabeabhängig: Entscheidend ist, wie viele Produktkandidaten für jede benötigte Form geprüft werden müssen, bevor die gesuchten Minimalwerte erscheinen. Wenn für eine Form \(s\) insgesamt \(K_s\) Kandidaten betrachtet werden, kostet die Heap-Verwaltung im üblichen Best-First-Merge-Modell \(O(K_s\log K_s)\).
Der teure Teil ist die Validierung der kanonischen Form, denn dafür braucht man Primzahltests, Faktorisierung, Divisor-Erzeugung und rekursive Baumrekonstruktion. Durch Memoisierung entfällt in der Praxis viel Wiederholungsarbeit. Deshalb ist die Methode für den geforderten Bereich schnell genug, auch wenn sich die Gesamtkosten am besten als faule Heap-Erzeugung mit zahlentheoretischer Validierung beschreiben lassen. Der Speicherbedarf wird vor allem von zwischengespeicherten Faktorisierungen, Primzahlresultaten, Formen und bereits erzeugten Folgenpräfixen bestimmt.
Her \(n\) için, \(2\le n\le 31\) aralığında önce
$$n!!=\prod_{\substack{1\le k\le n \\ k\equiv n\pmod{2}}} k$$
çift faktöriyeli oluşturulur. Ardından her pozitif tam sayıya kanonik bir ikili çarpan ağacı atanır: asallar yapraktır; bileşik bir sayı ise \(\sqrt m\)'yi aşmayan en büyük bölen üzerinden iki parçaya ayrılır ve aynı kural özyinelemeli olarak sürdürülür. Bu ağacı \(T(m)\) ile gösterirsek, her \(n\) için \(T(M(n))=T(n!!)\) şartını sağlayan en küçük \(M(n)\ge 2\) bulunur ve sonunda
$$\sum_{n=2}^{31} M(n)$$
hesaplanır. Zorluk, aynı ağaca sahip çok sayıda farklı tam sayı bulunabilmesidir; bu yüzden çözüm tek tek sayıları taramaz, şekil sınıflarını üretir.
Kanonik ayrışım deterministiktir; dolayısıyla her pozitif tam sayı tam olarak bir şekil sınıfına aittir. Problem böylece, \(n!!\) değerlerinden gelen hedef şekiller için artan sayı dizileri üretme problemine dönüşür.
Bir asal \(p\) için
$$T(p)=\bullet$$
olsun. Bileşik bir \(m\) için
$$\delta(m)=\max\{d:d\mid m,\ d\le \sqrt m\},\qquad a=\delta(m),\qquad b=\frac{m}{a}$$
tanımlanır ve sonra
$$T(m)=\langle T(a),T(b)\rangle$$
alınır. Burada \(a\), \(\sqrt m\)'yi aşmayan en büyük bölen olduğu için \((a,b)\), \(m\)'nin en dengeli bölen çiftidir. Böylece üst ayrım ve dolayısıyla tüm ağaç tektir.
\(n=2,3,\dots,31\) için
$$t_n=T(n!!),\qquad M(n)=\min\{m\ge 2:T(m)=t_n\}$$
tanımını yapalım. Minimum vardır, çünkü \(n!!\) zaten \(t_n\) şekline sahiptir. Özellikle
$$M(n)\le n!!\le 31!!$$
olur; yani tüm cevaplar sonlu bir üst sınırın altındadır.
Her şekil \(s\) için, \(T(m)=s\) şartını sağlayan ve \(31!!\)'yi aşmayan sayıların artan dizisini \(S_s\) ile gösterelim. O zaman \(M(n)\), \(S_{t_n}\) dizisinin ilk terimidir.
Yaprak şekil için dizi doğrudan bellidir:
$$S_{\bullet}=(2,3,5,7,11,\dots),$$
çünkü tek yapraklı ağaç tam olarak asallara karşılık gelir.
Şimdi \(s=\langle u,v\rangle\) olsun. Eğer \(T(m)=s\) ise, \(m\)'nin üst düzey kanonik ayrımı \(m=xy\) biçimindedir ve
$$T(x)=u,\qquad T(y)=v,\qquad x\le y$$
olur. O halde \(S_s\) içindeki her sayı şu tür çarpımlar arasından gelmek zorundadır:
$$x\in S_u,\qquad y\in S_v,\qquad x\le y,\qquad m=xy.$$
Fakat bu biçimde elde edilen her \(xy\), gerçekten \(S_s\)'ye ait değildir. Çarpım yapıldıktan sonra \(xy\), \((x,y)\)'den daha dengeli başka bir bölen çiftine sahip olabilir; bu durumda kanonik üst ayrım değişir ve sayı başka bir şekil sınıfına düşer.
Bu yüzden doğru tanım
$$S_s=\{xy:x\in S_u,\ y\in S_v,\ x\le y,\ T(xy)=s\}$$
şeklindedir. Son koşul, yöntemi sezgisel olmaktan çıkarıp tam doğru hale getiren filtredir.
Şöyle yazalım:
$$S_u=(x_0,x_1,x_2,\dots),\qquad S_v=(y_0,y_1,y_2,\dots).$$
Sabit bir \(i\) için sadece \(y_j\ge x_i\) olan terimler geçerlidir. Bu nedenle
$$x_i y_j\qquad (j\ge j_0(i))$$
satırı başlı başına sıralıdır; burada \(j_0(i)\), \(y_{j_0(i)}\ge x_i\) eşitsizliğini sağlayan ilk indextir.
Bir öncelik kuyruğu bu satırları tam Kartezyen çarpımı üretmeden birleştirebilir. En küçük aday çıkarılır, sonra sadece o satır ilerletilir. Yeni bir satır ise ancak ilk olası çarpımı mevcut minimumla yarışabilecek kadar küçük olduğunda açılır. Yinelenen ürünler atlanır ve her kalan ürün için kanonik şekil yeniden hesaplanır.
Burada
$$9!!=9\cdot 7\cdot 5\cdot 3\cdot 1=945$$
olur. \(945\)'in \(\sqrt{945}\)'yi aşmayan en büyük böleni \(27\) olduğundan üst ayrım
$$945=27\cdot 35$$
şeklindedir. Devam edersek
$$27=3\cdot 9,\qquad 9=3\cdot 3,\qquad 35=5\cdot 7.$$
Böylece
$$T(945)=\langle \langle \bullet,\langle \bullet,\bullet\rangle\rangle,\langle \bullet,\bullet\rangle\rangle$$
elde edilir. Şimdi \(72\)'ye bakalım. \(\sqrt{72}\)'yi aşmayan en büyük bölen \(8\)'dir, dolayısıyla
$$72=8\cdot 9,\qquad 8=2\cdot 4,\qquad 4=2\cdot 2,\qquad 9=3\cdot 3.$$
Bu da tam aynı ağacı verir. İlgili artan dizi \(72\) ile başlar ve uygulamalar şu kontrol değerini doğrular:
$$M(9)=72.$$
C++, Python ve Java implementasyonları önce \(2\le n\le 31\) için hedef şekilleri \(T(n!!)\) hesaplar. Sonra yalnızca bu hedeflerin ve onların alt şekillerinin gerçekten ihtiyaç duyduğu şekilleri işaretler; böylece gereksiz diziler üretilmez.
\(T(m)\) hesabında implementasyon, 64-bit sayılar için deterministik asal testi, bileşik sayılar için Pollard rho çarpanlara ayırması ve asal çarpan ayrışımından bölen üretimi kullanarak \(\sqrt m\)'yi aşmayan en büyük böleni bulur. Bu sonuçlar önbelleğe alınır; böylece aynı sayılar tekrar tekrar hesaplanmaz.
Gereken her şekil için tembel bir artan dizi tutulur. Yaprak dizi asalları sırayla üretir. İç düğüm dizileri ise çocuk dizilerinin ürünlerini öncelik kuyruğunda birleştirir, \(x\le y\) koşulunu zorlar, tekrar eden ürünleri eler, \(31!!\)'yi aşanları atar ve yalnızca yeniden hesaplanan kanonik şekli hedef şekille eşleşen ürünleri kabul eder. Her hedef dizinin ilk elemanı elde edildiğinde bu minimumlar toplanır.
Çalışma süresi çıktı-duyarlıdır: Her gerekli şekil için, istenen ilk geçerli değerler bulunana kadar kaç ürün adayının incelenmesi gerektiğine bağlıdır. Bir şekil \(s\) için \(K_s\) aday inceleniyorsa, yığın işlemleri standart en-iyi-önce birleştirme modeli altında \(O(K_s\log K_s)\) maliyet getirir.
Asıl pahalı bölüm kanonik şekil doğrulamasıdır; çünkü bunun için asal testi, çarpanlara ayırma, bölen üretimi ve özyinelemeli ağaç kurma gerekir. Önbellekleme pratikte tekrar maliyetini ciddi biçimde düşürür. Bu yüzden yöntem gerekli aralıkta hızlıdır, ancak en doğru tanım tek bir kapalı form yerine “öncelik kuyruğuyla tembel üretim ve sayı kuramsal doğrulama” şeklindedir. Bellek kullanımı da çoğunlukla çarpan ayrışımı önbellekleri, asal sonuçları, şekil kayıtları ve üretilmiş dizi öneklerinden gelir.
Para cada entero \(n\) con \(2\le n\le 31\), se forma primero el doble factorial
$$n!!=\prod_{\substack{1\le k\le n \\ k\equiv n\pmod{2}}} k.$$
Después, a cada entero positivo se le asocia un árbol binario canónico de factores: los primos son hojas y un compuesto se divide por el divisor más grande que no supera \(\sqrt m\), continuando luego de manera recursiva. Si \(T(m)\) denota esa forma, para cada \(n\) debemos hallar el menor entero \(M(n)\ge 2\) tal que \(T(M(n))=T(n!!)\), y finalmente calcular
$$\sum_{n=2}^{31} M(n).$$
La dificultad es que muchos enteros distintos pueden compartir la misma forma, de modo que la solución genera números por clase de forma en lugar de recorrer todos los enteros.
La descomposición canónica es determinista, así que cada entero positivo pertenece a una única clase de forma. El problema se convierte entonces en generar, en orden creciente, los enteros que pertenecen a cada forma objetivo obtenida a partir de \(n!!\).
Para un primo \(p\), definimos
$$T(p)=\bullet.$$
Para un compuesto \(m\), definimos
$$\delta(m)=\max\{d:d\mid m,\ d\le \sqrt m\},\qquad a=\delta(m),\qquad b=\frac{m}{a},$$
de modo que \(a\le b\), y luego
$$T(m)=\langle T(a),T(b)\rangle.$$
El factor \(a\) es el mayor divisor de \(m\) que no rebasa \(\sqrt m\), así que \((a,b)\) es el par de factores más equilibrado. Eso hace única la división superior y, por recursión, única toda la forma.
Para \(n=2,3,\dots,31\), ponemos
$$t_n=T(n!!),\qquad M(n)=\min\{m\ge 2:T(m)=t_n\}.$$
Ese mínimo existe porque \(n!!\) ya tiene la forma \(t_n\). En particular,
$$M(n)\le n!!\le 31!!.$$
Así, todos los mínimos requeridos quedan por debajo de una cota global finita.
Para cada forma \(s\), llamemos \(S_s\) a la sucesión creciente de todos los enteros \(m\le 31!!\) con \(T(m)=s\). Entonces \(M(n)\) es simplemente el primer término de \(S_{t_n}\).
La forma hoja es inmediata:
$$S_{\bullet}=(2,3,5,7,11,\dots),$$
porque los primos son exactamente los enteros cuyo árbol canónico tiene una sola hoja.
Ahora sea \(s=\langle u,v\rangle\) una forma interna. Si \(T(m)=s\), entonces la descomposición canónica superior de \(m\) es \(m=xy\) con
$$T(x)=u,\qquad T(y)=v,\qquad x\le y.$$
Por tanto, todo elemento de \(S_s\) debe aparecer entre los productos
$$x\in S_u,\qquad y\in S_v,\qquad x\le y,\qquad m=xy.$$
No todo producto \(xy\) generado desde las sucesiones hijas pertenece realmente a \(S_s\). Una vez multiplicados, puede ocurrir que \(xy\) posea un par de divisores más equilibrado que \((x,y)\); en ese caso, su división canónica cambia y el producto cae en otra forma.
La caracterización correcta es entonces
$$S_s=\{xy:x\in S_u,\ y\in S_v,\ x\le y,\ T(xy)=s\}.$$
La comprobación final \(T(xy)=s\) es el filtro que convierte la generación de candidatos en un método exacto.
Escribamos
$$S_u=(x_0,x_1,x_2,\dots),\qquad S_v=(y_0,y_1,y_2,\dots).$$
Para un \(i\) fijo, solo sirven los índices \(j\) con \(y_j\ge x_i\). Por ello, cada fila
$$x_i y_j\qquad (j\ge j_0(i))$$
es creciente, donde \(j_0(i)\) es el primer índice permitido.
Una cola de prioridad puede fusionar estas filas sin construir todo el producto cartesiano. Se extrae siempre el menor producto disponible, luego se avanza únicamente la fila de la que salió dicho producto, y solo se activa una fila nueva cuando su primer producto posible puede competir con el mínimo actual. Los valores repetidos se descartan y cada producto superviviente se vuelve a comprobar con la regla de forma canónica.
Tenemos
$$9!!=9\cdot 7\cdot 5\cdot 3\cdot 1=945.$$
El mayor divisor de \(945\) que no supera \(\sqrt{945}\) es \(27\), así que la división superior es
$$945=27\cdot 35.$$
Continuando recursivamente,
$$27=3\cdot 9,\qquad 9=3\cdot 3,\qquad 35=5\cdot 7.$$
Por tanto,
$$T(945)=\langle \langle \bullet,\langle \bullet,\bullet\rangle\rangle,\langle \bullet,\bullet\rangle\rangle.$$
Ahora observemos \(72\). Su mayor divisor que no rebasa \(\sqrt{72}\) es \(8\), y por eso
$$72=8\cdot 9,\qquad 8=2\cdot 4,\qquad 4=2\cdot 2,\qquad 9=3\cdot 3.$$
La forma resultante es exactamente la misma. La sucesión creciente asociada a esa forma empieza en \(72\), y las implementaciones confirman el punto de control
$$M(9)=72.$$
Las implementaciones en C++, Python y Java calculan primero las formas objetivo \(T(n!!)\) para \(2\le n\le 31\). Después marcan únicamente las formas necesarias para esos objetivos y para sus subformas, con lo que se evita generar secuencias irrelevantes.
Para evaluar \(T(m)\), la implementación usa una prueba de primalidad determinista en 64 bits, factorización de Pollard rho para compuestos y generación de divisores a partir de la factorización prima para localizar el mayor divisor \(\le \sqrt m\). Todo ello se memoriza, de modo que las consultas repetidas resultan baratas.
Cada forma necesaria posee una sucesión creciente perezosa. La forma hoja emite primos en orden. Cada forma interna fusiona con una cola de prioridad los productos de las secuencias hijas, impone la restricción \(x\le y\), elimina duplicados, descarta los productos mayores que \(31!!\) y conserva solo aquellos cuya forma canónica recomputada coincide con la forma objetivo. Cuando ya se conoce el primer término de cada secuencia objetivo, esos mínimos se suman.
El tiempo de ejecución depende de la salida: lo que importa es cuántos productos candidatos hay que inspeccionar para cada forma antes de encontrar los valores mínimos requeridos. Si una forma \(s\) examina \(K_s\) candidatos, el trabajo de la cola de prioridad es \(O(K_s\log K_s)\) en el modelo usual de fusión best-first.
La subrutina costosa es la validación de la forma canónica, porque exige prueba de primalidad, factorización, enumeración de divisores y reconstrucción recursiva del árbol. La memoización elimina gran parte del trabajo repetido en la práctica. Por eso el método es lo bastante rápido para el rango del problema, aunque la descripción más fiel es “generación perezosa guiada por heap con validación aritmética”, más que una cota cerrada simple. La memoria está dominada por las factorizaciones memorizadas, los resultados de primalidad, las formas canónicas y los prefijos almacenados de las secuencias generadas.
对每个满足 \(2\le n\le 31\) 的整数，先构造双阶乘
$$n!!=\prod_{\substack{1\le k\le n \\ k\equiv n\pmod{2}}} k.$$
然后给每个正整数规定一个规范的二叉因子树：素数对应单个叶子；合数则在“不超过 \(\sqrt m\) 的最大因子”处分裂，再对左右两部分递归执行同样的规则。若用 \(T(m)\) 表示这种树形，那么对每个 \(n\)，题目要求找出最小的整数 \(M(n)\ge 2\)，使得
$$T(M(n))=T(n!!),$$
最后求出
$$\sum_{n=2}^{31} M(n).$$
难点在于：很多不同的整数会落在同一个树形类里，所以解法不能按数值盲目枚举，而要按“形状类”来生成候选。
规范分解是确定性的，因此每个正整数恰好属于一个树形类。于是问题可以改写成：对每个由 \(n!!\) 产生的目标形状，按从小到大的顺序生成所有拥有该形状的整数，然后取第一个。
对素数 \(p\)，定义
$$T(p)=\bullet.$$
对合数 \(m\)，定义
$$\delta(m)=\max\{d:d\mid m,\ d\le \sqrt m\},\qquad a=\delta(m),\qquad b=\frac{m}{a},$$
于是 \(a\le b\)，再规定
$$T(m)=\langle T(a),T(b)\rangle.$$
这里的 \(a\) 是不超过 \(\sqrt m\) 的最大因子，所以 \((a,b)\) 是 \(m\) 最接近平方根的那组因子。顶层分裂因此唯一，递归下去整棵树也唯一。
对 \(n=2,3,\dots,31\)，设
$$t_n=T(n!!),\qquad M(n)=\min\{m\ge 2:T(m)=t_n\}.$$
这个最小值一定存在，因为 \(n!!\) 本身就已经具有形状 \(t_n\)。特别地，
$$M(n)\le n!!\le 31!!.$$
这说明所有需要的最小值都落在一个统一的有限上界之下。
现在对每个形状 \(s\)，定义 \(S_s\) 为所有满足 \(m\le 31!!\) 且 \(T(m)=s\) 的整数按升序排列得到的序列。那么所求 \(M(n)\) 就是 \(S_{t_n}\) 的首项。
叶子形状对应的序列最简单：
$$S_{\bullet}=(2,3,5,7,11,\dots),$$
因为规范树只有一个叶子的整数恰好就是所有素数。
现在设某个内部形状为 \(s=\langle u,v\rangle\)。如果 \(T(m)=s\)，那么 \(m\) 的顶层规范分裂必然是 \(m=xy\)，并满足
$$T(x)=u,\qquad T(y)=v,\qquad x\le y.$$
因此 \(S_s\) 中的每个元素都一定出现在下面这种候选乘积里：
$$x\in S_u,\qquad y\in S_v,\qquad x\le y,\qquad m=xy.$$
这给出了父形状的完整候选来源。
但并不是每个这样得到的 \(xy\) 都真的属于 \(S_s\)。原因是：把 \(x\) 和 \(y\) 相乘之后，新的整数 \(xy\) 可能存在比 \((x,y)\) 更接近平方根的因子对，于是它的顶层规范分裂会改成别的样子，整个树形也就变了。
因此真正正确的描述是
$$S_s=\{xy:x\in S_u,\ y\in S_v,\ x\le y,\ T(xy)=s\}.$$
最后这一条 \(T(xy)=s\) 正是数学上不可省略的过滤条件。没有它，得到的只是“可能来源”；加上它，才是精确的形状枚举。
把两个子序列写成
$$S_u=(x_0,x_1,x_2,\dots),\qquad S_v=(y_0,y_1,y_2,\dots).$$
对固定的 \(i\)，只有满足 \(y_j\ge x_i\) 的项才允许出现，所以一整行
$$x_i y_j\qquad (j\ge j_0(i))$$
本身已经是递增的，其中 \(j_0(i)\) 表示第一个使 \(y_{j_0(i)}\ge x_i\) 成立的索引。
于是可以用优先队列对这些递增行做惰性归并，而不必展开完整的笛卡尔积。每次都取出当前最小的可用乘积，然后只推进那个乘积所在的行；只有当某一新行的最小可能乘积有机会不大于当前候选时，才把这行激活。重复值会被跳过，而每一个剩下的乘积都要重新计算规范树，确认它真的落在目标形状里。
此时
$$9!!=9\cdot 7\cdot 5\cdot 3\cdot 1=945.$$
\(945\) 中不超过 \(\sqrt{945}\) 的最大因子是 \(27\)，所以顶层分裂为
$$945=27\cdot 35.$$
继续递归可得
$$27=3\cdot 9,\qquad 9=3\cdot 3,\qquad 35=5\cdot 7.$$
因此
$$T(945)=\langle \langle \bullet,\langle \bullet,\bullet\rangle\rangle,\langle \bullet,\bullet\rangle\rangle.$$
再看 \(72\)。它不超过 \(\sqrt{72}\) 的最大因子是 \(8\)，于是
$$72=8\cdot 9,\qquad 8=2\cdot 4,\qquad 4=2\cdot 2,\qquad 9=3\cdot 3.$$
得到的树形完全相同，所以 \(T(72)=T(945)\)。该形状对应的递增序列以 \(72\) 开头，因此实现中确认了检查点
$$M(9)=72.$$
C++、Python 和 Java 实现都会先计算 \(2\le n\le 31\) 的所有目标形状 \(T(n!!)\)，然后只保留这些目标及其子形状真正需要的那部分树形空间，从而避免无关的序列构造。
为了求 \(T(m)\)，实现会对 64 位整数做确定性的素性测试，对合数使用 Pollard rho 分解，再根据素因子分解枚举约数，从中找出不超过 \(\sqrt m\) 的最大约数。素性结果、分解结果和规范形状都会被缓存，因此重复查询会越来越便宜。
每个需要的形状都维护一个惰性递增序列。叶子序列按顺序产生素数。内部序列则把两个子序列的乘积用优先队列做 best-first 归并，强制满足 \(x\le y\)，跳过重复值，丢弃大于 \(31!!\) 的候选，并且只保留那些重新计算后仍然具有目标规范形状的乘积。等到每个目标序列的首项都得到以后，再把这些最小值求和。
运行时间是输出敏感的：关键不在于 \(31\) 本身，而在于每个所需形状在得到首个有效值之前要检查多少个候选乘积。若某个形状 \(s\) 总共检查了 \(K_s\) 个候选，那么其优先队列操作在标准 best-first 归并模型下为 \(O(K_s\log K_s)\)。
最昂贵的子过程是规范形状验证，因为它涉及素性测试、整数分解、约数枚举以及递归重建整棵树。缓存显著降低了重复成本，所以在题目要求的范围内速度足够快。不过最准确的描述仍然不是一个简单的初等闭式，而是“带有数论验证的堆驱动惰性生成”。空间主要消耗在分解缓存、素性缓存、规范形状缓存以及已生成序列前缀上。
Для каждого целого \(n\) из диапазона \(2\le n\le 31\) сначала строится двойной факториал
$$n!!=\prod_{\substack{1\le k\le n \\ k\equiv n\pmod{2}}} k.$$
Затем каждому положительному числу сопоставляется каноническое бинарное дерево разложения на множители: простые числа считаются листьями, а составное число разбивается по наибольшему делителю, не превосходящему \(\sqrt m\), после чего правило применяется рекурсивно к обоим сомножителям. Если такую форму обозначить через \(T(m)\), то для каждого \(n\) нужно найти минимальное число \(M(n)\ge 2\), удовлетворяющее
$$T(M(n))=T(n!!),$$
а затем вычислить
$$\sum_{n=2}^{31} M(n).$$
Трудность в том, что одна и та же форма может соответствовать многим разным числам, поэтому решение генерирует числа по классам форм, а не перебирает их подряд.
Каноническое разбиение определяется однозначно, поэтому каждое положительное целое принадлежит ровно одному классу форм. Значит, задачу можно переформулировать так: для каждой целевой формы, возникающей из \(n!!\), породить числа этой формы в возрастающем порядке и взять первое.
Для простого \(p\) положим
$$T(p)=\bullet.$$
Для составного \(m\) введем
$$\delta(m)=\max\{d:d\mid m,\ d\le \sqrt m\},\qquad a=\delta(m),\qquad b=\frac{m}{a},$$
так что \(a\le b\), и затем определим
$$T(m)=\langle T(a),T(b)\rangle.$$
Число \(a\) есть наибольший делитель, не превосходящий \(\sqrt m\), то есть верхнее разбиение выбирает наиболее сбалансированную пару множителей. Благодаря этому верхний шаг единственен, а значит, единственна и вся рекурсивная форма.
Для \(n=2,3,\dots,31\) зададим
$$t_n=T(n!!),\qquad M(n)=\min\{m\ge 2:T(m)=t_n\}.$$
Такой минимум существует, потому что \(n!!\) уже принадлежит форме \(t_n\). В частности,
$$M(n)\le n!!\le 31!!.$$
Следовательно, все нужные минимумы лежат ниже общей конечной границы.
Для каждой формы \(s\) обозначим через \(S_s\) возрастающую последовательность всех чисел \(m\le 31!!\), для которых \(T(m)=s\). Тогда \(M(n)\) есть просто первый элемент последовательности \(S_{t_n}\).
Для листовой формы последовательность очевидна:
$$S_{\bullet}=(2,3,5,7,11,\dots),$$
потому что именно простые числа имеют каноническое дерево из одного листа.
Пусть теперь \(s=\langle u,v\rangle\) — внутренняя форма. Если \(T(m)=s\), то верхнее каноническое разбиение числа \(m\) имеет вид \(m=xy\), где
$$T(x)=u,\qquad T(y)=v,\qquad x\le y.$$
Значит, любой элемент \(S_s\) обязан появиться среди произведений вида
$$x\in S_u,\qquad y\in S_v,\qquad x\le y,\qquad m=xy.$$
Однако не каждое такое произведение действительно принадлежит \(S_s\). После перемножения может оказаться, что у числа \(xy\) существует более сбалансированная пара делителей, чем \((x,y)\). Тогда его каноническое верхнее разбиение меняется, и число попадает в другую форму.
Поэтому верное описание таково:
$$S_s=\{xy:x\in S_u,\ y\in S_v,\ x\le y,\ T(xy)=s\}.$$
Условие \(T(xy)=s\) — это не украшение, а ключевой математический фильтр, делающий перечисление точным.
Запишем
$$S_u=(x_0,x_1,x_2,\dots),\qquad S_v=(y_0,y_1,y_2,\dots).$$
Для фиксированного \(i\) допустимы только такие \(j\), что \(y_j\ge x_i\). Поэтому каждая строка
$$x_i y_j\qquad (j\ge j_0(i))$$
сама по себе отсортирована, где \(j_0(i)\) — первый индекс, удовлетворяющий условию \(y_{j_0(i)}\ge x_i\).
Эти строки можно сливать лениво при помощи очереди с приоритетом, не разворачивая весь декартов продукт. Каждый раз извлекается наименьшее доступное произведение, после чего продвигается только соответствующая строка. Новая строка активируется лишь тогда, когда ее первый возможный элемент способен конкурировать с текущим минимумом. Повторы пропускаются, а каждая оставшаяся кандидатура снова проверяется по канонической форме.
Имеем
$$9!!=9\cdot 7\cdot 5\cdot 3\cdot 1=945.$$
Наибольший делитель числа \(945\), не превосходящий \(\sqrt{945}\), равен \(27\), поэтому верхнее разбиение таково:
$$945=27\cdot 35.$$
Далее рекурсивно получаем
$$27=3\cdot 9,\qquad 9=3\cdot 3,\qquad 35=5\cdot 7.$$
Следовательно,
$$T(945)=\langle \langle \bullet,\langle \bullet,\bullet\rangle\rangle,\langle \bullet,\bullet\rangle\rangle.$$
Теперь рассмотрим \(72\). Для него наибольший делитель ниже \(\sqrt{72}\) равен \(8\), значит
$$72=8\cdot 9,\qquad 8=2\cdot 4,\qquad 4=2\cdot 2,\qquad 9=3\cdot 3.$$
Получается та же форма дерева, то есть \(T(72)=T(945)\). Возрастающая последовательность для этой формы начинается с \(72\), и реализации подтверждают контрольное значение
$$M(9)=72.$$
Реализации на C++, Python и Java сначала вычисляют целевые формы \(T(n!!)\) для всех \(2\le n\le 31\). Затем они помечают только те формы, которые действительно нужны этим целям и их поддеревьям, чтобы не строить лишние последовательности.
Для вычисления \(T(m)\) реализация использует детерминированный тест простоты для 64-битных чисел, факторизацию Pollard rho для составных чисел и перебор делителей, полученных из разложения на простые множители, чтобы найти наибольший делитель \(\le \sqrt m\). Результаты кэшируются, поэтому повторные обращения становятся дешевыми.
Каждая нужная форма получает ленивую возрастающую последовательность. Листовая последовательность выдает простые числа. Внутренние последовательности выполняют best-first слияние произведений дочерних последовательностей через очередь с приоритетом, поддерживают ограничение \(x\le y\), убирают дубликаты, отбрасывают произведения больше \(31!!\) и сохраняют только те кандидаты, у которых пересчитанная каноническая форма совпадает с целевой. После того как первые элементы всех целевых последовательностей найдены, эти минимумы суммируются.
Время работы зависит от объема фактически нужного вывода: важно, сколько кандидатных произведений приходится просмотреть для каждой формы до появления требуемого минимального значения. Если для формы \(s\) проверяется \(K_s\) кандидатов, то работа очереди с приоритетом имеет порядок \(O(K_s\log K_s)\) в стандартной модели best-first слияния.
Самая дорогая часть — проверка канонической формы, поскольку она требует теста простоты, факторизации, перечисления делителей и рекурсивного восстановления дерева. Кэширование существенно уменьшает повторные затраты на практике. Поэтому метод достаточно быстр для нужного диапазона, хотя точнее всего его описывать как «ленивую генерацию с кучей и арифметической проверкой», а не одной простой замкнутой формулой. Память в основном расходуется на кэши факторизаций, результатов тестов простоты, канонических форм и на уже сгенерированные префиксы последовательностей.
لكل عدد صحيح \(n\) يحقق \(2\le n\le 31\)، نبني أولًا المضروب المزدوج
$$n!!=\prod_{\substack{1\le k\le n \\ k\equiv n\pmod{2}}} k.$$
ثم نربط بكل عدد صحيح موجب شجرة عوامل ثنائية قياسية: العدد الأولي يمثل ورقة واحدة، أما العدد المركب فيُقسَّم عند أكبر قاسم لا يتجاوز \(\sqrt m\)، ثم تُطبَّق القاعدة نفسها على الجزأين بصورة تكرارية. إذا رمزنا إلى هذا الشكل بالرمز \(T(m)\)، فإن المطلوب لكل \(n\) هو إيجاد أصغر عدد \(M(n)\ge 2\) يحقق
$$T(M(n))=T(n!!),$$
ثم حساب
$$\sum_{n=2}^{31} M(n).$$
الصعوبة أن أعدادًا مختلفة كثيرة قد تشترك في الشكل نفسه، ولذلك لا تعتمد الخوارزمية على الفحص المتتابع لجميع الأعداد، بل تولِّد الأعداد بحسب فئات الأشكال.
بما أن التحليل القياسي محدد بشكل وحيد، فإن كل عدد صحيح موجب ينتمي إلى فئة شكل واحدة فقط. ومن ثم يمكن تحويل المسألة إلى مهمة توليد: لكل شكل هدف يأتي من \(n!!\)، نولّد الأعداد التي تحمل هذا الشكل بترتيب تصاعدي ثم نأخذ أول عنصر.
إذا كان \(p\) أوليًا، فنعرّف
$$T(p)=\bullet.$$
أما إذا كان \(m\) مركبًا، فنعرّف
$$\delta(m)=\max\{d:d\mid m,\ d\le \sqrt m\},\qquad a=\delta(m),\qquad b=\frac{m}{a},$$
وبالتالي \(a\le b\)، ثم نضع
$$T(m)=\langle T(a),T(b)\rangle.$$
العدد \(a\) هو أكبر قاسم لا يتجاوز \(\sqrt m\)، أي إن الزوج \((a,b)\) هو أكثر زوج عوامل اتزانًا بالنسبة إلى الجذر التربيعي. وبهذا تكون القسمة العليا وحيدة، وبالتالي تكون الشجرة كلها وحيدة أيضًا.
لكل \(n=2,3,\dots,31\) نعرّف
$$t_n=T(n!!),\qquad M(n)=\min\{m\ge 2:T(m)=t_n\}.$$
هذا الحد الأدنى موجود لأن \(n!!\) نفسه يملك الشكل \(t_n\). وعلى وجه الخصوص،
$$M(n)\le n!!\le 31!!.$$
إذن جميع القيم الدنيا المطلوبة تقع تحت حد علوي منتهٍ واحد.
ولكل شكل \(s\)، لنرمز بـ \(S_s\) إلى المتتالية التصاعدية لجميع الأعداد \(m\le 31!!\) التي تحقق \(T(m)=s\). عندئذ يكون \(M(n)\) هو الحد الأول في المتتالية \(S_{t_n}\).
شكل الورقة مباشر:
$$S_{\bullet}=(2,3,5,7,11,\dots),$$
لأن الأعداد الأولية وحدها هي التي يكون شكلها القياسي ورقة واحدة.
الآن لنفترض أن \(s=\langle u,v\rangle\) شكل داخلي. إذا كان \(T(m)=s\)، فإن القسمة القياسية العليا لـ \(m\) تكون على الصورة \(m=xy\) مع
$$T(x)=u,\qquad T(y)=v,\qquad x\le y.$$
إذًا كل عنصر في \(S_s\) لا بد أن يظهر بين المرشحات من النوع
$$x\in S_u,\qquad y\in S_v,\qquad x\le y,\qquad m=xy.$$
لكن ليس كل جداء \(xy\) ناتج من متتاليتي الابنين ينتمي فعلًا إلى \(S_s\). فقد يحدث بعد الضرب أن يمتلك \(xy\) زوج عوامل أكثر اتزانًا من \((x,y)\)، وعندها تتغير القسمة القياسية العليا ويتحوّل العدد إلى شكل مختلف.
لذلك يكون الوصف الصحيح هو
$$S_s=\{xy:x\in S_u,\ y\in S_v,\ x\le y,\ T(xy)=s\}.$$
الشرط الأخير \(T(xy)=s\) هو الفلتر الحاسم الذي يجعل العدّ دقيقًا رياضيًا، لا مجرد توليد تقريبي للمرشحات.
لنكتب
$$S_u=(x_0,x_1,x_2,\dots),\qquad S_v=(y_0,y_1,y_2,\dots).$$
عند تثبيت \(i\)، لا يسمح إلا بالمؤشرات \(j\) التي تحقق \(y_j\ge x_i\). ولذلك فإن كل سطر من الشكل
$$x_i y_j\qquad (j\ge j_0(i))$$
يكون مرتبًا تصاعديًا بحد ذاته، حيث \(j_0(i)\) هو أول مؤشر يحقق الشرط \(y_{j_0(i)}\ge x_i\).
يمكن لصف أولوية أن يدمج هذه الأسطر بصورة كسولة دون توليد حاصل الضرب الديكارتي كاملًا. في كل مرة نأخذ أصغر جداء متاح، ثم نُقدِّم السطر الذي خرج منه هذا الجداء فقط. ولا نفتح سطرًا جديدًا إلا إذا كان أول جداء ممكن فيه قادرًا على منافسة الحد الأدنى الحالي. كما تُتجاوز القيم المكررة، ويُعاد فحص كل جداء باقٍ وفق قاعدة الشكل القياسي.
لدينا
$$9!!=9\cdot 7\cdot 5\cdot 3\cdot 1=945.$$
أكبر قاسم للعدد \(945\) لا يتجاوز \(\sqrt{945}\) هو \(27\)، ولذلك تكون القسمة العليا
$$945=27\cdot 35.$$
وبمتابعة التحليل تكراريًا نحصل على
$$27=3\cdot 9,\qquad 9=3\cdot 3,\qquad 35=5\cdot 7.$$
ومن ثم
$$T(945)=\langle \langle \bullet,\langle \bullet,\bullet\rangle\rangle,\langle \bullet,\bullet\rangle\rangle.$$
الآن انظر إلى \(72\). أكبر قاسم له لا يتجاوز \(\sqrt{72}\) هو \(8\)، ومن ثم
$$72=8\cdot 9,\qquad 8=2\cdot 4,\qquad 4=2\cdot 2,\qquad 9=3\cdot 3.$$
فنحصل على الشجرة نفسها تمامًا، أي \(T(72)=T(945)\). والمتتالية التصاعدية الموافقة لهذا الشكل تبدأ بالعدد \(72\)، ولذلك تؤكد التطبيقات نقطة التحقق
$$M(9)=72.$$
تبدأ تطبيقات C++ وPython وJava بحساب الأشكال الهدف \(T(n!!)\) لكل \(2\le n\le 31\). ثم تُعلَّم فقط الأشكال التي تحتاجها هذه الأهداف وأشكالها الفرعية فعلًا، حتى لا يُصرف الجهد على أجزاء غير لازمة من فضاء الأشكال.
ولحساب \(T(m)\)، تستخدم التنفيذات اختبار أولية حتميًا للأعداد ذات 64 بت، وخوارزمية Pollard rho لتحليل الأعداد المركبة، ثم توليد القواسم من التحليل الأولي من أجل اختيار أكبر قاسم لا يتجاوز \(\sqrt m\). كما تُخزَّن نتائج الأولية والتحليل والأشكال القياسية في الذاكرة المؤقتة حتى تصبح الاستدعاءات المكررة أقل كلفة.
يمتلك كل شكل مطلوب متتالية تصاعدية كسولة. متتالية الورقة تنتج الأعداد الأولية بترتيبها. أما المتتاليات الداخلية فتجري دمجًا best-first لجداءات متتاليتي الابنين باستخدام صف أولوية، وتفرض الشرط \(x\le y\)، وتحذف التكرارات، وتستبعد الجداءات الأكبر من \(31!!\)، ولا تحتفظ إلا بالجداءات التي يطابق شكلها القياسي المعاد حسابه الشكل الهدف. وبعد الحصول على الحد الأول لكل متتالية هدف، تُجمع هذه القيم الدنيا.
زمن التنفيذ حساس لحجم المخرجات المطلوبة: العامل الحاسم هو عدد الجداءات المرشحة التي يجب فحصها لكل شكل قبل الوصول إلى أول قيمة صحيحة مطلوبة. فإذا كان الشكل \(s\) يحتاج إلى فحص \(K_s\) مرشحًا، فإن عمل صف الأولوية له يكون من رتبة \(O(K_s\log K_s)\) ضمن نموذج الدمج best-first المعتاد.
الجزء المكلف هو التحقق من الشكل القياسي، لأنه يحتاج إلى اختبار الأولية، والتحليل إلى عوامل، وتوليد القواسم، ثم إعادة بناء الشجرة تكراريًا. ويخفف التخزين المؤقت كثيرًا من تكرار هذه الكلفة عمليًا. لذلك تكون الطريقة سريعة بما يكفي للنطاق المطلوب، لكن الوصف الأدق لها ليس حدًا مغلقًا بسيطًا، بل «توليد كسول موجَّه بصف أولوية مع تحقق عددي». ويهيمن على الذاكرة تخزين التحليلات، ونتائج اختبارات الأولية، والأشكال القياسية، ومقدمات المتتاليات التي جرى توليدها.