For a decimal prefix \(L\), let \(p(L,n)\) denote the exponent \(j\) of the \(n\)-th power of two whose leading decimal digits are exactly \(L\). Problem 686 asks for \(p(123,678910)\).
A direct search by forming huge powers of two is unnecessary. The decisive observation is that leading digits depend only on the fractional part of a base-10 logarithm, so the whole task becomes an interval-hitting problem on \([0,1)\).
Write
$$\theta=\log_{10}2.$$
For each exponent \(j\), the decimal size of \(2^j\) is governed by \(j\theta\).
Assume \(L\) has \(d\) decimal digits. Saying that \(2^j\) begins with the digits \(L\) means that for some integer \(m\),
$$L\cdot 10^m \le 2^j \lt (L+1)\cdot 10^m.$$
Taking \(\log_{10}\) gives
$$\log_{10}L + m \le j\theta \lt \log_{10}(L+1) + m.$$
Because \(L\) has \(d\) digits, the relevant normalization is obtained by subtracting \(d-1\). Therefore the condition is equivalent to
$$a \le \{j\theta\} \lt b,$$
where
$$a=\log_{10}L-(d-1), \qquad b=\log_{10}(L+1)-(d-1),$$
and \(\{x\}\) denotes the fractional part of \(x\). So the leading-digit question has been reduced to testing whether \(\{j\theta\}\) lands inside one fixed half-open interval.
Define
$$r_j=\{j\theta\}.$$
Then
$$r_{j+1}=\{r_j+\theta\}, \qquad r_0=0.$$
This is just repeated rotation by the constant angle \(\theta\) on the unit interval. Each time \(r_j\) falls in \([a,b)\), the power \(2^j\) starts with \(L\). Hence \(p(L,n)\) is exactly the index of the \(n\)-th visit of this orbit to that interval.
The integer part of \(j\theta\) only tells us how many digits \(2^j\) has. The first few digits come from the mantissa \(10^{\{j\theta\}}\). In fact,
$$2^j = 10^{\lfloor j\theta \rfloor + \{j\theta\}} = 10^{\lfloor j\theta \rfloor}\cdot 10^{\{j\theta\}}.$$
Therefore the prefix is determined entirely by the number \(10^{\{j\theta\}}\in[1,10)\). For the target prefix \(123\), the interval used by the implementations is
$$a=\log_{10}(123)-2 \approx 0.08990511143939792,$$
$$b=\log_{10}(124)-2 \approx 0.09342168516225026.$$
Whenever \(\{j\theta\}\) falls inside that window, the mantissa lies in \([1.23,1.24)\), which means the decimal expansion of \(2^j\) begins with \(123\).
For \(L=12\), we have \(d=2\), so
$$a=\log_{10}(12)-1 \approx 0.07918124604762482,$$
$$b=\log_{10}(13)-1 \approx 0.11394335230683678.$$
Now check a few exponents. For \(j=7\),
$$7\theta \approx 2.1072099696478683,$$
so
$$\{7\theta\}\approx 0.1072099696478683 \in [a,b).$$
That predicts that \(2^7\) begins with \(12\), and indeed \(2^7=128\).
For \(j=80\),
$$80\theta \approx 24.082399653118495,$$
hence
$$\{80\theta\}\approx 0.082399653118495 \in [a,b).$$
So the second hit occurs at \(j=80\), matching the small checkpoints used by the implementation.
Nothing changes for \(L=123\) except the interval endpoints. We keep iterating the orbit \(r_{j+1}=\{r_j+\theta\}\), count how many times it enters the window for prefix \(123\), and stop at the \(678910\)-th hit. No large integer powers need to be constructed, because the logarithmic window already captures the leading digits exactly.
The C++, Python, and Java implementations all follow the same mathematical plan: convert the prefix condition into a logarithmic interval, iterate the fractional parts of successive multiples of \(\log_{10}2\), and count interval hits until the requested occurrence is reached.
The C++ implementation computes the number of digits of the prefix and the two interval endpoints at runtime, then advances one exponent at a time using extended floating-point precision. It also checks small benchmark cases such as \(p(12,1)=7\), \(p(12,2)=80\), and \(p(123,45)=12710\) before producing the final answer.
The Python implementation uses the same floating-point recurrence but is specialized directly to the target query \(L=123\), \(n=678910\). The Java implementation is more specialized still: it stores scaled integer approximations of \(\log_{10}2\) and of the two interval endpoints for prefix \(123\). Since the upper endpoint for \(123\) is smaller than \(\log_{10}2\), every successful hit must occur immediately after a wraparound, so the integer-based version only needs to test wrapped updates.
Each iteration performs a constant number of additions, comparisons, and at most one wraparound reduction. Therefore the running time is \(O(p(L,n))\), because we advance through exponents until the desired hit is found. The memory usage is \(O(1)\), since only a few scalar values are maintained throughout the search.
Für ein Dezimalpräfix \(L\) bezeichnet \(p(L,n)\) den Exponenten \(j\), bei dem zum \(n\)-ten Mal eine Zweierpotenz mit genau diesen Anfangsziffern beginnt. In Problem 686 ist also \(p(123,678910)\) gesucht.
Man muss dafür keine riesigen Zahlen \(2^j\) direkt ausrechnen. Entscheidend ist, dass die führenden Ziffern nur von der Nachkommastelle eines Zehnerlogarithmus abhängen. Damit wird die Aufgabe zu einem Intervalltrefferproblem auf \([0,1)\).
Setze
$$\theta=\log_{10}2.$$
Dann wird die Dezimalstruktur von \(2^j\) vollständig durch \(j\theta\) beschrieben.
Hat \(L\) genau \(d\) Stellen, dann bedeutet „\(2^j\) beginnt mit \(L\)“, dass es ein ganzzahliges \(m\) gibt mit
$$L\cdot 10^m \le 2^j \lt (L+1)\cdot 10^m.$$
Nach Anwendung von \(\log_{10}\) erhält man
$$\log_{10}L + m \le j\theta \lt \log_{10}(L+1) + m.$$
Da \(L\) \(d\) Stellen besitzt, normiert man durch \(d-1\). Genau dann gilt
$$a \le \{j\theta\} \lt b,$$
wobei
$$a=\log_{10}L-(d-1), \qquad b=\log_{10}(L+1)-(d-1)$$
und \(\{x\}\) den Nachkommateil bezeichnet. Aus einer Ziffernfrage wird also ein Test, ob die gebrochene Komponente \(\{j\theta\}\) in einem festen halboffenen Intervall liegt.
Definiere
$$r_j=\{j\theta\}.$$
Dann folgt unmittelbar die Rekursion
$$r_{j+1}=\{r_j+\theta\}, \qquad r_0=0.$$
Wir drehen also bei jedem Schritt um denselben Betrag \(\theta\) auf dem Einheitsintervall. Immer wenn \(r_j\) in \([a,b)\) landet, beginnt \(2^j\) mit \(L\). Damit ist \(p(L,n)\) genau der Index des \(n\)-ten Treffers dieses Orbits.
Der ganzzahlige Teil von \(j\theta\) sagt nur, wie viele Stellen \(2^j\) hat. Die ersten Ziffern stammen aus der Mantisse \(10^{\{j\theta\}}\). Es gilt nämlich
$$2^j = 10^{\lfloor j\theta \rfloor + \{j\theta\}} = 10^{\lfloor j\theta \rfloor}\cdot 10^{\{j\theta\}}.$$
Somit bestimmt allein \(10^{\{j\theta\}}\in[1,10)\) das Präfix. Für das Zielpräfix \(123\) verwenden die Implementierungen das Intervall
$$a=\log_{10}(123)-2 \approx 0.08990511143939792,$$
$$b=\log_{10}(124)-2 \approx 0.09342168516225026.$$
Liegt \(\{j\theta\}\) in diesem Bereich, dann liegt die Mantisse in \([1.23,1.24)\), also beginnt \(2^j\) tatsächlich mit \(123\).
Für \(L=12\) ist \(d=2\), also
$$a=\log_{10}(12)-1 \approx 0.07918124604762482,$$
$$b=\log_{10}(13)-1 \approx 0.11394335230683678.$$
Bei \(j=7\) erhält man
$$7\theta \approx 2.1072099696478683,$$
also
$$\{7\theta\}\approx 0.1072099696478683 \in [a,b).$$
Damit beginnt \(2^7\) mit \(12\), und tatsächlich ist \(2^7=128\).
Für \(j=80\) gilt
$$80\theta \approx 24.082399653118495,$$
sodass
$$\{80\theta\}\approx 0.082399653118495 \in [a,b).$$
Der zweite Treffer liegt also bei \(j=80\). Genau diese kleinen Kontrollwerte werden in der Implementierung verwendet.
Für \(L=123\) ändert sich nur das Intervall. Man iteriert weiterhin \(r_{j+1}=\{r_j+\theta\}\), zählt die Treffer im Fenster für \(123\) und stoppt beim \(678910\)-ten Treffer. Große Ganzzahlen werden dabei nie benötigt, weil die Logarithmen die Anfangsziffern bereits vollständig kodieren.
Die C++-, Python- und Java-Implementierungen folgen alle demselben Plan: Zuerst werden aus dem Präfix zwei logarithmische Intervallgrenzen gebildet, danach werden die Nachkommateile sukzessiver Vielfacher von \(\log_{10}2\) iteriert und die Treffer gezählt.
Die C++-Implementierung berechnet Stellenzahl und Intervallgrenzen zur Laufzeit und arbeitet dann Exponent für Exponent mit erhöhter Gleitkommapräzision ab. Außerdem prüft sie vor der Endausgabe kleine Referenzwerte wie \(p(12,1)=7\), \(p(12,2)=80\) und \(p(123,45)=12710\).
Die Python-Implementierung verwendet denselben Gleitkomma-Ansatz, ist aber direkt auf die Zielanfrage \(L=123\), \(n=678910\) spezialisiert. Die Java-Implementierung geht noch einen Schritt weiter und speichert skalierte Ganzzahlapproximationen von \(\log_{10}2\) sowie der beiden Intervallgrenzen für das Präfix \(123\). Weil die obere Grenze für \(123\) kleiner als \(\log_{10}2\) ist, kann ein Treffer nur unmittelbar nach einem Überlauf auftreten; deshalb prüft die ganzzahlige Variante nur diese gewrappten Schritte.
Jede Iteration besteht nur aus konstant vielen Additionen, Vergleichen und höchstens einer Reduktion modulo \(1\). Daher beträgt die Laufzeit \(O(p(L,n))\), denn es werden alle Exponenten bis zum gesuchten Treffer durchlaufen. Der Speicherbedarf ist \(O(1)\), weil nur wenige skalare Zustandsgrößen gehalten werden.
Bir ondalık önek \(L\) için \(p(L,n)\), soldan ilk basamakları tam olarak \(L\) olan \(n\). iki kuvvetinin üssü \(j\) anlamına gelir. Problem 686, \(p(123,678910)\) değerini sorar.
Bunu çözmek için devasa büyüklükte \(2^j\) sayıları üretmek gerekmez. Belirleyici nokta şudur: ilk basamaklar yalnızca taban-10 logaritmanın kesir kısmına bağlıdır. Böylece problem \([0,1)\) aralığında bir pencereye düşme sayımı haline gelir.
Şunu tanımlayalım:
$$\theta=\log_{10}2.$$
Her \(j\) için \(2^j\) sayısının ondalık yapısı \(j\theta\) üzerinden okunur.
\(L\) sayısı \(d\) basamaklı olsun. “\(2^j\) sayısı \(L\) ile başlar” demek, bir tamsayı \(m\) için
$$L\cdot 10^m \le 2^j \lt (L+1)\cdot 10^m$$
olması demektir. Her iki tarafa \(\log_{10}\) uygulanınca
$$\log_{10}L + m \le j\theta \lt \log_{10}(L+1) + m$$
elde edilir. \(L\) \(d\) basamaklı olduğundan, uygun normalizasyon \(d-1\) çıkarılarak yapılır. Böylece koşul
$$a \le \{j\theta\} \lt b$$
eşdeğerliğine iner; burada
$$a=\log_{10}L-(d-1), \qquad b=\log_{10}(L+1)-(d-1)$$
ve \(\{x\}\), \(x\)'in kesir kısmıdır. Yani ilk basamakları test etmek yerine sabit bir yarı açık aralığa düşmeyi test ederiz.
Şimdi
$$r_j=\{j\theta\}$$
tanımını yapalım. O zaman
$$r_{j+1}=\{r_j+\theta\}, \qquad r_0=0$$
olur. Bu, birim aralık üzerinde her adımda aynı miktar kadar dönmek demektir. \(r_j\) değeri \([a,b)\) penceresine her girdiğinde, \(2^j\) sayısı \(L\) ile başlar. Dolayısıyla \(p(L,n)\), bu pencereye yapılan \(n\). ziyaretin indisidir.
\(j\theta\)'nın tam kısmı yalnızca \(2^j\)'nin kaç basamaklı olduğunu söyler. İlk basamakları belirleyen kısım, mantissa olan \(10^{\{j\theta\}}\) ifadesidir. Gerçekten de
$$2^j = 10^{\lfloor j\theta \rfloor + \{j\theta\}} = 10^{\lfloor j\theta \rfloor}\cdot 10^{\{j\theta\}}.$$
Bu yüzden önek tamamen \(10^{\{j\theta\}}\in[1,10)\) değeriyle belirlenir. Hedef önek \(123\) için uygulamaların kullandığı pencere
$$a=\log_{10}(123)-2 \approx 0.08990511143939792,$$
$$b=\log_{10}(124)-2 \approx 0.09342168516225026$$
şeklindedir. \(\{j\theta\}\) bu aralığa düştüğünde mantissa \([1.23,1.24)\) içinde olur; yani ondalık gösterim kesin olarak \(123\) ile başlar.
\(L=12\) olduğunda \(d=2\) ve
$$a=\log_{10}(12)-1 \approx 0.07918124604762482,$$
$$b=\log_{10}(13)-1 \approx 0.11394335230683678$$
olur. \(j=7\) için
$$7\theta \approx 2.1072099696478683$$
ve dolayısıyla
$$\{7\theta\}\approx 0.1072099696478683 \in [a,b).$$
Bu, \(2^7\) sayısının \(12\) ile başlaması gerektiğini söyler; gerçekten \(2^7=128\).
\(j=80\) için ise
$$80\theta \approx 24.082399653118495,$$
yani
$$\{80\theta\}\approx 0.082399653118495 \in [a,b).$$
Böylece ikinci eşleşme \(j=80\)'de gelir. Uygulamadaki küçük kontrol değerleri tam olarak budur.
\(L=123\) için değişen tek şey pencerenin uçlarıdır. Yine \(r_{j+1}=\{r_j+\theta\}\) yinelemesini sürdürür, \(123\) penceresine düşüşleri sayar ve \(678910\). düşüşte dururuz. Büyük tam sayılar üretmeye ihtiyaç yoktur; logaritmik pencere ilk basamak bilgisini zaten tam olarak taşır.
C++, Python ve Java implementasyonlarının hepsi aynı matematiksel planı izler: önek koşulu iki logaritmik sınırla ifade edilir, sonra \(\log_{10}2\)'nin ardışık katlarının kesir kısımları üretilir ve pencereye girenler sayılır.
C++ implementasyonu önekin basamak sayısını ve iki sınırı çalışma anında hesaplar, ardından üsleri tek tek ilerleterek daha yüksek duyarlıklı kayan nokta aritmetiğiyle tarar. Sonuca geçmeden önce \(p(12,1)=7\), \(p(12,2)=80\) ve \(p(123,45)=12710\) gibi küçük doğrulama değerlerini de kontrol eder.
Python implementasyonu aynı kayan nokta yaklaşımını doğrudan hedef sorgu \(L=123\), \(n=678910\) için uygular. Java implementasyonu daha da özelleşmiştir: \(\log_{10}2\) ile \(123\) için gereken iki sınırı \(10^{18}\) ölçeğinde tam sayılar olarak saklar. \(123\) için üst sınır \(\log_{10}2\)'den küçük olduğu için her isabet yalnızca bir sarmalama adımından hemen sonra oluşabilir; bu yüzden tam sayı tabanlı sürüm sadece bu sarılan adımları test eder.
Her iterasyonda sabit sayıda toplama, karşılaştırma ve en fazla bir kez sarmalama düzeltmesi yapılır. Bu nedenle çalışma süresi \(O(p(L,n))\) olur; çünkü aranan isabete ulaşana kadar üsleri sırayla gezeriz. Bellek kullanımı \(O(1)\)'dir; süreç boyunca yalnızca birkaç skaler değer tutulur.
Para un prefijo decimal \(L\), \(p(L,n)\) es el exponente \(j\) de la \(n\)-ésima potencia de dos cuya expansión decimal empieza exactamente por \(L\). En el problema 686 se pide \(p(123,678910)\).
No hace falta construir potencias gigantes de dos. La clave es que los primeros dígitos dependen solo de la parte fraccionaria de un logaritmo en base 10, de modo que todo se reduce a contar visitas a un intervalo fijo de \([0,1)\).
Escribimos
$$\theta=\log_{10}2.$$
Entonces la forma decimal de \(2^j\) queda codificada por \(j\theta\).
Supongamos que \(L\) tiene \(d\) cifras. Decir que \(2^j\) empieza por \(L\) significa que existe un entero \(m\) tal que
$$L\cdot 10^m \le 2^j \lt (L+1)\cdot 10^m.$$
Al tomar \(\log_{10}\), obtenemos
$$\log_{10}L + m \le j\theta \lt \log_{10}(L+1) + m.$$
Como \(L\) tiene \(d\) cifras, la normalización adecuada consiste en restar \(d-1\). Así, la condición es equivalente a
$$a \le \{j\theta\} \lt b,$$
donde
$$a=\log_{10}L-(d-1), \qquad b=\log_{10}(L+1)-(d-1),$$
y \(\{x\}\) denota la parte fraccionaria de \(x\). La pregunta sobre los primeros dígitos se convierte entonces en un simple test de pertenencia a un intervalo semiabierto fijo.
Definimos
$$r_j=\{j\theta\}.$$
Entonces
$$r_{j+1}=\{r_j+\theta\}, \qquad r_0=0.$$
Eso es una rotación repetida por el mismo desplazamiento \(\theta\) en el intervalo unidad. Cada vez que \(r_j\) entra en \([a,b)\), la potencia \(2^j\) tiene prefijo \(L\). Por tanto, \(p(L,n)\) es exactamente el índice de la \(n\)-ésima visita de esta órbita a esa ventana.
La parte entera de \(j\theta\) solo indica cuántas cifras tiene \(2^j\). Los primeros dígitos vienen dados por la mantisa \(10^{\{j\theta\}}\). De hecho,
$$2^j = 10^{\lfloor j\theta \rfloor + \{j\theta\}} = 10^{\lfloor j\theta \rfloor}\cdot 10^{\{j\theta\}}.$$
Así que el prefijo depende únicamente del valor \(10^{\{j\theta\}}\in[1,10)\). Para el prefijo objetivo \(123\), la ventana usada por las implementaciones es
$$a=\log_{10}(123)-2 \approx 0.08990511143939792,$$
$$b=\log_{10}(124)-2 \approx 0.09342168516225026.$$
Cuando \(\{j\theta\}\) cae en ese intervalo, la mantisa pertenece a \([1.23,1.24)\), lo que obliga a que la expansión decimal de \(2^j\) empiece por \(123\).
Si \(L=12\), entonces \(d=2\) y
$$a=\log_{10}(12)-1 \approx 0.07918124604762482,$$
$$b=\log_{10}(13)-1 \approx 0.11394335230683678.$$
Para \(j=7\),
$$7\theta \approx 2.1072099696478683,$$
así que
$$\{7\theta\}\approx 0.1072099696478683 \in [a,b).$$
Eso predice que \(2^7\) empieza por \(12\), y en efecto \(2^7=128\).
Para \(j=80\),
$$80\theta \approx 24.082399653118495,$$
por lo que
$$\{80\theta\}\approx 0.082399653118495 \in [a,b).$$
Así, el segundo acierto ocurre en \(j=80\), exactamente como indican las comprobaciones pequeñas de la implementación.
Para \(L=123\) el mecanismo no cambia; solo cambian los extremos de la ventana. Se itera \(r_{j+1}=\{r_j+\theta\}\), se cuentan las visitas al intervalo correspondiente a \(123\) y se detiene el proceso en la visita número \(678910\). Nunca hace falta calcular el entero gigantesco \(2^j\), porque la ventana logarítmica ya contiene toda la información sobre los primeros dígitos.
Las implementaciones en C++, Python y Java siguen exactamente este esquema: convierten la condición de prefijo en dos límites logarítmicos, generan las partes fraccionarias de múltiplos sucesivos de \(\log_{10}2\) y cuentan cuántas veces caen dentro del intervalo objetivo.
La implementación en C++ calcula en tiempo de ejecución el número de cifras del prefijo y los dos extremos del intervalo, y luego avanza exponente por exponente usando aritmética de coma flotante de mayor precisión. Antes de imprimir la respuesta final también verifica casos pequeños como \(p(12,1)=7\), \(p(12,2)=80\) y \(p(123,45)=12710\).
La implementación en Python usa la misma recurrencia en coma flotante, pero ya especializada al caso final \(L=123\), \(n=678910\). La implementación en Java está aún más especializada: guarda aproximaciones enteras escaladas de \(\log_{10}2\) y de los dos extremos del intervalo para \(123\). Como el extremo superior para \(123\) es menor que \(\log_{10}2\), todo acierto debe aparecer justo después de una vuelta completa, así que la versión entera solo comprueba los pasos que hacen wraparound.
Cada iteración realiza un número constante de sumas, comparaciones y, como mucho, una reducción por wraparound. Por ello, el tiempo total es \(O(p(L,n))\), ya que se recorren exponentes hasta encontrar el acierto deseado. La memoria es \(O(1)\), porque durante todo el proceso solo se mantienen unas pocas cantidades escalares.
对一个十进制前缀 \(L\)，记 \(p(L,n)\) 为第 \(n\) 个满足“\(2^j\) 的十进制表示恰好以 \(L\) 开头”的指数 \(j\)。第 686 题要求的就是 \(p(123,678910)\)。
这道题表面上像是在寻找非常巨大的二次幂，但真正决定首位数字的并不是 \(2^j\) 的完整值，而是它的十进制对数的小数部分。因此问题可以改写成：在单位区间上不断做一次固定旋转，统计轨道有多少次落入某个小窗口。
设
$$\theta=\log_{10}2.$$
那么每个指数 \(j\) 对应的十进制结构都由 \(j\theta\) 决定。
设前缀 \(L\) 有 \(d\) 位。说“\(2^j\) 以 \(L\) 开头”，等价于存在某个整数 \(m\)，使得
$$L\cdot 10^m \le 2^j \lt (L+1)\cdot 10^m.$$
对不等式取 \(\log_{10}\)，得到
$$\log_{10}L + m \le j\theta \lt \log_{10}(L+1) + m.$$
由于 \(L\) 有 \(d\) 位，适合的归一化方式是减去 \(d-1\)。这样一来，上式就等价于
$$a \le \{j\theta\} \lt b,$$
其中
$$a=\log_{10}L-(d-1), \qquad b=\log_{10}(L+1)-(d-1),$$
\(\{x\}\) 表示 \(x\) 的小数部分。于是“首位数字是否为 \(L\)”被完全转化成了“\(\{j\theta\}\) 是否落在固定半开区间 \([a,b)\) 内”。
定义
$$r_j=\{j\theta\}.$$
那么显然有递推式
$$r_{j+1}=\{r_j+\theta\}, \qquad r_0=0.$$
这意味着我们并不需要真的计算 \(2^j\)，只要从 \(0\) 开始不断加上固定常数 \(\theta\)，超过 \(1\) 就减去 \(1\)，就能依次得到所有 \(\{j\theta\}\)。每当 \(r_j\) 落入区间 \([a,b)\)，对应的 \(2^j\) 就以 \(L\) 开头。因此 \(p(L,n)\) 恰好是这个轨道第 \(n\) 次命中目标窗口时的指数。
\(j\theta\) 的整数部分只负责告诉我们 \(2^j\) 有多少位，而前面的有效数字来自 mantissa，也就是 \(10^{\{j\theta\}}\)。因为
$$2^j = 10^{\lfloor j\theta \rfloor + \{j\theta\}} = 10^{\lfloor j\theta \rfloor}\cdot 10^{\{j\theta\}}.$$
右边的第一个因子只是把小数点向右移动若干位，真正决定首位数字的是第二个因子 \(10^{\{j\theta\}}\in[1,10)\)。对题目里的目标前缀 \(123\)，实现中使用的窗口是
$$a=\log_{10}(123)-2 \approx 0.08990511143939792,$$
$$b=\log_{10}(124)-2 \approx 0.09342168516225026.$$
也就是说，只要 \(\{j\theta\}\) 落入这个区间，\(10^{\{j\theta\}}\) 就落在 \([1.23,1.24)\) 内，于是 \(2^j\) 的十进制表示必然以 \(123\) 开头。
为了看清楚这个判定过程，先看较小的前缀 \(L=12\)。这时 \(d=2\)，所以
$$a=\log_{10}(12)-1 \approx 0.07918124604762482,$$
$$b=\log_{10}(13)-1 \approx 0.11394335230683678.$$
当 \(j=7\) 时，
$$7\theta \approx 2.1072099696478683,$$
于是
$$\{7\theta\}\approx 0.1072099696478683 \in [a,b).$$
所以算法会判定 \(2^7\) 以 \(12\) 开头，而这确实成立，因为 \(2^7=128\)。
再看 \(j=80\)：
$$80\theta \approx 24.082399653118495,$$
因此
$$\{80\theta\}\approx 0.082399653118495 \in [a,b).$$
这说明第二次命中发生在 \(j=80\)。这些小例子正好对应实现里使用的校验点，说明“对数窗口 + 小数部分迭代”的方法与真实的首位数字完全一致。
当 \(L\) 改成 \(123\) 时，算法本身没有任何变化，只是窗口端点换成了上面的 \([a,b)\)。接下来只需不断更新
$$r_{j+1}=\{r_j+\theta\}$$
并统计它落入该窗口的次数。第 \(678910\) 次命中对应的指数就是 \(p(123,678910)\)。整个过程中完全不需要构造大整数，也不需要保留任何幂的十进制字符串，因为所有必要信息都压缩在 \(\{j\theta\}\) 里了。
C++、Python 和 Java 三个实现共享同一套核心思路：先把前缀条件变成两个对数端点，再依次生成 \(\log_{10}2\) 的倍数的小数部分，统计有多少次落进目标区间。
C++ 实现会在运行时根据给定前缀计算位数和区间端点，然后用较高精度的浮点数逐个推进指数，同时先验证几个小检查点，例如 \(p(12,1)=7\)、\(p(12,2)=80\) 以及 \(p(123,45)=12710\)。Python 实现使用同样的浮点递推，只是直接针对最终问题 \(L=123\)、\(n=678910\) 进行求解。
Java 实现则更进一步地针对这个固定输入做了特化。它把 \(\log_{10}2\) 以及前缀 \(123\) 对应的两个端点都预先写成按 \(10^{18}\) 放大的整数，从而用纯整数运算模拟“加上 \(\theta\) 再对 1 取模”的过程。由于前缀 \(123\) 的上端点小于 \(\log_{10}2\)，一次命中只能出现在发生回绕的那一步之后，所以这份整数实现只需要在回绕时检查区间命中情况即可。
每次迭代都只包含常数次加法、比较以及至多一次“减去 1”的回绕修正，因此单步代价是 \(O(1)\)。总时间复杂度就是 \(O(p(L,n))\)，因为算法会从小到大检查指数，直到找到第 \(n\) 次命中。空间复杂度为 \(O(1)\)，整个过程中只维护少量标量状态。
Для десятичного префикса \(L\) величина \(p(L,n)\) означает показатель \(j\) у \(n\)-й степени двойки, десятичная запись которой начинается ровно с цифр \(L\). В задаче 686 требуется найти \(p(123,678910)\).
Полностью вычислять огромные числа \(2^j\) не нужно. Ведущие цифры определяются только дробной частью десятичного логарифма, поэтому задача превращается в подсчет попаданий орбиты в фиксированное окно внутри \([0,1)\).
Обозначим
$$\theta=\log_{10}2.$$
Тогда десятичная форма \(2^j\) контролируется величиной \(j\theta\).
Пусть число \(L\) состоит из \(d\) цифр. Условие «\(2^j\) начинается с \(L\)» означает, что существует целое \(m\), для которого
$$L\cdot 10^m \le 2^j \lt (L+1)\cdot 10^m.$$
После применения \(\log_{10}\) получаем
$$\log_{10}L + m \le j\theta \lt \log_{10}(L+1) + m.$$
Так как у \(L\) ровно \(d\) цифр, удобно вычесть \(d-1\). Тогда условие эквивалентно
$$a \le \{j\theta\} \lt b,$$
где
$$a=\log_{10}L-(d-1), \qquad b=\log_{10}(L+1)-(d-1),$$
а \(\{x\}\) обозначает дробную часть \(x\). Значит, вопрос о ведущих цифрах сводится к проверке попадания дробной части \(\{j\theta\}\) в одно фиксированное полуоткрытое окно.
Определим
$$r_j=\{j\theta\}.$$
Тогда автоматически
$$r_{j+1}=\{r_j+\theta\}, \qquad r_0=0.$$
Это означает, что на каждом шаге мы сдвигаемся на одну и ту же величину \(\theta\) по единичному интервалу. Когда \(r_j\) попадает в \([a,b)\), число \(2^j\) начинается с префикса \(L\). Следовательно, \(p(L,n)\) есть просто индекс \(n\)-го попадания этой орбиты в целевое окно.
Целая часть \(j\theta\) отвечает только за число цифр в \(2^j\). Первые цифры определяются мантиссой \(10^{\{j\theta\}}\). Действительно,
$$2^j = 10^{\lfloor j\theta \rfloor + \{j\theta\}} = 10^{\lfloor j\theta \rfloor}\cdot 10^{\{j\theta\}}.$$
Первый множитель лишь сдвигает десятичную точку, а нужный префикс содержится во втором множителе \(10^{\{j\theta\}}\in[1,10)\). Для целевого префикса \(123\) реализации используют окно
$$a=\log_{10}(123)-2 \approx 0.08990511143939792,$$
$$b=\log_{10}(124)-2 \approx 0.09342168516225026.$$
Если \(\{j\theta\}\) лежит внутри этого интервала, то мантисса попадает в \([1.23,1.24)\), а значит десятичная запись \(2^j\) начинается именно с \(123\).
Возьмем более короткий префикс \(L=12\). Тогда \(d=2\), и
$$a=\log_{10}(12)-1 \approx 0.07918124604762482,$$
$$b=\log_{10}(13)-1 \approx 0.11394335230683678.$$
При \(j=7\)
$$7\theta \approx 2.1072099696478683,$$
следовательно,
$$\{7\theta\}\approx 0.1072099696478683 \in [a,b).$$
Это предсказывает, что \(2^7\) начинается с \(12\), и действительно \(2^7=128\).
При \(j=80\)
$$80\theta \approx 24.082399653118495,$$
откуда
$$\{80\theta\}\approx 0.082399653118495 \in [a,b).$$
Значит, второе попадание происходит при \(j=80\). Эти же контрольные значения используются в реализации.
Для \(L=123\) меняются только границы окна. Мы продолжаем итерацию
$$r_{j+1}=\{r_j+\theta\}$$
и считаем, сколько раз орбита входит в интервал для префикса \(123\). Индекс \(678910\)-го такого попадания и есть искомое значение \(p(123,678910)\). Никакие длинные целые числа хранить не нужно: всю важную информацию уже несет дробная часть логарифма.
Реализации на C++, Python и Java используют одну и ту же идею: сначала из префикса строятся две логарифмические границы, затем последовательно генерируются дробные части кратных \(\log_{10}2\), и каждое попадание в целевое окно увеличивает счетчик.
Реализация на C++ вычисляет число цифр и границы окна во время выполнения, после чего проходит показатели по одному, используя повышенную точность вещественных вычислений. Перед выводом окончательного ответа она также проверяет небольшие контрольные случаи \(p(12,1)=7\), \(p(12,2)=80\) и \(p(123,45)=12710\).
Реализация на Python применяет ту же вещественную рекурсию, но уже напрямую для входа \(L=123\), \(n=678910\). Реализация на Java еще более специализирована: она хранит \(\log_{10}2\) и обе границы окна для \(123\) как целые числа, масштабированные множителем \(10^{18}\). Поскольку верхняя граница окна для \(123\) меньше, чем \(\log_{10}2\), успешное попадание возможно только сразу после перехода через \(1\); поэтому целочисленная версия проверяет только такие шаги с wraparound.
Каждая итерация требует лишь постоянного числа сложений, сравнений и не более одной операции приведения обратно в \([0,1)\). Поэтому время работы равно \(O(p(L,n))\): алгоритм перебирает показатели, пока не дойдет до нужного попадания. Память равна \(O(1)\), так как поддерживается только несколько скалярных величин.
لأي بادئة عشرية \(L\)، نرمز بـ \(p(L,n)\) إلى الأس \(j\) الذي تمثل عنده القوة \(2^j\) الحالة رقم \(n\) التي تبدأ فيها الكتابة العشرية بالبادئة \(L\) بالضبط. في المسألة 686 نريد حساب \(p(123,678910)\).
لا حاجة إلى تكوين أعداد هائلة مثل \(2^j\) مباشرة. الفكرة الحاسمة هي أن الأرقام الأولى تعتمد فقط على الجزء الكسري من اللوغاريتم العشري، ولذلك تتحول المسألة إلى عد مرات دخول متتالية معينة إلى نافذة ثابتة داخل \([0,1)\).
لنضع
$$\theta=\log_{10}2.$$
عندئذ تصبح البنية العشرية للعدد \(2^j\) محكومة بالقيمة \(j\theta\).
إذا كان للعدد \(L\) عدد أرقام يساوي \(d\)، فإن عبارة «\(2^j\) يبدأ بـ \(L\)» تعني وجود عدد صحيح \(m\) بحيث
$$L\cdot 10^m \le 2^j \lt (L+1)\cdot 10^m.$$
وبأخذ \(\log_{10}\) نحصل على
$$\log_{10}L + m \le j\theta \lt \log_{10}(L+1) + m.$$
ولأن \(L\) يتكون من \(d\) خانات، فإن التطبيع الطبيعي يكون بطرح \(d-1\). وهكذا يصبح الشرط مكافئًا لـ
$$a \le \{j\theta\} \lt b,$$
حيث
$$a=\log_{10}L-(d-1), \qquad b=\log_{10}(L+1)-(d-1),$$
والرمز \(\{x\}\) يعني الجزء الكسري من \(x\). بهذا نكون قد استبدلنا سؤالًا عن أوائل الأرقام باختبار بسيط: هل يقع \(\{j\theta\}\) داخل مجال نصف مفتوح ثابت أم لا.
نعرّف
$$r_j=\{j\theta\}.$$
ومن ثم
$$r_{j+1}=\{r_j+\theta\}, \qquad r_0=0.$$
هذا يعني أننا نتحرك في كل خطوة بالمقدار نفسه \(\theta\) على الفترة الواحدة. كل مرة يقع فيها \(r_j\) داخل \([a,b)\)، تكون القوة \(2^j\) بادئتها العشرية هي \(L\). لذلك فإن \(p(L,n)\) هو ببساطة فهرس الزيارة رقم \(n\) لهذه النافذة.
الجزء الصحيح من \(j\theta\) يخبرنا فقط بعدد خانات \(2^j\)، أما الأرقام الأولى نفسها فتأتي من المانتيسا \(10^{\{j\theta\}}\). ذلك لأن
$$2^j = 10^{\lfloor j\theta \rfloor + \{j\theta\}} = 10^{\lfloor j\theta \rfloor}\cdot 10^{\{j\theta\}}.$$
العامل الأول لا يفعل أكثر من تحريك الفاصلة العشرية، بينما العامل الثاني \(10^{\{j\theta\}}\in[1,10)\) هو الذي يحدد البادئة. بالنسبة إلى البادئة الهدف \(123\)، فإن النافذة المستخدمة في التطبيقات هي
$$a=\log_{10}(123)-2 \approx 0.08990511143939792,$$
$$b=\log_{10}(124)-2 \approx 0.09342168516225026.$$
فإذا وقع \(\{j\theta\}\) داخل هذا المجال، أصبحت المانتيسا في \([1.23,1.24)\)، وهذا يعني مباشرة أن الكتابة العشرية لـ \(2^j\) تبدأ بـ \(123\).
لنأخذ بادئة أصغر هي \(L=12\). عندها \(d=2\)، وبالتالي
$$a=\log_{10}(12)-1 \approx 0.07918124604762482,$$
$$b=\log_{10}(13)-1 \approx 0.11394335230683678.$$
عندما \(j=7\)، نجد
$$7\theta \approx 2.1072099696478683,$$
ومن ثم
$$\{7\theta\}\approx 0.1072099696478683 \in [a,b).$$
إذن تتنبأ الطريقة بأن \(2^7\) يبدأ بـ \(12\)، وهذا صحيح لأن \(2^7=128\).
وعندما \(j=80\)،
$$80\theta \approx 24.082399653118495,$$
فتكون
$$\{80\theta\}\approx 0.082399653118495 \in [a,b).$$
لذلك تأتي المطابقة الثانية عند \(j=80\). هذه القيم الصغيرة نفسها تُستخدم كنقاط تحقق في التطبيق.
عند الانتقال إلى \(L=123\) لا تتغير الخوارزمية، بل تتغير فقط حدود النافذة. نستمر في تحديث
$$r_{j+1}=\{r_j+\theta\}$$
ونعد عدد مرات الدخول إلى نافذة \(123\). وعند الزيارة رقم \(678910\) يكون الأس المقابل هو \(p(123,678910)\). لا توجد أي حاجة إلى التعامل مع أعداد صحيحة ضخمة، لأن نافذة اللوغاريتم تعطي معلومات البداية العشرية كاملة.
تتبع تطبيقات C++ وPython وJava الخطة الرياضية نفسها: تحويل شرط البادئة إلى حدين لوغاريتميين، ثم توليد الأجزاء الكسرية للمضاعفات المتتالية لـ \(\log_{10}2\)، ثم زيادة العداد كلما دخلت القيمة في المجال المطلوب.
تنفذ نسخة C++ الحساب العام للبادئة المطلوبة أثناء التشغيل، وتستخدم دقة عددية أعلى في الحسابات العشرية، كما تتحقق قبل إخراج النتيجة من حالات صغيرة مثل \(p(12,1)=7\) و\(p(12,2)=80\) و\(p(123,45)=12710\). أما نسخة Python فتستعمل التكرار نفسه بالكسور العشرية ولكنها مخصصة مباشرة للحالة \(L=123\)، \(n=678910\).
نسخة Java أكثر تخصيصًا للحالة النهائية: فهي تخزن \(\log_{10}2\) وحدي النافذة الخاصة بالبادئة \(123\) على هيئة أعداد صحيحة بعد تكبيرها بمقياس \(10^{18}\). وبما أن الحد العلوي لنافذة \(123\) أصغر من \(\log_{10}2\)، فإن كل إصابة لا بد أن تحدث مباشرة بعد خطوة التفاف حول \(1\)، ولذلك تكتفي النسخة الصحيحة بفحص الخطوات التي يحدث فيها هذا الالتفاف.
كل دورة من الخوارزمية تنفذ عددًا ثابتًا من عمليات الجمع والمقارنة، ومعها على الأكثر عملية واحدة لإرجاع القيمة إلى المجال \([0,1)\). لذا فإن زمن التنفيذ هو \(O(p(L,n))\)، لأننا نمر على الأسس حتى نصل إلى الضربة المطلوبة. أما الذاكرة فهي \(O(1)\)، لأن الحالة كلها تختزل في بضعة مقادير عددية فقط.