Detailed mathematical approach

Problem Summary

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.

Mathematical Approach

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.

Step 1: Separate the Power of Three

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\).

Step 2: Cancel Every Denominator Prime Other Than \(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.

Step 3: Leave a Positive Power of \(3\) Behind

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.$

Step 4: Build \(m\) Prime Power by Prime Power

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.

Step 5: Sum Independent \(3\)-Layers

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.

Worked Example: Why \(84\) Is Triffle

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.

How the Code Works

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.

Complexity Analysis

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.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=699
2. Divisor function: Wikipedia - Divisor function
3. \(p\)-adic valuation: Wikipedia - p-adic valuation
4. Pollard-Rho algorithm: Wikipedia - Pollard-Rho algorithm
5. Miller-Rabin primality test: Wikipedia - Miller-Rabin primality test