The goal is to find the smallest integer \(n\) such that the four consecutive numbers \(n, n+1, n+2, n+3\) each have exactly four distinct prime factors. If
$$m=\prod_{i=1}^{t} p_i^{e_i},\qquad e_i\ge 1,$$
with distinct primes \(p_i\), then the relevant arithmetic function is \(\omega(m)=t\).
The implementations solve the problem directly. They do not build a sieve or a table of precomputed factorizations. Instead, they move upward one integer at a time, compute \(\omega(m)\) by trial division, and stop as soon as the first valid four-term block appears. Because the scan is strictly increasing, the first block found is automatically the smallest possible answer.
The mathematics is simple but very precise: unique factorization tells us how to count distinct prime divisors correctly, and a running streak invariant turns those local counts into the first global solution.
Problem 47 is about distinct prime factors, not total multiplicity. Thus
$$\omega(12)=\omega(2^2\cdot 3)=2,\qquad \omega(18)=\omega(2\cdot 3^2)=2,$$
even though both numbers contain repeated prime powers. The target condition is therefore
$$\omega(n)=\omega(n+1)=\omega(n+2)=\omega(n+3)=4.$$
This is the exact quantity computed by the C++, Python, and Java implementations.
Suppose we want \(\omega(m)\). If \(2\mid m\), then 2 contributes one distinct prime factor, so the count should increase by exactly 1. After that, dividing out every factor of 2 leaves a reduced number whose remaining distinct prime divisors are all odd. The same logic applies to every odd divisor \(p\): once \(p\mid m\), the count increases by 1, and then every copy of \(p\) is removed before the search continues.
Formally, if
$$m=p^a q,\qquad a\ge 1,\qquad p\nmid q,$$
then
$$\omega(m)=1+\omega(q).$$
Stripping the full power \(p^a\) is exactly what prevents a repeated prime such as \(2^2\) or \(3^2\) from being counted more than once.
After removing the factor 2, the implementations test odd divisors \(3,5,7,\dots\) only while
$$p^2 \le m_{\mathrm{red}},$$
where \(m_{\mathrm{red}}\) denotes the current reduced number. If the loop ends with \(m_{\mathrm{red}}>1\), that leftover value must be prime. Otherwise it would be composite and would therefore have a prime divisor at most \(\sqrt{m_{\mathrm{red}}}\), contradicting the fact that all such candidates have already been tested and removed.
If \(r(m)\) denotes the number of distinct prime divisors removed during the loop, the final count is
$$\omega(m)=r(m)+\begin{cases}1,&m_{\mathrm{red}}>1,\\0,&m_{\mathrm{red}}=1.\end{cases}$$
Once \(\omega(m)\) can be computed for one integer, the search becomes a streaming recurrence. Let \(s_m\) be the length of the longest suffix of consecutive integers ending at \(m\) for which every value has four distinct prime factors. Then
$$s_m=\begin{cases} s_{m-1}+1,&\omega(m)=4,\\ 0,&\omega(m)\ne 4. \end{cases}$$
As soon as \(s_m=4\), the desired block is
$$m-3,\ m-2,\ m-1,\ m.$$
Because the scan checks integers in increasing order, the first time this happens yields the smallest possible starting value.
The first block reached by the search is
$$134043,\ 134044,\ 134045,\ 134046.$$
Their factorizations are
$$134043=3\cdot 7\cdot 13\cdot 491,$$
$$134044=2^2\cdot 23\cdot 31\cdot 47,$$
$$134045=5\cdot 17\cdot 19\cdot 83,$$
$$134046=2\cdot 3^2\cdot 11\cdot 677.$$
Each number has exactly four distinct prime factors, so the streak length reaches 4 at \(m=134046\), and the algorithm returns \(134046-3=134043\).
The C++, Python, and Java implementations all use the same structure. They first test divisibility by 2, count that prime once if it appears, and divide out all powers of 2. Then they try odd divisors in increasing order. Whenever an odd divisor divides the current value, the implementation counts one new distinct prime and strips that divisor completely before moving on. If the reduced value is still greater than 1 after the loop, it is counted as one final prime factor.
After the factor count for one integer is available, the implementation advances to the next integer and updates two pieces of state: the length of the current streak of successful consecutive numbers and the first integer in that streak. A mismatch resets the streak immediately. A match extends it. When the streak length reaches four, the stored starting value is returned without any further search.
Before solving the target case, the implementations also validate the logic on smaller checkpoint cases. In particular, they confirm that \(14=2\cdot 7\) has two distinct prime factors and that the first case of two consecutive integers with two distinct prime factors starts at \(14\). Those checks verify both the factor-counting routine and the streak update logic.
For a single integer \(m\), trial division costs \(O(\sqrt{m})\) in the worst case. The practical constant is smaller because the factor 2 is handled separately, only odd candidates are tested afterward, and repeated prime powers are removed in batches. If \(N\) denotes the first returned value, then scanning through \(N+3\) costs
$$O\!\left(\sum_{m=2}^{N+3}\sqrt{m}\right)=O(N^{3/2})$$
in the worst case.
The extra memory usage is \(O(1)\). No sieve table, factor cache, or prime list is stored. That tradeoff matches the implementations well: the code stays short and transparent, and the first valid block occurs early enough that plain trial division is easily fast enough.
Gesucht ist die kleinste ganze Zahl \(n\), für die die vier aufeinanderfolgenden Zahlen \(n, n+1, n+2, n+3\) jeweils genau vier verschiedene Primfaktoren besitzen. Gilt
$$m=\prod_{i=1}^{t} p_i^{e_i},\qquad e_i\ge 1,$$
wobei die \(p_i\) paarweise verschiedene Primzahlen sind, dann ist die relevante arithmetische Funktion \(\omega(m)=t\).
Die Implementierungen lösen das Problem direkt. Sie verwenden weder ein Sieb noch eine vorberechnete Faktortabelle. Stattdessen gehen sie Zahl für Zahl nach oben, bestimmen \(\omega(m)\) per Probedivision und brechen ab, sobald der erste gültige Viererblock gefunden ist. Weil streng aufsteigend gesucht wird, ist der zuerst gefundene Block automatisch die kleinste Lösung.
Die zugrunde liegende Mathematik ist knapp, aber exakt: Die eindeutige Primfaktorzerlegung erklärt das korrekte Zählen verschiedener Primteiler, und eine Invariante über eine laufende Serie verwandelt diese lokalen Zählungen in die erste globale Lösung.
In Problem 47 zählt man verschiedene Primfaktoren, nicht die Summe der Exponenten. Deshalb gilt
$$\omega(12)=\omega(2^2\cdot 3)=2,\qquad \omega(18)=\omega(2\cdot 3^2)=2,$$
obwohl beide Zahlen wiederholte Primfaktorpotenzen enthalten. Die Zielbedingung lautet also
$$\omega(n)=\omega(n+1)=\omega(n+2)=\omega(n+3)=4.$$
Genau diese Größe berechnen die C++-, Python- und Java-Implementierungen.
Um \(\omega(m)\) zu bestimmen, betrachtet man zunächst den Faktor 2. Falls \(2\mid m\), trägt die Primzahl 2 genau einen verschiedenen Primfaktor bei, also muss der Zähler genau um 1 steigen. Danach entfernt man alle Zweierpotenzen. Das übrig bleibende reduzierte Zahlstück hat dieselben restlichen ungeraden Primteiler wie zuvor. Dasselbe gilt für jeden ungeraden Teiler \(p\): Sobald \(p\mid m\) ist, erhöht man den Zähler um 1 und teilt anschließend alle Kopien von \(p\) heraus.
Formal: Gilt
$$m=p^a q,\qquad a\ge 1,\qquad p\nmid q,$$
dann folgt
$$\omega(m)=1+\omega(q).$$
Gerade das vollständige Entfernen von \(p^a\) verhindert, dass eine wiederholte Primzahl wie \(2^2\) oder \(3^2\) mehrfach gezählt wird.
Nach dem Entfernen des Faktors 2 testen die Implementierungen nur noch ungerade Teiler \(3,5,7,\dots\), und zwar solange
$$p^2 \le m_{\mathrm{red}},$$
wobei \(m_{\mathrm{red}}\) die aktuell reduzierte Zahl bezeichnet. Endet die Schleife mit \(m_{\mathrm{red}}>1\), dann muss dieser Rest prim sein. Wäre er zusammengesetzt, hätte er einen Primteiler höchstens \(\sqrt{m_{\mathrm{red}}}\), also einen Kandidaten, der bereits hätte gefunden und entfernt werden müssen.
Bezeichnet \(r(m)\) die Anzahl der in der Schleife entfernten verschiedenen Primteiler, dann lautet die vollständige Zählregel
$$\omega(m)=r(m)+\begin{cases}1,&m_{\mathrm{red}}>1,\\0,&m_{\mathrm{red}}=1.\end{cases}$$
Sobald \(\omega(m)\) für eine einzelne Zahl berechnet werden kann, wird die Suche zu einer laufenden Rekursion. Sei \(s_m\) die Länge des längsten Suffixes aufeinanderfolgender ganzer Zahlen, das bei \(m\) endet und in dem jede Zahl genau vier verschiedene Primfaktoren hat. Dann gilt
$$s_m=\begin{cases} s_{m-1}+1,&\omega(m)=4,\\ 0,&\omega(m)\ne 4. \end{cases}$$
Sobald \(s_m=4\) erreicht ist, lautet der gesuchte Block
$$m-3,\ m-2,\ m-1,\ m.$$
Da die Zahlen streng aufsteigend geprüft werden, liefert das erste Auftreten automatisch den kleinsten möglichen Startwert.
Der erste von der Suche gefundene Block ist
$$134043,\ 134044,\ 134045,\ 134046.$$
Die Zerlegungen lauten
$$134043=3\cdot 7\cdot 13\cdot 491,$$
$$134044=2^2\cdot 23\cdot 31\cdot 47,$$
$$134045=5\cdot 17\cdot 19\cdot 83,$$
$$134046=2\cdot 3^2\cdot 11\cdot 677.$$
Jede dieser Zahlen hat genau vier verschiedene Primfaktoren. Also erreicht die Serienlänge bei \(m=134046\) den Wert 4, und der Algorithmus gibt \(134046-3=134043\) zurück.
Die C++-, Python- und Java-Implementierungen verwenden dieselbe Struktur. Zuerst wird auf Teilbarkeit durch 2 geprüft. Falls 2 vorkommt, wird diese Primzahl genau einmal gezählt und anschließend vollständig herausdividiert. Danach werden nur noch ungerade Teiler in aufsteigender Reihenfolge getestet. Immer wenn ein solcher Teiler die aktuelle Zahl teilt, zählt die Implementierung einen neuen verschiedenen Primfaktor und entfernt diesen Teiler vollständig. Bleibt nach der Schleife ein Wert größer als 1 übrig, wird er als letzter Primfaktor gezählt.
Nach der Faktorzählung für eine Zahl geht die Implementierung zur nächsten Zahl weiter und aktualisiert zwei Zustände: die aktuelle Länge der erfolgreichen Serie und die erste Zahl dieser Serie. Ein Fehlschlag setzt die Serie sofort zurück. Ein Treffer verlängert sie. Sobald die Serienlänge 4 erreicht, wird der gespeicherte Startwert ohne weitere Suche zurückgegeben.
Vor dem eigentlichen Zieltest prüfen die Implementierungen außerdem kleinere Kontrollfälle. Insbesondere wird bestätigt, dass \(14=2\cdot 7\) genau zwei verschiedene Primfaktoren besitzt und dass der erste Fall von zwei aufeinanderfolgenden Zahlen mit je zwei verschiedenen Primfaktoren bei \(14\) beginnt. Damit werden sowohl die Faktorzählung als auch die Logik der Serienaktualisierung abgesichert.
Für eine einzelne Zahl \(m\) kostet Probedivision im schlechtesten Fall \(O(\sqrt{m})\). Praktisch ist der konstante Faktor kleiner, weil der Faktor 2 separat behandelt wird, danach nur ungerade Kandidaten getestet werden und wiederholte Primzahlpotenzen in einem Schritt entfernt werden. Bezeichnet \(N\) den ersten zurückgegebenen Startwert, dann kostet die Suche bis \(N+3\)
$$O\!\left(\sum_{m=2}^{N+3}\sqrt{m}\right)=O(N^{3/2})$$
im Worst Case.
Der zusätzliche Speicherbedarf ist \(O(1)\). Es wird weder ein Sieb noch ein Primzahl-Cache noch eine Faktortabelle gespeichert. Genau das passt zu den Implementierungen: Der Code bleibt kurz und direkt, und der erste gültige Viererblock liegt früh genug, dass einfache Probedivision völlig ausreicht.
Amaç, \(n, n+1, n+2, n+3\) ardışık dört sayısının her birinin tam olarak dört farklı asal çarpana sahip olduğu en küçük \(n\) değerini bulmaktır. Eğer
$$m=\prod_{i=1}^{t} p_i^{e_i},\qquad e_i\ge 1,$$
olup \(p_i\) değerleri birbirinden farklı asallarsa, bu problemde kullanılan aritmetik fonksiyon \(\omega(m)=t\) olur.
Uygulamalar problemi doğrudan çözüyor. Ne bir elek kuruluyor ne de önceden hesaplanmış bir çarpan tablosu tutuluyor. Bunun yerine sayılar 2'den başlayarak tek tek yukarı doğru taranıyor, her sayı için \(\omega(m)\) deneme bölmesiyle hesaplanıyor ve ilk geçerli dört terimli blok bulunur bulunmaz arama bitiyor. Tarama artan sırada yapıldığı için bulunan ilk blok otomatik olarak en küçük çözümdür.
Temel fikir iki parçadan oluşur: asal çarpanlara tekil ayrışım, farklı asal sayısını doğru saymamızı sağlar; art arda başarı uzunluğunu izleyen bir değişmez de bu yerel sayımları ilk küresel çözüme dönüştürür.
Problem 47'de aranan şey asal çarpanların farklı sayısıdır; üslerin toplamı değildir. Bu nedenle
$$\omega(12)=\omega(2^2\cdot 3)=2,\qquad \omega(18)=\omega(2\cdot 3^2)=2,$$
olur. Her iki sayıda da tekrar eden asal kuvvetler vardır, ama aynı asal yalnızca bir kez sayılır. Dolayısıyla hedef koşul
$$\omega(n)=\omega(n+1)=\omega(n+2)=\omega(n+3)=4$$
şeklindedir. C++, Python ve Java uygulamalarının hesapladığı nicelik tam olarak budur.
\(\omega(m)\) değerini hesaplamak istediğimizi düşünelim. Eğer \(2\mid m\) ise, 2 bu sayıya tam olarak bir farklı asal çarpan katkısı yapar; sayaç bu yüzden yalnızca 1 artmalıdır. Ardından bütün 2 kuvvetleri dışarı alınır. Geriye kalan sayının farklı asal çarpanları artık yalnızca tek asallardan gelir. Aynı mantık her tek bölen \(p\) için de geçerlidir: \(p\mid m\) olduğu anda sayaç 1 artar, sonra \(p\)'nin bütün kopyaları temizlenir.
Biçimsel olarak
$$m=p^a q,\qquad a\ge 1,\qquad p\nmid q,$$
ise
$$\omega(m)=1+\omega(q)$$
olur. Tam kuvveti sökmek, \(2^2\) ya da \(3^2\) gibi tekrar eden asalların birden fazla kez sayılmasını tam olarak engeller.
2 çarpanı çıkarıldıktan sonra uygulamalar yalnızca \(3,5,7,\dots\) biçimindeki tek bölenleri dener ve bunu da
$$p^2 \le m_{\mathrm{red}}$$
koşulu sağlandığı sürece yapar. Burada \(m_{\mathrm{red}}\), o andaki indirgenmiş sayıdır. Döngü \(m_{\mathrm{red}}>1\) ile biterse bu artakalan değer asal olmak zorundadır. Aksi halde bileşik olurdu ve \(\sqrt{m_{\mathrm{red}}}\)'den büyük olmayan bir asal böleni bulunurdu; böyle bir bölen ise döngü sırasında zaten yakalanmış olmalıydı.
Döngü içinde çıkarılan farklı asal çarpan sayısını \(r(m)\) ile gösterirsek tam sayım kuralı
$$\omega(m)=r(m)+\begin{cases}1,&m_{\mathrm{red}}>1,\\0,&m_{\mathrm{red}}=1.\end{cases}$$
\(\omega(m)\) bir sayı için hesaplanabildiğinde arama problemi akış halinde güncellenen bir bağıntıya dönüşür. \(s_m\), \(m\) noktasında biten ve içindeki her sayının dört farklı asal çarpanı olduğu en uzun ardışık son parçanın uzunluğu olsun. O zaman
$$s_m=\begin{cases} s_{m-1}+1,&\omega(m)=4,\\ 0,&\omega(m)\ne 4. \end{cases}$$
olur. \(s_m=4\) olur olmaz aranan blok
$$m-3,\ m-2,\ m-1,\ m$$
şeklindedir. Sayılar artan sırayla kontrol edildiği için bunun ilk gerçekleştiği an, en küçük başlangıç değerini verir.
Taramanın ulaştığı ilk blok
$$134043,\ 134044,\ 134045,\ 134046$$
değerleridir. Asal çarpan ayrışımları
$$134043=3\cdot 7\cdot 13\cdot 491,$$
$$134044=2^2\cdot 23\cdot 31\cdot 47,$$
$$134045=5\cdot 17\cdot 19\cdot 83,$$
$$134046=2\cdot 3^2\cdot 11\cdot 677$$
şeklindedir. Bu dört sayının her birinde tam dört farklı asal vardır. Bu yüzden koşu uzunluğu \(m=134046\) anında 4 olur ve algoritma \(134046-3=134043\) döndürür.
C++, Python ve Java uygulamaları aynı iskeleti izler. Önce sayı 2'ye bölünüyor mu diye bakılır. Eğer bölünüyorsa bu asal bir kez sayılır ve tüm 2 kuvvetleri temizlenir. Sonra artan sırada yalnızca tek bölenler denenir. Herhangi bir tek bölen geçerli olduğunda yeni bir farklı asal sayılır ve o bölen tamamen çıkarılır. Döngü sonunda indirgenmiş değer 1'den büyükse son bir asal çarpan daha eklenir.
Bir sayı için asal çarpan sayısı elde edildikten sonra uygulama bir sonraki tam sayıya geçer ve iki durumu günceller: başarılı ardışık bloğun mevcut uzunluğu ve bu bloğun ilk sayısı. Başarısızlık olursa uzunluk sıfırlanır. Başarı olursa uzunluk artar. Uzunluk 4'e ulaştığında kayıtlı başlangıç değeri hemen döndürülür.
Uygulamalar hedef duruma geçmeden önce daha küçük kontrol örnekleriyle mantığı da doğrular. Özellikle \(14=2\cdot 7\) için iki farklı asal bulunduğu ve iki farklı asal çarpanlı iki ardışık sayının ilk örneğinin \(14\) ile başladığı test edilir. Böylece hem çarpan sayma rutini hem de ardışık blok güncellemesi doğrulanmış olur.
Tek bir \(m\) sayısı için deneme bölmesi en kötü durumda \(O(\sqrt{m})\) zaman alır. Uygulamada sabit çarpan daha küçüktür; çünkü 2 ayrı ele alınır, sonrasında yalnızca tek adaylar denenir ve tekrar eden asal kuvvetler tek hamlede çıkarılır. İlk döndürülen değer \(N\) ise, \(N+3\)'e kadar yapılan toplam tarama
$$O\!\left(\sum_{m=2}^{N+3}\sqrt{m}\right)=O(N^{3/2})$$
şeklinde sınırlanır.
Ek bellek kullanımı \(O(1)\)'dir. Ne bir elek tablosu ne de asal listesi veya çarpan önbelleği tutulur. Bu tercih uygulamalarla uyumludur: kod kısa kalır ve ilk geçerli blok yeterince erken geldiği için yalın deneme bölmesi rahatlıkla yeter.
Se busca el menor entero \(n\) tal que los cuatro números consecutivos \(n, n+1, n+2, n+3\) tengan exactamente cuatro factores primos distintos cada uno. Si
$$m=\prod_{i=1}^{t} p_i^{e_i},\qquad e_i\ge 1,$$
con primos distintos \(p_i\), entonces la función aritmética relevante es \(\omega(m)=t\).
Las implementaciones resuelven el problema de forma directa. No construyen un tamiz ni una tabla de factorizaciones precalculadas. En cambio, avanzan entero por entero, calculan \(\omega(m)\) mediante división por prueba y se detienen en cuanto aparece el primer bloque válido de cuatro términos. Como la exploración es estrictamente creciente, el primer bloque encontrado es automáticamente la respuesta mínima.
La idea matemática tiene dos piezas: la factorización única permite contar correctamente los primos distintos, y un invariante de racha convierte esos conteos locales en la primera solución global.
En el problema 47 importan los factores primos distintos, no la suma de multiplicidades. Por eso
$$\omega(12)=\omega(2^2\cdot 3)=2,\qquad \omega(18)=\omega(2\cdot 3^2)=2,$$
aunque ambos números contengan potencias repetidas. La condición objetivo es entonces
$$\omega(n)=\omega(n+1)=\omega(n+2)=\omega(n+3)=4.$$
Esa es exactamente la cantidad que calculan las implementaciones en C++, Python y Java.
Supongamos que queremos calcular \(\omega(m)\). Si \(2\mid m\), entonces el primo 2 aporta exactamente un factor primo distinto, así que el contador debe aumentar en 1 y no más. Después se eliminan todas las potencias de 2. El número reducido conserva exactamente los primos impares distintos que faltan por contar. Lo mismo ocurre con cualquier divisor impar \(p\): en cuanto \(p\mid m\), el contador aumenta en 1 y luego se eliminan todas las copias de \(p\).
Formalmente, si
$$m=p^a q,\qquad a\ge 1,\qquad p\nmid q,$$
entonces
$$\omega(m)=1+\omega(q).$$
Quitar la potencia completa \(p^a\) es precisamente lo que evita contar más de una vez un primo repetido como \(2^2\) o \(3^2\).
Tras eliminar el factor 2, las implementaciones prueban solo divisores impares \(3,5,7,\dots\) mientras
$$p^2 \le m_{\mathrm{red}},$$
donde \(m_{\mathrm{red}}\) es el valor reducido en ese momento. Si el bucle termina con \(m_{\mathrm{red}}>1\), ese residuo tiene que ser primo. De lo contrario sería compuesto y tendría un divisor primo no mayor que \(\sqrt{m_{\mathrm{red}}}\), lo cual contradice que todos esos candidatos ya fueron comprobados y eliminados.
Si \(r(m)\) denota el número de divisores primos distintos eliminados dentro del bucle, la regla final de conteo es
$$\omega(m)=r(m)+\begin{cases}1,&m_{\mathrm{red}}>1,\\0,&m_{\mathrm{red}}=1.\end{cases}$$
Una vez que \(\omega(m)\) puede calcularse para un entero, la búsqueda se convierte en una recurrencia en flujo. Sea \(s_m\) la longitud del sufijo más largo de enteros consecutivos que termina en \(m\) y cuyos valores tienen cuatro factores primos distintos. Entonces
$$s_m=\begin{cases} s_{m-1}+1,&\omega(m)=4,\\ 0,&\omega(m)\ne 4. \end{cases}$$
En cuanto \(s_m=4\), el bloque buscado es
$$m-3,\ m-2,\ m-1,\ m.$$
Como los enteros se revisan en orden creciente, la primera vez que ocurre produce el menor inicio posible.
El primer bloque encontrado por la búsqueda es
$$134043,\ 134044,\ 134045,\ 134046.$$
Sus factorizaciones son
$$134043=3\cdot 7\cdot 13\cdot 491,$$
$$134044=2^2\cdot 23\cdot 31\cdot 47,$$
$$134045=5\cdot 17\cdot 19\cdot 83,$$
$$134046=2\cdot 3^2\cdot 11\cdot 677.$$
Cada número tiene exactamente cuatro factores primos distintos. Por eso la racha alcanza longitud 4 en \(m=134046\), y el algoritmo devuelve \(134046-3=134043\).
Las implementaciones en C++, Python y Java siguen la misma estructura. Primero comprueban la divisibilidad por 2, cuentan ese primo una sola vez si aparece y eliminan todas sus potencias. Después prueban divisores impares en orden creciente. Cada vez que uno de ellos divide al valor actual, la implementación cuenta un nuevo primo distinto y lo elimina por completo antes de seguir. Si al final del bucle el valor reducido sigue siendo mayor que 1, se cuenta como un último factor primo.
Una vez disponible el conteo para un entero, la implementación pasa al siguiente y actualiza dos estados: la longitud de la racha actual de éxitos consecutivos y el primer entero de esa racha. Un fallo reinicia la racha. Un acierto la alarga. Cuando la longitud llega a cuatro, se devuelve inmediatamente el valor inicial almacenado.
Antes de resolver el caso objetivo, las implementaciones también verifican ejemplos de control más pequeños. En particular, comprueban que \(14=2\cdot 7\) tiene dos factores primos distintos y que el primer caso de dos enteros consecutivos con dos factores primos distintos empieza en \(14\). Eso valida tanto el conteo de factores como la lógica de actualización de la racha.
Para un solo entero \(m\), la división por prueba cuesta \(O(\sqrt{m})\) en el peor caso. En la práctica la constante es menor porque el factor 2 se trata por separado, después solo se prueban candidatos impares y las potencias repetidas se eliminan en bloque. Si \(N\) es el primer valor devuelto, el coste total de examinar hasta \(N+3\) es
$$O\!\left(\sum_{m=2}^{N+3}\sqrt{m}\right)=O(N^{3/2})$$
en el peor caso.
El uso extra de memoria es \(O(1)\). No se almacena un tamiz, ni una caché de factorizaciones, ni una lista de primos. Ese equilibrio coincide con las implementaciones: el código se mantiene corto y claro, y el primer bloque válido aparece lo bastante pronto como para que la división por prueba sea más que suficiente.
目标是找到最小的整数 \(n\)，使得四个连续整数 \(n, n+1, n+2, n+3\) 都恰好有四个不同的质因数。若
$$m=\prod_{i=1}^{t} p_i^{e_i},\qquad e_i\ge 1,$$
其中 \(p_i\) 是互不相同的质数，那么本题真正关心的算术函数就是 \(\omega(m)=t\)。
这些实现采用的是直接搜索，而不是筛法。它们不会预先建立质因数表，也不会一次性计算一大段区间的结果。做法是从小到大逐个检查整数，用试除法求出 \(\omega(m)\)，一旦第一次遇到满足条件的四连段就立即停止。由于搜索顺序严格递增，所以第一次找到的四连段必然就是起点最小的答案。
这里的数学结构很朴素，但足够严密：唯一分解定理保证了不同质因数可以被正确计数，而一个关于连续成功段长度的不变量，则把单点的因数统计转化成了整道题的最小解。
本题统计的是不同的质因数个数，而不是把重复次数也算进去。因此
$$\omega(12)=\omega(2^2\cdot 3)=2,\qquad \omega(18)=\omega(2\cdot 3^2)=2,$$
虽然这两个数都含有重复的质因数幂，但同一个质数只记一次。所以目标条件是
$$\omega(n)=\omega(n+1)=\omega(n+2)=\omega(n+3)=4.$$
C++、Python 和 Java 三个实现计算的正是这个量。
设我们要计算 \(\omega(m)\)。如果 \(2\mid m\)，那么质数 2 显然贡献了一个不同的质因数，所以计数器应该只增加 1 次。之后把所有 2 的因子全部除掉，剩下的约化数中只保留尚未统计的奇质因数。对任何奇质数 \(p\) 也是同样的道理：一旦发现 \(p\mid m\)，就说明出现了一个新的不同质因数，此时计数器加 1，然后把 \(p\) 的所有幂全部剥离。
形式化地说，如果
$$m=p^a q,\qquad a\ge 1,\qquad p\nmid q,$$
那么
$$\omega(m)=1+\omega(q).$$
正是因为把整个 \(p^a\) 一次性剥掉，像 \(2^2\) 或 \(3^2\) 这样的重复质因子才不会被重复计数。
去掉因子 2 之后，实现只继续尝试奇除数 \(3,5,7,\dots\)，并且只在
$$p^2 \le m_{\mathrm{red}}$$
时继续循环。这里 \(m_{\mathrm{red}}\) 表示当前已经被约化过的数。如果循环结束时 \(m_{\mathrm{red}}>1\)，那么这个剩余值一定是质数。否则它若是合数，就必然存在一个不超过 \(\sqrt{m_{\mathrm{red}}}\) 的质因子；而这样的候选除数本该已经在循环中被发现并去掉了。
若记 \(r(m)\) 为循环中已经剥离掉的不同质因数个数，那么完整的计数公式就是
$$\omega(m)=r(m)+\begin{cases}1,&m_{\mathrm{red}}>1,\\0,&m_{\mathrm{red}}=1.\end{cases}$$
当 \(\omega(m)\) 能够对单个整数求出来以后，整体搜索就变成了一个流式递推。记 \(s_m\) 为“以 \(m\) 结尾、并且其中每个整数都恰好有四个不同质因数的最长连续后缀长度”。那么
$$s_m=\begin{cases} s_{m-1}+1,&\omega(m)=4,\\ 0,&\omega(m)\ne 4. \end{cases}$$
一旦 \(s_m=4\)，所求四连段就是
$$m-3,\ m-2,\ m-1,\ m.$$
由于整数是按从小到大的顺序被检查的，所以第一次达到这个状态时，对应的起点必然最小。
搜索第一次命中的区间是
$$134043,\ 134044,\ 134045,\ 134046.$$
它们的质因数分解分别为
$$134043=3\cdot 7\cdot 13\cdot 491,$$
$$134044=2^2\cdot 23\cdot 31\cdot 47,$$
$$134045=5\cdot 17\cdot 19\cdot 83,$$
$$134046=2\cdot 3^2\cdot 11\cdot 677.$$
这四个数都恰好有四个不同的质因数，因此当搜索走到 \(m=134046\) 时，连续成功长度达到 4，算法返回的起点就是 \(134046-3=134043\)。
C++、Python 和 Java 的实现结构完全一致。它们先检查是否能被 2 整除；如果可以，就把质数 2 计入一次，并把所有 2 的幂全部除掉。随后只测试递增的奇除数。每当某个奇除数能够整除当前值时，实现就把它当作一个新的不同质因数记入，并把该除数完整地剥离。循环结束后，如果约化后的值仍然大于 1，就把它作为最后一个质因数再计一次。
得到某个整数的质因数个数后，实现就前进到下一个整数，并更新两个状态：当前连续成功段的长度，以及这一段的起始整数。一旦遇到不满足条件的数，连续长度立即清零；如果满足条件，长度就加 1。当长度达到 4 时，保存下来的起点会被立刻返回，不再继续搜索。
在处理目标情形之前，实现还会先验证较小的检查例子。它们会确认 \(14=2\cdot 7\) 的不同质因数个数是 2，并且“两 个连续整数都恰好有两个不同质因数”的第一个例子起点是 \(14\)。这同时验证了因数统计过程和连续段更新逻辑。
对单个整数 \(m\) 来说，试除法在最坏情况下需要 \(O(\sqrt{m})\) 时间。实际常数会更小，因为因子 2 被单独处理，之后只测试奇数候选，而且重复的质因数幂会一次性全部去掉。若记最终返回的起点为 \(N\)，那么检查到 \(N+3\) 为止的总最坏时间为
$$O\!\left(\sum_{m=2}^{N+3}\sqrt{m}\right)=O(N^{3/2})$$
。
额外空间复杂度是 \(O(1)\)。实现不会保存筛表、质数表或分解缓存。这与代码风格完全一致：实现简短直接，而本题的第一个有效四连段出现得足够早，朴素试除法已经完全够用。
Нужно найти наименьшее целое число \(n\), для которого четыре последовательных числа \(n, n+1, n+2, n+3\) имеют ровно по четыре различных простых делителя. Если
$$m=\prod_{i=1}^{t} p_i^{e_i},\qquad e_i\ge 1,$$
где \(p_i\) - попарно различные простые числа, то нужная арифметическая функция равна \(\omega(m)=t\).
Реализации решают задачу напрямую. Они не строят решето и не хранят заранее подготовленную таблицу разложений. Вместо этого они последовательно перебирают числа, для каждого вычисляют \(\omega(m)\) пробным делением и останавливаются в тот момент, когда впервые появляется подходящий блок из четырех чисел. Поскольку перебор идет строго вверх, первый найденный блок автоматически дает минимальный ответ.
Здесь используются две ключевые идеи: единственность разложения на простые множители гарантирует правильный подсчет различных простых делителей, а инвариант текущей серии превращает эти локальные подсчеты в первую глобальную точку успеха.
В задаче 47 важно число различных простых делителей, а не сумма кратностей. Поэтому
$$\omega(12)=\omega(2^2\cdot 3)=2,\qquad \omega(18)=\omega(2\cdot 3^2)=2,$$
хотя в обоих случаях есть повторяющиеся простые степени. Значит, искомое условие имеет вид
$$\omega(n)=\omega(n+1)=\omega(n+2)=\omega(n+3)=4.$$
Именно эту величину вычисляют реализации на C++, Python и Java.
Пусть нужно вычислить \(\omega(m)\). Если \(2\mid m\), то простое число 2 должно увеличить счетчик ровно на 1, поскольку речь идет о различных простых множителях. После этого удаляются все степени двойки. Оставшееся сокращенное число содержит ровно те неучтенные нечетные простые делители, которые еще нужно найти. Точно такая же логика работает для любого нечетного делителя \(p\): как только обнаружено \(p\mid m\), счетчик увеличивается на 1, а затем из числа убираются все копии \(p\).
Формально, если
$$m=p^a q,\qquad a\ge 1,\qquad p\nmid q,$$
то
$$\omega(m)=1+\omega(q).$$
Именно полное удаление степени \(p^a\) не позволяет посчитать один и тот же простой множитель, например \(2^2\) или \(3^2\), больше одного раза.
После удаления множителя 2 реализации проверяют только нечетные делители \(3,5,7,\dots\), пока выполняется условие
$$p^2 \le m_{\mathrm{red}}.$$
Здесь \(m_{\mathrm{red}}\) обозначает текущее сокращенное число. Если цикл завершился при \(m_{\mathrm{red}}>1\), то этот остаток обязан быть простым. Иначе он был бы составным и имел бы простой делитель, не превосходящий \(\sqrt{m_{\mathrm{red}}}\), но все такие кандидаты уже были проверены и удалены.
Если через \(r(m)\) обозначить число различных простых делителей, удаленных в цикле, то полное правило подсчета имеет вид
$$\omega(m)=r(m)+\begin{cases}1,&m_{\mathrm{red}}>1,\\0,&m_{\mathrm{red}}=1.\end{cases}$$
Когда \(\omega(m)\) можно вычислять для одного числа, поиск превращается в потоковую рекурсию. Обозначим через \(s_m\) длину самого длинного суффикса последовательных чисел, оканчивающегося в \(m\), в котором каждое число имеет ровно четыре различных простых делителя. Тогда
$$s_m=\begin{cases} s_{m-1}+1,&\omega(m)=4,\\ 0,&\omega(m)\ne 4. \end{cases}$$
Как только \(s_m=4\), искомый блок равен
$$m-3,\ m-2,\ m-1,\ m.$$
Поскольку числа проверяются по возрастанию, первое достижение этого состояния дает наименьшее возможное начальное значение.
Первый блок, найденный поиском, равен
$$134043,\ 134044,\ 134045,\ 134046.$$
Его разложения на простые множители таковы:
$$134043=3\cdot 7\cdot 13\cdot 491,$$
$$134044=2^2\cdot 23\cdot 31\cdot 47,$$
$$134045=5\cdot 17\cdot 19\cdot 83,$$
$$134046=2\cdot 3^2\cdot 11\cdot 677.$$
У каждого из этих чисел ровно четыре различных простых делителя. Значит, при \(m=134046\) длина серии становится равной 4, и алгоритм возвращает \(134046-3=134043\).
Реализации на C++, Python и Java устроены одинаково. Сначала проверяется делимость на 2. Если делимость есть, простое число 2 засчитывается один раз, а затем удаляются все степени двойки. После этого последовательно пробуются только нечетные делители. Каждый раз, когда такой делитель делит текущее значение, реализация засчитывает один новый простой множитель и полностью убирает его из числа. Если после завершения цикла сокращенное значение все еще больше 1, оно засчитывается как последний простой множитель.
После вычисления числа различных простых делителей для очередного целого реализация переходит к следующему числу и обновляет два состояния: текущую длину успешной последовательной серии и первое число этой серии. Несоответствие условию немедленно обнуляет серию. Соответствие удлиняет ее. Как только длина серии достигает четырех, сохраненное начальное значение возвращается сразу же.
Перед запуском целевого случая реализации также проверяют более маленькие контрольные примеры. В частности, подтверждается, что \(14=2\cdot 7\) имеет два различных простых делителя и что первый случай двух последовательных чисел с двумя различными простыми делителями начинается с \(14\). Эти проверки подтверждают корректность и процедуры факторизации, и логики обновления серии.
Для одного числа \(m\) пробное деление требует \(O(\sqrt{m})\) операций в худшем случае. На практике константа меньше, потому что множитель 2 обрабатывается отдельно, затем проверяются только нечетные кандидаты, а повторяющиеся простые степени удаляются сразу целиком. Если \(N\) - первое возвращаемое значение, то суммарная стоимость проверки до \(N+3\) оценивается как
$$O\!\left(\sum_{m=2}^{N+3}\sqrt{m}\right)=O(N^{3/2})$$
в худшем случае.
Дополнительная память равна \(O(1)\). Не хранится ни решето, ни список простых чисел, ни кэш разложений. Это хорошо согласуется с реализациями: код остается коротким и прозрачным, а первый подходящий блок появляется достаточно рано, чтобы простого пробного деления было более чем достаточно.
المطلوب هو إيجاد أصغر عدد صحيح \(n\) بحيث إن الأعداد المتتالية الأربعة \(n, n+1, n+2, n+3\) يملك كل واحد منها بالضبط أربعة عوامل أولية متميزة. إذا كان
$$m=\prod_{i=1}^{t} p_i^{e_i},\qquad e_i\ge 1,$$
حيث إن \(p_i\) أعداد أولية متميزة، فإن الدالة الحسابية المهمة هنا هي \(\omega(m)=t\).
التنفيذات تتعامل مع المسألة بصورة مباشرة. فهي لا تبني منخلًا ولا جدولًا مسبقًا للتحليل إلى العوامل. بدلًا من ذلك تصعد عددًا بعد عدد، وتحسب \(\omega(m)\) بالقسمة التجريبية، وتتوقف لحظة ظهور أول كتلة صحيحة من أربعة أعداد. وبما أن الفحص يتم بترتيب تصاعدي صارم، فإن أول كتلة يتم العثور عليها هي تلقائيًا أصغر حل ممكن.
الفكرة الرياضية هنا تقوم على جزأين واضحين: مبرهنة التحليل الأولي الفريد تضمن العد الصحيح للعوامل الأولية المتميزة، وثابت تتبع السلسلة المتتالية يحول هذه القيم المحلية إلى أول حل كلي للمسألة.
في هذه المسألة نهتم بعدد العوامل الأولية المتميزة، لا بمجموع التكرارات. لذلك
$$\omega(12)=\omega(2^2\cdot 3)=2,\qquad \omega(18)=\omega(2\cdot 3^2)=2,$$
مع أن كلا العددين يحتوي على قوى أولية مكررة. وعليه فإن الشرط المطلوب هو
$$\omega(n)=\omega(n+1)=\omega(n+2)=\omega(n+3)=4.$$
وهذا هو بالضبط المقدار الذي تحسبه تنفيذات C++ وPython وJava.
لنفترض أننا نريد حساب \(\omega(m)\). إذا كان \(2\mid m\)، فإن العدد الأولي 2 يساهم بعامل أولي متميز واحد فقط، ولذلك يجب زيادة العداد بمقدار 1 مرة واحدة لا أكثر. بعد ذلك تُزال كل قوى 2 من العدد. والعدد المختزل الباقي يحتفظ فقط بالعوامل الأولية الفردية المتميزة التي لم تُحسب بعد. والمنطق نفسه ينطبق على أي قاسم فردي \(p\): بمجرد أن يتحقق \(p\mid m\)، نزداد بمقدار 1 ثم نزيل كل نسخ \(p\) قبل متابعة الفحص.
بصيغة رياضية، إذا كان
$$m=p^a q,\qquad a\ge 1,\qquad p\nmid q,$$
فإن
$$\omega(m)=1+\omega(q).$$
إزالة القوة الكاملة \(p^a\) هي بالضبط ما يمنع احتساب عدد أولي مكرر مثل \(2^2\) أو \(3^2\) أكثر من مرة.
بعد إزالة العامل 2، تختبر التنفيذات فقط القواسم الفردية \(3,5,7,\dots\) ما دام الشرط
$$p^2 \le m_{\mathrm{red}}$$
متحققًا، حيث يرمز \(m_{\mathrm{red}}\) إلى العدد المختزل الحالي. إذا انتهت الحلقة وبقي \(m_{\mathrm{red}}>1\)، فلا بد أن تكون هذه القيمة المتبقية أولية. لأنها لو كانت مركبة لامتلكت قاسمًا أوليًا لا يتجاوز \(\sqrt{m_{\mathrm{red}}}\)، وهذا يناقض أن جميع هذه القيم المرشحة قد تم اختبارها وإزالتها بالفعل.
وإذا رمزنا بعدد العوامل الأولية المتميزة التي أزيلت داخل الحلقة بالرمز \(r(m)\)، فإن قاعدة العد النهائية تصبح
$$\omega(m)=r(m)+\begin{cases}1,&m_{\mathrm{red}}>1,\\0,&m_{\mathrm{red}}=1.\end{cases}$$
بمجرد أن يصبح حساب \(\omega(m)\) ممكنًا لعدد واحد، تتحول عملية البحث كلها إلى علاقة تحديث متدفقة. لِنعرّف \(s_m\) بأنه طول أطول ذيل من الأعداد المتتالية ينتهي عند \(m\)، بحيث يملك كل عدد فيه أربعة عوامل أولية متميزة. عندئذ
$$s_m=\begin{cases} s_{m-1}+1,&\omega(m)=4,\\ 0,&\omega(m)\ne 4. \end{cases}$$
وما إن يصبح \(s_m=4\)، تكون الكتلة المطلوبة هي
$$m-3,\ m-2,\ m-1,\ m.$$
ولأن الأعداد تُفحص تصاعديًا، فإن أول مرة يتحقق فيها هذا الشرط تعطي أصغر بداية ممكنة.
أول كتلة يعثر عليها البحث هي
$$134043,\ 134044,\ 134045,\ 134046.$$
وتحليلاتها إلى العوامل الأولية هي
$$134043=3\cdot 7\cdot 13\cdot 491,$$
$$134044=2^2\cdot 23\cdot 31\cdot 47,$$
$$134045=5\cdot 17\cdot 19\cdot 83,$$
$$134046=2\cdot 3^2\cdot 11\cdot 677.$$
كل واحد من هذه الأعداد يملك أربعة عوامل أولية متميزة بالضبط. لذلك يصل طول السلسلة إلى 4 عند \(m=134046\)، ويعيد الخوارزم \(134046-3=134043\).
تنفيذات C++ وPython وJava تتبع البنية نفسها. تبدأ بفحص قابلية القسمة على 2. فإذا ظهر هذا العامل، يُحسب مرة واحدة ثم تُزال جميع قواه. بعد ذلك لا تُختبر إلا القواسم الفردية بترتيب تصاعدي. وكلما قسم قاسم فردي القيمة الحالية، يُحسب كعامل أولي متميز جديد ثم يُزال كاملًا قبل الانتقال إلى المرشح التالي. وإذا بقيت قيمة مختزلة أكبر من 1 بعد نهاية الحلقة، فإنها تُحسب كعامل أولي أخير.
بعد معرفة عدد العوامل الأولية المتميزة لعدد معين، تنتقل التنفيذات إلى العدد التالي وتحدّث حالتين: طول السلسلة الحالية من النجاحات المتتالية، وبداية تلك السلسلة. إذا فشل العدد الحالي في الشرط تُصفَّر السلسلة فورًا، وإذا نجح تمتد السلسلة بمقدار واحد. وعندما يصل الطول إلى أربعة، تُعاد قيمة البداية المخزنة مباشرة من دون أي بحث إضافي.
وقبل معالجة الحالة الهدف، تتحقق التنفيذات أيضًا من أمثلة اختبار أصغر. فهي تؤكد أن \(14=2\cdot 7\) يملك عاملين أوليين متميزين، وأن أول حالة لعددين متتاليين يملك كل منهما عاملين أوليين متميزين تبدأ عند \(14\). هذه الخطوات تثبت صحة روتين العد وصحة منطق تحديث السلسلة معًا.
بالنسبة إلى عدد واحد \(m\)، تكلف القسمة التجريبية \(O(\sqrt{m})\) في أسوأ الأحوال. أما عمليًا فالثابت أصغر لأن العامل 2 يعالج منفصلًا، ثم تُفحص المرشحات الفردية فقط، كما أن القوى الأولية المكررة تُزال دفعة واحدة. وإذا رمزنا إلى أول قيمة معادة بالرمز \(N\)، فإن التكلفة الكلية للمسح حتى \(N+3\) تساوي
$$O\!\left(\sum_{m=2}^{N+3}\sqrt{m}\right)=O(N^{3/2})$$
في أسوأ حالة.
استهلاك الذاكرة الإضافي هو \(O(1)\). فلا يوجد منخل مخزَّن، ولا قائمة أوليات، ولا ذاكرة مؤقتة للتحليل. وهذا ينسجم مع التنفيذات تمامًا: الكود يبقى قصيرًا ومباشرًا، والكتلة الصالحة الأولى تظهر مبكرًا بما يكفي لأن تكون القسمة التجريبية البسيطة أكثر من كافية.