Let \(\sigma(n)\) be the sum of the positive divisors of \(n\). A positive integer \(n\) is called triffle when the reduced fraction \(\sigma(n)/n\) has denominator \(3^k\) for some \(k\ge 1\). In other words, after all common factors of \(\sigma(n)\) and \(n\) are canceled, the denominator is a positive power of \(3\).
If \(\mathcal{T}\) denotes the set of triffle numbers, the goal is to compute
$$T(N)=\sum_{\substack{n\le N \\ n\in \mathcal{T}}} n.$$
The C++, Python, and Java implementations do not test every \(n\le N\). They separate the exact power of \(3\) dividing \(n\), convert the triffle condition into divisibility statements involving \(\sigma(m)\), and then search only the multiplicative branches that can still satisfy those statements.
Every triffle number is divisible by \(3\), so write it uniquely as
$$n=3^a m,\qquad a\ge 1,\qquad 3\nmid m.$$
This isolates the only prime that is allowed to remain in the reduced denominator.
Because \(\sigma\) is multiplicative on coprime factors,
$$\sigma(n)=\sigma(3^a)\sigma(m).$$
The divisor sum of the pure \(3\)-part is
$$\sigma(3^a)=1+3+\cdots+3^a=\frac{3^{a+1}-1}{2}.$$
Define
$$c_a=\frac{3^{a+1}-1}{2}.$$
Then
$$\frac{\sigma(n)}{n}=\frac{c_a\sigma(m)}{3^a m}.$$
Since \(3^{a+1}-1\equiv -1 \pmod 3\), the factor \(c_a\) is never divisible by \(3\).
All primes outside \(3\) that could remain in the denominator must come from \(m\), because \(m\) is coprime to \(3\). Therefore the reduced denominator is a power of \(3\) exactly when every prime factor of \(m\) cancels against the numerator \(c_a\sigma(m)\).
This gives the key divisibility condition
$$m \mid c_a\sigma(m).$$
Once this is true, all non-\(3\) denominator factors are gone.
After the non-\(3\) part vanishes, the remaining denominator can only come from \(3^a\). Because \(3\nmid c_a\) and \(3\nmid m\), the only cancellation with \(3^a\) comes from \(\sigma(m)\). Hence, when \(m \mid c_a\sigma(m)\), the reduced denominator is
$$3^{a-v_3(\sigma(m))}.$$
To be triffle, this denominator must still be greater than \(1\), so
$$a-v_3(\sigma(m))\ge 1,$$
which is equivalent to
$$v_3(\sigma(m))\le a-1.$$
Thus \(n=3^a m\) is triffle if and only if
$$m \mid c_a\sigma(m),\qquad v_3(\sigma(m))\le a-1.$$
Write
$$m=\prod_{j=1}^r p_j^{e_j},\qquad p_j\neq 3.$$
Then
$$\sigma(m)=\prod_{j=1}^r \sigma(p_j^{e_j}),\qquad \sigma(p^e)=\frac{p^{e+1}-1}{p-1}.$$
So
$$\frac{c_a\sigma(m)}{m}=c_a\prod_{j=1}^r \frac{\sigma(p_j^{e_j})}{p_j^{e_j}}.$$
This identity is ideal for depth-first search. Start from \(m=1\), add a new prime power \(p^e\), update the reduced fraction above, and increase \(v_3(\sigma(m))\) by \(v_3(\sigma(p^e))\). Any branch that already exceeds the layer bound or violates the \(3\)-adic limit can be pruned immediately.
For each \(a\ge 1\) with \(3^a\le N\), define
$$\mathcal{M}_a(N)=\left\{m\le \frac{N}{3^a}: 3\nmid m,\ m\mid c_a\sigma(m),\ v_3(\sigma(m))\le a-1\right\}.$$
Then
$$\boxed{T(N)=\sum_{\substack{a\ge 1\\3^a\le N}} 3^a\sum_{m\in\mathcal{M}_a(N)} m.}$$
Each value of \(a\) defines an independent search layer, so the layer sums can be computed separately and combined at the end.
Take \(n=84=3^1\cdot 28\). Here \(a=1\), \(m=28\), and
$$c_1=\frac{3^2-1}{2}=4,\qquad \sigma(28)=56.$$
Now
$$\frac{c_1\sigma(m)}{m}=\frac{4\cdot 56}{28}=8,$$
so every denominator prime other than \(3\) disappears. Also
$$v_3(\sigma(28))=v_3(56)=0\le 1-1.$$
Therefore the reduced denominator is \(3^{1-0}=3\), and indeed
$$\frac{\sigma(84)}{84}=\frac{4\cdot 56}{84}=\frac{8}{3}.$$
So \(84\) is triffle. The small checkpoint
$$T(100)=3+9+12+27+54+81+84=270$$
matches the value verified by the implementations.
The C++, Python, and Java implementations iterate over all \(a\) with \(3^a\le N\). For each layer they compute the bound \(\lfloor N/3^a\rfloor\) and the geometric-series factor \(c_a\), then start a depth-first search from \(m=1\).
The search state stores the current \(m\), the reduced fraction for \(c_a\sigma(m)/m\), the current value of \(v_3(\sigma(m))\), and the current divisor sum \(\sigma(m)\). When a new prime power \(p^e\) with \(p\neq 3\) is appended, the implementations multiply by \(\sigma(p^e)/p^e\), cancel common factors immediately, and recurse only if the new \(m\) stays within the layer bound and the \(3\)-adic valuation still satisfies \(v_3(\sigma(m))\le a-1\).
To keep branching small, the next prime candidates are taken from the prime factors of the current reduced numerator, with \(2\) always included as a cheap fallback. A state is accepted when the reduced fraction has denominator \(1\), because that means every non-\(3\) denominator factor has already been removed. The accepted \(m\)-values are summed, then multiplied by \(3^a\).
For 64-bit factorization, the implementations use deterministic Miller-Rabin primality testing and Pollard-Rho splitting. Different \(a\)-layers are independent, so they can also be processed in parallel. Small checkpoints such as \(T(100)=270\) and \(T(10^6)=26089287\) are used as correctness guards.
There is no simple closed-form bound because the runtime depends on how strongly the divisibility tests and valuation bounds prune the search tree. A practical summary is
$$\text{time} \approx \text{visited DFS states} \times \text{average 64-bit factorization cost}.$$
Memory is dominated by the recursion path, the set of already visited \(m\)-values inside each layer, and the factorization cache. In practice the method works because most branches die early and the different \(3\)-layers are independent.
Sei \(\sigma(n)\) die Summe der positiven Teiler von \(n\). Eine positive ganze Zahl \(n\) heißt triffle, wenn der vollständig gekürzte Bruch \(\sigma(n)/n\) den Nenner \(3^k\) mit \(k\ge 1\) besitzt. Nach dem Kürzen aller gemeinsamen Faktoren bleibt also genau eine positive Dreierpotenz im Nenner übrig.
Bezeichnet \(\mathcal{T}\) die Menge aller triffle-Zahlen, so ist gesucht:
$$T(N)=\sum_{\substack{n\le N \\ n\in \mathcal{T}}} n.$$
Die Implementierungen prüfen nicht jede Zahl bis \(N\). Stattdessen trennen sie die exakte Dreierpotenz von \(n\), formulieren die Bedingung über \(\sigma(m)\) neu und durchsuchen anschließend nur die multiplikativen Zweige, die diese Bedingung überhaupt noch erfüllen können.
Jede triffle-Zahl ist durch \(3\) teilbar. Daher schreiben wir eindeutig
$$n=3^a m,\qquad a\ge 1,\qquad 3\nmid m.$$
So wird die einzige Primzahl isoliert, die nach dem Kürzen im Nenner übrig bleiben darf.
Wegen der Multiplikativität von \(\sigma\) auf teilerfremden Faktoren gilt
$$\sigma(n)=\sigma(3^a)\sigma(m).$$
Für den reinen \(3\)-Anteil erhält man
$$\sigma(3^a)=1+3+\cdots+3^a=\frac{3^{a+1}-1}{2}.$$
Setze
$$c_a=\frac{3^{a+1}-1}{2}.$$
Dann folgt
$$\frac{\sigma(n)}{n}=\frac{c_a\sigma(m)}{3^a m}.$$
Da \(3^{a+1}-1\equiv -1 \pmod 3\), ist \(c_a\) nie durch \(3\) teilbar.
Jede Primzahl \(p\neq 3\), die im gekürzten Nenner stehen könnte, stammt aus \(m\). Deshalb ist der gekürzte Nenner genau dann eine Dreierpotenz, wenn alle Primfaktoren von \(m\) gegen den Zähler \(c_a\sigma(m)\) weggekürzt werden.
Die zentrale Teilbarkeitsbedingung lautet also
$$m \mid c_a\sigma(m).$$
Ist sie erfüllt, verschwinden alle Nennerfaktoren ungleich \(3\).
Nach dem Entfernen des nicht durch \(3\) teilbaren Anteils kann nur noch ein Teil von \(3^a\) im Nenner stehen. Weil \(3\nmid c_a\) und \(3\nmid m\), kommt diese Kürzung nur aus \(\sigma(m)\). Dann wird der reduzierte Nenner zu
$$3^{a-v_3(\sigma(m))}.$$
Für eine triffle-Zahl darf dieser Nenner nicht \(1\) sein. Also braucht man
$$a-v_3(\sigma(m))\ge 1,$$
äquivalent zu
$$v_3(\sigma(m))\le a-1.$$
Somit ist \(n=3^a m\) genau dann triffle, wenn
$$m \mid c_a\sigma(m),\qquad v_3(\sigma(m))\le a-1.$$
Schreibe
$$m=\prod_{j=1}^r p_j^{e_j},\qquad p_j\neq 3.$$
Dann gilt
$$\sigma(m)=\prod_{j=1}^r \sigma(p_j^{e_j}),\qquad \sigma(p^e)=\frac{p^{e+1}-1}{p-1}.$$
Daraus folgt
$$\frac{c_a\sigma(m)}{m}=c_a\prod_{j=1}^r \frac{\sigma(p_j^{e_j})}{p_j^{e_j}}.$$
Genau diese Darstellung nutzt die Tiefensuche. Man beginnt mit \(m=1\), fügt eine neue Primzahlpotenz \(p^e\) hinzu, aktualisiert den gekürzten Bruch und erhöht gleichzeitig \(v_3(\sigma(m))\) um \(v_3(\sigma(p^e))\). Jeder Zweig, der das Schichtlimit überschreitet oder die \(3\)-adische Schranke verletzt, kann sofort verworfen werden.
Für jedes \(a\ge 1\) mit \(3^a\le N\) definieren wir
$$\mathcal{M}_a(N)=\left\{m\le \frac{N}{3^a}: 3\nmid m,\ m\mid c_a\sigma(m),\ v_3(\sigma(m))\le a-1\right\}.$$
Dann gilt
$$\boxed{T(N)=\sum_{\substack{a\ge 1\\3^a\le N}} 3^a\sum_{m\in\mathcal{M}_a(N)} m.}$$
Jeder Wert von \(a\) definiert eine eigene Schicht, und genau deshalb können diese Schichten unabhängig berechnet werden.
Betrachte \(n=84=3^1\cdot 28\). Dann ist \(a=1\), \(m=28\), und
$$c_1=\frac{3^2-1}{2}=4,\qquad \sigma(28)=56.$$
Damit
$$\frac{c_1\sigma(m)}{m}=\frac{4\cdot 56}{28}=8,$$
also verschwindet jeder Nennerfaktor außer \(3\). Außerdem gilt
$$v_3(\sigma(28))=v_3(56)=0\le 1-1.$$
Der reduzierte Nenner ist somit \(3^{1-0}=3\), und tatsächlich
$$\frac{\sigma(84)}{84}=\frac{4\cdot 56}{84}=\frac{8}{3}.$$
Also ist \(84\) triffle. Die kleine Kontrollsumme
$$T(100)=3+9+12+27+54+81+84=270$$
stimmt mit dem geprüften Referenzwert überein.
Die C++-, Python- und Java-Implementierungen laufen über alle \(a\) mit \(3^a\le N\). Für jede Schicht berechnen sie die Schranke \(\lfloor N/3^a\rfloor\) und den Faktor \(c_a\), anschließend startet eine Tiefensuche bei \(m=1\).
Im Suchzustand stehen der aktuelle Wert \(m\), der gekürzte Bruch für \(c_a\sigma(m)/m\), der aktuelle Wert \(v_3(\sigma(m))\) und die laufende Teilersumme \(\sigma(m)\). Wird eine neue Primzahlpotenz \(p^e\) mit \(p\neq 3\) angehängt, multipliziert die Implementierung mit \(\sigma(p^e)/p^e\), kürzt sofort gemeinsame Faktoren heraus und steigt nur dann tiefer hinab, wenn das neue \(m\) innerhalb der Schichtschranke bleibt und die Bedingung \(v_3(\sigma(m))\le a-1\) noch erfüllt ist.
Um die Verzweigung klein zu halten, stammen die nächsten Primkandidaten aus den Primfaktoren des aktuellen gekürzten Zählers; zusätzlich wird \(2\) immer als billiger Fallback aufgenommen. Ein Zustand wird akzeptiert, sobald der gekürzte Bruch den Nenner \(1\) besitzt, denn dann sind alle Nennerfaktoren außer möglichen Dreierpotenzen bereits verschwunden. Die zulässigen \(m\)-Werte werden summiert und anschließend mit \(3^a\) multipliziert.
Für Faktorisierungen im 64-Bit-Bereich verwenden die Implementierungen einen deterministischen Miller-Rabin-Test sowie Pollard-Rho zum Zerlegen zusammengesetzter Zahlen. Die Schichten sind unabhängig und können deshalb parallel abgearbeitet werden. Kleine Prüfpunkte wie \(T(100)=270\) und \(T(10^6)=26089287\) dienen als Sicherheitsnetz.
Eine einfache geschlossene Laufzeitformel gibt es nicht, weil die tatsächliche Dauer davon abhängt, wie stark die Teilbarkeitsbedingungen und die \(3\)-adische Schranke den Suchbaum ausdünnen. Praktisch lässt sich die Zeit beschreiben als
$$\text{time} \approx \text{visited DFS states} \times \text{average 64-bit factorization cost}.$$
Der Speicherbedarf wird vor allem durch den Rekursionspfad, die Menge bereits besuchter \(m\)-Werte pro Schicht und den Faktorisierungs-Cache bestimmt. In der Praxis funktioniert die Methode gut, weil die meisten Zweige früh abgeschnitten werden und die verschiedenen Dreier-Schichten vollständig unabhängig sind.
\(\sigma(n)\), \(n\)'in pozitif bölenlerinin toplamı olsun. Bir pozitif tamsayı \(n\), \(\sigma(n)/n\) kesri en sade hale getirildiğinde paydası \(3^k\) biçiminde kalıyorsa ve \(k\ge 1\) ise triffle sayıdır. Yani tüm ortak bölenler sadeleştirildikten sonra paydada yalnızca pozitif bir \(3\) kuvveti kalır.
\(\mathcal{T}\) triffle sayıların kümesi olmak üzere amaç
$$T(N)=\sum_{\substack{n\le N \\ n\in \mathcal{T}}} n$$
toplamını hesaplamaktır. C++, Python ve Java implementasyonları tüm \(n\le N\) değerlerini tek tek denemez. Bunun yerine \(n\)'in içindeki tam \(3\) kuvvetini ayırır, koşulu \(\sigma(m)\) üzerinden bölünebilirlik ifadelerine dönüştürür ve yalnızca hala başarılı olabilecek çarpımsal dalları araştırır.
Her triffle sayı mutlaka \(3\) ile bölünür. Bu yüzden onu tekil olarak
$$n=3^a m,\qquad a\ge 1,\qquad 3\nmid m$$
şeklinde yazarız. Böylece sadeleşmeden sonra paydada kalmasına izin verilen tek asal olan \(3\) ayrı tutulmuş olur.
\(\sigma\) fonksiyonu aralarında asal çarpanlarda çarpımsal olduğundan
$$\sigma(n)=\sigma(3^a)\sigma(m)$$
yazabiliriz. Saf \(3\)-parçası için
$$\sigma(3^a)=1+3+\cdots+3^a=\frac{3^{a+1}-1}{2}$$
olur. Şimdi
$$c_a=\frac{3^{a+1}-1}{2}$$
tanımını yapalım. O zaman
$$\frac{\sigma(n)}{n}=\frac{c_a\sigma(m)}{3^a m}$$
elde edilir. Ayrıca \(3^{a+1}-1\equiv -1 \pmod 3\) olduğu için \(c_a\) hiçbir zaman \(3\) ile bölünmez.
Sadeleştirme sonrası paydada kalabilecek \(3\) dışı tüm asallar \(m\)'den gelir; çünkü \(m\), \(3\) ile aralarında asaldır. Dolayısıyla indirgenmiş paydanın bir \(3\) kuvveti olması için \(m\)'nin tüm asal çarpanlarının pay \(c_a\sigma(m)\) tarafından götürülmesi gerekir.
Temel koşul şudur:
$$m \mid c_a\sigma(m).$$
Bu sağlanırsa paydadaki \(3\) dışı tüm çarpanlar kaybolur.
\(3\) dışı kısım sadeleştikten sonra geriye yalnızca \(3^a\)'nın bir bölümü kalabilir. Çünkü \(3\nmid c_a\) ve \(3\nmid m\), \(3\) ile gelen tek sadeleşme kaynağı \(\sigma(m)\)'dir. Bu yüzden indirgenmiş payda
$$3^{a-v_3(\sigma(m))}$$
şeklini alır. Triffle olmak için bu payda \(1\) olamaz. Yani
$$a-v_3(\sigma(m))\ge 1$$
ve eşdeğer olarak
$$v_3(\sigma(m))\le a-1$$
gereklidir. Sonuç olarak \(n=3^a m\) ancak ve ancak
$$m \mid c_a\sigma(m),\qquad v_3(\sigma(m))\le a-1$$
olduğunda triffle sayıdır.
\(m\)'yi
$$m=\prod_{j=1}^r p_j^{e_j},\qquad p_j\neq 3$$
şeklinde yazalım. Çarpımsallıktan
$$\sigma(m)=\prod_{j=1}^r \sigma(p_j^{e_j}),\qquad \sigma(p^e)=\frac{p^{e+1}-1}{p-1}$$
elde edilir. O halde
$$\frac{c_a\sigma(m)}{m}=c_a\prod_{j=1}^r \frac{\sigma(p_j^{e_j})}{p_j^{e_j}}.$$
Arama tam olarak bu formül üzerine kuruludur. \(m=1\)'den başlanır, yeni bir asal kuvvet \(p^e\) eklenir, kesir sadeleştirilir ve \(v_3(\sigma(m))\) değeri \(v_3(\sigma(p^e))\) kadar artırılır. Katman limitini aşan veya \(3\)-adik sınırı bozan her dal anında kesilir.
Her \(a\ge 1\) ve \(3^a\le N\) için
$$\mathcal{M}_a(N)=\left\{m\le \frac{N}{3^a}: 3\nmid m,\ m\mid c_a\sigma(m),\ v_3(\sigma(m))\le a-1\right\}$$
kümesini tanımlayalım. O zaman hedef toplam
$$\boxed{T(N)=\sum_{\substack{a\ge 1\\3^a\le N}} 3^a\sum_{m\in\mathcal{M}_a(N)} m.}$$
Her \(a\) değeri bağımsız bir arama katmanı üretir; bu nedenle implementasyonlar bu katmanları ayrı ayrı hesaplayıp sonunda birleştirebilir.
\(n=84=3^1\cdot 28\) alalım. Burada \(a=1\), \(m=28\) ve
$$c_1=\frac{3^2-1}{2}=4,\qquad \sigma(28)=56.$$
Şimdi
$$\frac{c_1\sigma(m)}{m}=\frac{4\cdot 56}{28}=8$$
olduğu için paydada \(3\) dışı hiçbir asal kalmaz. Ayrıca
$$v_3(\sigma(28))=v_3(56)=0\le 1-1.$$
Böylece indirgenmiş payda \(3^{1-0}=3\) olur ve gerçekten
$$\frac{\sigma(84)}{84}=\frac{4\cdot 56}{84}=\frac{8}{3}$$
çıkar. Demek ki \(84\) triffle sayıdır. Küçük kontrol toplamı
$$T(100)=3+9+12+27+54+81+84=270$$
implementasyonların doğruladığı değerle tam olarak uyuşur.
C++, Python ve Java implementasyonları, \(3^a\le N\) olan tüm \(a\) değerleri üzerinde döner. Her katman için \(\lfloor N/3^a\rfloor\) üst sınırı ve \(c_a\) katsayısı hesaplanır; ardından arama \(m=1\)'den başlatılır.
Arama durumu; geçerli \(m\) değerini, \(c_a\sigma(m)/m\) ifadesinin sadeleştirilmiş kesrini, anlık \(v_3(\sigma(m))\) değerini ve mevcut bölen toplamı \(\sigma(m)\)'yi tutar. Yeni bir \(p^e\) asal kuvveti eklendiğinde ve \(p\neq 3\) olduğunda, implementasyon \(\sigma(p^e)/p^e\) çarpanını uygular, ortak bölenleri hemen sadeleştirir ve sadece yeni \(m\) katman sınırını aşmıyorsa ve \(v_3(\sigma(m))\le a-1\) koşulu bozulmuyorsa derine iner.
Dallanmayı küçültmek için sıradaki asal adayları mevcut sadeleştirilmiş payın asal çarpanlarından seçilir; buna ek olarak \(2\) her zaman ucuz bir yedek aday olarak eklenir. Sadeleştirilmiş kesrin paydası \(1\) olduğunda durum kabul edilir; çünkü bu, \(3\) dışındaki tüm payda çarpanlarının yok olduğu anlamına gelir. Katmanda bulunan uygun \(m\) değerleri toplanır, sonra \(3^a\) ile çarpılıp nihai toplama eklenir.
64-bit çarpanlara ayırma için deterministik Miller-Rabin asallık testi ve Pollard-Rho kullanılır. Katmanlar birbirinden bağımsız olduğu için paralel çalıştırma da mümkündür. \(T(100)=270\) ve \(T(10^6)=26089287\) gibi küçük doğrulama değerleri de güvenlik kontrolü olarak kullanılır.
Basit bir kapalı üst sınır yoktur; çalışma süresi, bölünebilirlik testlerinin ve değerlik sınırlarının arama ağacını ne kadar daralttığına bağlıdır. Pratik bir özet şu şekildedir:
$$\text{time} \approx \text{visited DFS states} \times \text{average 64-bit factorization cost}.$$
Bellek kullanımı esas olarak özyineleme yolu, her katmandaki ziyaret edilmiş \(m\) kümesi ve çarpanlara ayırma önbelleğinden gelir. Yöntemin işe yaramasının nedeni, çoğu dalın çok erken kesilmesi ve farklı \(3\)-katmanlarının tamamen bağımsız olmasıdır.
Sea \(\sigma(n)\) la suma de los divisores positivos de \(n\). Un entero positivo \(n\) es triffle cuando la fracción \(\sigma(n)/n\), reducida a términos mínimos, tiene denominador \(3^k\) para algún \(k\ge 1\). Es decir, tras cancelar todos los factores comunes entre \(\sigma(n)\) y \(n\), en el denominador queda una potencia positiva de \(3\).
Si \(\mathcal{T}\) es el conjunto de números triffle, hay que calcular
$$T(N)=\sum_{\substack{n\le N \\ n\in \mathcal{T}}} n.$$
Las implementaciones en C++, Python y Java no prueban todos los enteros hasta \(N\). Separan la potencia exacta de \(3\) que divide a \(n\), transforman la condición triffle en reglas de divisibilidad con \(\sigma(m)\), y después exploran solo las ramas multiplicativas que todavía pueden cumplir esas reglas.
Toda cantidad triffle debe ser múltiplo de \(3\), así que la escribimos de forma única como
$$n=3^a m,\qquad a\ge 1,\qquad 3\nmid m.$$
Esto aísla al único primo que puede sobrevivir en el denominador final.
Como \(\sigma\) es multiplicativa en factores coprimos,
$$\sigma(n)=\sigma(3^a)\sigma(m).$$
La suma de divisores de la parte pura en \(3\) es
$$\sigma(3^a)=1+3+\cdots+3^a=\frac{3^{a+1}-1}{2}.$$
Definimos
$$c_a=\frac{3^{a+1}-1}{2}.$$
Entonces
$$\frac{\sigma(n)}{n}=\frac{c_a\sigma(m)}{3^a m}.$$
Además, como \(3^{a+1}-1\equiv -1 \pmod 3\), el factor \(c_a\) nunca es divisible por \(3\).
Los únicos primos distintos de \(3\) que podrían quedar en el denominador reducido vienen de \(m\), ya que \(m\) es coprimo con \(3\). Por lo tanto, el denominador final será una potencia de \(3\) exactamente cuando todos los factores primos de \(m\) se cancelen con el numerador \(c_a\sigma(m)\).
Eso conduce a la condición fundamental
$$m \mid c_a\sigma(m).$$
Si se cumple, desaparece toda la parte del denominador que no es potencia de \(3\).
Una vez cancelada la parte ajena a \(3\), el único resto posible en el denominador proviene de \(3^a\). Como \(3\nmid c_a\) y \(3\nmid m\), esa cancelación solo puede venir de \(\sigma(m)\). En consecuencia, el denominador reducido pasa a ser
$$3^{a-v_3(\sigma(m))}.$$
Para que \(n\) sea triffle, ese denominador no puede ser \(1\). Necesitamos
$$a-v_3(\sigma(m))\ge 1,$$
o de forma equivalente
$$v_3(\sigma(m))\le a-1.$$
Por tanto, \(n=3^a m\) es triffle si y solo si
$$m \mid c_a\sigma(m),\qquad v_3(\sigma(m))\le a-1.$$
Escribimos
$$m=\prod_{j=1}^r p_j^{e_j},\qquad p_j\neq 3.$$
La multiplicatividad da
$$\sigma(m)=\prod_{j=1}^r \sigma(p_j^{e_j}),\qquad \sigma(p^e)=\frac{p^{e+1}-1}{p-1}.$$
Entonces
$$\frac{c_a\sigma(m)}{m}=c_a\prod_{j=1}^r \frac{\sigma(p_j^{e_j})}{p_j^{e_j}}.$$
Esta identidad es la base de la búsqueda. Se comienza con \(m=1\), se añade una nueva potencia prima \(p^e\), se actualiza la fracción reducida y también el valor \(v_3(\sigma(m))\) sumando \(v_3(\sigma(p^e))\). Si una rama ya supera el límite de la capa o rompe la cota \(v_3(\sigma(m))\le a-1\), se descarta de inmediato.
Para cada \(a\ge 1\) con \(3^a\le N\), definimos
$$\mathcal{M}_a(N)=\left\{m\le \frac{N}{3^a}: 3\nmid m,\ m\mid c_a\sigma(m),\ v_3(\sigma(m))\le a-1\right\}.$$
La suma buscada queda
$$\boxed{T(N)=\sum_{\substack{a\ge 1\\3^a\le N}} 3^a\sum_{m\in\mathcal{M}_a(N)} m.}$$
Cada valor de \(a\) define una capa independiente, por eso las implementaciones pueden resolverlas por separado y unir los resultados al final.
Tomemos \(n=84=3^1\cdot 28\). Aquí \(a=1\), \(m=28\), y
$$c_1=\frac{3^2-1}{2}=4,\qquad \sigma(28)=56.$$
Entonces
$$\frac{c_1\sigma(m)}{m}=\frac{4\cdot 56}{28}=8,$$
de modo que desaparece cualquier primo del denominador distinto de \(3\). Además,
$$v_3(\sigma(28))=v_3(56)=0\le 1-1.$$
Por tanto el denominador reducido es \(3^{1-0}=3\), y en efecto
$$\frac{\sigma(84)}{84}=\frac{4\cdot 56}{84}=\frac{8}{3}.$$
Así que \(84\) es triffle. El pequeño punto de control
$$T(100)=3+9+12+27+54+81+84=270$$
coincide exactamente con el valor verificado por las implementaciones.
Las implementaciones en C++, Python y Java recorren todos los \(a\) con \(3^a\le N\). Para cada capa calculan el límite \(\lfloor N/3^a\rfloor\) y el factor geométrico \(c_a\), y luego inician una búsqueda en profundidad desde \(m=1\).
El estado de búsqueda guarda el valor actual de \(m\), la fracción reducida que representa \(c_a\sigma(m)/m\), el valor acumulado \(v_3(\sigma(m))\) y la suma de divisores actual \(\sigma(m)\). Al añadir una nueva potencia prima \(p^e\) con \(p\neq 3\), la implementación multiplica por \(\sigma(p^e)/p^e\), cancela factores comunes de inmediato y solo continúa si el nuevo \(m\) sigue dentro del límite de la capa y la condición \(v_3(\sigma(m))\le a-1\) permanece válida.
Para reducir la ramificación, los siguientes primos candidatos se toman de los factores primos del numerador reducido actual, añadiendo siempre \(2\) como respaldo barato. Un estado se acepta cuando la fracción reducida tiene denominador \(1\), porque eso significa que ya desaparecieron todos los factores del denominador distintos de \(3\). La suma de los \(m\) válidos se multiplica por \(3^a\) y se agrega al total final.
La factorización de enteros de 64 bits usa Miller-Rabin determinista para primalidad y Pollard-Rho para descomposición. Como las capas son independientes, también pueden procesarse en paralelo. Los valores \(T(100)=270\) y \(T(10^6)=26089287\) se utilizan como comprobaciones de corrección.
No existe una cota cerrada simple, porque el tiempo real depende de cuántos estados sobreviven a las podas por divisibilidad y valoración \(3\)-ádica. Una forma práctica de describirlo es
$$\text{time} \approx \text{visited DFS states} \times \text{average 64-bit factorization cost}.$$
La memoria está dominada por la pila de recursión, el conjunto de valores \(m\) ya visitados dentro de cada capa y la caché de factorizaciones. En la práctica el método funciona bien porque la mayoría de las ramas se cortan pronto y las distintas capas en potencias de \(3\) son completamente independientes.
记 \(\sigma(n)\) 为 \(n\) 的正因子和。如果把分数 \(\sigma(n)/n\) 约成最简分数后，它的分母是 \(3^k\) 且 \(k\ge 1\)，那么 \(n\) 就称为 triffle 数。也就是说，把 \(\sigma(n)\) 和 \(n\) 的公因子全部约掉以后，分母里只剩下一项正的 \(3\) 的幂。
如果用 \(\mathcal{T}\) 表示 triffle 数集合，那么题目要求计算
$$T(N)=\sum_{\substack{n\le N \\ n\in \mathcal{T}}} n.$$
C++、Python 和 Java 实现都没有对 \(1\) 到 \(N\) 做暴力枚举。它们先把 \(n\) 中恰好含有多少个因子 \(3\) 分离出来，再把 triffle 条件改写成关于 \(\sigma(m)\) 的整除条件，最后只搜索那些仍然可能满足条件的乘法结构分支。
任何 triffle 数都必须被 \(3\) 整除，因此可以唯一写成
$$n=3^a m,\qquad a\ge 1,\qquad 3\nmid m.$$
这样处理之后，最简分母中唯一允许保留下来的素因子就是 \(3\)。
由于 \(\sigma\) 在互素因子上是乘法性的，
$$\sigma(n)=\sigma(3^a)\sigma(m).$$
而纯 \(3\) 部分的因子和是
$$\sigma(3^a)=1+3+\cdots+3^a=\frac{3^{a+1}-1}{2}.$$
记
$$c_a=\frac{3^{a+1}-1}{2}.$$
于是
$$\frac{\sigma(n)}{n}=\frac{c_a\sigma(m)}{3^a m}.$$
因为 \(3^{a+1}-1\equiv -1 \pmod 3\)，所以 \(c_a\) 永远不会被 \(3\) 整除。
既然 \(m\) 与 \(3\) 互素，那么最简分母里所有不是 \(3\) 的素因子只能来自 \(m\)。因此，最简分母要成为 \(3\) 的幂，当且仅当 \(m\) 的全部素因子都能被分子 \(c_a\sigma(m)\) 抵消掉。
这给出核心整除条件
$$m \mid c_a\sigma(m).$$
只要这个条件成立，分母中所有非 \(3\) 部分都会消失。
在非 \(3\) 部分已经完全约掉之后，分母只可能来自原式中的 \(3^a\)。又因为 \(3\nmid c_a\) 且 \(3\nmid m\)，所以与 \(3^a\) 发生约分的唯一来源就是 \(\sigma(m)\) 中含有的 \(3\) 的幂。因此，在满足 \(m \mid c_a\sigma(m)\) 的前提下，最简分母变成
$$3^{a-v_3(\sigma(m))}.$$
题目要求的不是分母为 \(1\)，而是分母为一个正的 \(3\) 次幂，因此必须有
$$a-v_3(\sigma(m))\ge 1,$$
等价地说，
$$v_3(\sigma(m))\le a-1.$$
所以 \(n=3^a m\) 是 triffle 数，当且仅当下面两个条件同时成立：
$$m \mid c_a\sigma(m),\qquad v_3(\sigma(m))\le a-1.$$
把 \(m\) 写成
$$m=\prod_{j=1}^r p_j^{e_j},\qquad p_j\neq 3.$$
利用乘法性可得
$$\sigma(m)=\prod_{j=1}^r \sigma(p_j^{e_j}),\qquad \sigma(p^e)=\frac{p^{e+1}-1}{p-1}.$$
因此
$$\frac{c_a\sigma(m)}{m}=c_a\prod_{j=1}^r \frac{\sigma(p_j^{e_j})}{p_j^{e_j}}.$$
这正是程序搜索的数学基础。它从 \(m=1\) 开始，一次加入一个新的素数幂 \(p^e\)，把上式对应的分数实时约分，同时把 \(v_3(\sigma(m))\) 增加 \(v_3(\sigma(p^e))\)。如果新的 \(m\) 已经超过当前层的上界，或者 \(v_3(\sigma(m))\) 已经大于 \(a-1\)，这个分支就可以立即剪掉。
对每个满足 \(3^a\le N\) 的 \(a\ge 1\)，定义
$$\mathcal{M}_a(N)=\left\{m\le \frac{N}{3^a}: 3\nmid m,\ m\mid c_a\sigma(m),\ v_3(\sigma(m))\le a-1\right\}.$$
那么目标函数就可以写成
$$\boxed{T(N)=\sum_{\substack{a\ge 1\\3^a\le N}} 3^a\sum_{m\in\mathcal{M}_a(N)} m.}$$
这说明每个 \(a\) 对应一层独立搜索，层与层之间互不影响，所以实现里可以把这些层分别计算，最后再求总和。
取 \(n=84=3^1\cdot 28\)。此时 \(a=1\)，\(m=28\)，并且
$$c_1=\frac{3^2-1}{2}=4,\qquad \sigma(28)=56.$$
于是
$$\frac{c_1\sigma(m)}{m}=\frac{4\cdot 56}{28}=8,$$
说明分母里所有不是 \(3\) 的因子都被约掉了。再看
$$v_3(\sigma(28))=v_3(56)=0\le 1-1.$$
所以最简分母就是 \(3^{1-0}=3\)，并且确实有
$$\frac{\sigma(84)}{84}=\frac{4\cdot 56}{84}=\frac{8}{3}.$$
因此 \(84\) 是 triffle 数。程序验证的小检查点
$$T(100)=3+9+12+27+54+81+84=270$$
也与这一定义完全一致。
C++、Python 和 Java 实现都会枚举所有满足 \(3^a\le N\) 的 \(a\)。对每一层，它们先算出上界 \(\lfloor N/3^a\rfloor\) 和等比级数因子 \(c_a\)，然后从 \(m=1\) 启动深度优先搜索。
搜索状态会保存当前的 \(m\)、表示 \(c_a\sigma(m)/m\) 的最简分数、当前的 \(v_3(\sigma(m))\) 以及当前的 \(\sigma(m)\)。当加入新的素数幂 \(p^e\) 且 \(p\neq 3\) 时，实现会乘上 \(\sigma(p^e)/p^e\)，立刻做最大公因子约分，并且只有在新的 \(m\) 没有超过该层限制、同时 \(v_3(\sigma(m))\le a-1\) 仍然成立时才继续递归。
为了把分支数控制在较小范围内，下一批素数候选主要来自当前最简分子中的素因子，并且总是额外加入 \(2\) 作为廉价后备。只要最简分数的分母变成 \(1\)，这个状态就被接受，因为这说明所有非 \(3\) 的分母因子已经全部消失。该层所有合格的 \(m\) 会先相加，再乘以 \(3^a\) 并并入最终答案。
对于 64 位整数分解，实现使用确定性的 Miller-Rabin 素性测试和 Pollard-Rho 分解。不同的 \(a\)-层相互独立，因此也可以并行执行。像 \(T(100)=270\) 和 \(T(10^6)=26089287\) 这样的检查值，则用来确认实现没有偏离数学条件。
这里没有一个简单的闭式复杂度，因为运行时间主要取决于整除条件和 \(3\)-进赋值约束能剪掉多少搜索分支。更贴近实现的描述是
$$\text{time} \approx \text{visited DFS states} \times \text{average 64-bit factorization cost}.$$
内存主要消耗在递归路径、每一层里已经访问过的 \(m\) 集合，以及分解结果缓存上。实际运行中该方法是可行的，因为绝大多数分支会很早被剪掉，而且各个 \(3\)-层完全独立，天然适合并行。
Пусть \(\sigma(n)\) обозначает сумму положительных делителей числа \(n\). Положительное целое \(n\) называется triffle, если дробь \(\sigma(n)/n\) после сокращения имеет знаменатель \(3^k\) при некотором \(k\ge 1\). Иначе говоря, после удаления всех общих множителей между \(\sigma(n)\) и \(n\) в знаменателе остается положительная степень тройки.
Если \(\mathcal{T}\) обозначает множество triffle-чисел, то нужно вычислить
$$T(N)=\sum_{\substack{n\le N \\ n\in \mathcal{T}}} n.$$
Реализации на C++, Python и Java не перебирают все числа до \(N\). Они сначала отделяют точную степень \(3\), входящую в \(n\), затем переписывают условие triffle через делимость, связанную с \(\sigma(m)\), и после этого обходят только те мультипликативные ветви, которые еще могут привести к успеху.
Любое triffle-число делится на \(3\), поэтому его можно единственным образом представить в виде
$$n=3^a m,\qquad a\ge 1,\qquad 3\nmid m.$$
Тем самым единственный простой делитель, которому разрешено остаться в знаменателе после сокращения, выделяется отдельно.
Поскольку \(\sigma\) мультипликативна на взаимно простых множителях, имеем
$$\sigma(n)=\sigma(3^a)\sigma(m).$$
Для чистой тройчной части получается
$$\sigma(3^a)=1+3+\cdots+3^a=\frac{3^{a+1}-1}{2}.$$
Обозначим
$$c_a=\frac{3^{a+1}-1}{2}.$$
Тогда
$$\frac{\sigma(n)}{n}=\frac{c_a\sigma(m)}{3^a m}.$$
Так как \(3^{a+1}-1\equiv -1 \pmod 3\), число \(c_a\) никогда не делится на \(3\).
Любой простой делитель \(p\neq 3\), который мог бы остаться в сокращенном знаменателе, приходит из \(m\), потому что \(m\) взаимно просто с \(3\). Значит, сокращенный знаменатель является степенью тройки тогда и только тогда, когда все простые множители \(m\) сокращаются числителем \(c_a\sigma(m)\).
Это дает главное условие делимости
$$m \mid c_a\sigma(m).$$
Если оно выполнено, вся не-тройчная часть знаменателя исчезает.
После сокращения нетройчной части в знаменателе может остаться только часть от \(3^a\). Поскольку \(3\nmid c_a\) и \(3\nmid m\), сокращение по тройке возможно только за счет \(\sigma(m)\). Следовательно, при условии \(m \mid c_a\sigma(m)\) сокращенный знаменатель равен
$$3^{a-v_3(\sigma(m))}.$$
Для triffle-числа этот знаменатель не должен стать равным \(1\). Нужно
$$a-v_3(\sigma(m))\ge 1,$$
то есть
$$v_3(\sigma(m))\le a-1.$$
Итак, \(n=3^a m\) является triffle тогда и только тогда, когда одновременно выполнены условия
$$m \mid c_a\sigma(m),\qquad v_3(\sigma(m))\le a-1.$$
Запишем
$$m=\prod_{j=1}^r p_j^{e_j},\qquad p_j\neq 3.$$
Тогда по мультипликативности
$$\sigma(m)=\prod_{j=1}^r \sigma(p_j^{e_j}),\qquad \sigma(p^e)=\frac{p^{e+1}-1}{p-1}.$$
Следовательно,
$$\frac{c_a\sigma(m)}{m}=c_a\prod_{j=1}^r \frac{\sigma(p_j^{e_j})}{p_j^{e_j}}.$$
Именно эта формула лежит в основе поиска. Алгоритм стартует с \(m=1\), затем добавляет новую простую степень \(p^e\), обновляет сокращенную дробь и увеличивает \(v_3(\sigma(m))\) на величину \(v_3(\sigma(p^e))\). Если новое \(m\) уже превышает предел текущего слоя или нарушает ограничение по \(3\)-адической оценке, ветвь немедленно отсекается.
Для каждого \(a\ge 1\) при \(3^a\le N\) определим
$$\mathcal{M}_a(N)=\left\{m\le \frac{N}{3^a}: 3\nmid m,\ m\mid c_a\sigma(m),\ v_3(\sigma(m))\le a-1\right\}.$$
Тогда искомая сумма имеет вид
$$\boxed{T(N)=\sum_{\substack{a\ge 1\\3^a\le N}} 3^a\sum_{m\in\mathcal{M}_a(N)} m.}$$
Каждое значение \(a\) задает отдельный независимый слой, поэтому реализации вычисляют их раздельно, а потом складывают.
Возьмем \(n=84=3^1\cdot 28\). Здесь \(a=1\), \(m=28\), и
$$c_1=\frac{3^2-1}{2}=4,\qquad \sigma(28)=56.$$
Тогда
$$\frac{c_1\sigma(m)}{m}=\frac{4\cdot 56}{28}=8,$$
то есть все простые множители знаменателя, кроме \(3\), сокращаются. Кроме того,
$$v_3(\sigma(28))=v_3(56)=0\le 1-1.$$
Следовательно, сокращенный знаменатель равен \(3^{1-0}=3\), и действительно
$$\frac{\sigma(84)}{84}=\frac{4\cdot 56}{84}=\frac{8}{3}.$$
Значит, \(84\) является triffle-числом. Маленькая контрольная сумма
$$T(100)=3+9+12+27+54+81+84=270$$
в точности совпадает со значением, проверяемым в реализациях.
Реализации на C++, Python и Java перебирают все \(a\), для которых \(3^a\le N\). Для каждого слоя они вычисляют границу \(\lfloor N/3^a\rfloor\) и коэффициент \(c_a\), после чего запускают поиск в глубину из состояния \(m=1\).
В состоянии поиска хранятся текущее \(m\), сокращенная дробь для \(c_a\sigma(m)/m\), текущее значение \(v_3(\sigma(m))\) и текущее значение \(\sigma(m)\). Когда добавляется новая простая степень \(p^e\) с \(p\neq 3\), реализация умножает на \(\sigma(p^e)/p^e\), немедленно сокращает общие множители и продолжает рекурсию только в том случае, если новое \(m\) не превысило предел слоя и оценка \(v_3(\sigma(m))\le a-1\) все еще выполняется.
Чтобы сдерживать ветвление, следующие кандидаты на простые числа берутся из простых делителей текущего сокращенного числителя, причем число \(2\) всегда добавляется как дешевый запасной вариант. Состояние принимается тогда и только тогда, когда сокращенная дробь имеет знаменатель \(1\): это означает, что все нетройчные знаменатели уже исчезли. После этого допустимые значения \(m\) суммируются, умножаются на \(3^a\) и добавляются к окончательному ответу.
Для факторизации 64-битных чисел используются детерминированный тест Миллера-Рабина и алгоритм Полларда-Rho. Поскольку слои независимы, их можно считать параллельно. Значения \(T(100)=270\) и \(T(10^6)=26089287\) служат дополнительными проверками корректности.
Простой замкнутой формулы для времени работы здесь нет, потому что все определяется тем, насколько сильно условия делимости и ограничение по \(3\)-адической оценке прореживают дерево поиска. Практически это можно описать так:
$$\text{time} \approx \text{visited DFS states} \times \text{average 64-bit factorization cost}.$$
Память в основном уходит на стек рекурсии, множество уже посещенных значений \(m\) в пределах слоя и кэш факторизаций. На практике метод работает быстро именно потому, что большинство ветвей отсеивается рано, а разные слои по степеням \(3\) полностью независимы.
لتكن \(\sigma(n)\) هي مجموع القواسم الموجبة للعدد \(n\). يسمى العدد الصحيح الموجب \(n\) عددًا من نوع triffle إذا كانت الكسرة \(\sigma(n)/n\) بعد الاختزال التام ذات مقام من الصورة \(3^k\) حيث \(k\ge 1\). أي بعد حذف كل العوامل المشتركة بين \(\sigma(n)\) و\(n\)، لا يبقى في المقام إلا قوة موجبة للعدد \(3\).
إذا رمزنا إلى مجموعة أعداد triffle بالرمز \(\mathcal{T}\)، فالمطلوب هو حساب
$$T(N)=\sum_{\substack{n\le N \\ n\in \mathcal{T}}} n.$$
تنفيذات ++C وPython وJava لا تفحص كل عدد حتى \(N\) مباشرة. بدلًا من ذلك تفصل قوة \(3\) الدقيقة داخل \(n\)، ثم تعيد كتابة شرط triffle على شكل شروط قسمة مرتبطة بـ \(\sigma(m)\)، ثم تبحث فقط في الفروع الضربية التي ما زالت قادرة على تحقيق تلك الشروط.
أي عدد triffle لا بد أن يكون قابلًا للقسمة على \(3\)، ولذلك نكتبه بصورة وحيدة على الشكل
$$n=3^a m,\qquad a\ge 1,\qquad 3\nmid m.$$
وبهذه الكتابة نعزل العدد الأولي الوحيد المسموح له بالبقاء في المقام بعد الاختزال، وهو \(3\).
بما أن \(\sigma\) دالة ضربّية على العوامل المتباينة أوليًا، فإن
$$\sigma(n)=\sigma(3^a)\sigma(m).$$
ومجموع قواسم الجزء الخاص بـ \(3\) فقط هو
$$\sigma(3^a)=1+3+\cdots+3^a=\frac{3^{a+1}-1}{2}.$$
لنعرّف
$$c_a=\frac{3^{a+1}-1}{2}.$$
عندئذ يصبح
$$\frac{\sigma(n)}{n}=\frac{c_a\sigma(m)}{3^a m}.$$
وبما أن \(3^{a+1}-1\equiv -1 \pmod 3\)، فإن \(c_a\) لا يقبل القسمة على \(3\) أبدًا.
كل عدد أولي \(p\neq 3\) قد يبقى في المقام المختزل لا بد أن يأتي من \(m\)، لأن \(m\) غير قابل للقسمة على \(3\). لذلك يكون المقام النهائي قوة للعدد \(3\) بالضبط عندما تُختزل كل العوامل الأولية الموجودة في \(m\) مع البسط \(c_a\sigma(m)\).
وهذا يعطينا شرط القسمة الأساسي:
$$m \mid c_a\sigma(m).$$
إذا تحقق هذا الشرط، تختفي كل أجزاء المقام التي لا تنتمي إلى قوى \(3\).
بعد اختزال الجزء غير الثلاثي من المقام، لا يمكن أن يبقى إلا جزء من \(3^a\). وبما أن \(3\nmid c_a\) و\(3\nmid m\)، فإن الاختزال مع \(3^a\) لا يأتي إلا من \(\sigma(m)\). لذلك يصبح المقام المختزل
$$3^{a-v_3(\sigma(m))}.$$
ولكي يكون العدد triffle، لا يجوز أن يصبح هذا المقام مساويًا لـ \(1\). إذن نحتاج إلى
$$a-v_3(\sigma(m))\ge 1,$$
أو بصورة مكافئة
$$v_3(\sigma(m))\le a-1.$$
إذن يكون \(n=3^a m\) عددًا من نوع triffle إذا وفقط إذا تحقق الشرطان
$$m \mid c_a\sigma(m),\qquad v_3(\sigma(m))\le a-1.$$
نكتب
$$m=\prod_{j=1}^r p_j^{e_j},\qquad p_j\neq 3.$$
وبالاعتماد على الضربية نحصل على
$$\sigma(m)=\prod_{j=1}^r \sigma(p_j^{e_j}),\qquad \sigma(p^e)=\frac{p^{e+1}-1}{p-1}.$$
ومن ثم
$$\frac{c_a\sigma(m)}{m}=c_a\prod_{j=1}^r \frac{\sigma(p_j^{e_j})}{p_j^{e_j}}.$$
هذه هي الصيغة التي يعتمد عليها البحث. يبدأ التنفيذ من \(m=1\)، ثم يضيف قوة أولية جديدة \(p^e\)، ويحدّث الكسر المختزل، ويزيد كذلك \(v_3(\sigma(m))\) بمقدار \(v_3(\sigma(p^e))\). وكل فرع يتجاوز حد الطبقة أو يخالف القيد \(v_3(\sigma(m))\le a-1\) يُقص فورًا.
لكل \(a\ge 1\) يحقق \(3^a\le N\)، نعرّف المجموعة
$$\mathcal{M}_a(N)=\left\{m\le \frac{N}{3^a}: 3\nmid m,\ m\mid c_a\sigma(m),\ v_3(\sigma(m))\le a-1\right\}.$$
عندها تصبح الدالة المطلوبة
$$\boxed{T(N)=\sum_{\substack{a\ge 1\\3^a\le N}} 3^a\sum_{m\in\mathcal{M}_a(N)} m.}$$
كل قيمة لـ \(a\) تنتج طبقة بحث مستقلة تمامًا، ولهذا تستطيع التنفيذات حساب هذه الطبقات منفصلة ثم جمعها في النهاية.
لنأخذ \(n=84=3^1\cdot 28\). هنا \(a=1\)، و\(m=28\)، ولدينا
$$c_1=\frac{3^2-1}{2}=4,\qquad \sigma(28)=56.$$
إذن
$$\frac{c_1\sigma(m)}{m}=\frac{4\cdot 56}{28}=8,$$
وبذلك تختفي كل عوامل المقام غير المرتبطة بالعدد \(3\). كذلك
$$v_3(\sigma(28))=v_3(56)=0\le 1-1.$$
إذن المقام المختزل هو \(3^{1-0}=3\)، ونجد فعلًا أن
$$\frac{\sigma(84)}{84}=\frac{4\cdot 56}{84}=\frac{8}{3}.$$
لذلك فإن \(84\) عدد triffle. كما أن نقطة التحقق الصغيرة
$$T(100)=3+9+12+27+54+81+84=270$$
تطابق تمامًا القيمة التي تتحقق منها التنفيذات.
تنفيذات ++C وPython وJava تمر على كل \(a\) يحقق \(3^a\le N\). في كل طبقة تحسب الحد الأعلى \(\lfloor N/3^a\rfloor\) والعامل \(c_a\)، ثم تبدأ بحثًا عمقيًا من الحالة \(m=1\).
حالة البحث تحتفظ بالقيمة الحالية لـ \(m\)، وبالكسر المختزل الذي يمثل \(c_a\sigma(m)/m\)، وبالقيمة الحالية لـ \(v_3(\sigma(m))\)، وكذلك بمجموع القواسم الحالي \(\sigma(m)\). عند إضافة قوة أولية جديدة \(p^e\) حيث \(p\neq 3\)، تضرب التنفيذات في \(\sigma(p^e)/p^e\)، وتختزل العوامل المشتركة فورًا، ثم تواصل التعمق فقط إذا بقيت القيمة الجديدة لـ \(m\) ضمن حد الطبقة، وإذا ظل الشرط \(v_3(\sigma(m))\le a-1\) محققًا.
ولتقليل عدد الفروع، تُختار الأعداد الأولية المرشحة التالية من العوامل الأولية في البسط المختزل الحالي، مع إضافة \(2\) دائمًا كخيار احتياطي رخيص. وتُقبل الحالة عندما يصبح مقام الكسر المختزل مساويًا لـ \(1\)، لأن هذا يعني أن كل عوامل المقام غير الثلاثية قد اختفت بالفعل. بعد ذلك تُجمع قيم \(m\) المقبولة داخل الطبقة، ثم تُضرب في \(3^a\) وتُضاف إلى النتيجة النهائية.
ولأجل تحليل الأعداد حتى 64-بت، تستخدم التنفيذات اختبار ميلر-رابين الحتمي لاختبار الأولية مع خوارزمية Pollard-Rho للتفكيك. وبما أن الطبقات مستقلة، يمكن أيضًا تشغيلها بالتوازي. كما تُستخدم القيمتان \(T(100)=270\) و\(T(10^6)=26089287\) كنقاط تحقق من صحة التنفيذ.
لا توجد صيغة مغلقة بسيطة لزمن التنفيذ، لأن الزمن الفعلي يعتمد على مدى نجاح شروط القسمة وقيد التقييم \(3\)-الأدي في تقليم شجرة البحث. والوصف العملي هو
$$\text{time} \approx \text{visited DFS states} \times \text{average 64-bit factorization cost}.$$
أما الذاكرة فتذهب أساسًا إلى مسار الاستدعاء العودي، ومجموعة قيم \(m\) التي زِيرت بالفعل داخل كل طبقة، وذاكرة التخزين المؤقت لنتائج التحليل إلى عوامل. ويكون الأسلوب عمليًا لأن معظم الفروع تُحذف مبكرًا، ولأن طبقات قوى \(3\) مستقلة تمامًا عن بعضها.