The equation \(4^t = 2^t + k\) defines the partitions considered in this problem. If we set \(m = 2^t\), then \(4^t = m^2\), so every valid partition must satisfy
$$m^2 = m + k,\qquad k = m(m-1).$$
Because the partition is required to be integral, \(m = 2^t\) must itself be an integer. Conversely, every integer \(m \ge 2\) gives one valid partition by taking \(t = \log_2 m\). Thus the problem is really about the sequence \(k_m = m(m-1)\) for \(m=2,3,4,\dots\).
A partition is called perfect when \(t\) is an integer. In the new parameterization that means exactly that \(m\) is a power of two. For a bound \(K\), the quantity \(P(K)\) is the proportion of partitions with \(k \le K\) that are perfect. The goal is to find the smallest \(K\) for which \(P(K) < \frac{1}{12345}\).
The key simplification is that the equation can be indexed by the integer \(m=2^t\). Once that is done, the only special values are the powers of two, so the whole problem becomes a discrete counting argument.
Start from
$$4^t = 2^t + k.$$
With \(m = 2^t\), we get \(4^t = (2^t)^2 = m^2\), so
$$m^2 = m + k,$$
and therefore
$$k = m^2 - m = m(m-1).$$
This already explains why the implementations never work with real exponents directly. They only need the integer parameter \(m\), because the exponent can always be recovered as \(t = \log_2 m\).
If \(m\) is an integer at least \(2\), then \(t=\log_2 m\) is a real number and
$$4^t = (2^t)^2 = m^2,\qquad 2^t = m,$$
so the equation becomes
$$m^2 = m + m(m-1).$$
This produces a valid integer partition with \(k=m(m-1)\). The mapping is one-to-one, and the associated \(k\)-values are strictly increasing because
$$k_{m+1} - k_m = (m+1)m - m(m-1) = 2m > 0.$$
That monotonicity is crucial: once we know the first \(m\) at which the target ratio falls below the threshold, the corresponding \(k=m(m-1)\) is automatically the smallest valid answer.
A partition is perfect exactly when \(t\) is an integer. Since \(m=2^t\), this happens exactly when \(m\) is a power of two:
$$m \in \{2,4,8,16,\dots\}.$$
So among the integers \(2 \le m \le M\), the number of perfect partitions is simply the number of powers of two not exceeding \(M\):
$$C(M)=\left\lfloor \log_2 M \right\rfloor.$$
There is no deeper recurrence hiding here. The perfect cases appear at very sparse, completely explicit positions.
For a fixed upper bound \(K\), define
$$M(K)=\max\{m \ge 2 : m(m-1)\le K\}.$$
Because \(m \mapsto m(m-1)\) is strictly increasing, the partitions counted by \(P(K)\) are exactly those with
$$2 \le m \le M(K).$$
Hence the total number of partitions up to \(K\) is
$$M(K)-1,$$
and the number of perfect ones is
$$\left\lfloor \log_2 M(K) \right\rfloor.$$
Therefore
$$P(K)=\frac{\left\lfloor \log_2 M(K) \right\rfloor}{M(K)-1}.$$
The ratio does not change between consecutive values \(k_m\) and \(k_{m+1}\), so it is enough to test the prefixes indexed by \(M\).
Let the target threshold be \(\frac{1}{d}\). We want the smallest \(K\) such that
$$P(K) < \frac{1}{d}.$$
Writing everything in terms of \(M=M(K)\) gives
$$\frac{\left\lfloor \log_2 M \right\rfloor}{M-1} < \frac{1}{d}$$
which is equivalent to the integer comparison
$$d \left\lfloor \log_2 M \right\rfloor < M-1.$$
So the mathematical problem reduces to this:
Find the smallest integer \(M \ge 2\) such that
$$d \left\lfloor \log_2 M \right\rfloor < M-1,$$
and then return
$$K = M(M-1).$$
This is exactly the condition tested by the implementations.
The checkpoint threshold \(\frac{1}{3}\) is a useful example. At \(M=10\) the perfect values are \(2,4,8\), so
$$P = \frac{3}{9} = \frac{1}{3},$$
which does not satisfy the strict inequality. At \(M=11\) the perfect count is still \(3\), but now
$$P = \frac{3}{10} < \frac{1}{3},$$
so the first corresponding bound on \(k\) is
$$K = 11 \cdot 10 = 110.$$
The second checkpoint \(\frac{1}{10}\) behaves the same way. At \(M=51\),
$$P = \frac{5}{50} = \frac{1}{10},$$
so the threshold has not yet been crossed. At \(M=52\),
$$P = \frac{5}{51} < \frac{1}{10},$$
and the corresponding value is
$$K = 52 \cdot 51 = 2652.$$
These examples show why the code scans \(M\) in order and checks the inequality after updating the perfect-count state.
The C++, Python, and Java implementations all follow the same discrete process. They never evaluate logarithms, never search over real \(t\), and never build a list of partitions explicitly.
The scan runs through \(m=2,3,4,\dots\). Along the way the implementation keeps three pieces of information:
\(m\), the current integer parameter; the number of perfect partitions already seen; and the next power of two at which that perfect count must increase. After processing a given \(m\), the invariant is that the stored perfect count equals the number of powers of two in the interval \([2,m]\).
Whenever the current \(m\) reaches the next power of two, the perfect counter is incremented and the next threshold is doubled. This exactly mirrors the formula
$$C(M)=\left\lfloor \log_2 M \right\rfloor,$$
but it avoids repeated logarithm calls and avoids any dependence on floating-point rounding.
At each step, if \(c\) denotes the current number of perfect partitions seen so far, the implementation checks
$$c \cdot d < m-1.$$
As soon as it becomes true, the algorithm returns
$$m(m-1).$$
That returned value is correct because the scan visits the integers \(m\) in increasing order and \(m(m-1)\) is strictly increasing. The first successful \(m\) therefore yields the smallest possible bound on \(k\).
The shared algorithm is identical in all three languages. The C++ implementation also allows a configurable denominator and checks the sample thresholds \(\frac{1}{3}\) and \(\frac{1}{10}\) before the main computation. Python uses arbitrary-precision integers automatically. The C++ version widens the comparison product explicitly, and the Java version stays within 64-bit arithmetic for the default problem range.
If \(M_\star\) is the first integer satisfying
$$d \left\lfloor \log_2 M_\star \right\rfloor < M_\star-1,$$
then the running time is \(O(M_\star)\), because each loop iteration performs only a constant amount of work. The memory usage is \(O(1)\): the algorithm stores just a few integers and no growing tables.
For this specific problem the search is efficient because the crossing occurs roughly when \(M\) is on the order of \(d \log d\), so a simple linear scan is entirely adequate. The main mathematical gain is not an advanced data structure but the correct reparameterization of the equation.
Die Gleichung \(4^t = 2^t + k\) beschreibt die in dieser Aufgabe betrachteten Partitionen. Setzt man \(m = 2^t\), dann ist \(4^t = m^2\), also muss jede gültige Partition die Form
$$m^2 = m + k,\qquad k = m(m-1)$$
haben. Da die Partition ganzzahlig sein soll, muss \(m = 2^t\) selbst eine ganze Zahl sein. Umgekehrt liefert jede ganze Zahl \(m \ge 2\) durch \(t=\log_2 m\) genau eine gültige Partition. Damit reduziert sich das Problem auf die Folge \(k_m=m(m-1)\) für \(m=2,3,4,\dots\).
Eine Partition heißt perfekt, wenn \(t\) ganzzahlig ist. In der neuen Parametrisierung bedeutet das genau, dass \(m\) eine Zweierpotenz ist. Für eine Schranke \(K\) bezeichnet \(P(K)\) den Anteil perfekter Partitionen unter allen Partitionen mit \(k \le K\). Gesucht ist das kleinste \(K\), für das \(P(K) < \frac{1}{12345}\) gilt.
Der entscheidende Schritt besteht darin, die Aufgabe nicht über reelle Exponenten \(t\), sondern über die ganze Zahl \(m=2^t\) zu beschreiben. Danach sind die einzigen besonderen Werte die Zweierpotenzen, und das gesamte Problem wird zu einer diskreten Zählung.
Ausgehend von
$$4^t = 2^t + k$$
setzen wir \(m=2^t\). Dann folgt \(4^t=(2^t)^2=m^2\), also
$$m^2 = m + k,$$
und damit
$$k = m^2 - m = m(m-1).$$
Genau deshalb arbeiten die Implementierungen nicht direkt mit reellen Exponenten. Die gesamte Struktur der Aufgabe steckt bereits in der ganzzahligen Variablen \(m\).
Ist \(m \ge 2\) eine ganze Zahl, dann ist \(t=\log_2 m\) reell und
$$4^t = (2^t)^2 = m^2,\qquad 2^t = m.$$
Die Gleichung wird somit zu
$$m^2 = m + m(m-1).$$
Jedes solche \(m\) erzeugt also eine gültige Partition mit \(k=m(m-1)\). Außerdem wachsen diese \(k\)-Werte streng monoton, denn
$$k_{m+1}-k_m=(m+1)m-m(m-1)=2m>0.$$
Darum genügt es, das erste passende \(m\) zu finden. Das zugehörige \(k\) ist dann automatisch die kleinste gesuchte Schranke.
Perfekt heißt: \(t\) ist eine ganze Zahl. Wegen \(m=2^t\) ist das genau dann der Fall, wenn \(m\) eine Zweierpotenz ist:
$$m \in \{2,4,8,16,\dots\}.$$
Unter allen ganzen Zahlen \(2 \le m \le M\) ist die Anzahl perfekter Partitionen daher einfach die Anzahl der Zweierpotenzen bis \(M\):
$$C(M)=\left\lfloor \log_2 M \right\rfloor.$$
Mehr ist nicht nötig: Die perfekten Fälle liegen an explizit bekannten Positionen.
Für eine feste Obergrenze \(K\) definieren wir
$$M(K)=\max\{m \ge 2 : m(m-1)\le K\}.$$
Da \(m(m-1)\) streng wächst, werden in \(P(K)\) genau die Partitionen mit
$$2 \le m \le M(K)$$
gezählt. Also beträgt die Gesamtzahl dieser Partitionen
$$M(K)-1,$$
und die Zahl der perfekten Partitionen ist
$$\left\lfloor \log_2 M(K) \right\rfloor.$$
Daher gilt
$$P(K)=\frac{\left\lfloor \log_2 M(K) \right\rfloor}{M(K)-1}.$$
Zwischen zwei aufeinanderfolgenden Werten \(k_m\) und \(k_{m+1}\) ändert sich diese Quote nicht, daher reicht es völlig, die Präfixe nach \(M\) zu testen.
Sei die Zielschranke \(\frac{1}{d}\). Gesucht ist das kleinste \(K\) mit
$$P(K) < \frac{1}{d}.$$
Mit \(M=M(K)\) wird daraus
$$\frac{\left\lfloor \log_2 M \right\rfloor}{M-1} < \frac{1}{d},$$
also äquivalent
$$d \left\lfloor \log_2 M \right\rfloor < M-1.$$
Damit ist die Aufgabe vollständig diskret geworden:
Finde das kleinste \(M \ge 2\) mit
$$d \left\lfloor \log_2 M \right\rfloor < M-1,$$
und gib anschließend
$$K = M(M-1)$$
zurück. Genau diese Bedingung prüfen die Implementierungen.
Die Prüfschranke \(\frac{1}{3}\) illustriert den Mechanismus sehr gut. Für \(M=10\) sind die perfekten Werte \(2,4,8\), also
$$P=\frac{3}{9}=\frac{1}{3}.$$
Die strikte Ungleichung ist noch nicht erfüllt. Bei \(M=11\) bleibt die Zahl perfekter Partitionen \(3\), aber nun gilt
$$P=\frac{3}{10} < \frac{1}{3},$$
also ist die erste passende Schranke
$$K=11\cdot 10=110.$$
Ebenso für \(\frac{1}{10}\): Bei \(M=51\) ist
$$P=\frac{5}{50}=\frac{1}{10},$$
also noch kein Unterschreiten. Erst bei \(M=52\) gilt
$$P=\frac{5}{51} < \frac{1}{10},$$
und daraus folgt
$$K=52\cdot 51=2652.$$
Diese Beispiele zeigen genau, warum der Code \(M\) in aufsteigender Reihenfolge durchläuft und die Bedingung nach jeder Aktualisierung prüft.
Die C++-, Python- und Java-Implementierungen benutzen denselben diskreten Kern. Es werden weder Logarithmen ausgewertet noch reelle \(t\)-Werte durchsucht noch Partitionen explizit gespeichert.
Die Schleife läuft über \(m=2,3,4,\dots\). Parallel dazu speichert die Implementierung drei Größen: das aktuelle \(m\), die Anzahl der bisher gesehenen perfekten Partitionen und die nächste Zweierpotenz, bei der dieser Zähler erhöht werden muss. Nach der Verarbeitung eines bestimmten \(m\) gilt als Invariante: Der gespeicherte Zähler ist genau die Anzahl der Zweierpotenzen in \([2,m]\).
Sobald \(m\) die nächste Zweierpotenz erreicht, wird der Perfekt-Zähler um eins erhöht und die nächste Schwelle verdoppelt. Das ist exakt dieselbe Information wie in
$$C(M)=\left\lfloor \log_2 M \right\rfloor,$$
nur ohne wiederholte Logarithmusberechnungen und ohne Rundungsrisiken.
In jedem Schleifendurchlauf wird mit \(c\) als aktuellem Perfekt-Zähler die ganzzahlige Bedingung
$$c \cdot d < m-1$$
geprüft. Sobald sie erfüllt ist, gibt der Algorithmus
$$m(m-1)$$
zurück. Die Korrektheit folgt direkt daraus, dass \(m\) aufsteigend durchlaufen wird und \(m(m-1)\) streng wächst.
Der mathematische Kern ist in allen drei Sprachen identisch. Die C++-Version erlaubt zusätzlich einen frei wählbaren Nenner und überprüft vor der Hauptrechnung die beiden Beispielschranken \(\frac{1}{3}\) und \(\frac{1}{10}\). Python verwendet automatisch beliebig große Ganzzahlen. C++ verbreitert das Vergleichsprodukt explizit, und Java bleibt für den Standardfall innerhalb des 64-Bit-Bereichs.
Ist \(M_\star\) die erste ganze Zahl mit
$$d \left\lfloor \log_2 M_\star \right\rfloor < M_\star-1,$$
dann beträgt die Laufzeit \(O(M_\star)\), weil jede Iteration nur konstante Arbeit leistet. Der Speicherverbrauch ist \(O(1)\), da nur wenige ganze Zahlen gehalten werden.
Für diese Aufgabe ist das effizient genug, weil der gesuchte Bereich grob bei einer Größenordnung von \(d \log d\) liegt. Der eigentliche Gewinn kommt nicht von komplizierten Datenstrukturen, sondern von der richtigen Umformulierung der Gleichung.
Bu problemde incelenen bölmeler \(4^t = 2^t + k\) denkleminden geliyor. \(m = 2^t\) yazarsak \(4^t = m^2\) olur ve her geçerli bölme
$$m^2 = m + k,\qquad k = m(m-1)$$
biçimine indirgenir. Bölmenin tam sayılı olması istendiği için \(m = 2^t\) değerinin de tam sayı olması gerekir. Tersine, her \(m \ge 2\) tam sayısı için \(t=\log_2 m\) alınarak tam bir bölme elde edilir. Böylece problem aslında \(m=2,3,4,\dots\) için \(k_m=m(m-1)\) dizisini incelemektedir.
Bir bölme, \(t\) tam sayıysa mükemmel olarak adlandırılır. Bu yeni parametreleştirmede bu, tam olarak \(m\)'nin bir 2 kuvveti olması demektir. \(K\) sınırı için \(P(K)\), \(k \le K\) olan bölmeler arasında mükemmel olanların oranıdır. Aranan şey, \(P(K) < \frac{1}{12345}\) koşulunu sağlayan en küçük \(K\)'dır.
Asıl sadeleştirme, problemi doğrudan gerçek üs \(t\) üzerinden değil, \(m=2^t\) tam sayısı üzerinden ifade etmektir. Bunu yaptıktan sonra özel durumların hepsi 2 kuvvetlerine iner ve problem saf bir sayma problemine dönüşür.
Başlangıç denklemi
$$4^t = 2^t + k$$
olsun. \(m=2^t\) yazarsak \(4^t=(2^t)^2=m^2\) elde edilir, yani
$$m^2 = m + k,$$
dolayısıyla
$$k = m^2 - m = m(m-1).$$
Bu yüzden uygulamalar gerçek üslerle doğrudan uğraşmaz. Bütün yapı, tek bir tam sayı parametresi olan \(m\) içinde saklıdır.
\(m \ge 2\) bir tam sayıysa \(t=\log_2 m\) gerçel sayıdır ve
$$4^t=(2^t)^2=m^2,\qquad 2^t=m$$
olur. Böylece denklem
$$m^2 = m + m(m-1)$$
şeklini alır. Yani her \(m\) için bir geçerli bölme vardır ve karşılık gelen değer
$$k_m = m(m-1)$$
olur. Ayrıca bu dizi sıkı biçimde artandır, çünkü
$$k_{m+1}-k_m=(m+1)m-m(m-1)=2m>0.$$
Bu tekdüzelik çok önemlidir: eşiği ilk kez sağlayan \(m\) bulunduğunda, onun ürettiği \(k\) değeri otomatik olarak en küçük cevaptır.
Mükemmel olmak, \(t\)'nin tam sayı olması demektir. \(m=2^t\) olduğuna göre bu da tam olarak \(m\)'nin bir 2 kuvveti olmasıyla eşdeğerdir:
$$m \in \{2,4,8,16,\dots\}.$$
Dolayısıyla \(2 \le m \le M\) aralığında mükemmel bölme sayısı, \(M\)'yi aşmayan 2 kuvvetlerinin sayısıdır:
$$C(M)=\left\lfloor \log_2 M \right\rfloor.$$
Burada gizli bir özyineleme yoktur; mükemmel durumlar açıkça bilinen, seyrek noktalarda ortaya çıkar.
Sabit bir \(K\) üst sınırı için
$$M(K)=\max\{m \ge 2 : m(m-1)\le K\}$$
tanımını yapalım. \(m(m-1)\) fonksiyonu sıkı biçimde arttığı için \(P(K)\) içinde sayılan bölmeler tam olarak
$$2 \le m \le M(K)$$
koşulunu sağlayanlardır. Bu nedenle toplam bölme sayısı
$$M(K)-1,$$
mükemmel bölme sayısı ise
$$\left\lfloor \log_2 M(K) \right\rfloor$$
olur. O halde
$$P(K)=\frac{\left\lfloor \log_2 M(K) \right\rfloor}{M(K)-1}.$$
Oran, ardışık iki \(k_m\) değeri arasında değişmez. Bu yüzden bütün problem, artan \(M\) öneklerini test etmekten ibarettir.
Hedef eşik \(\frac{1}{d}\) olsun. Aradığımız şey
$$P(K) < \frac{1}{d}$$
koşulunu sağlayan en küçük \(K\)'dır. \(M=M(K)\) yazınca bu
$$\frac{\left\lfloor \log_2 M \right\rfloor}{M-1} < \frac{1}{d}$$
olur; bu da tam sayı karşılaştırması olarak
$$d \left\lfloor \log_2 M \right\rfloor < M-1$$
ile eşdeğerdir. Sonuç olarak problem şu hale gelir:
\(d \left\lfloor \log_2 M \right\rfloor < M-1\) sağlayan en küçük \(M \ge 2\) bulunur ve sonra
$$K=M(M-1)$$
döndürülür. Kodun doğrudan test ettiği koşul tam olarak budur.
\(\frac{1}{3}\) eşiği, sıkı eşitsizliğin neden önemli olduğunu açıkça gösterir. \(M=10\) için mükemmel değerler \(2,4,8\) olduğundan
$$P=\frac{3}{9}=\frac{1}{3}$$
elde edilir; bu henüz yeterli değildir. \(M=11\) olduğunda mükemmel sayı hâlâ \(3\) tanedir ama artık
$$P=\frac{3}{10} < \frac{1}{3}$$
olur. Bu durumda ilk uygun sınır
$$K=11\cdot 10=110$$
şeklindedir.
\(\frac{1}{10}\) için de aynı yapı görülür. \(M=51\) iken
$$P=\frac{5}{50}=\frac{1}{10}$$
olduğu için henüz geçiş yoktur. \(M=52\) olduğunda ise
$$P=\frac{5}{51} < \frac{1}{10},$$
dolayısıyla
$$K=52\cdot 51=2652$$
elde edilir. Uygulamadaki doğrulama örnekleri tam olarak bunlardır.
C++, Python ve Java uygulamaları aynı ayrık algoritmayı uygular. Hiçbiri kayan noktalı logaritma hesaplaması yapmaz, gerçek üsleri taramaz ve bölmeleri tek tek depolamaz.
Tarama \(m=2,3,4,\dots\) şeklinde ilerler. Aynı anda üç bilgi tutulur: mevcut \(m\), o ana kadar görülen mükemmel bölme sayısı ve bu sayının artacağı bir sonraki 2 kuvveti. Belirli bir \(m\) işlendiğinde korunan invariant şudur: saklanan mükemmel sayaç, \([2,m]\) aralığındaki 2 kuvvetlerinin sayısına eşittir.
Mevcut \(m\), bir sonraki 2 kuvvetine ulaştığında mükemmel sayaç bir artırılır ve yeni eşik ikiyle çarpılır. Bu mekanizma
$$C(M)=\left\lfloor \log_2 M \right\rfloor$$
formülüyle aynı bilgiyi taşır; ancak tekrarlı logaritma çağrılarından ve yuvarlama sorunlarından kaçınır.
Her adımda, o ana kadarki mükemmel bölme sayısını \(c\) ile gösterirsek, şu tam sayı eşitsizliği sınanır:
$$c \cdot d < m-1.$$
İlk kez doğru olduğunda algoritma
$$m(m-1)$$
değerini döndürür. Bunun doğru olmasının nedeni, taramanın artan \(m\) sırasını izlemesi ve \(m(m-1)\) değerlerinin de sıkı biçimde artmasıdır.
Matematiksel çekirdek üç dilde de aynıdır. C++ sürümü ayrıca paydanın dışarıdan verilmesine izin verir ve ana hesaplamadan önce \(\frac{1}{3}\) ile \(\frac{1}{10}\) örneklerini sınar. Python keyfi büyüklükte tamsayıları doğal olarak kullanır. C++ karşılaştırma çarpımını açıkça genişletir; Java sürümü ise varsayılan problem aralığında 64 bit sınırları içinde kalır.
\(M_\star\),
$$d \left\lfloor \log_2 M_\star \right\rfloor < M_\star-1$$
koşulunu sağlayan ilk tam sayı olsun. Çalışma süresi \(O(M_\star)\)'dır; çünkü her döngü adımı sabit miktarda iş yapar. Bellek kullanımı \(O(1)\)'dir; büyüyen bir tablo ya da dizi tutulmaz.
Bu problemde doğrusal tarama yeterince hızlıdır; çünkü geçiş noktası kabaca \(d \log d\) ölçeğinde ortaya çıkar. Esas kazanç, gelişmiş veri yapılarından değil, denklemin doğru biçimde yeniden yazılmasından gelir.
La ecuación \(4^t = 2^t + k\) define las particiones estudiadas en este problema. Si escribimos \(m = 2^t\), entonces \(4^t = m^2\), de modo que toda partición válida debe satisfacer
$$m^2 = m + k,\qquad k = m(m-1).$$
Como la partición debe ser entera, \(m = 2^t\) también tiene que ser un entero. A la inversa, cada entero \(m \ge 2\) produce una partición válida tomando \(t=\log_2 m\). Por eso el problema real está indexado por la sucesión \(k_m=m(m-1)\) para \(m=2,3,4,\dots\).
Una partición es perfecta cuando \(t\) es un entero. En la nueva parametrización eso equivale exactamente a que \(m\) sea una potencia de dos. Para una cota \(K\), \(P(K)\) representa la proporción de particiones perfectas entre todas las particiones con \(k \le K\). Se pide el menor \(K\) tal que \(P(K) < \frac{1}{12345}\).
La simplificación decisiva consiste en reescribir todo en función del entero \(m=2^t\). Una vez hecho eso, los únicos valores especiales son las potencias de dos, y el problema se convierte en un conteo discreto.
Partimos de
$$4^t = 2^t + k.$$
Al poner \(m=2^t\), obtenemos \(4^t=(2^t)^2=m^2\), así que
$$m^2 = m + k,$$
y por lo tanto
$$k = m^2 - m = m(m-1).$$
Esta es la razón por la que las implementaciones no trabajan directamente con exponentes reales. Toda la estructura relevante está contenida en el parámetro entero \(m\).
Si \(m \ge 2\) es entero, entonces \(t=\log_2 m\) es real y
$$4^t=(2^t)^2=m^2,\qquad 2^t=m.$$
La ecuación se convierte en
$$m^2 = m + m(m-1).$$
Cada entero \(m\) genera así una partición válida con
$$k_m = m(m-1).$$
Además, estos valores crecen estrictamente, porque
$$k_{m+1}-k_m=(m+1)m-m(m-1)=2m>0.$$
Esa monotonía es lo que permite pasar del primer \(m\) válido al menor \(K\) buscado.
Una partición es perfecta si y solo si \(t\) es entero. Dado que \(m=2^t\), eso sucede exactamente cuando \(m\) es una potencia de dos:
$$m \in \{2,4,8,16,\dots\}.$$
Por tanto, entre \(2 \le m \le M\), el número de particiones perfectas es simplemente el número de potencias de dos no mayores que \(M\):
$$C(M)=\left\lfloor \log_2 M \right\rfloor.$$
No hace falta ninguna teoría más sofisticada: los casos perfectos aparecen en posiciones completamente explícitas.
Para un límite fijo \(K\), definimos
$$M(K)=\max\{m \ge 2 : m(m-1)\le K\}.$$
Como la función \(m(m-1)\) es estrictamente creciente, las particiones contadas por \(P(K)\) son exactamente las que cumplen
$$2 \le m \le M(K).$$
Así, el número total de particiones hasta \(K\) es
$$M(K)-1,$$
mientras que el número de perfectas es
$$\left\lfloor \log_2 M(K) \right\rfloor.$$
Por consiguiente,
$$P(K)=\frac{\left\lfloor \log_2 M(K) \right\rfloor}{M(K)-1}.$$
La proporción solo cambia cuando \(K\) alcanza alguno de los valores \(k_m\), así que basta con estudiar los prefijos indexados por \(M\).
Sea \(\frac{1}{d}\) el umbral objetivo. Queremos el menor \(K\) tal que
$$P(K) < \frac{1}{d}.$$
En términos de \(M=M(K)\), esto equivale a
$$\frac{\left\lfloor \log_2 M \right\rfloor}{M-1} < \frac{1}{d},$$
o, como comparación entera, a
$$d \left\lfloor \log_2 M \right\rfloor < M-1.$$
Así, el problema completo se reduce a encontrar el menor \(M \ge 2\) que satisfaga esa desigualdad y devolver después
$$K = M(M-1).$$
Esa es exactamente la condición que verifica la implementación.
El umbral \(\frac{1}{3}\) muestra por qué la desigualdad debe ser estricta. Cuando \(M=10\), las potencias de dos relevantes son \(2,4,8\), así que
$$P=\frac{3}{9}=\frac{1}{3}.$$
Todavía no se ha cruzado el límite. En \(M=11\), el número de perfectas sigue siendo \(3\), pero ahora
$$P=\frac{3}{10} < \frac{1}{3},$$
por lo que la primera cota válida es
$$K=11\cdot 10=110.$$
Con \(\frac{1}{10}\) ocurre lo mismo. En \(M=51\),
$$P=\frac{5}{50}=\frac{1}{10},$$
de modo que aún no basta. En \(M=52\),
$$P=\frac{5}{51} < \frac{1}{10},$$
y el valor correspondiente es
$$K=52\cdot 51=2652.$$
Estos ejemplos coinciden con las comprobaciones del programa y muestran por qué se recorre \(M\) en orden creciente.
Las implementaciones en C++, Python y Java siguen exactamente el mismo proceso discreto. No evalúan logaritmos en tiempo de ejecución, no buscan sobre exponentes reales y no almacenan una lista explícita de particiones.
El recorrido avanza por \(m=2,3,4,\dots\). Al mismo tiempo, la implementación mantiene tres datos: el valor actual de \(m\), la cantidad de particiones perfectas vistas hasta el momento y la siguiente potencia de dos en la que ese contador debe incrementarse. Tras procesar un valor dado de \(m\), la invariante es que el contador almacenado coincide con el número de potencias de dos en el intervalo \([2,m]\).
Cuando \(m\) alcanza la siguiente potencia de dos, se incrementa el contador de perfectas y se duplica el siguiente umbral. Eso implementa de manera exacta la fórmula
$$C(M)=\left\lfloor \log_2 M \right\rfloor,$$
pero sin llamadas repetidas a logaritmos ni riesgos de redondeo.
En cada iteración, si \(c\) denota el número actual de particiones perfectas vistas, se verifica la desigualdad entera
$$c \cdot d < m-1.$$
En cuanto se cumple, el algoritmo devuelve
$$m(m-1).$$
La corrección es inmediata: el recorrido visita los \(m\) en orden creciente y la función \(m(m-1)\) también es estrictamente creciente.
El algoritmo es el mismo en los tres lenguajes. La versión en C++ además admite un denominador configurable y verifica antes dos casos de control, \(\frac{1}{3}\) y \(\frac{1}{10}\). Python usa enteros de precisión arbitraria. C++ amplía explícitamente el producto de la comparación, y Java permanece dentro del rango de 64 bits para el caso estándar del problema.
Si \(M_\star\) es el primer entero que satisface
$$d \left\lfloor \log_2 M_\star \right\rfloor < M_\star-1,$$
entonces el tiempo de ejecución es \(O(M_\star)\), porque cada iteración hace trabajo constante. El uso de memoria es \(O(1)\): solo se conservan unas pocas variables enteras.
En este problema la búsqueda lineal es suficiente, porque el punto de cruce aparece aproximadamente cuando \(M\) está en la escala de \(d \log d\). La ganancia esencial no proviene de estructuras complejas, sino de haber identificado la parametrización correcta.
本题研究的分划来自方程 \(4^t = 2^t + k\)。令 \(m = 2^t\)，则 \(4^t = m^2\)，所以任何合法分划都必须满足
$$m^2 = m + k,\qquad k = m(m-1).$$
由于题目讨论的是整数分划，所以 \(m = 2^t\) 本身必须是整数。反过来，任意整数 \(m \ge 2\) 都能通过 \(t=\log_2 m\) 产生一个合法分划。因此，问题本质上是在研究序列 \(k_m=m(m-1)\)，其中 \(m=2,3,4,\dots\)。
当 \(t\) 是整数时，这个分划称为完美分划。在新的参数下，这等价于 \(m\) 是 \(2\) 的幂。对给定上界 \(K\)，记 \(P(K)\) 为所有满足 \(k \le K\) 的分划中完美分划所占的比例。目标是求出最小的 \(K\)，使得 \(P(K) < \frac{1}{12345}\)。
真正的简化不是直接处理实数指数 \(t\)，而是改用整数参数 \(m=2^t\)。完成这一步以后，特殊位置只剩下 \(2\) 的幂，整个问题就变成了一个离散计数问题。
从
$$4^t = 2^t + k$$
出发，设 \(m=2^t\)。于是 \(4^t=(2^t)^2=m^2\)，从而有
$$m^2 = m + k,$$
因此
$$k = m^2 - m = m(m-1).$$
这就是为什么实现完全不需要直接处理实数 \(t\)。题目的结构已经全部压缩到了整数 \(m\) 上。
如果 \(m \ge 2\) 是整数，那么 \(t=\log_2 m\) 是实数，并且
$$4^t=(2^t)^2=m^2,\qquad 2^t=m.$$
于是原方程变成
$$m^2 = m + m(m-1).$$
也就是说，每个整数 \(m\) 都对应一个合法分划，其参数为
$$k_m = m(m-1).$$
而且这些 \(k_m\) 严格递增，因为
$$k_{m+1}-k_m=(m+1)m-m(m-1)=2m>0.$$
这个单调性非常关键。只要找到第一个满足条件的 \(m\)，对应的 \(k=m(m-1)\) 就一定是题目要求的最小答案。
完美分划的定义是 \(t\) 为整数。由于 \(m=2^t\)，这与 \(m\) 是 \(2\) 的幂完全等价：
$$m \in \{2,4,8,16,\dots\}.$$
因此，在区间 \(2 \le m \le M\) 内，完美分划的个数就是不超过 \(M\) 的 \(2\) 的幂的个数：
$$C(M)=\left\lfloor \log_2 M \right\rfloor.$$
这里没有隐藏的复杂递推。完美情形出现在哪些位置是完全显式的。
对固定上界 \(K\)，定义
$$M(K)=\max\{m \ge 2 : m(m-1)\le K\}.$$
因为函数 \(m(m-1)\) 严格递增，所以所有满足 \(k \le K\) 的分划，恰好对应
$$2 \le m \le M(K)$$
这些整数。于是，分划总数为
$$M(K)-1,$$
其中完美分划个数为
$$\left\lfloor \log_2 M(K) \right\rfloor.$$
因此比例公式变为
$$P(K)=\frac{\left\lfloor \log_2 M(K) \right\rfloor}{M(K)-1}.$$
在相邻两个值 \(k_m\) 与 \(k_{m+1}\) 之间，这个比例不会发生变化，所以只需要按 \(M\) 的前缀逐步检查即可。
设目标阈值是 \(\frac{1}{d}\)。我们要找最小的 \(K\)，使得
$$P(K) < \frac{1}{d}.$$
写成 \(M=M(K)\) 后，这等价于
$$\frac{\left\lfloor \log_2 M \right\rfloor}{M-1} < \frac{1}{d},$$
也就是整数不等式
$$d \left\lfloor \log_2 M \right\rfloor < M-1.$$
于是题目被彻底离散化为：
寻找最小的整数 \(M \ge 2\)，使
$$d \left\lfloor \log_2 M \right\rfloor < M-1,$$
然后返回
$$K = M(M-1).$$
实现中实际测试的正是这一条件。
阈值 \(\frac{1}{3}\) 很适合说明“严格小于”为什么重要。当 \(M=10\) 时，相关的完美值是 \(2,4,8\)，所以
$$P=\frac{3}{9}=\frac{1}{3}.$$
这还没有低于目标阈值。到 \(M=11\) 时，完美分划仍然只有 \(3\) 个，但比例变成
$$P=\frac{3}{10} < \frac{1}{3},$$
因此第一个满足条件的上界是
$$K=11\cdot 10=110.$$
阈值 \(\frac{1}{10}\) 也是同样的结构。\(M=51\) 时，
$$P=\frac{5}{50}=\frac{1}{10},$$
仍然没有越过阈值；而 \(M=52\) 时，
$$P=\frac{5}{51} < \frac{1}{10},$$
所以对应的值为
$$K=52\cdot 51=2652.$$
这些例子正好解释了为什么程序按 \(M\) 的自然顺序扫描，并在状态更新后立刻检测不等式。
C++、Python 和 Java 实现都遵循同一个离散算法。它们不在运行时计算对数，不搜索实数 \(t\)，也不显式构造所有分划。
扫描按 \(m=2,3,4,\dots\) 递增进行。实现同时维护三个量：当前的 \(m\)、目前为止已经遇到的完美分划个数，以及下一个会触发计数增加的 \(2\) 的幂。处理完某个 \(m\) 之后，始终保持这样的不变量：当前保存的完美计数，正好等于区间 \([2,m]\) 内 \(2\) 的幂的数量。
当当前 \(m\) 恰好到达下一个 \(2\) 的幂时，完美计数加一，同时把下一个阈值翻倍。这与公式
$$C(M)=\left\lfloor \log_2 M \right\rfloor$$
表达的是同一件事，但避免了重复计算对数，也避免了浮点舍入问题。
每一步都检查一个整数不等式。若用 \(c\) 表示当前已经累计到的完美分划个数，那么检验的是
$$c \cdot d < m-1.$$
一旦成立，就返回
$$m(m-1).$$
其正确性直接来自两个单调性：扫描顺序中的 \(m\) 严格递增，而函数 \(m(m-1)\) 也严格递增。
三种语言共享完全相同的数学核心。C++ 版本额外支持可配置的分母，并在主计算前验证 \(\frac{1}{3}\) 与 \(\frac{1}{10}\) 这两个检查点。Python 自动使用任意精度整数。C++ 在比较时显式扩大乘积的整数宽度，而 Java 在默认题目范围内保持在 64 位整数范围之内。
设 \(M_\star\) 为第一个满足
$$d \left\lfloor \log_2 M_\star \right\rfloor < M_\star-1$$
的整数，则时间复杂度为 \(O(M_\star)\)，因为每次循环只做常数工作。空间复杂度为 \(O(1)\)，因为算法只保存少量整数状态，不需要任何增长型表结构。
对这道题来说，线性扫描已经足够快，因为越过阈值的位置大致出现在 \(d \log d\) 这个规模上。真正重要的优化不是复杂数据结构，而是把方程改写成正确的整数参数形式。
Рассматриваемые в задаче разбиения задаются уравнением \(4^t = 2^t + k\). Если ввести обозначение \(m = 2^t\), то \(4^t = m^2\), и каждое допустимое разбиение принимает вид
$$m^2 = m + k,\qquad k = m(m-1).$$
Поскольку разбиение должно быть целочисленным, величина \(m = 2^t\) тоже должна быть целым числом. Обратно, любое целое \(m \ge 2\) дает корректное разбиение при \(t=\log_2 m\). Значит, задача сводится к последовательности \(k_m=m(m-1)\) для \(m=2,3,4,\dots\).
Разбиение называется совершенным, если \(t\) является целым числом. В новой параметризации это эквивалентно тому, что \(m\) является степенью двойки. Для границы \(K\) величина \(P(K)\) обозначает долю совершенных разбиений среди всех разбиений с \(k \le K\). Нужно найти наименьшее \(K\), для которого \(P(K) < \frac{1}{12345}\).
Главное упрощение состоит в том, что вместо поиска по вещественному параметру \(t\) задача переписывается через целый параметр \(m=2^t\). После этого особые точки оказываются просто степенями двойки, а задача превращается в аккуратный дискретный подсчет.
Начнем с уравнения
$$4^t = 2^t + k.$$
Положим \(m=2^t\). Тогда \(4^t=(2^t)^2=m^2\), откуда
$$m^2 = m + k,$$
и, следовательно,
$$k = m^2 - m = m(m-1).$$
Именно поэтому реализации не работают напрямую с вещественными степенями. Вся полезная структура уже содержится в одном целом параметре \(m\).
Если \(m \ge 2\) целое, то \(t=\log_2 m\) является вещественным числом, и
$$4^t=(2^t)^2=m^2,\qquad 2^t=m.$$
Тогда исходное уравнение принимает вид
$$m^2 = m + m(m-1).$$
Значит, каждое такое \(m\) задает корректное разбиение с параметром
$$k_m = m(m-1).$$
Более того, значения \(k_m\) строго возрастают, поскольку
$$k_{m+1}-k_m=(m+1)m-m(m-1)=2m>0.$$
Эта монотонность и делает решение простым: достаточно найти первое подходящее \(m\), и соответствующее \(k\) автоматически будет минимальным.
Разбиение является совершенным тогда и только тогда, когда \(t\) целое. Так как \(m=2^t\), это эквивалентно условию, что \(m\) является степенью двойки:
$$m \in \{2,4,8,16,\dots\}.$$
Следовательно, среди чисел \(2 \le m \le M\) число совершенных разбиений равно количеству степеней двойки, не превосходящих \(M\):
$$C(M)=\left\lfloor \log_2 M \right\rfloor.$$
Никакой скрытой рекурсии здесь нет: все совершенные случаи расположены в явно известных точках.
Для фиксированной верхней границы \(K\) введем
$$M(K)=\max\{m \ge 2 : m(m-1)\le K\}.$$
Так как функция \(m(m-1)\) строго возрастает, разбиения, учитываемые в \(P(K)\), это в точности те, для которых
$$2 \le m \le M(K).$$
Значит, общее число разбиений до границы \(K\) равно
$$M(K)-1,$$
а число совершенных равно
$$\left\lfloor \log_2 M(K) \right\rfloor.$$
Отсюда получаем формулу
$$P(K)=\frac{\left\lfloor \log_2 M(K) \right\rfloor}{M(K)-1}.$$
Между соседними значениями \(k_m\) и \(k_{m+1}\) эта доля не меняется, поэтому достаточно рассматривать только префиксы по \(M\).
Пусть целевой порог равен \(\frac{1}{d}\). Требуется минимальное \(K\), для которого
$$P(K) < \frac{1}{d}.$$
После подстановки \(M=M(K)\) получаем
$$\frac{\left\lfloor \log_2 M \right\rfloor}{M-1} < \frac{1}{d},$$
то есть эквивалентное целочисленное условие
$$d \left\lfloor \log_2 M \right\rfloor < M-1.$$
Таким образом, задача становится полностью дискретной:
найти наименьшее \(M \ge 2\), удовлетворяющее этому неравенству, а затем вернуть
$$K = M(M-1).$$
Именно это условие и проверяют реализации.
Контрольный порог \(\frac{1}{3}\) хорошо показывает важность строгого знака. При \(M=10\) совершенные значения равны \(2,4,8\), поэтому
$$P=\frac{3}{9}=\frac{1}{3}.$$
Порог еще не пройден. При \(M=11\) число совершенных разбиений все еще равно \(3\), но теперь
$$P=\frac{3}{10} < \frac{1}{3},$$
и первое подходящее значение равно
$$K=11\cdot 10=110.$$
Для \(\frac{1}{10}\) картина та же. При \(M=51\),
$$P=\frac{5}{50}=\frac{1}{10},$$
поэтому условие еще не выполнено. При \(M=52\),
$$P=\frac{5}{51} < \frac{1}{10},$$
откуда
$$K=52\cdot 51=2652.$$
Эти примеры совпадают с контрольными проверками в коде и наглядно объясняют стратегию последовательного перебора.
Реализации на C++, Python и Java используют один и тот же дискретный алгоритм. Они не вычисляют логарифмы в цикле, не перебирают вещественные значения \(t\) и не строят список разбиений явно.
Перебор идет по \(m=2,3,4,\dots\). Одновременно поддерживаются три величины: текущее \(m\), число уже встреченных совершенных разбиений и следующая степень двойки, при достижении которой этот счетчик должен увеличиться. После обработки данного \(m\) сохраняется инвариант: счетчик совершенных разбиений точно равен числу степеней двойки в интервале \([2,m]\).
Когда текущее \(m\) достигает следующей степени двойки, счетчик совершенных разбиений увеличивается на единицу, а следующий порог удваивается. Это в точности реализует формулу
$$C(M)=\left\lfloor \log_2 M \right\rfloor,$$
но без вызовов логарифма и без риска ошибок округления.
На каждом шаге проверяется целочисленное неравенство. Если через \(c\) обозначить текущее число совершенных разбиений, то тест имеет вид
$$c \cdot d < m-1.$$
Как только оно становится истинным, алгоритм возвращает
$$m(m-1).$$
Корректность следует сразу из двух фактов: значения \(m\) перебираются по возрастанию, и функция \(m(m-1)\) также строго возрастает.
Математическое ядро одинаково во всех трех языках. Версия на C++ дополнительно поддерживает настраиваемый знаменатель и проверяет два контрольных случая, \(\frac{1}{3}\) и \(\frac{1}{10}\), перед основным вычислением. Python использует целые произвольной длины. В C++ произведение в сравнении явно расширяется по разрядности, а Java остается в пределах 64-битной арифметики для стандартного диапазона задачи.
Если \(M_\star\) обозначает первое целое число, для которого выполнено
$$d \left\lfloor \log_2 M_\star \right\rfloor < M_\star-1,$$
то время работы равно \(O(M_\star)\), поскольку в каждой итерации выполняется лишь константное количество операций. Память равна \(O(1)\): алгоритму нужно хранить только несколько целых переменных.
Для данной задачи этого более чем достаточно, потому что точка пересечения появляется примерно на масштабе \(d \log d\). Главное ускорение дает не сложная структура данных, а правильная параметризация исходного уравнения.
المعادلة \(4^t = 2^t + k\) هي التي تولد التقسيمات المدروسة في هذه المسألة. إذا وضعنا \(m = 2^t\)، فإن \(4^t = m^2\)، ولذلك فإن كل تقسيم صحيح لا بد أن يحقق
$$m^2 = m + k,\qquad k = m(m-1).$$
وبما أن المسألة تتحدث عن تقسيمات صحيحة، فلا بد أن تكون القيمة \(m = 2^t\) نفسها عددًا صحيحًا. وبالعكس، كل عدد صحيح \(m \ge 2\) يعطي تقسيمًا صحيحًا عند أخذ \(t=\log_2 m\). لذلك فجوهر المسألة هو دراسة المتتالية \(k_m=m(m-1)\) عندما \(m=2,3,4,\dots\).
يسمى التقسيم كاملًا إذا كان \(t\) عددًا صحيحًا. وفي هذا التمثيل الجديد يعني ذلك تمامًا أن \(m\) قوة للعدد \(2\). ولأي حد علوي \(K\)، ترمز \(P(K)\) إلى نسبة التقسيمات الكاملة بين جميع التقسيمات التي تحقق \(k \le K\). والمطلوب هو إيجاد أصغر \(K\) بحيث
$$P(K) < \frac{1}{12345}.$$
الفكرة الحاسمة ليست التعامل المباشر مع الأس الحقيقي \(t\)، بل إعادة كتابة المسألة كلها بدلالة العدد الصحيح \(m=2^t\). بعد هذه الخطوة تصبح القيم الخاصة الوحيدة هي قوى العدد \(2\)، وتتحول المسألة إلى عد متقطع واضح.
نبدأ من
$$4^t = 2^t + k.$$
بوضع \(m=2^t\) نحصل على \(4^t=(2^t)^2=m^2\)، ومن ثم
$$m^2 = m + k,$$
أي
$$k = m^2 - m = m(m-1).$$
ولهذا السبب لا تحتاج الحلول البرمجية إلى التعامل المباشر مع الأسس الحقيقية. فكل البنية الرياضية المهمة أصبحت مخزنة في المتغير الصحيح \(m\).
إذا كان \(m \ge 2\) عددًا صحيحًا، فإن \(t=\log_2 m\) عدد حقيقي، وعندها
$$4^t=(2^t)^2=m^2,\qquad 2^t=m.$$
فتصير المعادلة
$$m^2 = m + m(m-1).$$
إذن كل عدد صحيح \(m\) يولد تقسيمًا صحيحًا بالقيمة
$$k_m = m(m-1).$$
كما أن هذه القيم تزداد زيادة صارمة لأن
$$k_{m+1}-k_m=(m+1)m-m(m-1)=2m>0.$$
وهذه الرتابة هي ما يضمن أن أول \(m\) يحقق الشرط يعطي مباشرة أصغر \(K\) مطلوب.
يكون التقسيم كاملًا إذا وفقط إذا كان \(t\) عددًا صحيحًا. وبما أن \(m=2^t\)، فهذا يكافئ تمامًا أن يكون \(m\) قوة للعدد \(2\):
$$m \in \{2,4,8,16,\dots\}.$$
لذلك فإن عدد التقسيمات الكاملة بين \(2 \le m \le M\) هو ببساطة عدد قوى \(2\) التي لا تتجاوز \(M\):
$$C(M)=\left\lfloor \log_2 M \right\rfloor.$$
لا توجد هنا علاقة عودية خفية أو بنية أصعب من ذلك؛ فمواضع الحالات الكاملة معلومة صراحة.
لأي حد ثابت \(K\)، نعرف
$$M(K)=\max\{m \ge 2 : m(m-1)\le K\}.$$
وبما أن الدالة \(m(m-1)\) متزايدة بصرامة، فإن جميع التقسيمات الداخلة في \(P(K)\) هي بالضبط تلك التي تحقق
$$2 \le m \le M(K).$$
ومن ثم فإن العدد الكلي لهذه التقسيمات هو
$$M(K)-1,$$
بينما عدد التقسيمات الكاملة هو
$$\left\lfloor \log_2 M(K) \right\rfloor.$$
إذن تصبح النسبة
$$P(K)=\frac{\left\lfloor \log_2 M(K) \right\rfloor}{M(K)-1}.$$
وهذه النسبة لا تتغير بين قيمتين متتاليتين من النوع \(k_m\) و\(k_{m+1}\)، لذلك يكفي اختبار البوادئ المفهرسة بـ \(M\).
إذا كانت العتبة المطلوبة هي \(\frac{1}{d}\)، فنحن نبحث عن أصغر \(K\) يحقق
$$P(K) < \frac{1}{d}.$$
وبالكتابة بدلالة \(M=M(K)\) نحصل على
$$\frac{\left\lfloor \log_2 M \right\rfloor}{M-1} < \frac{1}{d},$$
وهو مكافئ تمامًا للمقارنة الصحيحة
$$d \left\lfloor \log_2 M \right\rfloor < M-1.$$
وهكذا تصبح المسألة كلها:
ابحث عن أصغر \(M \ge 2\) يحقق هذه المتباينة، ثم أعد
$$K = M(M-1).$$
وهذا هو الشرط نفسه الذي تختبره جميع التطبيقات.
العتبة \(\frac{1}{3}\) توضح أهمية كون المتباينة صارمة. عندما \(M=10\)، تكون القيم الكاملة هي \(2,4,8\)، وبالتالي
$$P=\frac{3}{9}=\frac{1}{3}.$$
إذن العتبة لم تُتجاوز بعد. وعند \(M=11\) يبقى عدد التقسيمات الكاملة مساويًا لـ \(3\)، لكن النسبة تصبح
$$P=\frac{3}{10} < \frac{1}{3},$$
ولذلك يكون أول حد مناسب هو
$$K=11\cdot 10=110.$$
والعتبة \(\frac{1}{10}\) تسلك النمط نفسه. عند \(M=51\)،
$$P=\frac{5}{50}=\frac{1}{10},$$
فلا يزال الشرط غير متحقق. أما عند \(M=52\)،
$$P=\frac{5}{51} < \frac{1}{10},$$
ومن ثم نحصل على
$$K=52\cdot 51=2652.$$
هذه الأمثلة هي نفسها نقاط التحقق الموجودة في التنفيذ، وهي تشرح تمامًا لماذا يجري المسح على \(M\) بترتيب تصاعدي.
تتبع تطبيقات C++ وPython وJava الخوارزمية المنفصلة نفسها. فهي لا تحسب اللوغاريتمات أثناء التنفيذ، ولا تبحث في قيم \(t\) الحقيقية، ولا تبني قائمة صريحة بكل التقسيمات.
يجري المسح على القيم \(m=2,3,4,\dots\). وفي الوقت نفسه يحتفظ التنفيذ بثلاثة عناصر: قيمة \(m\) الحالية، وعدد التقسيمات الكاملة التي ظهرت حتى الآن، وقوة العدد \(2\) التالية التي يجب عندها زيادة هذا العداد. وبعد معالجة أي قيمة \(m\)، تكون الثابتة المحفوظة هي أن عداد التقسيمات الكاملة يساوي بالضبط عدد قوى \(2\) ضمن المجال \([2,m]\).
عندما تصل \(m\) الحالية إلى قوة العدد \(2\) التالية، يزداد عداد التقسيمات الكاملة بمقدار واحد، ثم تتضاعف العتبة التالية. وهذا يطابق تمامًا الصيغة
$$C(M)=\left\lfloor \log_2 M \right\rfloor,$$
لكن من دون استدعاءات متكررة للوغاريتم ومن دون مخاطر التقريب العشري.
في كل خطوة تُفحص متباينة صحيحة. إذا رمزنا بعدد التقسيمات الكاملة التي شوهدت حتى اللحظة بالرمز \(c\)، فإن الاختبار هو
$$c \cdot d < m-1.$$
وفور تحققها تعيد الخوارزمية القيمة
$$m(m-1).$$
وصحة ذلك مباشرة لأن القيم \(m\) تُفحص بترتيب متزايد، ولأن الدالة \(m(m-1)\) نفسها متزايدة بصرامة.
اللب الرياضي واحد في اللغات الثلاث. تنفيذ C++ يدعم أيضًا مقامًا قابلًا للتعديل ويتحقق من حالتي الاختبار \(\frac{1}{3}\) و\(\frac{1}{10}\) قبل الحساب الرئيسي. Python تستخدم أعدادًا صحيحة غير محدودة عمليًا. أما C++ فيوسّع عرض حاصل الضرب في المقارنة صراحة، بينما تبقى نسخة Java ضمن حدود 64 بت في المجال الافتراضي للمسألة.
إذا رمزنا بـ \(M_\star\) إلى أول عدد صحيح يحقق
$$d \left\lfloor \log_2 M_\star \right\rfloor < M_\star-1,$$
فإن زمن التنفيذ يساوي \(O(M_\star)\)، لأن كل دورة من الحلقة تقوم بعمل ثابت فقط. أما الذاكرة فهي \(O(1)\)، إذ لا توجد جداول نامية أو هياكل إضافية كبيرة.
وفي هذه المسألة يكون المسح الخطي كافيًا تمامًا، لأن نقطة العبور تظهر تقريبًا على مقياس \(d \log d\). المكسب الحقيقي ليس في بنية بيانات معقدة، بل في اختيار التمثيل الرياضي الصحيح منذ البداية.