We must count the integers \(n\) with \(1<n<10^7\) such that \(n\) and \(n+1\) have the same number of positive divisors. If \(d(m)\) denotes the divisor-count function, the required quantity is
$$A=\sum_{n=2}^{10^7-1}\mathbf{1}_{d(n)=d(n+1)}.$$
Consecutive integers are always coprime, so this is not a question about two numbers sharing prime factors. Instead, it asks when two different factorizations happen to produce the same divisor count. The implementations therefore avoid factoring one pair at a time and compute the whole divisor-count table in a single structured pass.
The problem is governed by the arithmetic function \(d(m)\), also written \(\tau(m)\). If
$$m=\prod_{i=1}^{r} p_i^{a_i},$$
then the number of positive divisors is
$$d(m)=\prod_{i=1}^{r}(a_i+1).$$
This explains why neighboring integers can still tie. For example, \(14=2^1\cdot 7^1\) and \(15=3^1\cdot 5^1\), so both have \(4\) divisors even though \(\gcd(14,15)=1\).
Factoring each integer separately would repeat the same work many times. The key observation used by all three implementations is the equivalent identity
$$d(m)=\sum_{k\mid m} 1=\sum_{k=1}^{10^7+1}\mathbf{1}_{k\mid m}.$$
For a fixed candidate divisor \(k\), the integers divisible by \(k\) are exactly
$$k,2k,3k,\dots.$$
So if an array starts at zero and we add \(1\) to every multiple of \(k\), then \(k\) contributes exactly once to each number it divides and never contributes to numbers it does not divide.
After the outer loop has processed \(1,2,\dots,D\), the table entry at \(m\) equals
$$c_D(m)=\sum_{k=1}^{D}\mathbf{1}_{k\mid m}.$$
That is the number of divisors of \(m\) that are at most \(D\). Whenever \(m\le D\), every positive divisor of \(m\) has already appeared, so \(c_D(m)=d(m)\). By running the sieve through \(10^7+1\), the implementations guarantee that every entry needed in the final comparison stage already stores the exact divisor count.
The factorization formula gives
$$14=2^1\cdot 7^1,\qquad 15=3^1\cdot 5^1,$$
hence
$$d(14)=(1+1)(1+1)=4,\qquad d(15)=(1+1)(1+1)=4.$$
The sieve sees the same fact from a different angle: the entry for \(14\) is incremented by the passes for \(1,2,7,14\), while the entry for \(15\) is incremented by the passes for \(1,3,5,15\). Once the table has been filled, the pair \((14,15)\) is recognized automatically as a match.
After the sieve, nothing subtle remains. The answer is simply the number of adjacent equalities in the divisor-count sequence:
$$A=\#\{n:2\le n<10^7,\ d(n)=d(n+1)\}.$$
So the second phase is a linear scan through neighboring entries. This is the right mathematical reduction for Problem 179: build the global sequence \(d(1),d(2),\dots,d(10^7)\) once, then test adjacency.
The C++, Python, and Java implementations allocate an array that covers the needed range and initialize it with zeros. The outer loop selects a divisor candidate \(d\), and the inner loop visits every multiple of \(d\), adding one at each visited position. In array form, this realizes the identity \(d(m)=\sum_{k\mid m}1\) for all \(m\) simultaneously instead of recomputing it number by number.
The C++ implementation also includes a small checkpoint at \(100\): in that shorter range, the correct count is \(15\). That sanity check confirms that the sieve and the final scan agree on a case that is easy to verify independently.
Once the table is complete, the implementation performs a single pass over \(n=2,3,\dots,10^7-1\). Whenever the counts at \(n\) and \(n+1\) are equal, it increments the answer. The three language versions are mathematically identical here; they differ only in syntax and in the concrete container types used to store the table.
The sieve performs
$$\sum_{d=1}^{10^7+1}\left\lfloor\frac{10^7+1}{d}\right\rfloor$$
array updates, because divisor \(d\) touches each of its multiples exactly once. This is a harmonic sum, so the running time is \(O(N\log N)\) with \(N=10^7\), more precisely \(N\log N+O(N)\).
The final adjacency scan is \(O(N)\), which does not change the overall asymptotic cost. Memory usage is \(O(N)\) for the divisor-count table. That tradeoff is exactly what makes the problem practical: one global sieve and one linear pass replace millions of repeated factorizations.
Gesucht ist die Anzahl der ganzen Zahlen \(n\) mit \(1<n<10^7\), für die \(n\) und \(n+1\) gleich viele positive Teiler besitzen. Mit der Teilerfunktion \(d(m)\) lautet die gesuchte Größe
$$A=\sum_{n=2}^{10^7-1}\mathbf{1}_{d(n)=d(n+1)}.$$
Da aufeinanderfolgende Zahlen immer teilerfremd sind, geht es nicht darum, gemeinsame Primfaktoren auszunutzen. Vielmehr können zwei verschiedene Primfaktorzerlegungen denselben Teileranzahlwert liefern. Deshalb berechnet die Implementierung nicht jedes Paar einzeln, sondern erzeugt die gesamte Folge der Teileranzahlen in einem einzigen strukturierten Durchlauf.
Das zentrale Objekt ist die Teileranzahlfunktion \(d(m)\), oft auch \(\tau(m)\) genannt. Für
$$m=\prod_{i=1}^{r} p_i^{a_i}$$
gilt
$$d(m)=\prod_{i=1}^{r}(a_i+1).$$
Diese Formel zeigt sofort, warum benachbarte Zahlen trotzdem gleich viele Teiler haben können. Zum Beispiel sind \(14=2^1\cdot 7^1\) und \(15=3^1\cdot 5^1\), also besitzen beide genau \(4\) positive Teiler, obwohl \(\gcd(14,15)=1\) ist.
Eine Einzelzerlegung jeder Zahl würde dieselbe Information immer wieder neu erzeugen. Alle drei Implementierungen verwenden stattdessen die äquivalente Identität
$$d(m)=\sum_{k\mid m}1=\sum_{k=1}^{10^7+1}\mathbf{1}_{k\mid m}.$$
Für einen festen möglichen Teiler \(k\) sind genau die Zahlen durch \(k\) teilbar, die zu den Vielfachen
$$k,2k,3k,\dots$$
gehören. Erhöht man also in einem Array bei jedem Vielfachen von \(k\) den Zähler um \(1\), dann trägt \(k\) genau einmal zu jeder Zahl bei, die er teilt, und zu keiner anderen.
Nachdem die äußere Schleife alle Werte \(1,2,\dots,D\) verarbeitet hat, steht an Position \(m\) der Wert
$$c_D(m)=\sum_{k=1}^{D}\mathbf{1}_{k\mid m}.$$
Das ist die Anzahl der Teiler von \(m\), die höchstens \(D\) sind. Sobald \(m\le D\) gilt, sind bereits alle positiven Teiler von \(m\) erfasst, also \(c_D(m)=d(m)\). Weil die Implementierungen bis \(10^7+1\) sieben, liegen im anschließenden Vergleichsschritt überall die exakten Teileranzahlen vor.
Aus der Primfaktorzerlegung folgt
$$14=2^1\cdot 7^1,\qquad 15=3^1\cdot 5^1,$$
und damit
$$d(14)=(1+1)(1+1)=4,\qquad d(15)=(1+1)(1+1)=4.$$
Im Siebbild sieht man dieselbe Aussage anders: Die Position \(14\) wird genau in den Durchgängen für \(1,2,7,14\) erhöht, die Position \(15\) in den Durchgängen für \(1,3,5,15\). Nach dem Aufbau der Tabelle ist das Paar \((14,15)\) also automatisch als Treffer erkennbar.
Ist das Array einmal gefüllt, bleibt nur noch eine einfache Nachbarschaftsprüfung. Gesucht ist
$$A=\#\{n:2\le n<10^7,\ d(n)=d(n+1)\}.$$
Die zweite Phase ist daher lediglich ein linearer Durchlauf über benachbarte Einträge. Genau diese Reduktion passt zu Problem 179: erst die gesamte Folge \(d(1),d(2),\dots,d(10^7)\) erzeugen, dann benachbarte Werte vergleichen.
Die C++-, Python- und Java-Implementierungen legen ein Array für den benötigten Bereich an und initialisieren es mit Nullen. Die äußere Schleife wählt einen Kandidaten \(d\) als möglichen Teiler, die innere Schleife besucht alle Vielfachen von \(d\) und erhöht dort den Zähler. Auf Array-Ebene ist das exakt die gleichzeitige Auswertung der Identität \(d(m)=\sum_{k\mid m}1\) für alle \(m\).
Die C++-Version enthält zusätzlich einen kleinen Prüfpunkt bei \(100\): In diesem kleineren Bereich ist die korrekte Anzahl \(15\). Damit wird bestätigt, dass Siebphase und Endscan auf einem überschaubaren Testfall konsistent zusammenarbeiten.
Nach dem Sieb enthält das Array bereits die vollständige Folge der Teileranzahlen. Danach läuft die Implementierung einmal über \(n=2,3,\dots,10^7-1\) und erhöht die Antwort immer dann, wenn die Einträge bei \(n\) und \(n+1\) übereinstimmen. Mathematisch ist diese zweite Phase in allen drei Sprachen identisch; nur Syntax und konkrete Speicherstrukturen unterscheiden sich.
Das Sieb führt
$$\sum_{d=1}^{10^7+1}\left\lfloor\frac{10^7+1}{d}\right\rfloor$$
Array-Aktualisierungen aus, weil jeder Teilerkandidat \(d\) genau seine Vielfachen besucht. Diese harmonische Summe liefert eine Laufzeit von \(O(N\log N)\) für \(N=10^7\), genauer \(N\log N+O(N)\).
Der abschließende Nachbarschaftsvergleich ist linear und ändert die Asymptotik nicht. Der Speicherbedarf beträgt \(O(N)\) für das Array der Teileranzahlen. Gerade diese Kombination macht die Aufgabe lösbar: ein globales Sieb plus ein linearer Enddurchlauf statt Millionen einzelner Zerlegungen.
Aranan şey, \(1<n<10^7\) koşulunu sağlayan ve \(n\) ile \(n+1\) sayılarının pozitif bölen sayıları eşit olan tüm \(n\) değerlerinin sayısıdır. \(d(m)\) bölen sayısı fonksiyonu olmak üzere hedef büyüklük
$$A=\sum_{n=2}^{10^7-1}\mathbf{1}_{d(n)=d(n+1)}$$
şeklinde yazılır. Ardışık sayılar her zaman aralarında asaldır; dolayısıyla burada ortak asal çarpanlardan yararlanılan bir durum yoktur. Esas mesele, iki farklı asal çarpan yapısının aynı bölen sayısına yol açabilmesidir. Bu yüzden uygulamalar her çifti ayrı ayrı çarpanlarına ayırmak yerine tüm bölen sayıları dizisini tek bir geçişte üretir.
Problemin merkezindeki nesne bölen sayısı fonksiyonu \(d(m)\), yani \(\tau(m)\)'dir. Eğer
$$m=\prod_{i=1}^{r} p_i^{a_i}$$
ise
$$d(m)=\prod_{i=1}^{r}(a_i+1)$$
olur. Bu formül, komşu sayıların neden yine de eşit bölen sayısına sahip olabildiğini açıklar. Örneğin \(14=2^1\cdot 7^1\) ve \(15=3^1\cdot 5^1\) olduğundan, \(\gcd(14,15)=1\) olmasına rağmen her ikisinin de tam \(4\) böleni vardır.
Her sayıyı tek tek asal çarpanlarına ayırmak çok fazla tekrar üretir. Üç uygulamanın ortak dayanağı şu eşdeğer özdeşliktir:
$$d(m)=\sum_{k\mid m}1=\sum_{k=1}^{10^7+1}\mathbf{1}_{k\mid m}.$$
Sabit bir \(k\) için, \(k\)'nın böldüğü sayılar tam olarak
$$k,2k,3k,\dots$$
dizisindeki katlardır. O halde bir diziyi sıfırdan başlatıp her \(k\) için bütün katlarına \(1\) eklersek, her gerçek bölen ilgili sayıya tam bir katkı yapmış olur.
Dış döngü \(1,2,\dots,D\) değerlerini bitirdiğinde, \(m\) konumundaki sayaç
$$c_D(m)=\sum_{k=1}^{D}\mathbf{1}_{k\mid m}$$
değerine eşittir. Bu, \(m\)'nin \(D\)'den büyük olmayan bölenlerinin sayısıdır. Eğer \(m\le D\) ise \(m\)'nin tüm pozitif bölenleri zaten görülmüştür; dolayısıyla \(c_D(m)=d(m)\) olur. Uygulamalar eleği \(10^7+1\)'e kadar yürüttüğü için son karşılaştırma aşamasında gereken her hücre gerçek bölen sayısını içerir.
Asal çarpanlara ayırma ile
$$14=2^1\cdot 7^1,\qquad 15=3^1\cdot 5^1,$$
dolayısıyla
$$d(14)=(1+1)(1+1)=4,\qquad d(15)=(1+1)(1+1)=4.$$
Elek açısından bakılırsa \(14\) hücresi yalnızca \(1,2,7,14\) geçişlerinde, \(15\) hücresi ise \(1,3,5,15\) geçişlerinde artar. Tablo tamamlandığında \((14,15)\) çifti herhangi bir ek sayı teorisi işlemi olmadan doğrudan eşleşme olarak görünür.
Bölen sayıları tablosu kurulduktan sonra geriye yalnızca komşu hücreleri karşılaştırmak kalır. Aranan değer
$$A=\#\{n:2\le n<10^7,\ d(n)=d(n+1)\}$$
olduğundan ikinci faz düz bir doğrusal taramadır. Problem 179 için doğru matematiksel indirgeme tam olarak budur: önce \(d(1),d(2),\dots,d(10^7)\) dizisini topluca üret, sonra ardışık eşitlikleri say.
C++, Python ve Java uygulamaları gerekli aralığı kapsayan bir dizi oluşturup tüm elemanları sıfırlar. Dış döngü olası bölen \(d\)'yi seçer; iç döngü ise \(d\)'nin tüm katlarını dolaşır ve ziyaret edilen her konuma \(1\) ekler. Dizi üzerinde yapılan bu işlem, \(d(m)=\sum_{k\mid m}1\) özdeşliğinin bütün \(m\) değerleri için aynı anda uygulanmış hâlidir.
C++ uygulamasında ayrıca \(100\) için küçük bir kontrol bulunur: bu aralıkta doğru sayı \(15\)'tir. Bu, eleğin ve son taramanın kolay denetlenebilen bir örnekte tutarlı çalıştığını gösteren yararlı bir sağlamadır.
Eleğin ardından dizi artık bölen sayılarının tamamını içerir. Uygulama daha sonra \(n=2,3,\dots,10^7-1\) boyunca tek bir geçiş yapar ve \(n\) ile \(n+1\) hücreleri eşitse cevabı bir artırır. Üç dildeki sürümler burada aynı matematiği uygular; değişen şey yalnızca sözdizimi ve kullanılan veri yapılarının ayrıntılarıdır.
Elek aşaması
$$\sum_{d=1}^{10^7+1}\left\lfloor\frac{10^7+1}{d}\right\rfloor$$
adet güncelleme yapar; çünkü her \(d\), yalnızca kendi katlarını ziyaret eder. Bu toplam harmonik yapıdadır, dolayısıyla \(N=10^7\) için zaman karmaşıklığı \(O(N\log N)\), daha hassas olarak \(N\log N+O(N)\) olur.
Son komşuluk taraması \(O(N)\) maliyetlidir ve genel asimptotiği değiştirmez. Bellek kullanımı bölen sayıları dizisi için \(O(N)\)'dir. Soruyu uygulanabilir kılan şey de budur: milyonlarca ayrı çarpan ayırma yerine tek bir küresel elek ve tek bir doğrusal geçiş yapılır.
Hay que contar los enteros \(n\) con \(1<n<10^7\) tales que \(n\) y \(n+1\) tengan el mismo número de divisores positivos. Si \(d(m)\) denota la función que cuenta divisores, la cantidad buscada es
$$A=\sum_{n=2}^{10^7-1}\mathbf{1}_{d(n)=d(n+1)}.$$
Como dos enteros consecutivos siempre son coprimos, la igualdad no aparece por compartir factores primos. Lo que ocurre es que dos factorizaciones distintas pueden producir el mismo valor de \(d\). Por eso la implementación no factoriza pareja por pareja, sino que construye toda la tabla de divisores de una sola vez.
El objeto principal es la función número de divisores \(d(m)\), también escrita \(\tau(m)\). Si
$$m=\prod_{i=1}^{r} p_i^{a_i},$$
entonces
$$d(m)=\prod_{i=1}^{r}(a_i+1).$$
Esta fórmula muestra por qué dos vecinos pueden empatar. Por ejemplo, \(14=2^1\cdot 7^1\) y \(15=3^1\cdot 5^1\), así que ambos tienen \(4\) divisores aunque \(\gcd(14,15)=1\).
Factorizar cada entero por separado repetiría mucho trabajo. Las tres implementaciones usan la identidad equivalente
$$d(m)=\sum_{k\mid m}1=\sum_{k=1}^{10^7+1}\mathbf{1}_{k\mid m}.$$
Para un posible divisor fijo \(k\), los enteros divisibles por \(k\) son exactamente sus múltiplos
$$k,2k,3k,\dots.$$
Por tanto, si mantenemos un arreglo de contadores y, para cada \(k\), sumamos \(1\) en todos sus múltiplos, cada divisor verdadero aporta una unidad exactamente a los lugares correctos.
Después de procesar \(1,2,\dots,D\) en el bucle exterior, la entrada correspondiente a \(m\) vale
$$c_D(m)=\sum_{k=1}^{D}\mathbf{1}_{k\mid m}.$$
Ese número cuenta los divisores de \(m\) que no exceden \(D\). Cuando \(m\le D\), todos los divisores positivos de \(m\) ya han aparecido, así que \(c_D(m)=d(m)\). Como las implementaciones ejecutan el cribado hasta \(10^7+1\), todas las posiciones necesarias para la fase final contienen el valor exacto.
Por factorización prima,
$$14=2^1\cdot 7^1,\qquad 15=3^1\cdot 5^1,$$
de donde
$$d(14)=(1+1)(1+1)=4,\qquad d(15)=(1+1)(1+1)=4.$$
Desde la perspectiva del cribado ocurre lo mismo: la casilla de \(14\) recibe incrementos en los pasos \(1,2,7,14\), mientras que la de \(15\) los recibe en \(1,3,5,15\). Una vez construida la tabla, el par \((14,15)\) se detecta automáticamente como válido.
Con todos los valores de \(d(m)\) ya calculados, no hace falta ninguna teoría adicional entre vecinos. La respuesta es simplemente
$$A=\#\{n:2\le n<10^7,\ d(n)=d(n+1)\}.$$
Eso convierte la segunda fase en un barrido lineal de la tabla. Para el Problema 179, la reducción natural es exactamente esta: construir una vez la sucesión global de números de divisores y luego revisar las igualdades consecutivas.
Las implementaciones en C++, Python y Java reservan un arreglo para el rango necesario y lo inicializan con ceros. El bucle exterior elige un candidato a divisor \(d\); el interior recorre \(d,2d,3d,\dots\) y suma uno en cada posición visitada. En otras palabras, el programa evalúa la identidad \(d(m)=\sum_{k\mid m}1\) de manera simultánea para todos los enteros del rango.
La implementación en C++ además incluye una comprobación pequeña en \(100\): en ese caso el conteo correcto es \(15\). Es una verificación útil para asegurar que el cribado y el barrido final están coordinados correctamente.
Después del cribado, el arreglo ya contiene toda la secuencia de números de divisores. La implementación recorre entonces \(n=2,3,\dots,10^7-1\) y aumenta la respuesta cada vez que las posiciones \(n\) y \(n+1\) coinciden. Las tres versiones hacen exactamente el mismo trabajo matemático; solo cambian la sintaxis y los detalles de almacenamiento.
La fase de cribado realiza
$$\sum_{d=1}^{10^7+1}\left\lfloor\frac{10^7+1}{d}\right\rfloor$$
actualizaciones de arreglo, porque cada \(d\) visita una vez cada múltiplo suyo. Esta suma es armónica, de modo que el tiempo total es \(O(N\log N)\) con \(N=10^7\), más precisamente \(N\log N+O(N)\).
El barrido final es lineal y no altera la cota dominante. La memoria es \(O(N)\) para almacenar la tabla de divisores. Ese es el equilibrio correcto para este problema: un cribado global y una pasada final sustituyen a millones de factorizaciones independientes.
题目要求统计所有满足 \(1<n<10^7\) 的整数 \(n\)，使得 \(n\) 与 \(n+1\) 拥有相同数量的正因子。记 \(d(m)\) 为正因子个数函数，则目标可以写成
$$A=\sum_{n=2}^{10^7-1}\mathbf{1}_{d(n)=d(n+1)}.$$
连续整数永远互素，因此这里的难点并不是处理公共质因子，而是理解两种完全不同的质因数分解为什么仍可能得到相同的因子个数。实现没有对每一对相邻整数单独分解，而是先一次性建立整个区间的因子个数表，再做相邻比较。
核心对象是因子个数函数 \(d(m)\)，也常写作 \(\tau(m)\)。若
$$m=\prod_{i=1}^{r} p_i^{a_i},$$
那么
$$d(m)=\prod_{i=1}^{r}(a_i+1).$$
这条公式立刻说明了为什么相邻整数也可能“打平”。例如 \(14=2^1\cdot 7^1\)，\(15=3^1\cdot 5^1\)，虽然 \(\gcd(14,15)=1\)，但二者的因子个数都等于 \(4\)。
如果把区间中的每个数都单独做质因数分解，会重复大量工作。三份实现共同利用的是下面这个等价表达式：
$$d(m)=\sum_{k\mid m}1=\sum_{k=1}^{10^7+1}\mathbf{1}_{k\mid m}.$$
对于固定的候选因子 \(k\)，所有能被 \(k\) 整除的整数恰好就是它的倍数
$$k,2k,3k,\dots.$$
因此，只要准备一个初始全为零的数组，并且对每个 \(k\) 把它的所有倍数对应位置都加一，那么每个真实因子都会且只会向正确的数贡献一次。
当外层循环已经处理完 \(1,2,\dots,D\) 以后，数组中位置 \(m\) 的值就是
$$c_D(m)=\sum_{k=1}^{D}\mathbf{1}_{k\mid m}.$$
这表示 \(m\) 的所有不超过 \(D\) 的正因子个数。一旦 \(m\le D\)，那么 \(m\) 的每个正因子都已经在外层循环中出现过，所以此时 \(c_D(m)=d(m)\)。实现把筛法一直做到 \(10^7+1\)，于是最终比较阶段用到的每个位置都已经是准确的因子个数。
从质因数分解出发，
$$14=2^1\cdot 7^1,\qquad 15=3^1\cdot 5^1,$$
所以
$$d(14)=(1+1)(1+1)=4,\qquad d(15)=(1+1)(1+1)=4.$$
从筛法角度看，同样的事实表现为：位置 \(14\) 恰好会在处理 \(1,2,7,14\) 时被加一；位置 \(15\) 恰好会在处理 \(1,3,5,15\) 时被加一。表格一旦建好，\((14,15)\) 这对相邻整数就会自动被识别为满足条件。
当所有 \(d(m)\) 都准备好以后，剩下的工作已经非常直接。答案就是相邻位置上相等的次数：
$$A=\#\{n:2\le n<10^7,\ d(n)=d(n+1)\}.$$
因此第二阶段只是一次线性扫描。对 Problem 179 来说，最自然的数学化简就是：先整体求出 \(d(1),d(2),\dots,d(10^7)\)，再检查相邻两项是否相等。
C++、Python 和 Java 实现都先分配一个足够覆盖所需范围的数组，并把它初始化为零。外层循环取一个候选因子 \(d\)，内层循环依次访问 \(d,2d,3d,\dots\) 这些倍数位置，每访问一次就把该位置的计数加一。换句话说，程序是在数组上同时实现恒等式 \(d(m)=\sum_{k\mid m}1\)。
C++ 实现还带有一个较小的校验点 \(100\)：在这个范围内，正确计数是 \(15\)。这类小规模检查不会改变算法本身，但能帮助确认筛法阶段与最终扫描阶段配合正确。
筛法完成后，数组中已经存放了完整的因子个数序列。实现随后对 \(n=2,3,\dots,10^7-1\) 做一次顺序扫描，只要 \(n\) 与 \(n+1\) 位置上的值相同，就把答案加一。三种语言版本在数学上完全一致，区别只体现在语法和具体的存储细节上。
筛法阶段总共进行了
$$\sum_{d=1}^{10^7+1}\left\lfloor\frac{10^7+1}{d}\right\rfloor$$
次数组更新，因为每个 \(d\) 只访问自己的倍数一次。这是一个典型的调和级数型求和，所以总时间复杂度为 \(O(N\log N)\)，其中 \(N=10^7\)，更精细地说是 \(N\log N+O(N)\)。
最后的相邻比较只是 \(O(N)\) 的线性过程，不会改变主导项。空间复杂度为 \(O(N)\)，用于保存因子个数表。正是这种一次全局筛表加一次线性扫描的结构，才让题目在 \(10^7\) 的范围上变得可行。
Нужно посчитать все целые \(n\), удовлетворяющие \(1<n<10^7\), для которых числа \(n\) и \(n+1\) имеют одинаковое количество положительных делителей. Если \(d(m)\) обозначает функцию числа делителей, то искомая величина равна
$$A=\sum_{n=2}^{10^7-1}\mathbf{1}_{d(n)=d(n+1)}.$$
Соседние целые всегда взаимно просты, поэтому задача не сводится к общим простым множителям. Она спрашивает, когда две разные факторизации дают одно и то же значение функции числа делителей. Именно поэтому реализации не раскладывают каждую пару отдельно, а сначала строят всю таблицу значений \(d(m)\) на нужном диапазоне.
Главный объект здесь - функция числа делителей \(d(m)\), часто обозначаемая \(\tau(m)\). Если
$$m=\prod_{i=1}^{r} p_i^{a_i},$$
то
$$d(m)=\prod_{i=1}^{r}(a_i+1).$$
Эта формула сразу показывает, почему соседние числа могут давать одинаковый результат. Например, \(14=2^1\cdot 7^1\) и \(15=3^1\cdot 5^1\), поэтому оба имеют ровно \(4\) положительных делителя, хотя \(\gcd(14,15)=1\).
Если факторизовать каждое число по отдельности, одна и та же работа будет повторяться снова и снова. Три реализации опираются на эквивалентную запись
$$d(m)=\sum_{k\mid m}1=\sum_{k=1}^{10^7+1}\mathbf{1}_{k\mid m}.$$
Для фиксированного потенциального делителя \(k\) все подходящие числа - это в точности его кратные
$$k,2k,3k,\dots.$$
Значит, если завести массив счётчиков и для каждого \(k\) прибавлять \(1\) ко всем его кратным, то каждый настоящий делитель попадёт в нужную ячейку ровно один раз.
После того как внешний цикл обработал значения \(1,2,\dots,D\), в позиции \(m\) хранится
$$c_D(m)=\sum_{k=1}^{D}\mathbf{1}_{k\mid m}.$$
Это число делителей \(m\), не превосходящих \(D\). Когда \(m\le D\), все положительные делители числа \(m\) уже учтены, и потому \(c_D(m)=d(m)\). Поскольку реализации просеивают значения до \(10^7+1\), к моменту финального прохода все нужные элементы содержат точное число делителей.
Из разложения на простые множители имеем
$$14=2^1\cdot 7^1,\qquad 15=3^1\cdot 5^1,$$
поэтому
$$d(14)=(1+1)(1+1)=4,\qquad d(15)=(1+1)(1+1)=4.$$
С точки зрения решета происходит то же самое: ячейка \(14\) увеличивается проходами для \(1,2,7,14\), а ячейка \(15\) - проходами для \(1,3,5,15\). Когда таблица построена, пара \((14,15)\) автоматически распознаётся как подходящая.
После построения таблицы никаких дополнительных трюков уже не требуется. Ответ есть просто количество соседних индексов, на которых значения совпадают:
$$A=\#\{n:2\le n<10^7,\ d(n)=d(n+1)\}.$$
Значит, вторая фаза алгоритма - это линейный просмотр соседних элементов. Для Problem 179 естественное математическое упрощение именно такое: сначала вычислить всю последовательность \(d(1),d(2),\dots,d(10^7)\), затем проверить равенства у соседей.
Реализации на C++, Python и Java выделяют массив нужной длины и заполняют его нулями. Внешний цикл выбирает кандидата в делители \(d\), внутренний проходит по \(d,2d,3d,\dots\) и прибавляет единицу в каждой посещённой позиции. Тем самым программа одновременно реализует тождество \(d(m)=\sum_{k\mid m}1\) для всех чисел диапазона.
В версии на C++ есть ещё небольшая проверка для \(100\): на этом диапазоне правильный результат равен \(15\). Такая проверка полезна как подтверждение того, что этап решета и финальный просмотр согласованы между собой.
После решета массив уже содержит полную последовательность значений функции числа делителей. Затем реализация один раз проходит по \(n=2,3,\dots,10^7-1\) и увеличивает ответ, если значения в позициях \(n\) и \(n+1\) совпадают. Во всех трёх языках математическая схема здесь одна и та же; различаются только синтаксис и детали хранения данных.
Фаза решета выполняет
$$\sum_{d=1}^{10^7+1}\left\lfloor\frac{10^7+1}{d}\right\rfloor$$
обновлений массива, потому что каждый \(d\) посещает каждый свой кратный ровно один раз. Это гармоническая сумма, поэтому время работы равно \(O(N\log N)\) при \(N=10^7\), а точнее \(N\log N+O(N)\).
Финальный проход по соседним значениям имеет линейную стоимость \(O(N)\) и не меняет главной оценки. Память равна \(O(N)\) из-за массива значений \(d(m)\). Именно такой обмен времени на память и делает задачу выполнимой на диапазоне до \(10^7\).
المطلوب هو عدّ جميع الأعداد الصحيحة \(n\) التي تحقق \(1<n<10^7\) ويكون فيها عدد القواسم الموجبة للعدد \(n\) مساويًا لعدد القواسم الموجبة للعدد \(n+1\). إذا رمزنا لدالة عدد القواسم بالرمز \(d(m)\)، فإن الكمية المطلوبة هي
$$A=\sum_{n=2}^{10^7-1}\mathbf{1}_{d(n)=d(n+1)}.$$
وبما أن كل عددين متتاليين متباينان أوليًا دائمًا، فالمسألة ليست مبنية على وجود عوامل أولية مشتركة. الفكرة الحقيقية هي أن تحليلين أوليين مختلفين قد يعطيان العدد نفسه من القواسم. لذلك لا تقوم التطبيقات بتحليل كل زوج على حدة، بل تبني جدول عدد القواسم لكل القيم في المجال دفعة واحدة.
الشيء الرياضي المركزي هنا هو دالة عدد القواسم \(d(m)\)، وتكتب أحيانًا \(\tau(m)\). إذا كان
$$m=\prod_{i=1}^{r} p_i^{a_i},$$
فإن
$$d(m)=\prod_{i=1}^{r}(a_i+1).$$
هذه الصيغة تفسر مباشرة لماذا يمكن لعددين متتاليين أن يتساويا في عدد القواسم. فمثلًا \(14=2^1\cdot 7^1\) و\(15=3^1\cdot 5^1\)، ولذلك يملك كل منهما \(4\) قواسم موجبة رغم أن \(\gcd(14,15)=1\).
لو قمنا بتحليل كل عدد على حدة فسنكرر العمل نفسه مرات كثيرة. تعتمد التطبيقات الثلاثة على الهوية المكافئة
$$d(m)=\sum_{k\mid m}1=\sum_{k=1}^{10^7+1}\mathbf{1}_{k\mid m}.$$
فعند تثبيت قاسم محتمل \(k\)، فإن جميع الأعداد التي يقسمها \(k\) هي مضاعفاته فقط:
$$k,2k,3k,\dots.$$
ومن ثم إذا بدأنا بمصفوفة أصفار، ثم أضفنا \(1\) إلى كل مضاعف من مضاعفات \(k\)، فإن هذا \(k\) يساهم مرة واحدة بالضبط في كل عدد يقسمه، ولا يساهم في غيره.
بعد أن تنتهي الحلقة الخارجية من معالجة القيم \(1,2,\dots,D\)، تصبح الخانة الخاصة بالعدد \(m\) مساوية لـ
$$c_D(m)=\sum_{k=1}^{D}\mathbf{1}_{k\mid m}.$$
وهذا هو عدد قواسم \(m\) التي لا تتجاوز \(D\). وعندما يكون \(m\le D\)، تكون جميع القواسم الموجبة للعدد \(m\) قد ظهرت بالفعل، وبالتالي نحصل على \(c_D(m)=d(m)\). وبما أن التنفيذ يمد الغربال حتى \(10^7+1\)، فإن كل خلية مطلوبة في مرحلة المقارنة النهائية تحتوي على القيمة الدقيقة.
من التحليل الأولي نحصل على
$$14=2^1\cdot 7^1,\qquad 15=3^1\cdot 5^1,$$
ومن ثم
$$d(14)=(1+1)(1+1)=4,\qquad d(15)=(1+1)(1+1)=4.$$
وفي صورة الغربال تظهر الحقيقة نفسها بشكل مختلف: الخانة \(14\) تزداد فقط عند المرور على \(1,2,7,14\)، بينما الخانة \(15\) تزداد عند المرور على \(1,3,5,15\). وبعد اكتمال الجدول يتضح تلقائيًا أن الزوج \((14,15)\) يحقق الشرط.
بعد بناء جدول عدد القواسم لا يبقى أي تعقيد إضافي. فالجواب هو ببساطة عدد المواضع المتجاورة التي تتساوى فيها القيم:
$$A=\#\{n:2\le n<10^7,\ d(n)=d(n+1)\}.$$
ولهذا تكون المرحلة الثانية مجرد مرور خطي على القيم المتجاورة. هذا هو الاختزال الرياضي المناسب تمامًا لمسألة 179: احسب المتتالية \(d(1),d(2),\dots,d(10^7)\) مرة واحدة، ثم افحص التساوي بين الجيران.
تنشئ تطبيقات C++ وPython وJava مصفوفة تغطي المجال المطلوب وتملؤها بالأصفار. تختار الحلقة الخارجية قاسمًا محتملًا \(d\)، ثم تمر الحلقة الداخلية على \(d,2d,3d,\dots\) وتضيف واحدًا إلى كل موضع تزوره. بهذه الصورة تنفذ البرامج الهوية \(d(m)=\sum_{k\mid m}1\) لكل الأعداد في الوقت نفسه بدل إعادة حسابها عددًا بعد عدد.
يتضمن تنفيذ C++ أيضًا فحصًا صغيرًا عند \(100\)، حيث يكون العدد الصحيح للحالات هو \(15\). هذا لا يغيّر الخوارزمية، لكنه يعطي تحققًا مفيدًا من أن مرحلة الغربال ومرحلة العد النهائي منسجمتان.
بعد انتهاء الغربال تحتوي المصفوفة بالفعل على متتالية أعداد القواسم كاملة. ثم يمر التنفيذ مرة واحدة على \(n=2,3,\dots,10^7-1\)، ويزيد الجواب كلما كانت القيمتان عند \(n\) و\(n+1\) متساويتين. الإصدارات الثلاثة متطابقة رياضيًا في هذه الخطوة، والاختلاف بينها يقتصر على الصياغة البرمجية وتفاصيل التخزين.
مرحلة الغربال تنفذ
$$\sum_{d=1}^{10^7+1}\left\lfloor\frac{10^7+1}{d}\right\rfloor$$
عملية تحديث للمصفوفة، لأن كل \(d\) يزور كل مضاعف له مرة واحدة فقط. وهذا مجموع توافقي، لذلك يكون الزمن الكلي \(O(N\log N)\) عندما \(N=10^7\)، وبصيغة أدق \(N\log N+O(N)\).
أما المرور النهائي على القيم المتجاورة فهو \(O(N)\) ولا يغيّر الرتبة المسيطرة. استهلاك الذاكرة هو \(O(N)\) من أجل جدول عدد القواسم. وهذا هو التوازن المناسب للمسألة: غربال شامل واحد ومرور خطي واحد بدل ملايين التحليلات المنفصلة.