For every pair of positive integers
$$1\le p \lt q,\qquad p+q\le 2011,$$
consider
$$\alpha=\sqrt p+\sqrt q.$$
We look at the even powers \(\alpha^{2n}\), and \(C(p,q,n)\) is the number of consecutive 9s at the beginning of the fractional part of \(\alpha^{2n}\).
Let \(N(p,q)\) be the smallest \(n\) such that
$$C(p,q,n)\ge 2011.$$
The goal is to compute
$$\sum_{p+q\le 2011} N(p,q),$$
but only for those pairs where the fractional part of \(\alpha^{2n}\) approaches \(1\).
1) Introduce the conjugate partner.
Set
$$\beta=\sqrt q-\sqrt p.$$
Then
$$\alpha^{2n}+\beta^{2n}$$
is always an integer. The reason is that in the binomial expansions of \((\sqrt q+\sqrt p)^{2n}\) and \((\sqrt q-\sqrt p)^{2n}\), all odd-radical terms cancel and only integer terms remain.
So if we define
$$A_n=\alpha^{2n}+\beta^{2n}\in\mathbb Z,$$
then
$$\alpha^{2n}=A_n-\beta^{2n}.$$
2) Exactly when does the fractional part approach \(1\)?
Because \(p \lt q\), we have \(\beta \gt 0\). The fractional part of \(\alpha^{2n}\) approaches \(1\) exactly when \(\beta^{2n}\to0\), i.e.
$$0\lt \beta \lt 1.$$
If \(\beta\ge1\), then \(\beta^{2n}\) does not decay to \(0\), so the fractional part cannot converge to \(1\).
Thus the admissible pairs are precisely those with
$$\sqrt q-\sqrt p \lt 1.$$
3) Fractional part as \(1-\beta^{2n}\).
For every admissible pair we have \(0\lt \beta^{2n}\lt1\), hence
$$\alpha^{2n}=A_n-\beta^{2n}$$
lies just below the integer \(A_n\). Therefore
$$\{\alpha^{2n}\}=1-\beta^{2n}.$$
This is the whole reason the problem becomes easy: the complicated-looking irrational power is controlled by the tiny positive quantity \(\beta^{2n}\).
4) Translate "at least \(K\) leading nines".
Let \(x=\{\alpha^{2n}\}\). The fractional part begins with at least \(K\) nines if and only if
$$x \gt 1-10^{-K}.$$
Since \(x=1-\beta^{2n}\), this is equivalent to
$$\beta^{2n}\lt 10^{-K}.$$
Here \(K=2011\) for the actual problem.
5) Take logarithms.
Because \(0\lt \beta^2 \lt 1\), the quantity
$$\lambda=-\log_{10}(\beta^2)$$
is positive. The inequality above becomes
$$n\lambda \gt K.$$
So the minimal valid exponent is
$$N(p,q)=\left\lceil\frac{K}{\lambda}\right\rceil=\left\lceil\frac{K}{-\log_{10}(\beta^2)}\right\rceil.$$
This is exactly what the C++ function minimal_n computes, with a tiny tolerance to avoid floating-point boundary mistakes.
6) Worked example: \((p,q)=(2,3)\).
Here
$$\beta=\sqrt3-\sqrt2\approx0.3178372452,$$
so
$$\beta^2\approx0.1010205144,$$
and
$$\lambda=-\log_{10}(\beta^2)\approx0.9955904242.$$
For one leading 9 we need \(K=1\), hence
$$N(2,3)=\left\lceil\frac{1}{0.9955904242}\right\rceil=2.$$
That matches the sequence shown in the statement:
\((\sqrt2+\sqrt3)^2=9.8989\ldots\) has no leading 9 in the fractional part,
\((\sqrt2+\sqrt3)^4=97.9897\ldots\) has one,
\((\sqrt2+\sqrt3)^6=969.9989\ldots\) has two,
\((\sqrt2+\sqrt3)^8=9601.9998\ldots\) has three.
So the checkpoints
$$N(2,3;K=1)=2,\qquad N(2,3;K=2)=3,\qquad N(2,3;K=3)=4$$
are exactly correct.
7) Small full example: \(M=5,\ K=1\).
The admissible pairs are
$$ (1,2),\ (1,3),\ (2,3). $$
Their minimal values are
$$N(1,2)=2,\qquad N(1,3)=4,\qquad N(2,3)=2.$$
Therefore
$$S(5,1)=2+4+2=8,$$
which is the second checkpoint in the source code.
8) Final summation formula.
The complete answer is
$$\sum_{\substack{1\le p \lt q\\ p+q\le 2011\\ \sqrt q-\sqrt p\lt1}} \left\lceil\frac{2011}{-\log_{10}\!\left((\sqrt q-\sqrt p)^2\right)}\right\rceil.$$
No deeper number theory is needed after this reduction; the implementation simply iterates over all candidate pairs.
1) Loop over all pairs \((p,q)\) with \(1\le p \lt q\) and \(p+q\le M\).
2) Compute
$$\beta=\sqrt q-\sqrt p.$$
3) Skip the pair if \(\beta\ge1\).
4) Compute \(\lambda=-\log_{10}(\beta^2)\).
5) Add
$$\left\lceil\frac{K}{\lambda}\right\rceil$$
to the running total.
The triangular region \(p+q\le M\) contains
$$O(M^2)$$
pairs. Each pair needs a constant amount of work: two square roots, one logarithm, and a few arithmetic operations. So the total complexity is
$$O(M^2)$$
time and
$$O(1)$$
memory.
The implementation checks
$$N(2,3;1)=2,\qquad N(2,3;2)=3,\qquad N(2,3;3)=4,$$
and
$$S(5,1)=8.$$
For the full problem \((M,K)=(2011,2011)\), the final answer is
$$709313889.$$
Fuer alle Paare
$$1\le p \lt q,\qquad p+q\le 2011$$
betrachten wir
$$\alpha=\sqrt p+\sqrt q.$$
Gesucht ist das kleinste \(n\), fuer das der Nachkommateil von \(\alpha^{2n}\) mit mindestens \(2011\) Neunen beginnt. Diese Minimalwerte werden ueber alle zulaessigen Paare aufsummiert.
1) Konjugierter Partner.
Setze
$$\beta=\sqrt q-\sqrt p.$$
Dann ist
$$A_n=\alpha^{2n}+\beta^{2n}$$
immer ganzzahlig, weil sich in den beiden Binomialentwicklungen alle ungeraden Wurzelterme wegheben.
Also gilt
$$\alpha^{2n}=A_n-\beta^{2n}.$$
2) Wann geht der Nachkommateil gegen \(1\)?
Genau dann, wenn \(\beta^{2n}\to0\), also
$$0\lt\beta\lt1.$$
Das ist exakt die zusaetzliche Bedingung aus dem Problem.
3) Nachkommateil als \(1-\beta^{2n}\).
Fuer zulaessige Paare liegt \(0\lt\beta^{2n}\lt1\), daher ist \(\alpha^{2n}\) immer knapp unter der ganzen Zahl \(A_n\). Also
$$\{\alpha^{2n}\}=1-\beta^{2n}.$$
4) Fuehrende Neunen.
Mindestens \(K\) fuehrende Neunen im Nachkommateil bedeuten
$$\{\alpha^{2n}\}\gt1-10^{-K},$$
also aequivalent
$$\beta^{2n}\lt10^{-K}.$$
5) Logarithmische Form.
Mit
$$\lambda=-\log_{10}(\beta^2)\gt0$$
wird das zu
$$n\lambda\gt K.$$
Folglich
$$N(p,q)=\left\lceil\frac{K}{\lambda}\right\rceil=\left\lceil\frac{K}{-\log_{10}(\beta^2)}\right\rceil.$$
6) Beispiel \((2,3)\).
Hier ist \(\beta=\sqrt3-\sqrt2\approx0.317837\), also \(\lambda\approx0.9955904\). Fuer \(K=1\) ergibt sich
$$N(2,3)=\left\lceil\frac{1}{0.9955904}\right\rceil=2.$$
Das passt genau zur im Problem gezeigten Folge der Potenzen.
7) Kleiner Vollcheck.
Fuer \(M=5\) und \(K=1\) sind die zulaessigen Paare \((1,2),(1,3),(2,3)\) mit Beitraegen \(2,4,2\). Also
$$S(5,1)=8.$$
8) Gesamtsumme.
Damit lautet die Loesung
$$\sum_{\substack{1\le p \lt q\\ p+q\le 2011\\ \sqrt q-\sqrt p\lt1}} \left\lceil\frac{2011}{-\log_{10}\!\left((\sqrt q-\sqrt p)^2\right)}\right\rceil.$$
1) Alle Paare \((p,q)\) im Dreiecksbereich durchlaufen.
2) \(\beta=\sqrt q-\sqrt p\) berechnen.
3) Falls \(\beta\ge1\), das Paar verwerfen.
4) \(\lambda=-\log_{10}(\beta^2)\) berechnen.
5) \(\lceil K/\lambda\rceil\) zur Summe addieren.
Die Paarzahl ist \(O(M^2)\). Pro Paar faellt nur konstante Arbeit an. Daher: \(O(M^2)\) Zeit und \(O(1)\) Speicher.
Der Code prueft
$$N(2,3;1)=2,\qquad N(2,3;2)=3,\qquad N(2,3;3)=4,$$
sowie
$$S(5,1)=8.$$
Fuer \((M,K)=(2011,2011)\) lautet das Endergebnis
$$709313889.$$
Her
$$1\le p \lt q,\qquad p+q\le 2011$$
cifti icin
$$\alpha=\sqrt p+\sqrt q$$
tanimlaniyor. \(\alpha^{2n}\) sayisinin kesir kisminin basinda en az \(2011\) tane ard arda \(9\) olmasi icin gereken en kucuk \(n\) degeri \(N(p,q)\). Sorulan sey bu \(N(p,q)\) degerlerinin toplami.
1) Eslenik terim.
Su sayiyi tanimlayalim:
$$\beta=\sqrt q-\sqrt p.$$
O zaman
$$A_n=\alpha^{2n}+\beta^{2n}$$
her zaman tam sayidir. Sebep, iki binom aciliminda tek sayida kok iceren tum terimlerin birbirini goturmesidir.
Boylece
$$\alpha^{2n}=A_n-\beta^{2n}$$
olur.
2) Kesir kismi ne zaman \(1\)'e gider?
\(p \lt q\) oldugu icin \(\beta \gt 0\). Kesir kisminin \(1\)'e gitmesi tam olarak \(\beta^{2n}\to0\) olmasi demektir; yani
$$0\lt\beta\lt1.$$
Dolayisiyla gecerli ciftler tam olarak
$$\sqrt q-\sqrt p\lt1$$
sartini saglayanlardir.
3) Kesir kismi neden \(1-\beta^{2n}\) olur?
Gecerli ciftlerde \(0\lt\beta^{2n}\lt1\) oldugu icin \(\alpha^{2n}\), tam sayi olan \(A_n\)'nin hemen altindadir. Bu nedenle
$$\{\alpha^{2n}\}=1-\beta^{2n}.$$
Problemin butun zorlugu burada kirilir: irrasyonel kuvvetin kesir kismi, cok kucuk pozitif bir terime indirgenir.
4) "Basinda en az \(K\) tane 9" kosulu.
Bir sayinin kesir kisminin basinda en az \(K\) tane \(9\) varsa
$$\{\alpha^{2n}\}\gt1-10^{-K}$$
olmalidir. Bu da
$$\beta^{2n}\lt10^{-K}$$
ile ayni seydir.
5) Logaritma alinca kapali form geliyor.
\(0\lt\beta^2\lt1\) icin
$$\lambda=-\log_{10}(\beta^2)\gt0$$
tanimi yaparsak esitssizlik
$$n\lambda\gt K$$
olur. O halde minimum deger
$$N(p,q)=\left\lceil\frac{K}{\lambda}\right\rceil=\left\lceil\frac{K}{-\log_{10}(\beta^2)}\right\rceil$$
seklindedir. Kodun minimal_n fonksiyonu tam olarak bunu, ceiling sinirlarinda cok kucuk bir toleransla hesaplar.
6) Calisan ornek: \((p,q)=(2,3)\).
Burada
$$\beta=\sqrt3-\sqrt2\approx0.3178372452,$$
$$\beta^2\approx0.1010205144,$$
$$\lambda\approx0.9955904242.$$
Bir adet baslangic \(9\) icin \(K=1\), dolayisiyla
$$N(2,3)=\left\lceil\frac{1}{0.9955904242}\right\rceil=2.$$
Gercekten de problemde verilen dizide \((\sqrt2+\sqrt3)^2\) kesir kisminda \(9\) ile baslamazken, dorduncu kuvvet bir \(9\), altinci kuvvet iki \(9\), sekizinci kuvvet uc \(9\) verir.
7) Kucuk tam checkpoint: \(M=5,\ K=1\).
Gecerli ciftler
$$ (1,2),\ (1,3),\ (2,3) $$
ve bunlarin katkiları
$$2,\ 4,\ 2$$
olur. Toplam
$$S(5,1)=8$$
cikar; bu da koddaki ikinci kontroldur.
8) Son toplam formulu.
Dolayisiyla aranan cevap
$$\sum_{\substack{1\le p \lt q\\ p+q\le 2011\\ \sqrt q-\sqrt p\lt1}} \left\lceil\frac{2011}{-\log_{10}\!\left((\sqrt q-\sqrt p)^2\right)}\right\rceil$$
olur.
1) \(p+q\le M\) ve \(p \lt q\) olan tum ciftleri dolas.
2) \(\beta=\sqrt q-\sqrt p\) hesapla.
3) \(\beta\ge1\) ise cifti atla.
4) \(\lambda=-\log_{10}(\beta^2)\) bul.
5) \(\lceil K/\lambda\rceil\) degerini toplama ekle.
Ucgensel bolgede aday cift sayisi
$$O(M^2)$$
kadardir. Her cift icin sabit sayida karekok, logaritma ve aritmetik islem vardir. Toplam zaman
$$O(M^2),$$
bellek ise
$$O(1)$$
olur.
Kod su degerleri kontrol eder:
$$N(2,3;1)=2,\qquad N(2,3;2)=3,\qquad N(2,3;3)=4,$$
ve
$$S(5,1)=8.$$
Tam problem icin \((M,K)=(2011,2011)\) oldugunda nihai cevap
$$709313889$$
olarak bulunur.
Para cada par
$$1\le p \lt q,\qquad p+q\le 2011,$$
definimos
$$\alpha=\sqrt p+\sqrt q.$$
Buscamos el menor \(n\) tal que la parte fraccionaria de \(\alpha^{2n}\) empiece con al menos \(2011\) nueves consecutivos. Luego sumamos esos valores minimos.
1) El conjugado util.
Sea
$$\beta=\sqrt q-\sqrt p.$$
Entonces
$$A_n=\alpha^{2n}+\beta^{2n}$$
siempre es entero, porque en las expansiones binomiales se cancelan los terminos radicales impares.
Por tanto
$$\alpha^{2n}=A_n-\beta^{2n}.$$
2) Cuando la parte fraccionaria tiende a \(1\).
Eso ocurre exactamente cuando \(\beta^{2n}\to0\), es decir, cuando
$$0\lt\beta\lt1.$$
3) Parte fraccionaria explicita.
En los pares validos se cumple \(0\lt\beta^{2n}\lt1\), asi que \(\alpha^{2n}\) queda justo por debajo del entero \(A_n\). Luego
$$\{\alpha^{2n}\}=1-\beta^{2n}.$$
4) Condicion de \(K\) nueves iniciales.
Tener al menos \(K\) nueves al principio de la parte fraccionaria equivale a
$$\{\alpha^{2n}\}\gt1-10^{-K},$$
o sea
$$\beta^{2n}\lt10^{-K}.$$
5) Paso logaritmico.
Definiendo
$$\lambda=-\log_{10}(\beta^2)\gt0,$$
obtenemos
$$n\lambda\gt K,$$
y por ello
$$N(p,q)=\left\lceil\frac{K}{\lambda}\right\rceil.$$
6) Ejemplo \((2,3)\).
Aqui \(\beta=\sqrt3-\sqrt2\approx0.317837\), asi que \(\lambda\approx0.9955904\). Para \(K=1\), resulta
$$N(2,3)=2.$$
Esto coincide con la sucesion mostrada en el enunciado.
7) Pequeño control completo.
Para \(M=5\) y \(K=1\), los pares validos son \((1,2)\), \((1,3)\) y \((2,3)\), con aportes \(2,4,2\). Por tanto
$$S(5,1)=8.$$
8) Suma final.
La expresion completa es
$$\sum_{\substack{1\le p \lt q\\ p+q\le 2011\\ \sqrt q-\sqrt p\lt1}} \left\lceil\frac{2011}{-\log_{10}\!\left((\sqrt q-\sqrt p)^2\right)}\right\rceil.$$
1) Recorrer todos los pares \((p,q)\) con \(p \lt q\) y \(p+q\le M\).
2) Calcular \(\beta=\sqrt q-\sqrt p\).
3) Si \(\beta\ge1\), descartar el par.
4) Calcular \(\lambda=-\log_{10}(\beta^2)\).
5) Sumar \(\lceil K/\lambda\rceil\).
El dominio triangular contiene \(O(M^2)\) pares, y cada uno requiere tiempo constante. Por tanto: tiempo \(O(M^2)\), memoria \(O(1)\).
El codigo verifica
$$N(2,3;1)=2,\qquad N(2,3;2)=3,\qquad N(2,3;3)=4,$$
y tambien
$$S(5,1)=8.$$
Para \((M,K)=(2011,2011)\), la respuesta final es
$$709313889.$$
对每个满足
$$1\le p \lt q,\qquad p+q\le 2011$$
的整数对，记
$$\alpha=\sqrt p+\sqrt q.$$
要求最小的 \(n\)，使得 \(\alpha^{2n}\) 的小数部分开头至少有 \(2011\) 个连续的 9，然后把这些最小值求和。
1）共轭量。
定义
$$\beta=\sqrt q-\sqrt p.$$
则
$$A_n=\alpha^{2n}+\beta^{2n}$$
总是整数，因为二项展开中奇数次根号项会彼此抵消。
于是
$$\alpha^{2n}=A_n-\beta^{2n}.$$
2）小数部分何时趋于 \(1\)。
这恰好等价于 \(\beta^{2n}\to0\)，也就是
$$0\lt\beta\lt1.$$
3）小数部分的精确形式。
对有效的 \((p,q)\)，有 \(0\lt\beta^{2n}\lt1\)，所以 \(\alpha^{2n}\) 恰好落在整数 \(A_n\) 的下方，故
$$\{\alpha^{2n}\}=1-\beta^{2n}.$$
4）“前面至少有 \(K\) 个 9” 的条件。
这等价于
$$\{\alpha^{2n}\}\gt1-10^{-K},$$
也即
$$\beta^{2n}\lt10^{-K}.$$
5）取对数。
记
$$\lambda=-\log_{10}(\beta^2)\gt0,$$
则条件变成
$$n\lambda\gt K.$$
因此
$$N(p,q)=\left\lceil\frac{K}{\lambda}\right\rceil.$$
6）例子 \((2,3)\)。
此时 \(\beta=\sqrt3-\sqrt2\approx0.317837\)，所以 \(\lambda\approx0.9955904\)。当 \(K=1\) 时，
$$N(2,3)=2,$$
与题目给出的幂次序列完全一致。
7）小规模完整检查。
当 \(M=5,\ K=1\) 时，有效对为 \((1,2)\)、\((1,3)\)、\((2,3)\)，对应贡献为 \(2,4,2\)，所以
$$S(5,1)=8.$$
8）最终求和式。
最终答案就是
$$\sum_{\substack{1\le p \lt q\\ p+q\le 2011\\ \sqrt q-\sqrt p\lt1}} \left\lceil\frac{2011}{-\log_{10}\!\left((\sqrt q-\sqrt p)^2\right)}\right\rceil.$$
1) 枚举所有 \(p \lt q,\ p+q\le M\) 的整数对。
2) 计算 \(\beta=\sqrt q-\sqrt p\)。
3) 若 \(\beta\ge1\)，则跳过。
4) 计算 \(\lambda=-\log_{10}(\beta^2)\)。
5) 将 \(\lceil K/\lambda\rceil\) 加入总和。
三角形区域中的候选对数量为 \(O(M^2)\)。每对只做常数次平方根、对数和算术运算，所以总时间复杂度为 \(O(M^2)\)，空间复杂度为 \(O(1)\)。
程序会检查
$$N(2,3;1)=2,\qquad N(2,3;2)=3,\qquad N(2,3;3)=4,$$
以及
$$S(5,1)=8.$$
对题目中的 \((M,K)=(2011,2011)\)，最终答案为
$$709313889.$$
Для каждой пары
$$1\le p \lt q,\qquad p+q\le 2011$$
рассматривается число
$$\alpha=\sqrt p+\sqrt q.$$
Нужно найти минимальное \(n\), при котором дробная часть \(\alpha^{2n}\) начинается как минимум с \(2011\) девяток, а затем просуммировать эти минимальные значения.
1) Полезное сопряженное выражение.
Положим
$$\beta=\sqrt q-\sqrt p.$$
Тогда
$$A_n=\alpha^{2n}+\beta^{2n}$$
всегда целое число, потому что в биномиальных разложениях сокращаются все нечетные радикальные слагаемые.
Следовательно,
$$\alpha^{2n}=A_n-\beta^{2n}.$$
2) Когда дробная часть стремится к \(1\).
Это происходит тогда и только тогда, когда \(\beta^{2n}\to0\), то есть
$$0\lt\beta\lt1.$$
3) Дробная часть в явном виде.
Для допустимых пар имеем \(0\lt\beta^{2n}\lt1\), значит \(\alpha^{2n}\) находится чуть ниже целого \(A_n\). Поэтому
$$\{\alpha^{2n}\}=1-\beta^{2n}.$$
4) Условие на \(K\) ведущих девяток.
Оно равносильно
$$\{\alpha^{2n}\}\gt1-10^{-K},$$
то есть
$$\beta^{2n}\lt10^{-K}.$$
5) Переход к логарифмам.
Пусть
$$\lambda=-\log_{10}(\beta^2)\gt0.$$
Тогда
$$n\lambda\gt K,$$
и потому
$$N(p,q)=\left\lceil\frac{K}{\lambda}\right\rceil.$$
6) Пример \((2,3)\).
Здесь \(\beta=\sqrt3-\sqrt2\approx0.317837\), откуда \(\lambda\approx0.9955904\). Для \(K=1\) получаем
$$N(2,3)=2.$$
7) Малый полный checkpoint.
При \(M=5,\ K=1\) допустимые пары: \((1,2)\), \((1,3)\), \((2,3)\), с вкладами \(2,4,2\). Итак,
$$S(5,1)=8.$$
8) Итоговая формула.
Ответ равен
$$\sum_{\substack{1\le p \lt q\\ p+q\le 2011\\ \sqrt q-\sqrt p\lt1}} \left\lceil\frac{2011}{-\log_{10}\!\left((\sqrt q-\sqrt p)^2\right)}\right\rceil.$$
1) Перебрать все пары \((p,q)\) с \(p \lt q\) и \(p+q\le M\).
2) Вычислить \(\beta=\sqrt q-\sqrt p\).
3) Если \(\beta\ge1\), пропустить пару.
4) Посчитать \(\lambda=-\log_{10}(\beta^2)\).
5) Добавить \(\lceil K/\lambda\rceil\) к сумме.
Число пар в треугольной области равно \(O(M^2)\). На каждую пару приходится константная работа, так что общая сложность: время \(O(M^2)\), память \(O(1)\).
Код проверяет
$$N(2,3;1)=2,\qquad N(2,3;2)=3,\qquad N(2,3;3)=4,$$
и
$$S(5,1)=8.$$
Для \((M,K)=(2011,2011)\) итоговый ответ:
$$709313889.$$
لكل زوج
$$1\le p \lt q,\qquad p+q\le 2011$$
نعرّف
$$\alpha=\sqrt p+\sqrt q.$$
نريد أصغر \(n\) بحيث تبدأ الكسور العشرية للعدد \(\alpha^{2n}\) بما لا يقل عن \(2011\) تسعة متتالية، ثم نجمع هذه القيم الدنيا.
1) العدد المرافق المفيد.
لنضع
$$\beta=\sqrt q-\sqrt p.$$
عندئذ
$$A_n=\alpha^{2n}+\beta^{2n}$$
عدد صحيح دائماً، لأن الحدود الجذرية ذات الرتبة الفردية تلغى بعضها بعضاً في التوسعين الثنائيين.
إذن
$$\alpha^{2n}=A_n-\beta^{2n}.$$
2) متى يقترب الجزء الكسري من \(1\)؟
يحدث هذا بالضبط عندما \(\beta^{2n}\to0\)، أي عندما
$$0\lt\beta\lt1.$$
3) الجزء الكسري يساوي \(1-\beta^{2n}\).
للأزواج المسموح بها لدينا \(0\lt\beta^{2n}\lt1\)، ومن ثم يكون \(\alpha^{2n}\) أقل بقليل من العدد الصحيح \(A_n\). لذلك
$$\{\alpha^{2n}\}=1-\beta^{2n}.$$
4) شرط وجود \(K\) تسعات متتالية في البداية.
هذا يكافئ
$$\{\alpha^{2n}\}\gt1-10^{-K},$$
أي
$$\beta^{2n}\lt10^{-K}.$$
5) الانتقال إلى اللوغاريتم.
إذا عرفنا
$$\lambda=-\log_{10}(\beta^2)\gt0,$$
فإن الشرط يصبح
$$n\lambda\gt K.$$
ومن هنا
$$N(p,q)=\left\lceil\frac{K}{\lambda}\right\rceil.$$
6) المثال \((2,3)\).
لدينا \(\beta=\sqrt3-\sqrt2\approx0.317837\)، ومنه \(\lambda\approx0.9955904\). عندما \(K=1\) نحصل على
$$N(2,3)=2.$$
7) نقطة تحقق صغيرة كاملة.
عند \(M=5\) و\(K=1\)، الأزواج المسموح بها هي \((1,2)\) و\((1,3)\) و\((2,3)\)، ومساهماتها \(2,4,2\). لذلك
$$S(5,1)=8.$$
8) صيغة المجموع النهائية.
إذن الجواب هو
$$\sum_{\substack{1\le p \lt q\\ p+q\le 2011\\ \sqrt q-\sqrt p\lt1}} \left\lceil\frac{2011}{-\log_{10}\!\left((\sqrt q-\sqrt p)^2\right)}\right\rceil.$$
1) نمر على جميع الأزواج \((p,q)\) بحيث \(p \lt q\) و\(p+q\le M\).
2) نحسب \(\beta=\sqrt q-\sqrt p\).
3) إذا كانت \(\beta\ge1\) نتجاهل الزوج.
4) نحسب \(\lambda=-\log_{10}(\beta^2)\).
5) نضيف \(\lceil K/\lambda\rceil\) إلى المجموع.
عدد الأزواج في المجال المثلثي هو \(O(M^2)\)، والعمل لكل زوج ثابت. لذلك الزمن \(O(M^2)\) والذاكرة \(O(1)\).
يتحقق البرنامج من
$$N(2,3;1)=2,\qquad N(2,3;2)=3,\qquad N(2,3;3)=4,$$
وكذلك من
$$S(5,1)=8.$$
أما للمدخل الكامل \((M,K)=(2011,2011)\) فالنتيجة النهائية هي
$$709313889.$$