A positive integer is called \(47\)-smooth when every prime divisor belongs to
$$P=\{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47\}.$$
For the triangular numbers
$$T(n)=\frac{n(n+1)}{2},$$
we must compute the sum of all indices \(n\) for which \(T(n)\) is \(47\)-smooth. The implementations do not factor every triangular number directly. Instead they rewrite each valid case in terms of one smooth core \(x\) and one neighboring value \(2x-1\) or \(2x+1\).
The search is built around the fixed prime set \(P\) above and around the coprimality of consecutive integers.
If \(n\) is even, write \(n=2x\). Then
$$T(n)=\frac{(2x)(2x+1)}{2}=x(2x+1).$$
If \(n\) is odd, write \(n=2x-1\). Then
$$T(n)=\frac{(2x-1)(2x)}{2}=x(2x-1).$$
In both cases the two factors are coprime, because
$$\gcd(x,2x+1)=1,\qquad \gcd(x,2x-1)=1.$$
A product of two coprime integers is \(47\)-smooth if and only if each factor is \(47\)-smooth. Therefore
$$T(2x)\text{ is }47\text{-smooth} \iff x\text{ and }2x+1\text{ are }47\text{-smooth},$$
$$T(2x-1)\text{ is }47\text{-smooth} \iff x\text{ and }2x-1\text{ are }47\text{-smooth}.$$
This converts the original problem into two tests around the same smooth core \(x\). Every valid index \(n\) determines \(x\) uniquely from its parity, so there is no double counting between the even and odd branches.
Every \(47\)-smooth integer has a unique factorization
$$x=\prod_{p\in P} p^{e_p},\qquad e_p\ge 0.$$
The implementations recurse over the primes in \(P\), choose each exponent \(e_p\) in turn, and multiply the running product by successive powers of that prime while the product stays below the fixed search cutoff
$$B=10^{13}.$$
Because of unique factorization, this depth-first enumeration visits each \(47\)-smooth \(x\le B\) exactly once.
For each enumerated \(x\), the implementations form
$$y_-=2x-1,\qquad y_+=2x+1.$$
To check whether one of these numbers is \(47\)-smooth, the algorithm repeatedly divides it by every prime in \(P\). If the remaining residue is \(1\), then all prime factors were allowed and the number is \(47\)-smooth. If the residue is larger than \(1\), then some prime factor exceeds \(47\), so the candidate must be rejected.
Whenever \(y_+\) passes, the even index \(n=2x\) is added to the total. Whenever \(y_-\) passes, the odd index \(n=2x-1\) is added.
Take \(x=3\). This \(x\) is \(47\)-smooth because its only prime factor is \(3\).
Then
$$2x-1=5,\qquad 2x+1=7,$$
and both numbers are also \(47\)-smooth. So the algorithm accepts both
$$n=5\qquad\text{and}\qquad n=6.$$
Indeed,
$$T(5)=\frac{5\cdot 6}{2}=15=3\cdot 5,$$
$$T(6)=\frac{6\cdot 7}{2}=21=3\cdot 7,$$
and every prime factor in both triangular numbers is at most \(47\).
Every accepted candidate produces a valid index, because the parity split reconstructs
$$T(2x)=x(2x+1),\qquad T(2x-1)=x(2x-1),$$
with both factors already verified to be \(47\)-smooth. Conversely, every valid index \(n\) belongs to exactly one of the two parity cases, so it yields one smooth core \(x\) and one successful neighbor test. The implementations therefore compute the desired sum by exhaustively enumerating the smooth cores in their chosen search range and adding precisely the matching indices.
The C++, Python, and Java implementations all follow the same structure. First they store the fifteen allowed primes up to \(47\). Next they perform a recursive search over exponent choices, so the current product always stays \(47\)-smooth by construction.
When the recursion has processed all fifteen primes, the current product is one completed candidate \(x\). At that point the implementation evaluates \(2x-1\) and \(2x+1\), checks each one by repeated division with the same prime list, and adds the corresponding index or indices to a running total.
The recursion only branches while another multiplication still fits under the fixed cutoff \(10^{13}\). Since the arithmetic never leaves this range, ordinary 64-bit integer types are enough for the search and for the accumulated sum.
Let \(S(B)\) denote the number of \(47\)-smooth integers \(x\le B\), where \(B=10^{13}\) is the cutoff used by the implementations. The recursive generator visits each such \(x\) once, and the recursion depth is the fixed constant \(15\).
For every generated \(x\), the code performs two smoothness checks, each over the same fixed prime set \(P\). Repeated divisions by prime powers add only a small extra factor in practice, so the total running time is essentially proportional to the number of enumerated smooth candidates. With \(47\) fixed, the memory usage is \(O(1)\) apart from the recursion stack, which also has constant depth.
Eine positive ganze Zahl heißt \(47\)-smooth, wenn alle ihre Primteiler in der Menge
$$P=\{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47\}$$
liegen. Für die Dreieckszahlen
$$T(n)=\frac{n(n+1)}{2}$$
soll die Summe aller Indizes \(n\) berechnet werden, für die \(T(n)\) \(47\)-smooth ist. Die Implementierungen faktorisieren dabei nicht jede Dreieckszahl direkt, sondern schreiben jeden gültigen Fall in der Form eines glatten Kerns \(x\) und eines Nachbarwerts \(2x-1\) oder \(2x+1\).
Die Suche basiert auf der festen Primzahlmenge \(P\) und auf der Tatsache, dass aufeinanderfolgende Zahlen teilerfremd sind.
Ist \(n\) gerade, so schreiben wir \(n=2x\). Dann gilt
$$T(n)=\frac{(2x)(2x+1)}{2}=x(2x+1).$$
Ist \(n\) ungerade, so schreiben wir \(n=2x-1\). Dann gilt
$$T(n)=\frac{(2x-1)(2x)}{2}=x(2x-1).$$
In beiden Fällen sind die beiden Faktoren teilerfremd, denn
$$\gcd(x,2x+1)=1,\qquad \gcd(x,2x-1)=1.$$
Das Produkt zweier teilerfremder Zahlen ist genau dann \(47\)-smooth, wenn beide Faktoren \(47\)-smooth sind. Also
$$T(2x)\text{ ist }47\text{-smooth} \iff x\text{ und }2x+1\text{ sind }47\text{-smooth},$$
$$T(2x-1)\text{ ist }47\text{-smooth} \iff x\text{ und }2x-1\text{ sind }47\text{-smooth}.$$
Damit wird das ursprüngliche Problem auf zwei Tests rund um denselben glatten Kern \(x\) reduziert. Jeder gültige Index \(n\) bestimmt sein \(x\) über die Parität eindeutig, daher gibt es keine Doppelzählung zwischen geradem und ungeradem Zweig.
Jede \(47\)-smooth Zahl besitzt die eindeutige Primfaktorzerlegung
$$x=\prod_{p\in P} p^{e_p},\qquad e_p\ge 0.$$
Die Implementierungen laufen rekursiv durch die Primzahlen in \(P\), wählen nacheinander die Exponenten \(e_p\) und multiplizieren das laufende Produkt mit aufeinanderfolgenden Potenzen der jeweiligen Primzahl, solange das Produkt unter der festen Suchschranke
$$B=10^{13}$$
bleibt. Wegen der eindeutigen Primfaktorzerlegung wird so jedes \(47\)-smooth \(x\le B\) genau einmal besucht.
Für jedes erzeugte \(x\) werden
$$y_-=2x-1,\qquad y_+=2x+1$$
gebildet. Um zu prüfen, ob einer dieser Werte \(47\)-smooth ist, teilt der Algorithmus ihn wiederholt durch jede Primzahl aus \(P\). Bleibt am Ende der Rest \(1\), dann waren alle Primfaktoren erlaubt und die Zahl ist \(47\)-smooth. Bleibt ein Rest größer als \(1\), dann besitzt der Kandidat einen Primfaktor größer als \(47\) und wird verworfen.
Besteht \(y_+\) den Test, wird der gerade Index \(n=2x\) addiert. Besteht \(y_-\) den Test, wird der ungerade Index \(n=2x-1\) addiert.
Nehmen wir \(x=3\). Diese Zahl ist \(47\)-smooth, weil ihr einziger Primfaktor \(3\) ist.
Dann ist
$$2x-1=5,\qquad 2x+1=7,$$
und beide Zahlen sind ebenfalls \(47\)-smooth. Also akzeptiert der Algorithmus sowohl
$$n=5\qquad\text{als auch}\qquad n=6.$$
Tatsächlich gilt
$$T(5)=\frac{5\cdot 6}{2}=15=3\cdot 5,$$
$$T(6)=\frac{6\cdot 7}{2}=21=3\cdot 7,$$
und alle Primfaktoren beider Dreieckszahlen sind höchstens \(47\).
Jeder akzeptierte Kandidat erzeugt einen gültigen Index, weil die Paritätszerlegung
$$T(2x)=x(2x+1),\qquad T(2x-1)=x(2x-1)$$
rekonstruiert und beide Faktoren bereits als \(47\)-smooth verifiziert wurden. Umgekehrt gehört jeder gültige Index \(n\) genau zu einem der beiden Paritätsfälle und liefert damit genau einen glatten Kern \(x\) und genau einen erfolgreichen Nachbartest. Die Implementierungen berechnen die gesuchte Summe also, indem sie alle glatten Kerne im gewählten Suchbereich vollständig erzeugen und genau die passenden Indizes addieren.
Die C++-, Python- und Java-Implementierungen haben dieselbe Struktur. Zuerst speichern sie die fünfzehn erlaubten Primzahlen bis \(47\). Danach führen sie eine rekursive Suche über die Exponenten aus, sodass das aktuelle Produkt per Konstruktion immer \(47\)-smooth bleibt.
Sobald die Rekursion alle fünfzehn Primzahlen verarbeitet hat, ist das aktuelle Produkt ein vollständiger Kandidat \(x\). Dann berechnet die Implementierung \(2x-1\) und \(2x+1\), prüft beide Werte mit derselben Primzahlliste per wiederholter Division und addiert die passende(n) Indexzahl(en) zu einer laufenden Summe.
Die Rekursion verzweigt nur dann weiter, wenn eine weitere Multiplikation noch unter die feste Schranke \(10^{13}\) fällt. Daher reicht für die Suche und die Summenbildung normale 64-Bit-Ganzzahlarithmetik aus.
Sei \(S(B)\) die Anzahl der \(47\)-smooth Zahlen \(x\le B\), wobei \(B=10^{13}\) die in den Implementierungen verwendete Schranke ist. Der rekursive Generator besucht jedes solche \(x\) genau einmal, und die Rekursionstiefe ist die feste Konstante \(15\).
Für jedes erzeugte \(x\) führt der Code zwei Glattheitstests über dieselbe feste Primzahlmenge \(P\) aus. Wiederholte Divisionen durch Primzahlpotenzen bringen in der Praxis nur einen kleinen Zusatzfaktor mit sich, sodass die Gesamtlaufzeit im Wesentlichen proportional zur Anzahl der erzeugten glatten Kandidaten ist. Da \(47\) fest ist, liegt der Speicherverbrauch abgesehen vom Rekursionsstapel bei \(O(1)\); auch der Stapel selbst hat konstante Tiefe.
Bir pozitif tam sayı, asal bölenlerinin tamamı
$$P=\{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47\}$$
kümesinde yer alıyorsa \(47\)-smooth olarak adlandırılır. Üçgensel sayılar
$$T(n)=\frac{n(n+1)}{2}$$
için, \(T(n)\) sayısı \(47\)-smooth olduğunda bu \(n\) değerlerinin toplamı istenir. Uygulamalar her üçgensel sayıyı doğrudan çarpanlara ayırmak yerine, geçerli her durumu bir smooth çekirdek \(x\) ve onun komşuları olan \(2x-1\) veya \(2x+1\) cinsinden yeniden yazar.
Arama, yukarıdaki sabit asal kümesi \(P\) ve ardışık tam sayıların aralarında asal olması gerçeği üzerine kuruludur.
\(n\) çiftse \(n=2x\) yazalım. O zaman
$$T(n)=\frac{(2x)(2x+1)}{2}=x(2x+1).$$
\(n\) tekse \(n=2x-1\) yazalım. O zaman
$$T(n)=\frac{(2x-1)(2x)}{2}=x(2x-1).$$
Her iki durumda da iki çarpan aralarında asaldır, çünkü
$$\gcd(x,2x+1)=1,\qquad \gcd(x,2x-1)=1.$$
Aralarında asal iki tam sayının çarpımı ancak ve ancak her iki çarpan da \(47\)-smooth ise \(47\)-smooth olur. Dolayısıyla
$$T(2x)\text{ is }47\text{-smooth} \iff x\text{ and }2x+1\text{ are }47\text{-smooth},$$
$$T(2x-1)\text{ is }47\text{-smooth} \iff x\text{ and }2x-1\text{ are }47\text{-smooth}.$$
Böylece asıl problem aynı smooth çekirdeğin iki komşusunu sınamaya dönüşür. Geçerli her \(n\), paritesine göre \(x\)'i tekil olarak belirlediği için çift ve tek durumlar arasında çifte sayım yoktur.
Her \(47\)-smooth tam sayı tekil biçimde
$$x=\prod_{p\in P} p^{e_p},\qquad e_p\ge 0$$
olarak yazılır. Uygulamalar \(P\) kümesindeki asallar boyunca özyinelemeli ilerler, her asal için uygun üssü seçer ve eldeki çarpımı o asalın ardışık kuvvetleriyle, sabit arama sınırı
$$B=10^{13}$$
aşılmadığı sürece büyütür. Aritmetiğin temel teoremi sayesinde bu derinlik öncelikli tarama her \(47\)-smooth \(x\le B\) değerini tam bir kez ziyaret eder.
Üretilen her \(x\) için
$$y_-=2x-1,\qquad y_+=2x+1$$
değerleri oluşturulur. Bu sayılardan birinin \(47\)-smooth olup olmadığını anlamak için algoritma onu \(P\) içindeki her asal ile tekrar tekrar böler. Sonunda kalan artık \(1\) ise tüm asal çarpanlar izin verilen listedendir ve sayı \(47\)-smooth'tur. Artık \(1\)'den büyükse, içeride \(47\)'den büyük bir asal çarpan vardır ve aday reddedilir.
\(y_+\) testi geçerse çift indis \(n=2x\) toplama eklenir. \(y_-\) testi geçerse tek indis \(n=2x-1\) eklenir.
\(x=3\) alalım. Bu \(x\) sayısı \(47\)-smooth'tur, çünkü tek asal çarpanı \(3\)'tür.
O zaman
$$2x-1=5,\qquad 2x+1=7,$$
ve her iki sayı da \(47\)-smooth'tur. Dolayısıyla algoritma hem
$$n=5\qquad\text{and}\qquad n=6$$
değerlerini kabul eder. Gerçekten de
$$T(5)=\frac{5\cdot 6}{2}=15=3\cdot 5,$$
$$T(6)=\frac{6\cdot 7}{2}=21=3\cdot 7,$$
olur ve her iki üçgensel sayının bütün asal çarpanları \(47\)'yi geçmez.
Kabul edilen her aday gerçekten geçerli bir indis üretir, çünkü parite ayrımı
$$T(2x)=x(2x+1),\qquad T(2x-1)=x(2x-1)$$
şeklindeki çarpanlaşmayı geri kurar ve iki çarpanın da \(47\)-smooth olduğu zaten doğrulanmıştır. Tersine, geçerli her \(n\) tam olarak bu iki parite durumundan birine aittir; dolayısıyla tek bir smooth çekirdek \(x\) ve tek bir başarılı komşu testi verir. Uygulamalar bu nedenle seçilen arama aralığındaki tüm smooth çekirdekleri eksiksiz üretip sadece eşleşen indisleri toplayarak istenen sonucu hesaplar.
C++, Python ve Java uygulamalarının yapısı aynıdır. Önce \(47\)'ye kadar olan on beş izinli asal saklanır. Ardından üs seçimleri üzerinde özyinelemeli bir arama yapılır; böylece eldeki çarpım yapı gereği her zaman \(47\)-smooth kalır.
Özyineleme on beş asalın tamamını işlediğinde, eldeki çarpım tamamlanmış bir aday \(x\) olur. O noktada uygulama \(2x-1\) ve \(2x+1\) değerlerini hesaplar, ikisini de aynı asal listesiyle tekrar tekrar bölerek test eder ve uygun olan indis ya da indisleri biriken toplama ekler.
Özyineleme yalnızca yeni bir çarpma sonucunun sabit sınır \(10^{13}\) içinde kaldığı durumlarda dallanır. Bu nedenle arama ve toplam için standart 64 bit tamsayı aritmetiği yeterlidir.
\(B=10^{13}\) olmak üzere, \(S(B)\) ile \(B\)'den küçük ya da eşit \(47\)-smooth \(x\) sayısını gösterelim. Özyinelemeli üreteç bu \(x\) değerlerinin her birini bir kez ziyaret eder ve özyineleme derinliği sabit \(15\)'tir.
Üretilen her \(x\) için kod aynı sabit asal kümesi \(P\) üzerinden iki smoothluk testi yapar. Asal kuvvetlerinden gelen tekrar bölmeler pratikte yalnızca küçük bir ek çarpan getirir; dolayısıyla toplam çalışma süresi özünde üretilen smooth adayların sayısıyla orantılıdır. \(47\) sabit olduğu için, özyineleme yığıtı dışında bellek kullanımı \(O(1)\)'dir; yığıt derinliği de sabittir.
Un entero positivo se llama \(47\)-smooth cuando todos sus divisores primos pertenecen al conjunto
$$P=\{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47\}.$$
Para los números triangulares
$$T(n)=\frac{n(n+1)}{2},$$
debemos calcular la suma de todos los índices \(n\) tales que \(T(n)\) sea \(47\)-smooth. Las implementaciones no factorizan cada triangular de forma directa; en su lugar reescriben cada caso válido mediante un núcleo suave \(x\) y uno de sus vecinos \(2x-1\) o \(2x+1\).
La búsqueda se apoya en el conjunto fijo de primos \(P\) y en que dos enteros consecutivos son coprimos.
Si \(n\) es par, escribimos \(n=2x\). Entonces
$$T(n)=\frac{(2x)(2x+1)}{2}=x(2x+1).$$
Si \(n\) es impar, escribimos \(n=2x-1\). Entonces
$$T(n)=\frac{(2x-1)(2x)}{2}=x(2x-1).$$
En ambos casos los dos factores son coprimos, porque
$$\gcd(x,2x+1)=1,\qquad \gcd(x,2x-1)=1.$$
El producto de dos enteros coprimos es \(47\)-smooth si y solo si cada factor lo es. Por tanto,
$$T(2x)\text{ es }47\text{-smooth} \iff x\text{ y }2x+1\text{ son }47\text{-smooth},$$
$$T(2x-1)\text{ es }47\text{-smooth} \iff x\text{ y }2x-1\text{ son }47\text{-smooth}.$$
El problema original queda reducido a dos pruebas alrededor del mismo núcleo suave \(x\). Cada índice válido \(n\) determina un único \(x\) a partir de su paridad, así que no hay doble conteo entre la rama par y la impar.
Todo entero \(47\)-smooth tiene una factorización única de la forma
$$x=\prod_{p\in P} p^{e_p},\qquad e_p\ge 0.$$
Las implementaciones recorren recursivamente los primos de \(P\), eligen cada exponente \(e_p\) y multiplican el producto actual por potencias sucesivas de ese primo mientras el valor permanezca por debajo del límite fijo de búsqueda
$$B=10^{13}.$$
Gracias a la unicidad de la factorización, esta enumeración en profundidad visita exactamente una vez cada \(47\)-smooth \(x\le B\).
Para cada \(x\) enumerado, las implementaciones forman
$$y_-=2x-1,\qquad y_+=2x+1.$$
Para comprobar si uno de esos valores es \(47\)-smooth, el algoritmo lo divide repetidamente por cada primo de \(P\). Si el residuo final es \(1\), entonces todos sus factores primos estaban permitidos y el número es \(47\)-smooth. Si el residuo queda mayor que \(1\), entonces existe algún factor primo superior a \(47\) y el candidato debe rechazarse.
Cuando \(y_+\) supera la prueba, se suma el índice par \(n=2x\). Cuando \(y_-\) la supera, se suma el índice impar \(n=2x-1\).
Tomemos \(x=3\). Este valor es \(47\)-smooth porque su único factor primo es \(3\).
Entonces
$$2x-1=5,\qquad 2x+1=7,$$
y ambos números también son \(47\)-smooth. Por eso el algoritmo acepta tanto
$$n=5\qquad\text{como}\qquad n=6.$$
En efecto,
$$T(5)=\frac{5\cdot 6}{2}=15=3\cdot 5,$$
$$T(6)=\frac{6\cdot 7}{2}=21=3\cdot 7,$$
y todos los factores primos de ambos triangulares son menores o iguales que \(47\).
Cada candidato aceptado genera un índice válido, porque la separación por paridad reconstruye
$$T(2x)=x(2x+1),\qquad T(2x-1)=x(2x-1),$$
y ambos factores ya fueron verificados como \(47\)-smooth. A la inversa, todo índice válido \(n\) pertenece a uno y solo uno de los dos casos de paridad, así que produce un único núcleo suave \(x\) y una única comprobación exitosa de vecino. Por eso las implementaciones obtienen la suma deseada enumerando exhaustivamente los núcleos suaves en su rango de búsqueda y añadiendo exactamente los índices que encajan.
Las implementaciones en C++, Python y Java siguen la misma idea. Primero guardan los quince primos permitidos hasta \(47\). Luego ejecutan una búsqueda recursiva sobre elecciones de exponentes, de manera que el producto actual siempre sea \(47\)-smooth por construcción.
Cuando la recursión ya ha procesado los quince primos, el producto actual es un candidato completo \(x\). En ese punto la implementación calcula \(2x-1\) y \(2x+1\), prueba ambos valores con la misma lista fija de primos mediante divisiones repetidas y agrega el índice o los índices correspondientes a una suma acumulada.
La recursión solo se ramifica mientras otra multiplicación siga cabiendo bajo el límite fijo \(10^{13}\). Como toda la aritmética permanece dentro de ese rango, bastan enteros normales de 64 bits.
Sea \(S(B)\) el número de enteros \(47\)-smooth \(x\le B\), donde \(B=10^{13}\) es el límite usado por las implementaciones. El generador recursivo visita cada uno de esos \(x\) exactamente una vez y la profundidad de la recursión es la constante fija \(15\).
Para cada \(x\) generado, el código realiza dos comprobaciones de suavidad sobre el mismo conjunto fijo de primos \(P\). Las divisiones repetidas por potencias primas solo añaden un factor pequeño en la práctica, de modo que el tiempo total es esencialmente proporcional al número de candidatos suaves enumerados. Como \(47\) es fijo, el uso de memoria es \(O(1)\) aparte de la pila recursiva, que también tiene profundidad constante.
如果一个正整数的所有素因子都属于
$$P=\{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47\},$$
那么它就称为 \(47\)-smooth。对于三角数
$$T(n)=\frac{n(n+1)}{2},$$
题目要求把所有使 \(T(n)\) 为 \(47\)-smooth 的下标 \(n\) 全部加起来。实现并不是对每个三角数直接分解因子，而是把每个合法情形重写成一个光滑内核 \(x\) 以及它的邻居 \(2x-1\) 或 \(2x+1\)。
这个解法的出发点是上面这个固定的素数集 \(P\) ，以及相邻两个整数互素的事实。
如果 \(n\) 是偶数，记 \(n=2x\)。那么
$$T(n)=\frac{(2x)(2x+1)}{2}=x(2x+1).$$
如果 \(n\) 是奇数，记 \(n=2x-1\)。那么
$$T(n)=\frac{(2x-1)(2x)}{2}=x(2x-1).$$
在这两种情况下，两个因子都互素，因为
$$\gcd(x,2x+1)=1,\qquad \gcd(x,2x-1)=1.$$
两个互素整数的乘积是 \(47\)-smooth，当且仅当它们各自都是 \(47\)-smooth。因此
$$T(2x)\text{ is }47\text{-smooth} \iff x\text{ and }2x+1\text{ are }47\text{-smooth},$$
$$T(2x-1)\text{ is }47\text{-smooth} \iff x\text{ and }2x-1\text{ are }47\text{-smooth}.$$
原问题于是被化成围绕同一个光滑内核 \(x\) 的两个测试。每个合法的下标 \(n\) 都会由它的奇偶性唯一地决定 \(x\)，所以偶数分支和奇数分支之间不会重复计数。
每个 \(47\)-smooth 整数都有唯一的分解
$$x=\prod_{p\in P} p^{e_p},\qquad e_p\ge 0.$$
实现按照 \(P\) 中的素数顺序进行递归枚举，为每个素数选择指数 \(e_p\)，并且在当前乘积仍然不超过固定搜索上界
$$B=10^{13}$$
的前提下，用该素数的各种幂次去扩展当前乘积。由于算术基本定理保证了分解的唯一性，所以这种深度优先枚举会对每个 \(47\)-smooth 的 \(x\le B\) 恰好访问一次。
对于每个枚举到的 \(x\)，实现会构造
$$y_-=2x-1,\qquad y_+=2x+1.$$
然后用 \(P\) 中的每个素数反复去除这两个值。如果最终残留的结果是 \(1\)，就说明所有素因子都在允许范围内，该数就是 \(47\)-smooth。如果最后还剩下一个大于 \(1\) 的残值，那么它必然含有某个大于 \(47\) 的素因子，这个候选就必须丢弃。
如果 \(y_+\) 通过测试，就把偶数下标 \(n=2x\) 加入总和。如果 \(y_-\) 通过测试，就把奇数下标 \(n=2x-1\) 加入总和。
取 \(x=3\)。这个 \(x\) 是 \(47\)-smooth，因为它只有一个素因子 \(3\)。
此时
$$2x-1=5,\qquad 2x+1=7,$$
而这两个数也都是 \(47\)-smooth。所以算法会接受
$$n=5\qquad\text{and}\qquad n=6.$$
确实有
$$T(5)=\frac{5\cdot 6}{2}=15=3\cdot 5,$$
$$T(6)=\frac{6\cdot 7}{2}=21=3\cdot 7,$$
两个三角数的所有素因子都不超过 \(47\)。
每个被接受的候选都会产生一个合法的下标，因为按照奇偶拆开后，我们总是可以重建
$$T(2x)=x(2x+1),\qquad T(2x-1)=x(2x-1),$$
而这两个因子都已经被验证为 \(47\)-smooth。反过来，每个合法的 \(n\) 必然属于两种奇偶情形之一，从而对应到唯一的光滑内核 \(x\) 和唯一次成功的邻居检查。因此，实现通过在选定的搜索范围内穷尽所有光滑内核，并且只把真正符合条件的下标加入总和，就得到了所需的答案。
C++、Python 和 Java 的实现结构是一样的。它们先保存不超过 \(47\) 的十五个允许素数，然后在指数选择上进行递归搜索，让当前乘积在构造过程中始终保持 \(47\)-smooth。
当递归已经处理完全部十五个素数时，当前乘积就是一个完整的候选 \(x\)。此时实现会计算 \(2x-1\) 和 \(2x+1\)，用同一张固定素数表对它们做反复除法检查，并把对应的下标加入累积总和。
只要再乘一次仍然不会超过固定上界 \(10^{13}\)，递归才会继续分支。由于所有运算都在这个范围内，使用普通的 64 位整数就够了。
记 \(S(B)\) 为不超过 \(B\) 的 \(47\)-smooth 整数 \(x\) 的个数，其中 \(B=10^{13}\) 是实现使用的截断上界。这个递归生成器恰好访问每个这样的 \(x\) 一次，而且递归深度是固定常数 \(15\)。
对于每个生成出来的 \(x\)，代码都要在同一个固定素数集 \(P\) 上执行两次光滑性检查。由于对素数幂次的反复除法只会带来很小的额外因子，所以总体时间基本上与枚举出的光滑候选数目成正比。在 \(47\) 固定的情况下，除了常数深度的递归栈之外，空间复杂度为 \(O(1)\)。
Положительное целое число называется \(47\)-smooth, если все его простые делители принадлежат множеству
$$P=\{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47\}.$$
Для треугольных чисел
$$T(n)=\frac{n(n+1)}{2},$$
нужно найти сумму всех индексов \(n\), для которых \(T(n)\) является \(47\)-smooth. Реализации не раскладывают каждое треугольное число напрямую. Вместо этого они сводят задачу к одному гладкому ядру \(x\) и к проверке соседних значений \(2x-1\) и \(2x+1\).
Вся конструкция опирается на фиксированное множество простых \(P\) и на то, что соседние целые числа взаимно просты.
Если \(n\) четно, пишем \(n=2x\). Тогда
$$T(n)=\frac{(2x)(2x+1)}{2}=x(2x+1).$$
Если \(n\) нечетно, пишем \(n=2x-1\). Тогда
$$T(n)=\frac{(2x-1)(2x)}{2}=x(2x-1).$$
В обоих случаях два множителя взаимно просты, потому что
$$\gcd(x,2x+1)=1,\qquad \gcd(x,2x-1)=1.$$
Произведение двух взаимно простых целых чисел является \(47\)-smooth тогда и только тогда, когда каждый множитель сам \(47\)-smooth. Поэтому
$$T(2x)\text{ is }47\text{-smooth} \iff x\text{ and }2x+1\text{ are }47\text{-smooth},$$
$$T(2x-1)\text{ is }47\text{-smooth} \iff x\text{ and }2x-1\text{ are }47\text{-smooth}.$$
Тем самым исходная задача превращается в две проверки вокруг одного и того же гладкого ядра \(x\). Каждый подходящий индекс \(n\) однозначно восстанавливает \(x\) по своей четности, поэтому двойного счета здесь нет.
Любое \(47\)-smooth число имеет единственное разложение
$$x=\prod_{p\in P} p^{e_p},\qquad e_p\ge 0.$$
Реализации рекурсивно проходят по простым из \(P\), выбирают для каждого показатель \(e_p\) и умножают текущее произведение на последовательные степени этого простого, пока число не превышает фиксированную границу
$$B=10^{13}.$$
Благодаря единственности разложения этот обход в глубину посещает каждое \(47\)-smooth число \(x\le B\) ровно один раз.
Для каждого перебранного \(x\) строятся
$$y_-=2x-1,\qquad y_+=2x+1.$$
Чтобы проверить, является ли одно из этих чисел \(47\)-smooth, алгоритм многократно делит его на каждый простой из \(P\). Если в конце остается \(1\), значит все простые множители были допустимыми и число является \(47\)-smooth. Если остаток больше \(1\), внутри есть простой делитель больше \(47\), и кандидат нужно отклонить.
Если тест проходит для \(y_+\), к сумме добавляется четный индекс \(n=2x\). Если тест проходит для \(y_-\), добавляется нечетный индекс \(n=2x-1\).
Возьмем \(x=3\). Это число \(47\)-smooth, потому что его единственный простой множитель равен \(3\).
Тогда
$$2x-1=5,\qquad 2x+1=7,$$
и оба эти числа тоже \(47\)-smooth. Значит, алгоритм принимает
$$n=5\qquad\text{and}\qquad n=6.$$
Действительно,
$$T(5)=\frac{5\cdot 6}{2}=15=3\cdot 5,$$
$$T(6)=\frac{6\cdot 7}{2}=21=3\cdot 7,$$
и все простые делители обоих треугольных чисел не превосходят \(47\).
Каждый принятый кандидат дает корректный индекс, потому что разбиение по четности восстанавливает
$$T(2x)=x(2x+1),\qquad T(2x-1)=x(2x-1),$$
и оба множителя уже проверены как \(47\)-smooth. Обратно, любой подходящий индекс \(n\) попадает ровно в один из двух паритетных случаев, поэтому он дает одно гладкое ядро \(x\) и один успешный тест соседа. Тем самым реализации получают искомую сумму, полностью перебирая гладкие ядра в выбранном диапазоне и добавляя ровно те индексы, которые подходят.
Реализации на C++, Python и Java устроены одинаково. Сначала они хранят пятнадцать допустимых простых до \(47\). Затем выполняют рекурсивный перебор по выбору показателей, так что текущее произведение по построению всегда остается \(47\)-smooth.
Когда рекурсия обработала все пятнадцать простых, текущее произведение становится готовым кандидатом \(x\). После этого реализация вычисляет \(2x-1\) и \(2x+1\), проверяет оба числа той же фиксированной таблицей простых через повторные деления и добавляет подходящий индекс или оба индекса к накопленной сумме.
Рекурсия ветвится только пока еще одно умножение не выводит число за фиксированную границу \(10^{13}\). Поэтому для поиска и накопления суммы достаточно обычных 64-битных целых типов.
Пусть \(S(B)\) обозначает число \(47\)-smooth чисел \(x\le B\), где \(B=10^{13}\) является фиксированной границей, используемой в реализациях. Рекурсивный генератор посещает каждое такое \(x\) ровно один раз, а глубина рекурсии равна постоянной \(15\).
Для каждого сгенерированного \(x\) код выполняет две проверки гладкости на том же фиксированном наборе простых \(P\). Повторные деления на степени простых дают лишь небольшой дополнительный множитель, поэтому общее время по существу пропорционально числу гладких кандидатов. При фиксированном \(47\) память расходуется как \(O(1)\), если не считать стек рекурсии, у которого тоже постоянная глубина.
يسمى العدد الصحيح الموجب \(47\)-smooth إذا كانت جميع قواسمه الأولية تنتمي إلى المجموعة
$$P=\{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47\}.$$
بالنسبة إلى الأعداد المثلثية
$$T(n)=\frac{n(n+1)}{2},$$
فالمطلوب هو حساب مجموع كل فهرس \(n\) يجعل \(T(n)\) عددًا \(47\)-smooth. التنفيذات لا تحلل كل عدد مثلثي مباشرةً، بل تعيد كتابة كل حالة صحيحة باستعمال نواة smooth واحدة \(x\) وقيمة مجاورة إما \(2x-1\) أو \(2x+1\).
تقوم الفكرة على مجموعة الأوليات الثابتة \(P\) ، وعلى حقيقة أن العددين المتتاليين متباينان أوليًا.
إذا كان \(n\) زوجيًا، نكتب \(n=2x\). عندئذٍ
$$T(n)=\frac{(2x)(2x+1)}{2}=x(2x+1).$$
وإذا كان \(n\) فرديًا، نكتب \(n=2x-1\). عندئذٍ
$$T(n)=\frac{(2x-1)(2x)}{2}=x(2x-1).$$
في كلتا الحالتين، العاملان متباينان أوليًا، لأن
$$\gcd(x,2x+1)=1,\qquad \gcd(x,2x-1)=1.$$
إذا كان ناتج ضرب عددين متباينين أوليًا \(47\)-smooth، فلا بد أن يكون كل عامل منهما \(47\)-smooth، والعʃɹ صحيح أيضًا. لذلك
$$T(2x)\text{ is }47\text{-smooth} \iff x\text{ and }2x+1\text{ are }47\text{-smooth},$$
$$T(2x-1)\text{ is }47\text{-smooth} \iff x\text{ and }2x-1\text{ are }47\text{-smooth}.$$
بهذا يتحول السؤال الأصلي إلى اختبارين حول نفس النواة \(x\). كل فهرس صحيح \(n\) يحدد \(x\) بشكل وحيد من خلال فرديته أو زوجيته، ولذلك لا يوجد عدّ مكرر بين الحالتين.
كل عدد \(47\)-smooth يمكن كتابته بشكل وحيد عʄى الصورة
$$x=\prod_{p\in P} p^{e_p},\qquad e_p\ge 0.$$
تمشي التنفيذات بشكل ترɳ>c;ɿي عɴر الأوليات في \(P\)، وتخ>a;ار كل أس \(e_p\) عʄى >d;>f;ة >b;ʅ تɼرب الحɳصل ɳʄ>d;ɳʄ@a; ʁ@a; ʂʈى ʅ>a;>a;ɳʄ@a;ɵ ʅʆ ɶʄʃ ɳʄɿ>f;>f; ɳʄɯʈل@a; ʅɳ >f;ɳʅ ɳʄ>d;>f; ɳʄ>b;ɳɴ>a; ʄʄɴ>d;>b;
$$B=10^{13}$$
ʄɳ @a;>a;ʅ >a;>c;ɳʈɸʇ. ɴɹɴɴ ʈ>d;>f;ɳʆ@a;ɵ ɳʄ>a;>d;ʄ@a;ʄ ɱʄʉ ɿʈɳʅʄ ɯʈʄ@a;ɵ، ʁɱʆ ʇɶɳ ɳʄ>a;ɿ>f;ɳ>f; ɴɳʄɿʅʂ @a;ɸʈɷ ʃʄ \(47\)-smooth \(x\le B\) ʅɷɵ ʈɳ>d;>f;ɵ ɴɳʄɼɴɽ.
ʄʃʄ \(x\) @a;>a;ʅ >a;ɿ>f;ɳ>f;ʇ، >a;@f;>d;ɹɴ ɳʄʂ@a;ʅ>a;ɳʆ
$$y_-=2x-1,\qquad y_+=2x+1.$$
ʄʄ>a;>d;ʂʂ ʅʅɳ ɱɶɳ ʃɳʆ>a; ɱ>d;>f;ʉ ʇɳ>a;@a;ʆ ɳʄʂ@a;ʅ>a;@a;ʆ \(47\)-smooth، @a;ʂɹʅ ɳʄ>e;ʈɳɷɸʅ ɳʄɿ>f;>f; ʅɷɳɷًɳ ɿʄى ʃʄ ɿ>f;>f; ɯʈʄ@a; ʁ@a; \(P\). ɱɶɳ ɯɻɴ>d; ɳʄɴɳʂ@a; ʁ@a; ɳʄʆʇɳ@a;ɵ ʅɹɳʈ@a;ًɳ ʄʀ \(1\)، ʁʇɶɳ @a;ɿʆ@a; ɯʆ >c;ʅ@a;ɿ ɳʄɿʈɳʅʄ ɳʄɯʈʄ@a;ɵ ʃɳʆ>a; ʅɹʅʈ>d;ة، ʈɴɳʄ>a;ɳʄ@a; ʁɳʄɿ>f;>f; \(47\)-smooth. ɯʅɳ ɱɶɳ ɴʂ@a;>a; ʂ@a;ʅɵ ɯʃɴɷ ʅʆ \(1\)، ʁʇʆɳʃ ɿɳʅʄ ɯʈʄ@a; ɯʃɴɷ ʅʆ \(47\)، ʈ@a;>c;ɴ ɷʁɼ ɳʄʅɷɺ>d;.
ɿʆ>f; ʆ>c;ɳ>d; ɳ>e;>a;ɴɳɷ \(y_+\) @a;>a;ʅ ɱɼɳʁɵ ɳʄʁʇɷɹ ɳʄɸʈ>c;@a; \(n=2x\). ʈɿʆ>f; ʆ>c;ɳ>d; ɳ>e;>a;ɴɳɷ \(y_-\) @a;>a;ʅ ɱɼɳʁɵ ɳʄʁʇɷɹ ɳʄʁɷ>f;@a; \(n=2x-1\).
ʄʆɯ>e;ɶ \(x=3\). ʇɶɳ ɳʄɿ>f;>f; \(47\)-smooth ʄɯʆ ɿɳʅʄʇ ɳʄɯʈʄ@a; ɳʄʈ>d;@a;>f; ʇʈ \(3\).
ɿʆ>f;ɲɶٍ
$$2x-1=5,\qquad 2x+1=7,$$
ʈʃʄɳʇʅɳ ɯ@a;ɼًɳ \(47\)-smooth. ʄɶʄʃ @a;ʂɴʄ ɳʄ>e;ʈɳɷɸʅ ʃʄاً ʅʆ
$$n=5\qquad\text{and}\qquad n=6.$$
ʁɿʄًɳ
$$T(5)=\frac{5\cdot 6}{2}=15=3\cdot 5,$$
$$T(6)=\frac{6\cdot 7}{2}=21=3\cdot 7,$$
ʈ>c;ʅ@a;ɿ ɿʈɳʅʄ ɳʄɯʈʄ@a;ɵ ʁ@a; ʃʄɳ ɳʄɿ>f;>f;@a;ʆ ɳʄʅ>b;ʄ>b;@a;@a;ʆ ʄɳ >a;>a;>c;ɳʈɸ \(47\).
ʃʄ ʅɷɺ>d; ʅʂɴʈʄ @a;ʆ>a;>c; ʁʇɷɹًɳ ɻ>d;@a;>d;ًɳ، ʄɯʆ >a;ʁʃ@a;ʃ ɳʄ>d;ɳʄɵ >d;ɹɴ ɳʄʁɷ>f;@a;ɵ ʈɳʄɸʈ>c;@a;ɵ @a;ɿ@a;>f; ɴʆɳɭ
$$T(2x)=x(2x+1),\qquad T(2x-1)=x(2x-1),$$
ʈʂ>f; >a;ʅ ɳʄ>a;>d;ʂʂ ʅɹɴʂًɳ ʅʆ ɯʆ ʃʄا ɳʄɿɳʅʄ@a;ʆ \(47\)-smooth. ʈɴɳʄɿʃɹ، ʁɱʆ ʃʄ ʁʇɷɹ ɻ>d;@a;>d; \(n\) @a;ʆ>a;ʅ@a; ɱʄʉ ɯ>d;>f; ɳʄ>d;ɳʄ>a;@a;ʆ ɳʄʅ>a;ʅ@a;ɸ>a;@a;ʆ ɴ>d;ɹɴ ɳʄʁɷ>f;@a;ɵ ɯʈ ɳʄɸʈ>c;@a;ɵ، ʈʅʆ >b;ʅ ʁʇʈ @a;ɿɽ@a; ʆʈɳɵ smooth ʈɳ>d;>f;ة \(x\) ʈɳ>e;>a;ɴɳɷًɳ ʆɳ>c;>d;ًɳ ʄɯ>d;>f; ɳʄ>c;ɳɷ@a;ʆ. ʄɶʄʃ >a;>d;ɹɴ ɳʄ>a;نفيذات ɳʄʅ>c;ʅʈɿ ɳʄʅɽʄʈɴ ʅʆ >e;ʄɳʄ >a;ɿ>f;ɳ>f; ʃʄ ɳʄʆʈʉ smooth ʁ@a; ʆɽɳʂ ɳʄɴ>d;>b; ɳʄʅ>e;>a;ɳɷ، >b;ʅ ɱɼɳʁɵ ɳʄʁʇɳɷɹ ɳʄʅɽɳɴʂɵ ʁʂɽ.
تتبع تنفيذات C++ وPython وJava ɳʄɴʆ@a;ɵ نʁɹʇɳ. ʁ@a; ɳʄɴ>f;ɳ@a;ɵ >a;>e;ɸʆ ɳʄ>e;ʅɹɵ ɿɺɷ ɿ>f;>f;ًɳ ɯʈʄ@a;ًɳ ɳʄʅɹʅʈ>d; ɴʇɳ >d;>a;ى \(47\). ɴɿ>f; ɶʄʃ >a;ʆʁذ ɴ>d;>b;ًɳ >a;ɷɳ>c;ɿيًɳ ɿʄى ɳ>e;>a;@a;ɳر ɳʄɯɹɹ، ɴ>d;@a;>b; @a;ɴقʉ ɳʄ>d;ɳɻʄ ɳʄ>d;ɳʄ@a; \(47\)-smooth ɴɳʄɴʆɳɭ ʆʁɹʇ.
ɿʆ>f;ʅɳ >a;ʆ>a;ʇ@a; ɳʄ>a;ɷɳ>c;ɿ@a;ɵ ʅʆ ʅɿɳʄ>c;ɵ ɳʄɯʈʄ@a;ɳ>a; ɳʄ>e;ʅɹɵ ɿɺɷɵ ʃʄهɳ، @a;ɻɴ>d; ɳʄ>d;ɳɻʄ ɳʄ>d;ɳʄ@a; ʅɷɺ>d;ًɳ ʅʃ>a;ʅʄًɳ \(x\). ʁ@a; >a;ʄʃ ɳʄʄ>d;ɾɵ >a;>d;ɹɴ ɳʄ>a;نفيذات \(2x-1\) ʈ \(2x+1\)، ʈ>a;>e;>a;ɴɷ ʃʄاً ʅʆʇʅɳ ɴɳɹ>a;ɿʅال ʆʁɹ ʂɳɲʅɵ ɳʄɯʈليات ɿɴɷ ʂɹʅɳ>a; ʅ>a;ʃɷɷة، >b;ʅ >a;ɼ@a;ʁ ɳʄʁʇɷɹ ɳʄʅʆɳɹɴ ɯʈ ɳʄʁʇɷɹ@a;ʆ ɱʄى ʅ>c;ʅʈɿ ʅ>a;ɷɳʃʅ.
ʄɳ >a;>a;ʁɷɿ ɳʄ>a;ɷɳ>c;ɿ@a;ɵ ɱʄا ʅɳ >f;ɳʅ ɳʄɼɷɴ ɳʄ>a;ɳʄ@a; ʄʆ @a;>a;>c;ɳʈɸ ɳʄ>d;>f; ɳʄ>b;ɳɴ>a; \(10^{13}\). ʈɴʅɳ ɯʆ >c;ʅ@a;ɿ ɳʄɿʅʄ@a;ɳ>a; >a;ɴʂى >f;ɳ>e;ʄ ʇɶɳ ɳʄʅ>f;ʉ، ʁɱʆ ɯʆʈɳɿ ɳʄɯɿ>f;ɳ>f; ɳʄɻ>d;@a;>d;ɵ ɶɳ>a; 64 ɴ>a;ًɳ >a;ʃʁ@a; ʄʇɶɳ ɳʄ?a;ɷɼ.
ʄʆɷʅɸ ɴـ \(S(B)\) ɱʄى ɿ>f;>f; ɳʄʂ@a;ʅ \(x\le B\) ɳʄ>a;@a; ʇ@a; \(47\)-smooth، >d;@a;>b; \(B=10^{13}\) ʇʈ ɳʄ>d;>f; ɳʄʅɿ>a;ʅ>f; ʁ@a; ɳʄ>a;نفيذات. @a;ɸʈɷ ɳʄʅʈʄ>f; ɳʄ>a;ɷɳ>c;ɿ@a; ʃʄ ʂ@a;ʅɵ ʅʆ ʇɶʇ ɳʄʂ@a;ʅ ʅɷɵ ʈɳ>d;>f;ɵ ɴɳʄɼɴɽ، ʈɿʅʂ ɳʄ>a;ɷɳ>c;ɿ ʇʈ ɳʄ>b;ɳɴ>a; \(15\).
ʄʃʄ \(x\) ʅʈل>f;، >a;ʆفذ ɳʄɺيفرة ɳ>e;>a;ɴɳɷ@a; smoothness ɿʄى ʆʁɹ ʅ>c;ʅʈɿɵ ɳʄɯʈليات \(P\). ɳʄʂɹʅɳ>a; ɳʄʅ>a;ʃɷرة ɿʄى ʂʈى ɳʄɯʈليات >a;ɼ@a;ʁ ʁ@a; ɳʄʅʅɳɷسة ɿɳʅʄًɳ ɻ?a;@a;رًɳ ʁʂɽ، ʄɶɳ ʁɱʆ ɳʄɸʅʆ ɳʄʃʄي @a;>a;ʆɳɹɴ ɴɻʈرة ɯɹɳɹ@a;ة ʅɿ ɿ>f;>f; ɳʄʅɷɺ>d;ا>a; smooth ɳʄʅɿ>f;>f;ɵ. ʈʅɿ >b;ɴɳ>a; \(47\)، @a;ʃʈن ɳɹ>a;هʄɳʃ ɳʄɶɳʃرة \(O(1)\) ɴɳɹ>a;>b;ʆɳɭ ʅʃ>f;س ɳʄ>a;ɷɳ>c;ɿ<c; ʈʇʈ ɴ>f;ʈرʇ ɶʈ ɿʅʂ >b;ɳɴ>a;.