Choose four distinct digits from \(\{1,2,\dots,9\}\). Using each chosen digit exactly once, together with the binary operations \(+\), \(-\), \(\times\), and \(\div\), and allowing parentheses, we ask which four-digit set can generate the longest consecutive run of positive integers \(1,2,3,\dots,n\).
For a fixed digit set \(D=\{a,b,c,d\}\), let \(I(D)\) be the set of positive integers obtainable from valid expressions. The score of \(D\) is
$$L(D)=\max\{n\ge 0:\{1,2,\dots,n\}\subseteq I(D)\}.$$
The goal is to maximize \(L(D)\) over all four-element subsets of \(\{1,\dots,9\}\), then output the winning digits in ascending order as one four-digit string.
The key point is that the problem is exhaustive but finite. Every legal expression can be described by a small collection of discrete choices: an ordering of the digits, a choice of three operators, and a choice of one full binary-tree shape. Once that state space is written down explicitly, the search becomes a complete enumeration rather than symbolic guesswork.
Fix an ordered tuple \((x_1,x_2,x_3,x_4)\) of the four chosen digits. Any legal expression using these four numbers exactly once and only binary operations has three internal operation nodes and four leaves, so it is a full binary tree with four leaves.
For four leaves there are exactly five such shapes, corresponding to the five fully parenthesized forms
$$(((x_1 \circ_1 x_2)\circ_2 x_3)\circ_3 x_4),$$
$$((x_1\circ_1 (x_2\circ_2 x_3))\circ_3 x_4),$$
$$((x_1\circ_1 x_2)\circ_2 (x_3\circ_3 x_4)),$$
$$x_1\circ_1 ((x_2\circ_2 x_3)\circ_3 x_4),$$
$$x_1\circ_1 (x_2\circ_2 (x_3\circ_3 x_4)).$$
The number \(5\) is the Catalan number \(C_3\). This is the mathematical reason there are exactly five parenthesization patterns to test and no others.
For one unordered digit set \(D\), the leaves can be arranged in \(4!=24\) orders. Each of the three internal nodes can carry any of the four operations, giving \(4^3=64\) operator triples. Combining these with the five tree shapes yields
$$N_{\text{expr}}=4!\cdot 4^3\cdot 5=24\cdot 64\cdot 5=7680$$
candidate expressions for one digit set.
The outer search runs over all
$$\binom{9}{4}=126$$
choices of four distinct digits from \(\{1,\dots,9\}\), so the entire problem requires only
$$126\cdot 7680=967680$$
candidate evaluations. That count is small enough for brute force, but it is also complete: every admissible expression belongs to exactly one leaf order, one operator assignment, and one of the five binary-tree shapes above. Different descriptions can still collapse to the same numerical value, but duplicates do not matter because we keep results in a set.
Division means intermediate results need not be integers, so the natural domain is \(\mathbb{Q}\), not \(\mathbb{Z}\). If
$$x=\frac{p}{q},\qquad y=\frac{r}{s},\qquad q\ne 0,\ s\ne 0,$$
then the four operations are
$$x+y=\frac{ps+rq}{qs},\qquad x-y=\frac{ps-rq}{qs},\qquad xy=\frac{pr}{qs},$$
$$\frac{x}{y}=\frac{ps}{qr}\qquad\text{provided }r\ne 0.$$
Any branch with division by zero is invalid and is discarded. A final outcome contributes only when it lies in \(\mathbb{Z}_{>0}\).
This viewpoint explains the implementations cleanly. The C++ implementation represents intermediates as reduced fractions, so integrality is exact. The Python and Java implementations explore the same expression space numerically and accept a value only if it is positive and numerically integral at the end.
Let \(R(D)\subseteq \mathbb{Q}\) be the set of all valid outcomes for the digit set \(D\), and define
$$I(D)=R(D)\cap \mathbb{Z}_{>0}.$$
The score is the length of the initial positive-integer prefix contained in \(I(D)\):
$$L(D)=\max\{n\ge 0:\{1,2,\dots,n\}\subseteq I(D)\}.$$
Only the first gap matters. If \(m\notin I(D)\), then the run cannot extend beyond \(m-1\), regardless of how many larger integers are also representable. So once all outcomes for \(D\) are collected, the score is recovered by checking \(1,2,3,\dots\) until the first missing value appears.
Take the ordered digits \((1,2,3,4)\) and the operator triple \((+,\times,-)\). The five binary-tree shapes give
$$((1+2)\times 3)-4=5,$$
$$\bigl(1+(2\times 3)\bigr)-4=3,$$
$$((1+2)\times(3-4))=-3,$$
$$1+\bigl((2\times 3)-4\bigr)=3,$$
$$1+\bigl(2\times(3-4)\bigr)=-1.$$
The digits are the same and the multiset of operations is the same, yet the results differ because the tree shape changes the evaluation order. That is why the five Catalan shapes are not optional boilerplate; they are the actual mathematical cases to enumerate. One implementation also uses the known fact that the digits \(\{1,2,3,4\}\) achieve the consecutive run \(1\) through \(28\) as a checkpoint.
The C++, Python, and Java implementations iterate over all combinations \(a<b<c<d\) from \(\{1,\dots,9\}\). This covers each four-digit set exactly once and keeps the eventual answer in ascending order automatically.
For each digit set, the implementation loops over all 24 digit permutations, all 64 operator triples, and the five parenthesization patterns listed above. Each pattern performs exactly three binary operations. Any attempt to divide by zero terminates that branch immediately.
The C++ version carries reduced fractions through the whole computation. The Python and Java versions use floating-point arithmetic, but they follow the same five-shape enumeration and keep only final values that are positive integers.
Every accepted positive integer is inserted into a set attached to the current digits. After the enumeration finishes, the implementation scans upward from \(1\) until it finds the first integer not present. That missing value determines \(L(D)\). If the new score exceeds the best score seen so far, the current digits become the new best answer.
For one digit set, the algorithm performs exactly \(24\cdot 64\cdot 5=7680\) candidate evaluations. Across all \(\binom{9}{4}=126\) digit sets, that is \(967680\) evaluations in total. Each candidate uses only three arithmetic operations plus constant-time validity checks, so the overall running time is effectively linear in that explicit count.
Auxiliary space is small. At any moment the implementation stores only the set of distinct positive integers reachable from the current digit set, together with a few temporary rational or floating-point values. In asymptotic terms this is \(O(U)\), where \(U\) is the number of distinct positive integers generated for one four-digit choice, and \(U\) remains modest in practice.
Wir wählen vier verschiedene Ziffern aus \(\{1,2,\dots,9\}\). Mit jeder dieser Ziffern genau einmal, den binären Operationen \(+\), \(-\), \(\times\) und \(\div\) sowie mit Klammern soll bestimmt werden, welche Vierergruppe die längste zusammenhängende Folge positiver Ganzzahlen \(1,2,3,\dots,n\) erzeugen kann.
Für eine feste Ziffernmenge \(D=\{a,b,c,d\}\) sei \(I(D)\) die Menge aller positiven Ganzzahlen, die durch zulässige Ausdrücke entstehen. Die Wertung der Menge ist
$$L(D)=\max\{n\ge 0:\{1,2,\dots,n\}\subseteq I(D)\}.$$
Gesucht ist also die Vierermenge mit maximalem \(L(D)\); ausgegeben werden ihre Ziffern in aufsteigender Reihenfolge als vierstellige Zeichenkette.
Die Aufgabe ist vollständig durchsuchbar, aber nur dann sauber, wenn man den Zustandsraum richtig beschreibt. Jeder zulässige Ausdruck wird durch drei diskrete Entscheidungen festgelegt: die Reihenfolge der vier Ziffern, die Wahl von drei Operatoren und die Wahl einer vollen Binärbaumform. Damit wird aus einer scheinbar offenen Symbolsuche eine endliche vollständige Enumeration.
Fixiere eine geordnete Viererfolge \((x_1,x_2,x_3,x_4)\) der gewählten Ziffern. Jeder zulässige Ausdruck, der jede Zahl genau einmal benutzt und nur binäre Operationen enthält, besitzt drei innere Operationsknoten und vier Blätter. Er ist also ein voller Binärbaum mit vier Blättern.
Für vier Blätter gibt es genau fünf Formen, also genau die fünf vollständigen Klammerungen
$$(((x_1 \circ_1 x_2)\circ_2 x_3)\circ_3 x_4),$$
$$((x_1\circ_1 (x_2\circ_2 x_3))\circ_3 x_4),$$
$$((x_1\circ_1 x_2)\circ_2 (x_3\circ_3 x_4)),$$
$$x_1\circ_1 ((x_2\circ_2 x_3)\circ_3 x_4),$$
$$x_1\circ_1 (x_2\circ_2 (x_3\circ_3 x_4)).$$
Die Zahl \(5\) ist die Catalan-Zahl \(C_3\). Genau deshalb müssen fünf Klammerungsmuster geprüft werden, aber nicht mehr.
Für eine ungeordnete Ziffernmenge \(D\) gibt es \(4!=24\) mögliche Blattreihenfolgen. Jeder der drei inneren Knoten kann mit einer der vier Operationen belegt werden, also gibt es \(4^3=64\) Operatordrillinge. Zusammen mit den fünf Baumformen ergibt das
$$N_{\text{expr}}=4!\cdot 4^3\cdot 5=24\cdot 64\cdot 5=7680$$
Kandidaten für genau eine Ziffernmenge.
Äußerlich werden alle
$$\binom{9}{4}=126$$
Vierermengen aus \(\{1,\dots,9\}\) betrachtet, also insgesamt
$$126\cdot 7680=967680$$
Auswertungen. Diese Zahl ist nicht nur klein genug für Brute Force, sondern auch vollständig: Jeder zulässige Ausdruck gehört zu genau einer Blattordnung, genau einer Operatorwahl und genau einer der fünf Baumformen. Dass verschiedene Beschreibungen denselben Zahlenwert liefern können, ist unschädlich, weil alle Resultate in einer Menge gesammelt werden.
Wegen der Division bleiben Zwischenwerte im Allgemeinen nicht ganzzahlig. Der natürliche Rechenraum ist also \(\mathbb{Q}\), nicht \(\mathbb{Z}\). Für
$$x=\frac{p}{q},\qquad y=\frac{r}{s},\qquad q\ne 0,\ s\ne 0$$
gelten
$$x+y=\frac{ps+rq}{qs},\qquad x-y=\frac{ps-rq}{qs},\qquad xy=\frac{pr}{qs},$$
$$\frac{x}{y}=\frac{ps}{qr}\qquad\text{falls }r\ne 0.$$
Jeder Zweig mit Division durch Null ist ungültig und wird verworfen. Ein Endwert zählt nur dann, wenn er in \(\mathbb{Z}_{>0}\) liegt.
Genau so spiegeln es die Implementierungen wider. Die C++-Version führt exakte, gekürzte Brüche. Die Python- und Java-Versionen durchsuchen denselben Ausdrucksraum numerisch und übernehmen einen Wert nur dann, wenn er am Ende positiv und ganzzahlig ist.
Sei \(R(D)\subseteq \mathbb{Q}\) die Menge aller gültigen Resultate zur Ziffernmenge \(D\), und definiere
$$I(D)=R(D)\cap \mathbb{Z}_{>0}.$$
Maximiert wird die Länge des Anfangssegments positiver Ganzzahlen in \(I(D)\):
$$L(D)=\max\{n\ge 0:\{1,2,\dots,n\}\subseteq I(D)\}.$$
Relevant ist also nur die erste Lücke. Wenn \(m\notin I(D)\), dann kann die zusammenhängende Folge nicht über \(m-1\) hinausreichen, ganz gleich wie viele größere Zahlen ebenfalls darstellbar sind. Nachdem alle Ergebnisse zu \(D\) gesammelt wurden, genügt daher ein Prüfen von \(1,2,3,\dots\) bis zum ersten fehlenden Wert.
Nimm die geordneten Ziffern \((1,2,3,4)\) und den Operatordrilling \((+,\times,-)\). Die fünf Baumformen liefern
$$((1+2)\times 3)-4=5,$$
$$\bigl(1+(2\times 3)\bigr)-4=3,$$
$$((1+2)\times(3-4))=-3,$$
$$1+\bigl((2\times 3)-4\bigr)=3,$$
$$1+\bigl(2\times(3-4)\bigr)=-1.$$
Die Ziffern sind gleich und auch die Operationsmenge ist gleich, aber die Ergebnisse unterscheiden sich, weil die Baumform die Auswertungsreihenfolge ändert. Deshalb sind die fünf Catalan-Fälle kein dekoratives Schema, sondern die eigentlichen mathematischen Fälle. Eine Implementierung benutzt außerdem die bekannte Tatsache, dass \(\{1,2,3,4\}\) die Folge \(1\) bis \(28\) erzeugt, als Kontrollpunkt.
Die Implementierungen in C++, Python und Java durchlaufen alle Kombinationen \(a<b<c<d\) aus \(\{1,\dots,9\}\). Jede Vierermenge wird so genau einmal betrachtet, und die spätere Ausgabe liegt automatisch in aufsteigender Reihenfolge vor.
Für jede Ziffernmenge werden alle 24 Permutationen, alle 64 Operatordrillinge und alle fünf oben beschriebenen Klammerungsmuster durchlaufen. Jedes Muster benötigt genau drei binäre Rechenschritte. Sobald irgendwo durch Null geteilt würde, wird dieser Zweig sofort verworfen.
Die C++-Variante transportiert gekürzte Brüche durch die gesamte Rechnung. Python und Java benutzen Fließkommazahlen, folgen aber derselben Fünf-Formen-Enumeration und behalten nur positive ganzzahlige Endwerte.
Jede akzeptierte positive Ganzzahl wird in eine Ergebnismenge zur aktuellen Ziffernwahl eingefügt. Nach Abschluss der Enumeration prüft die Implementierung aufsteigend \(1,2,3,\dots\), bis die erste fehlende Zahl gefunden ist. Daraus ergibt sich \(L(D)\). Wenn dieser Wert größer ist als der bisher beste, wird die aktuelle Ziffernmenge zum neuen Kandidaten für die Endausgabe.
Für eine feste Ziffernmenge werden exakt \(24\cdot 64\cdot 5=7680\) Kandidaten ausgewertet. Über alle \(\binom{9}{4}=126\) Vierermengen sind das insgesamt \(967680\) Auswertungen. Jede einzelne benötigt nur drei arithmetische Operationen plus konstante Prüfungen auf Gültigkeit, daher ist die Gesamtlaufzeit effektiv linear in dieser expliziten Anzahl.
Der Speicherbedarf ist klein. Zu jedem Zeitpunkt wird nur die Menge der verschiedenen positiven Ganzzahlen für die aktuelle Ziffernmenge gehalten, ergänzt durch einige temporäre rationale oder reelle Zwischenwerte. Asymptotisch ist das \(O(U)\), wobei \(U\) die Zahl der unterschiedlichen positiven Ganzzahlen für eine einzelne Viererauswahl ist; in der Praxis bleibt \(U\) überschaubar.
\(\{1,2,\dots,9\}\) kümesinden dört farklı rakam seçiyoruz. Bu rakamların her biri tam bir kez kullanılacak; işlemler yalnızca \(+\), \(-\), \(\times\) ve \(\div\) olacak; parantez kullanımı serbest olacak. Amaç, bu şekilde elde edilebilen pozitif tamsayılar arasında \(1,2,3,\dots,n\) biçimindeki en uzun ardışık başlangıç dizisini üreten dört rakamlı kümeyi bulmaktır.
Sabit bir \(D=\{a,b,c,d\}\) rakam kümesi için, geçerli ifadelerden üretilebilen pozitif tamsayılar kümesini \(I(D)\) ile gösterelim. Kümenin puanı
$$L(D)=\max\{n\ge 0:\{1,2,\dots,n\}\subseteq I(D)\}$$
olarak tanımlanır. Aranan şey, \(L(D)\) değerini en büyük yapan dört rakam kümesidir; çıktı da bu rakamların artan sırada yan yana yazılmasıdır.
Problem kaba kuvvetle çözülebilir, fakat bunu doğru söylemek için arama uzayını açıkça tanımlamak gerekir. Her geçerli ifade üç ayrık seçimle belirlenir: rakamların sırası, üç işlem düğümüne hangi işlemlerin yerleştirildiği ve dört yapraklı tam ikili ağacın hangi biçiminin kullanıldığı. Bu bakış açısı, soruyu belirsiz bir sembolik aramadan küçük ve sonlu bir sayım problemine dönüştürür.
Seçilen dört rakamın sıralı bir düzenini \((x_1,x_2,x_3,x_4)\) olarak sabitleyelim. Bu dört sayıyı tam birer kez kullanan ve yalnızca ikili işlemler içeren herhangi bir ifade, üç iç işlem düğümüne ve dört yaprağa sahiptir. Yani bu ifade, dört yapraklı tam bir ikili ağaçtır.
Dört yaprak için tam olarak beş ağaç biçimi vardır; bunlar da şu beş tam parantezleme kalıbına karşılık gelir:
$$(((x_1 \circ_1 x_2)\circ_2 x_3)\circ_3 x_4),$$
$$((x_1\circ_1 (x_2\circ_2 x_3))\circ_3 x_4),$$
$$((x_1\circ_1 x_2)\circ_2 (x_3\circ_3 x_4)),$$
$$x_1\circ_1 ((x_2\circ_2 x_3)\circ_3 x_4),$$
$$x_1\circ_1 (x_2\circ_2 (x_3\circ_3 x_4)).$$
Bu \(5\) sayısı, Catalan sayısı \(C_3\)'tür. Yani denenecek parantezleme sayısının tam olarak beş olmasının matematiksel nedeni budur.
Tek bir sırasız rakam kümesi \(D\) için yapraklar \(4!=24\) farklı sırada yerleştirilebilir. Üç iç düğümün her biri dört işlemden birini seçtiği için \(4^3=64\) farklı işlem üçlüsü vardır. Beş ağaç biçimiyle birlikte
$$N_{\text{expr}}=4!\cdot 4^3\cdot 5=24\cdot 64\cdot 5=7680$$
aday ifade elde edilir.
Dış döngü ise \(\{1,\dots,9\}\) içinden seçilen
$$\binom{9}{4}=126$$
farklı dört rakam kümesinin hepsini dolaşır. Böylece toplam değerlendirme sayısı
$$126\cdot 7680=967680$$
olur. Bu sayı hem yeterince küçüktür hem de matematiksel olarak tamdır: geçerli her ifade, yukarıdaki beş ağaçtan birine, bir rakam sırasına ve bir işlem atamasına karşılık gelir. Farklı açıklamalar aynı sayısal sonucu verebilir; bunun zararı yoktur çünkü sonuçlar kümede tutulur.
Bölme işlemi yüzünden ara değerler tam sayı kalmak zorunda değildir. Bu nedenle doğal durum uzayı \(\mathbb{Z}\) değil, \(\mathbb{Q}\)'dur. Eğer
$$x=\frac{p}{q},\qquad y=\frac{r}{s},\qquad q\ne 0,\ s\ne 0$$
ise dört işlem
$$x+y=\frac{ps+rq}{qs},\qquad x-y=\frac{ps-rq}{qs},\qquad xy=\frac{pr}{qs},$$
$$\frac{x}{y}=\frac{ps}{qr}\qquad\text{yalnızca }r\ne 0\text{ ise}$$
şeklindedir. Sıfıra bölme isteyen her dal geçersizdir ve atılır. Bir sonucun kabul edilmesi için de son değerin \(\mathbb{Z}_{>0}\) içinde olması gerekir.
Uygulamalar bunu farklı sayısal temsillerle yapar. C++ sürümü ara sonuçları sadeleştirilmiş kesirler olarak taşır ve tam sayılık kontrolü tam olarak yapar. Python ve Java sürümleri aynı ifade uzayını kayan noktalı sayılarla dolaşır; ama sonunda yalnızca pozitif ve sayısal olarak tam sayı olan değerleri tutar.
\(D\) rakam kümesi için bütün geçerli sonuçların kümesini \(R(D)\subseteq \mathbb{Q}\) ile gösterelim ve
$$I(D)=R(D)\cap \mathbb{Z}_{>0}$$
tanımını yapalım. Maksimize edilen büyüklük, \(I(D)\) içindeki başlangıç pozitif tamsayı bloğunun uzunluğudur:
$$L(D)=\max\{n\ge 0:\{1,2,\dots,n\}\subseteq I(D)\}.$$
Burada yalnızca ilk eksik değer önemlidir. Eğer \(m\notin I(D)\) ise, \(m-1\)'in ötesine uzanan kesintisiz bir başlangıç dizisi mümkün değildir; daha büyük birçok sayı üretilebiliyor olsa bile durum değişmez. Bu yüzden bir rakam kümesi için bütün sonuçlar toplandıktan sonra \(1,2,3,\dots\) diye ilerleyip ilk boşluğu bulmak yeterlidir.
Sıralı rakamlar \((1,2,3,4)\) ve işlem üçlüsü \((+,\times,-)\) olsun. Beş ağaç biçimi şu sonuçları verir:
$$((1+2)\times 3)-4=5,$$
$$\bigl(1+(2\times 3)\bigr)-4=3,$$
$$((1+2)\times(3-4))=-3,$$
$$1+\bigl((2\times 3)-4\bigr)=3,$$
$$1+\bigl(2\times(3-4)\bigr)=-1.$$
Rakamlar aynı, kullanılan işlemler aynı; ama sonuçlar farklı, çünkü ağaç biçimi değerlendirme sırasını değiştiriyor. Bu nedenle beş Catalan biçimi yapay bir şablon değil, doğrudan çözümün matematiksel durumlarıdır. Uygulamalardan biri ayrıca \(\{1,2,3,4\}\) kümesinin \(1\) ile \(28\) arasını ürettiği bilgisini bir kontrol noktası olarak kullanır.
C++, Python ve Java uygulamaları \(\{1,\dots,9\}\) içindeki tüm \(a<b<c<d\) kombinasyonlarını dolaşır. Böylece her dört rakam kümesi tam bir kez incelenir ve nihai çıktı zaten artan sırada tutulmuş olur.
Her rakam kümesi için uygulama 24 permütasyonu, 64 işlem üçlüsünü ve yukarıdaki beş parantezleme kalıbını gezer. Her kalıp tam olarak üç ikili işlem uygular. Herhangi bir yerde sıfıra bölme oluşursa o dal anında bırakılır.
C++ sürümü tüm hesap boyunca sadeleştirilmiş kesirler kullanır. Python ve Java sürümleri kayan noktalı aritmetik kullanır; fakat aynı beş-biçimli taramayı yapar ve yalnızca pozitif tamsayı son değerlerini kabul eder.
Kabul edilen her pozitif tamsayı, mevcut rakam kümesi için bir sonuç kümesine eklenir. Tam tarama bittikten sonra uygulama \(1\)'den başlayarak yukarı doğru gider ve ilk eksik tamsayıyı bulur. Bu eksik değer, \(L(D)\) puanını belirler. Yeni puan şimdiye kadarki en iyiden büyükse, ilgili rakamlar yeni cevap adayı olur.
Tek bir rakam kümesi için algoritma tam olarak \(24\cdot 64\cdot 5=7680\) aday değerlendirmesi yapar. Tüm \(\binom{9}{4}=126\) küme üzerinde bu sayı toplam \(967680\)'dir. Her aday yalnızca üç aritmetik işlem ve sabit sayıda geçerlilik kontrolü içerdiğinden toplam süre bu açık sayım cinsinden doğrusal kabul edilebilir.
Ek bellek kullanımı küçüktür. Aynı anda yalnızca mevcut rakam kümesinden üretilebilen farklı pozitif tamsayılar kümesi ile birkaç geçici rasyonel ya da kayan noktalı değer tutulur. Asimptotik olarak bu \(O(U)\)'dur; burada \(U\), tek bir dört-rakam seçimi için üretilen farklı pozitif tamsayı sayısıdır ve pratikte küçüktür.
Se eligen cuatro dígitos distintos de \(\{1,2,\dots,9\}\). Usando cada dígito exactamente una vez, junto con las operaciones binarias \(+\), \(-\), \(\times\) y \(\div\), y permitiendo paréntesis, hay que decidir qué conjunto de cuatro dígitos produce la secuencia consecutiva más larga de enteros positivos \(1,2,3,\dots,n\).
Para un conjunto fijo \(D=\{a,b,c,d\}\), sea \(I(D)\) el conjunto de enteros positivos que pueden obtenerse mediante expresiones válidas. La puntuación de \(D\) es
$$L(D)=\max\{n\ge 0:\{1,2,\dots,n\}\subseteq I(D)\}.$$
Debemos maximizar \(L(D)\) entre todos los subconjuntos de cuatro elementos de \(\{1,\dots,9\}\) y devolver los dígitos ganadores en orden ascendente, concatenados.
La clave es que el problema es exhaustivo pero finito. Cada expresión legal queda determinada por unas pocas decisiones discretas: el orden de los dígitos, la elección de tres operadores y la forma del árbol binario completo que fija la parentización. Una vez descrito ese espacio de estados, la tarea deja de ser una búsqueda simbólica abierta y se convierte en una enumeración completa muy pequeña.
Fijemos una tupla ordenada \((x_1,x_2,x_3,x_4)\) formada con los cuatro dígitos elegidos. Cualquier expresión válida que use esos cuatro números exactamente una vez y solo operaciones binarias tiene tres nodos internos de operación y cuatro hojas, así que es un árbol binario completo con cuatro hojas.
Para cuatro hojas existen exactamente cinco formas, que corresponden a las cinco parentizaciones completas
$$(((x_1 \circ_1 x_2)\circ_2 x_3)\circ_3 x_4),$$
$$((x_1\circ_1 (x_2\circ_2 x_3))\circ_3 x_4),$$
$$((x_1\circ_1 x_2)\circ_2 (x_3\circ_3 x_4)),$$
$$x_1\circ_1 ((x_2\circ_2 x_3)\circ_3 x_4),$$
$$x_1\circ_1 (x_2\circ_2 (x_3\circ_3 x_4)).$$
El número \(5\) es el número de Catalan \(C_3\). Esa es la razón matemática por la que hay exactamente cinco patrones de paréntesis que considerar.
Para un conjunto no ordenado \(D\), las hojas pueden colocarse en \(4!=24\) órdenes. Cada uno de los tres nodos internos puede llevar cualquiera de las cuatro operaciones, de modo que hay \(4^3=64\) ternas de operadores. Junto con las cinco formas del árbol, esto da
$$N_{\text{expr}}=4!\cdot 4^3\cdot 5=24\cdot 64\cdot 5=7680$$
expresiones candidatas para un solo conjunto de dígitos.
El barrido exterior recorre los
$$\binom{9}{4}=126$$
subconjuntos de cuatro dígitos de \(\{1,\dots,9\}\), así que el problema completo necesita únicamente
$$126\cdot 7680=967680$$
evaluaciones. Además, esta cuenta es completa: cualquier expresión admisible con cuatro hojas pertenece a un único orden de hojas, a una única asignación de operadores y a una de las cinco formas anteriores. Puede haber descripciones distintas que produzcan el mismo valor numérico, pero eso no afecta porque los resultados se guardan en un conjunto.
La división hace que los valores intermedios no tengan por qué ser enteros, así que el dominio natural es \(\mathbb{Q}\), no \(\mathbb{Z}\). Si
$$x=\frac{p}{q},\qquad y=\frac{r}{s},\qquad q\ne 0,\ s\ne 0,$$
entonces
$$x+y=\frac{ps+rq}{qs},\qquad x-y=\frac{ps-rq}{qs},\qquad xy=\frac{pr}{qs},$$
$$\frac{x}{y}=\frac{ps}{qr}\qquad\text{siempre que }r\ne 0.$$
Cualquier rama que intente dividir entre cero es inválida y se descarta. Un valor final solo cuenta cuando pertenece a \(\mathbb{Z}_{>0}\).
Así se entienden también las implementaciones. La versión en C++ transporta fracciones reducidas, por lo que la integridad se decide exactamente. Las versiones en Python y Java recorren el mismo espacio de expresiones con valores numéricos y aceptan solo resultados finales positivos e íntegros.
Sea \(R(D)\subseteq \mathbb{Q}\) el conjunto de todos los resultados válidos para el conjunto \(D\), y definamos
$$I(D)=R(D)\cap \mathbb{Z}_{>0}.$$
La cantidad que se maximiza es la longitud del prefijo inicial de enteros positivos contenido en \(I(D)\):
$$L(D)=\max\{n\ge 0:\{1,2,\dots,n\}\subseteq I(D)\}.$$
Solo importa el primer hueco. Si \(m\notin I(D)\), entonces la racha no puede pasar de \(m-1\), aunque también existan muchos enteros mayores representables. Por eso, una vez reunidos todos los resultados de \(D\), basta con comprobar \(1,2,3,\dots\) hasta encontrar la primera ausencia.
Tomemos los dígitos ordenados \((1,2,3,4)\) y la terna de operadores \((+,\times,-)\). Las cinco formas del árbol producen
$$((1+2)\times 3)-4=5,$$
$$\bigl(1+(2\times 3)\bigr)-4=3,$$
$$((1+2)\times(3-4))=-3,$$
$$1+\bigl((2\times 3)-4\bigr)=3,$$
$$1+\bigl(2\times(3-4)\bigr)=-1.$$
Los dígitos son los mismos y también el multiconjunto de operaciones, pero los resultados cambian porque la forma del árbol altera el orden de evaluación. Precisamente por eso las cinco formas de Catalan no son una plantilla genérica, sino los casos matemáticos reales del problema. Una de las implementaciones usa además como comprobación el hecho conocido de que \(\{1,2,3,4\}\) alcanza la racha consecutiva de \(1\) a \(28\).
Las implementaciones en C++, Python y Java recorren todas las combinaciones \(a<b<c<d\) dentro de \(\{1,\dots,9\}\). Así, cada conjunto de cuatro dígitos se visita exactamente una vez y la respuesta final ya queda almacenada en orden ascendente.
Para cada conjunto de dígitos, la implementación itera sobre las 24 permutaciones, las 64 ternas de operadores y los cinco patrones de parentización descritos antes. Cada patrón realiza exactamente tres operaciones binarias. Si aparece una división por cero, esa rama se abandona inmediatamente.
La versión en C++ usa fracciones reducidas durante toda la cuenta. Las versiones en Python y Java usan aritmética de punto flotante, pero siguen exactamente la misma enumeración de cinco formas y conservan solo los valores finales que son enteros positivos.
Cada entero positivo aceptado se inserta en un conjunto asociado a los dígitos actuales. Cuando termina la enumeración, la implementación revisa \(1,2,3,\dots\) hasta encontrar el primer entero ausente. Ese punto fija \(L(D)\). Si la nueva puntuación supera la mejor observada hasta entonces, esos dígitos pasan a ser la mejor respuesta provisional.
Para un conjunto de dígitos, el algoritmo realiza exactamente \(24\cdot 64\cdot 5=7680\) evaluaciones candidatas. Sobre los \(\binom{9}{4}=126\) conjuntos posibles, eso suma \(967680\) evaluaciones. Cada una usa solo tres operaciones aritméticas y comprobaciones de validez de costo constante, así que el tiempo total es lineal en ese recuento explícito.
El espacio auxiliar es pequeño. En cada momento solo se mantiene el conjunto de enteros positivos distintos alcanzables con el conjunto actual, más unos pocos valores temporales racionales o de punto flotante. En notación asintótica es \(O(U)\), donde \(U\) es el número de enteros positivos distintos generados por una elección concreta de cuatro dígitos; en la práctica, \(U\) es reducido.
从 \(\{1,2,\dots,9\}\) 中选出四个互不相同的数字。要求每个数字恰好使用一次，只允许使用二元运算 \(+\)、\(-\)、\(\times\)、\(\div\)，并允许加入括号。问题是：哪一个四数字集合能够表示最长的连续正整数序列 \(1,2,3,\dots,n\)。
对固定的数字集合 \(D=\{a,b,c,d\}\)，记 \(I(D)\) 为所有合法表达式能够得到的正整数集合。它的评分定义为
$$L(D)=\max\{n\ge 0:\{1,2,\dots,n\}\subseteq I(D)\}.$$
也就是说，我们要在所有 \(\{1,\dots,9\}\) 的四元子集里找出使 \(L(D)\) 最大的那个集合，并把这四个数字按升序连写输出。
这道题的核心并不是“猜表达式”，而是把所有可能的表达式组织成一个很小而且完全可枚举的离散空间。每个合法表达式都由三部分信息唯一确定：四个数字的排列顺序、三个内部节点使用的运算符、以及四个叶子的满二叉树结构。把这三件事写清楚以后，问题就变成一次完整而有限的枚举。
先固定四个数字的一种有序排列 \((x_1,x_2,x_3,x_4)\)。任何一个“每个数字恰用一次、且只使用二元运算”的表达式，都有四个叶子和三个内部运算节点，因此必然是一棵四叶满二叉树。
四个叶子的满二叉树一共只有五种形状，也就是下面五种完全加括号的形式：
$$(((x_1 \circ_1 x_2)\circ_2 x_3)\circ_3 x_4),$$
$$((x_1\circ_1 (x_2\circ_2 x_3))\circ_3 x_4),$$
$$((x_1\circ_1 x_2)\circ_2 (x_3\circ_3 x_4)),$$
$$x_1\circ_1 ((x_2\circ_2 x_3)\circ_3 x_4),$$
$$x_1\circ_1 (x_2\circ_2 (x_3\circ_3 x_4)).$$
这里的 \(5\) 正好是 Catalan 数 \(C_3\)。这就是为什么四个操作数只有五种需要检查的括号结构，而不是随意更多。
对一个无序数字集合 \(D\)，四个叶子的排列有 \(4!=24\) 种。三个内部节点各自可以选择四种运算之一，所以运算符三元组共有 \(4^3=64\) 种。再乘上五种树形，就得到
$$N_{\text{expr}}=4!\cdot 4^3\cdot 5=24\cdot 64\cdot 5=7680$$
个候选表达式。
外层需要遍历 \(\{1,\dots,9\}\) 中所有四元素子集，总数是
$$\binom{9}{4}=126,$$
因此全题总共只需要
$$126\cdot 7680=967680$$
次候选计算。这个数量足够小，可以直接穷举；同时它又是数学上完备的，因为任何一个合法表达式都一定对应某个数字顺序、某组运算符和上述五种树形之一。不同描述可能得到同一个数值，但这不会造成问题，因为结果最终存入集合，重复值会自动合并。
一旦出现除法，中间结果就不必保持整数，所以自然的状态空间是 \(\mathbb{Q}\)，而不是 \(\mathbb{Z}\)。若
$$x=\frac{p}{q},\qquad y=\frac{r}{s},\qquad q\ne 0,\ s\ne 0,$$
那么四种运算满足
$$x+y=\frac{ps+rq}{qs},\qquad x-y=\frac{ps-rq}{qs},\qquad xy=\frac{pr}{qs},$$
$$\frac{x}{y}=\frac{ps}{qr}\qquad\text{前提是 }r\ne 0.$$
凡是出现除以零的分支都直接判为无效并丢弃。最终结果只有落在 \(\mathbb{Z}_{>0}\) 中时才计入。
这也正好解释了三个实现的数值处理方式。C++ 实现把中间值表示成约分后的分数，所以“是否为整数”是精确判断。Python 和 Java 实现则用浮点数遍历同一个表达式空间，但只在最终值为正且数值上等于整数时才接受。
记 \(R(D)\subseteq \mathbb{Q}\) 为数字集合 \(D\) 的所有合法结果集合，再定义
$$I(D)=R(D)\cap \mathbb{Z}_{>0}.$$
题目真正优化的是 \(I(D)\) 中从 \(1\) 开始的连续前缀长度：
$$L(D)=\max\{n\ge 0:\{1,2,\dots,n\}\subseteq I(D)\}.$$
因此最关键的不变量就是“首个缺失的正整数”。如果某个 \(m\) 不在 \(I(D)\) 里，那么连续前缀最多只能到 \(m-1\)，哪怕更大的很多整数也能表示出来。于是，当一个数字集合的所有表达式都枚举完以后，只要从 \(1\) 开始顺次检查，遇到第一个缺口就能立刻得到评分。
取有序数字 \((1,2,3,4)\)，再取运算符三元组 \((+,\times,-)\)。五种树形分别得到
$$((1+2)\times 3)-4=5,$$
$$\bigl(1+(2\times 3)\bigr)-4=3,$$
$$((1+2)\times(3-4))=-3,$$
$$1+\bigl((2\times 3)-4\bigr)=3,$$
$$1+\bigl(2\times(3-4)\bigr)=-1.$$
可以看到，数字完全相同，运算符多重集也相同，但因为括号结构不同，结果就会改变。这正说明树形是问题状态的一部分，而不是可有可无的排版细节。实现中还利用了一个已知检验点：数字集合 \(\{1,2,3,4\}\) 能够覆盖从 \(1\) 到 \(28\) 的连续整数。
C++、Python 和 Java 三个实现都会遍历 \(\{1,\dots,9\}\) 中所有满足 \(a<b<c<d\) 的四元组合。这样每个四数字集合只会处理一次，而且最终答案天然已经按升序保存。
对每一个数字集合，程序都会遍历 24 种数字排列、64 种运算符三元组以及上面列出的 5 种括号结构。每种结构都只需要 3 次二元运算。如果某一步出现除以零，对应分支立即终止。
C++ 版本在整个过程中维护约分后的分数。Python 和 Java 版本使用浮点运算，但它们探索的是完全相同的五种树形空间，并且只保留最终为正整数的结果。
所有被接受的正整数都会加入当前数字集合对应的结果集合。等该集合的全部表达式枚举完成后，程序从 \(1\) 开始向上检查，找到第一个不存在的整数。这个缺口决定了 \(L(D)\)。如果新分数严格超过当前最优分数，那么这四个数字就成为新的最优答案。
对一个固定数字集合，算法恰好进行 \(24\cdot 64\cdot 5=7680\) 次候选求值。对全部 \(\binom{9}{4}=126\) 个集合，总计为 \(967680\) 次。每次求值只涉及 3 次算术运算和常数次合法性判断，因此总时间复杂度可以直接看成与这个显式计数成正比。
辅助空间开销很小。程序任一时刻只需保存当前数字集合能够产生的不同正整数集合，以及少量临时的分数或浮点数。若把当前集合产生的不同正整数个数记为 \(U\)，则额外空间为 \(O(U)\)；在本题的范围内，\(U\) 很小。
Нужно выбрать четыре различные цифры из \(\{1,2,\dots,9\}\). Используя каждую из них ровно один раз, бинарные операции \(+\), \(-\), \(\times\), \(\div\) и произвольную расстановку скобок, требуется определить, какой набор из четырёх цифр порождает самую длинную последовательность подряд идущих положительных целых чисел \(1,2,3,\dots,n\).
Для фиксированного набора \(D=\{a,b,c,d\}\) обозначим через \(I(D)\) множество всех положительных целых чисел, которые можно получить корректными выражениями. Тогда оценка набора равна
$$L(D)=\max\{n\ge 0:\{1,2,\dots,n\}\subseteq I(D)\}.$$
Значит, нужно максимизировать \(L(D)\) по всем четырёхэлементным подмножествам \(\{1,\dots,9\}\), а затем вывести выигравшие цифры по возрастанию как одну строку из четырёх символов.
Главная идея в том, что задача допускает полный перебор, но только после правильного описания пространства состояний. Каждое допустимое выражение определяется тремя дискретными выборами: порядком цифр, выбором трёх операторов и формой полного бинарного дерева с четырьмя листьями. После такой формулировки задача превращается из неопределённого поиска формул в маленькую и полностью конечную комбинаторную проверку.
Зафиксируем упорядоченную четвёрку \((x_1,x_2,x_3,x_4)\), состоящую из выбранных цифр. Всякое выражение, использующее эти четыре числа ровно по одному разу и только бинарные операции, имеет три внутренних операционных узла и четыре листа. Значит, это полное бинарное дерево с четырьмя листьями.
Для четырёх листьев существует ровно пять форм, то есть ровно пять полных расстановок скобок:
$$(((x_1 \circ_1 x_2)\circ_2 x_3)\circ_3 x_4),$$
$$((x_1\circ_1 (x_2\circ_2 x_3))\circ_3 x_4),$$
$$((x_1\circ_1 x_2)\circ_2 (x_3\circ_3 x_4)),$$
$$x_1\circ_1 ((x_2\circ_2 x_3)\circ_3 x_4),$$
$$x_1\circ_1 (x_2\circ_2 (x_3\circ_3 x_4)).$$
Число \(5\) здесь является числом Каталана \(C_3\). Именно поэтому у четырёх операндов имеется ровно пять действительно разных схем скобок.
Для одного неупорядоченного набора \(D\) существует \(4!=24\) способов упорядочить листья. Каждый из трёх внутренних узлов может быть помечен одной из четырёх операций, поэтому есть \(4^3=64\) тройки операторов. Вместе с пятью формами дерева это даёт
$$N_{\text{expr}}=4!\cdot 4^3\cdot 5=24\cdot 64\cdot 5=7680$$
кандидатных выражений для одного набора цифр.
Внешний перебор идёт по всем
$$\binom{9}{4}=126$$
четырёхэлементным подмножествам \(\{1,\dots,9\}\), так что полная задача требует всего
$$126\cdot 7680=967680$$
вычислений. Эта оценка не только мала, но и математически полна: каждое допустимое выражение с четырьмя листьями принадлежит ровно одному порядку листьев, ровно одной тройке операторов и ровно одной из пяти форм выше. Разные описания могут давать одинаковое числовое значение, но это не мешает, потому что результаты складываются в множество.
Из-за деления промежуточные значения вообще не обязаны быть целыми, так что естественная область вычислений здесь \(\mathbb{Q}\), а не \(\mathbb{Z}\). Если
$$x=\frac{p}{q},\qquad y=\frac{r}{s},\qquad q\ne 0,\ s\ne 0,$$
то
$$x+y=\frac{ps+rq}{qs},\qquad x-y=\frac{ps-rq}{qs},\qquad xy=\frac{pr}{qs},$$
$$\frac{x}{y}=\frac{ps}{qr}\qquad\text{при условии }r\ne 0.$$
Любая ветвь, в которой возникает деление на ноль, признаётся недопустимой и сразу отбрасывается. Финальное значение засчитывается только тогда, когда оно лежит в \(\mathbb{Z}_{>0}\).
Именно так естественно читать и реализации. В версии на C++ промежуточные значения представлены сокращёнными дробями, поэтому проверка на целочисленность точна. Версии на Python и Java обходят то же пространство выражений численно и принимают только те финальные значения, которые положительны и численно совпадают с целым числом.
Пусть \(R(D)\subseteq \mathbb{Q}\) — множество всех корректных результатов для набора \(D\), и пусть
$$I(D)=R(D)\cap \mathbb{Z}_{>0}.$$
Максимизируется длина начального непрерывного префикса положительных целых, содержащегося в \(I(D)\):
$$L(D)=\max\{n\ge 0:\{1,2,\dots,n\}\subseteq I(D)\}.$$
Поэтому важен только первый отсутствующий элемент. Если \(m\notin I(D)\), то непрерывная цепочка уже не может идти дальше \(m-1\), даже если многие большие числа достижимы. Отсюда возникает простой инвариант: после завершения перечисления всех выражений для данного набора достаточно проверять \(1,2,3,\dots\) до первого пропуска.
Возьмём упорядоченные цифры \((1,2,3,4)\) и тройку операторов \((+,\times,-)\). Пять форм дерева дают
$$((1+2)\times 3)-4=5,$$
$$\bigl(1+(2\times 3)\bigr)-4=3,$$
$$((1+2)\times(3-4))=-3,$$
$$1+\bigl((2\times 3)-4\bigr)=3,$$
$$1+\bigl(2\times(3-4)\bigr)=-1.$$
Цифры одинаковы, набор операций одинаков, но результаты различаются, потому что форма дерева меняет порядок вычисления. Именно поэтому пять каталановских схем — это не формальный шаблон, а реальные математические случаи задачи. Одна из реализаций дополнительно использует известный факт, что набор \(\{1,2,3,4\}\) покрывает подряд числа от \(1\) до \(28\), как контрольную проверку.
Реализации на C++, Python и Java проходят по всем комбинациям \(a<b<c<d\) из \(\{1,\dots,9\}\). Тем самым каждый набор из четырёх цифр обрабатывается ровно один раз, а итоговый ответ уже автоматически хранится в возрастающем порядке.
Для каждого набора программа перебирает 24 перестановки цифр, 64 тройки операторов и пять схем расстановки скобок, перечисленных выше. Каждая схема требует ровно трёх бинарных операций. Если на каком-то шаге возникло деление на ноль, соответствующая ветвь сразу прекращается.
Версия на C++ выполняет вычисления на сокращённых дробях. Версии на Python и Java используют числа с плавающей точкой, но исследуют то же самое пространство из пяти форм и сохраняют только положительные целочисленные финальные значения.
Каждое принятое положительное целое число добавляется в множество результатов для текущего набора цифр. После завершения перебора программа идёт вверх от \(1\), пока не встретит первое отсутствующее число. Этот момент определяет \(L(D)\). Если новая оценка строго больше текущей лучшей, соответствующие цифры становятся новым кандидатом на ответ.
Для одного набора цифр алгоритм выполняет ровно \(24\cdot 64\cdot 5=7680\) кандидатных вычислений. По всем \(\binom{9}{4}=126\) наборам это даёт \(967680\) вычислений. Каждое из них состоит всего из трёх арифметических операций и нескольких проверок постоянной стоимости, так что общее время фактически линейно по этому явному числу.
Дополнительная память невелика. В каждый момент времени хранится только множество различных положительных целых чисел, достижимых для текущего набора, и несколько временных рациональных или вещественных значений. В асимптотической записи это \(O(U)\), где \(U\) — число различных положительных целых, порождаемых одним конкретным выбором четырёх цифр; на практике \(U\) остаётся небольшим.
نختار أربعة أرقام مختلفة من المجموعة \(\{1,2,\dots,9\}\). ثم نستخدم كل رقم مرة واحدة بالضبط مع العمليات الثنائية \(+\) و\(-\) و\(\times\) و\(\div\)، مع السماح بوضع الأقواس. المطلوب هو تحديد أي مجموعة من أربعة أرقام تستطيع توليد أطول سلسلة متتالية من الأعداد الصحيحة الموجبة \(1,2,3,\dots,n\).
للمجموعة الثابتة \(D=\{a,b,c,d\}\)، نرمز بـ \(I(D)\) إلى مجموعة الأعداد الصحيحة الموجبة التي يمكن الوصول إليها بتعبيرات صالحة. وتُعرَّف درجة هذه المجموعة بـ
$$L(D)=\max\{n\ge 0:\{1,2,\dots,n\}\subseteq I(D)\}.$$
إذن نريد تعظيم \(L(D)\) على جميع المجموعات ذات الأربعة عناصر من \(\{1,\dots,9\}\)، ثم إخراج الأرقام الفائزة بترتيب تصاعدي على هيئة سلسلة من أربع خانات.
فكرة الحل ليست التخمين العشوائي للتعابير، بل وصف جميع التعابير الممكنة بوصفٍ تركيبي صغير ومغلق. فكل تعبير صالح يتحدد بثلاثة اختيارات منفصلة: ترتيب الأرقام الأربعة، واختيار ثلاثة معاملات، واختيار شكل شجرة ثنائية كاملة ذات أربع أوراق. وما إن نكتب هذا الفضاء بوضوح حتى تتحول المسألة إلى تعداد كامل محدود بدلاً من بحث رمزي مفتوح.
لنثبت ترتيبًا معينًا للأرقام على الصورة \((x_1,x_2,x_3,x_4)\). أي تعبير صالح يستخدم هذه القيم الأربع مرة واحدة فقط، ولا يستعمل إلا عمليات ثنائية، سيكون له ثلاث عقد داخلية للعمليات وأربع أوراق. أي إنه شجرة ثنائية كاملة ذات أربع أوراق.
ولهذه الحالة خمس بُنى فقط، وهي صور التحويط الكامل الآتية:
$$(((x_1 \circ_1 x_2)\circ_2 x_3)\circ_3 x_4),$$
$$((x_1\circ_1 (x_2\circ_2 x_3))\circ_3 x_4),$$
$$((x_1\circ_1 x_2)\circ_2 (x_3\circ_3 x_4)),$$
$$x_1\circ_1 ((x_2\circ_2 x_3)\circ_3 x_4),$$
$$x_1\circ_1 (x_2\circ_2 (x_3\circ_3 x_4)).$$
العدد \(5\) هنا هو عدد كاتالان \(C_3\). لذلك فعدد أشكال الأقواس التي يجب فحصها هو خمسة بالضبط، لا أكثر ولا أقل.
بالنسبة إلى مجموعة غير مرتبة \(D\)، توجد \(4!=24\) طريقة لترتيب الأوراق. ولكل واحدة من العقد الداخلية الثلاث إمكان اختيار واحدة من أربع عمليات، ولذلك يوجد \(4^3=64\) ثلاثيات للعمليات. ومع أشكال الأشجار الخمسة نحصل على
$$N_{\text{expr}}=4!\cdot 4^3\cdot 5=24\cdot 64\cdot 5=7680$$
تعبيرًا مرشحًا لمجموعة واحدة من الأرقام.
أما المسح الخارجي فيمر على جميع الاختيارات
$$\binom{9}{4}=126$$
لأربعة أرقام مختلفة من \(\{1,\dots,9\}\)، ومن ثم فالمسألة كلها تحتاج إلى
$$126\cdot 7680=967680$$
تقييمًا فقط. وهذا العدد ليس صغيرًا فحسب، بل كامل رياضيًا أيضًا، لأن كل تعبير مقبول لا بد أن ينتمي إلى ترتيب واحد للأوراق، وإسناد واحد للعمليات، وشكل واحد من الأشكال الخمسة أعلاه. وقد تقود أوصاف مختلفة إلى القيمة العددية نفسها، لكن هذا لا يسبب مشكلة لأن النتائج تُجمَع في مجموعة دون تكرار.
بسبب القسمة، قد لا تبقى القيم الوسيطة أعدادًا صحيحة. لذا فالمجال الطبيعي للحساب هو \(\mathbb{Q}\) لا \(\mathbb{Z}\). إذا كان
$$x=\frac{p}{q},\qquad y=\frac{r}{s},\qquad q\ne 0,\ s\ne 0,$$
فإن العمليات الأربع هي
$$x+y=\frac{ps+rq}{qs},\qquad x-y=\frac{ps-rq}{qs},\qquad xy=\frac{pr}{qs},$$
$$\frac{x}{y}=\frac{ps}{qr}\qquad (r\ne 0).$$
وأي فرع يتطلب قسمة على الصفر يُعد غير صالح ويُهمل فورًا. أما النتيجة النهائية فلا تُحتسب إلا إذا كانت ضمن \(\mathbb{Z}_{>0}\).
وهذا يفسر كذلك أسلوب التنفيذ. فتنفيذ C++ يحمل القيم الوسيطة على هيئة كسور مختزلة، لذا يكون التحقق من كون النتيجة عددًا صحيحًا دقيقًا تمامًا. أما تنفيذا Python وJava فيستكشفان فضاء التعابير نفسه عدديًا، لكنهما يحتفظان فقط بالقيم النهائية الموجبة التي تساوي عددًا صحيحًا عدديًا.
لنرمز بـ \(R(D)\subseteq \mathbb{Q}\) إلى مجموعة جميع النتائج الصالحة للمجموعة \(D\)، ثم نعرّف
$$I(D)=R(D)\cap \mathbb{Z}_{>0}.$$
والكمية التي نريد تعظيمها هي طول المقطع الأولي المتصل من الأعداد الصحيحة الموجبة داخل \(I(D)\):
$$L(D)=\max\{n\ge 0:\{1,2,\dots,n\}\subseteq I(D)\}.$$
إذًا الشيء الحاسم هو أول عدد موجب مفقود. فإذا كان \(m\notin I(D)\)، فلا يمكن للسلسلة المتصلة أن تمتد إلى ما بعد \(m-1\)، مهما وُجدت أعداد أكبر قابلة للتوليد. لذلك، بعد جمع جميع النتائج الخاصة بالمجموعة \(D\)، يكفي فحص \(1,2,3,\dots\) تصاعديًا حتى تظهر أول فجوة.
خذ الأرقام المرتبة \((1,2,3,4)\) وثلاثية العمليات \((+,\times,-)\). تعطي أشكال الأشجار الخمسة النتائج الآتية:
$$((1+2)\times 3)-4=5,$$
$$\bigl(1+(2\times 3)\bigr)-4=3,$$
$$((1+2)\times(3-4))=-3,$$
$$1+\bigl((2\times 3)-4\bigr)=3,$$
$$1+\bigl(2\times(3-4)\bigr)=-1.$$
الأرقام نفسها هي نفسها، وحتى مجموعة العمليات هي نفسها، لكن النتائج تختلف لأن شكل الشجرة يغيّر ترتيب التنفيذ. ولهذا فالأشكال الخمسة المرتبطة بأعداد كاتالان ليست قالبًا شكليًا، بل هي الحالات الرياضية الفعلية التي يجب تعدادها. كما أن أحد التنفيذات يستخدم الحقيقة المعروفة أن المجموعة \(\{1,2,3,4\}\) تولّد السلسلة من \(1\) إلى \(28\) بوصفها نقطة تحقق.
تمر تنفيذات C++ وPython وJava على جميع التركيبات \(a<b<c<d\) من \(\{1,\dots,9\}\). وبهذا تُفحَص كل مجموعة مكوّنة من أربعة أرقام مرة واحدة فقط، وتبقى الإجابة النهائية محفوظة تلقائيًا بالترتيب التصاعدي المطلوب.
لكل مجموعة أرقام، يدور التنفيذ على 24 تبديلًا للأرقام، و64 ثلاثية للعمليات، والأشكال الخمسة للأقواس المذكورة أعلاه. وكل شكل يحتاج إلى ثلاث عمليات ثنائية فقط. وإذا ظهر في أي خطوة قسمة على الصفر فإن ذلك الفرع يُوقَف فورًا.
نسخة C++ تستخدم كسورًا مختزلة طوال الحساب. أما نسختا Python وJava فتستخدمان الأعداد العشرية، لكنهما تتبعان فضاء التعداد نفسه ذي الأشكال الخمسة ولا تقبلان إلا النتائج النهائية التي تكون أعدادًا صحيحة موجبة.
كل عدد صحيح موجب مقبول يُضاف إلى مجموعة النتائج الخاصة بالأرقام الحالية. وبعد انتهاء التعداد، يفحص التنفيذ القيم \(1,2,3,\dots\) تصاعديًا حتى يجد أول عدد غير موجود. ومن هذه الفجوة تُستخرج القيمة \(L(D)\). وإذا كانت الدرجة الجديدة أكبر من أفضل درجة سابقة، تصبح هذه الأرقام هي الجواب الأفضل الحالي.
بالنسبة إلى مجموعة أرقام واحدة، ينفذ الخوارزمية بدقة \(24\cdot 64\cdot 5=7680\) تقييمًا مرشحًا. وعبر جميع المجموعات \(\binom{9}{4}=126\)، يصبح المجموع \(967680\) تقييمًا. وكل تقييم يتضمن فقط ثلاث عمليات حسابية وعددًا ثابتًا من اختبارات الصلاحية، لذلك فالزمن الكلي يتناسب عمليًا مع هذا العدد الصريح.
أما الذاكرة الإضافية فهي صغيرة. ففي أي لحظة يحتفظ التنفيذ فقط بمجموعة الأعداد الصحيحة الموجبة المختلفة التي أمكن توليدها من المجموعة الحالية، إضافة إلى عدد قليل من القيم المؤقتة الكسرية أو العشرية. وبصياغةٍ لا-أسيمبتوطية هذا يساوي \(O(U)\)، حيث \(U\) هو عدد الأعداد الصحيحة الموجبة المختلفة المتولدة من اختيار واحد للأربعة أرقام، وهو صغير عمليًا.