Detailed mathematical approach

Problem Summary

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

Mathematical Approach

The search is built around the fixed prime set \(P\) above and around the coprimality of consecutive integers.

Step 1: Split the triangular number by parity

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

Step 2: Turn smooth triangular numbers into smooth neighbors

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.

Step 3: Enumerate every possible smooth core \(x\)

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.

Step 4: Test the two neighbors \(2x-1\) and \(2x+1\)

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.

Worked Example

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

Step 5: Why the enumeration matches the required sum

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.

How the Code Works

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.

Complexity Analysis

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.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=581
2. Smooth number: Wikipedia — Smooth number
3. Triangular number: Wikipedia — Triangular number
4. Coprime integers: Wikipedia — Coprime integers
5. Fundamental theorem of arithmetic: Wikipedia — Fundamental theorem of arithmetic