Detailed mathematical approach

Problem Summary

A repunit in base \(b\) is a number whose digits are all 1, such as \(111_b\) or \(11111_b\). Problem 346 asks for the sum of all strong repunits below a limit \(L\). A positive integer is called strong if it is a repunit in at least two bases \(b \gt 1\). The published sample below \(50\) is \(\{1,7,13,15,21,31,40,43\}\), so the goal is to generate exactly those values without scanning every integer below the limit.

Mathematical Approach

For base \(b \ge 2\) and length \(k \ge 1\), the repunit value is

$R_{b,k}=1+b+b^2+\cdots+b^{k-1}=\frac{b^k-1}{b-1}.$

This is the finite geometric-series formula, and it shows immediately that for fixed \(b\), repunits grow strictly as \(k\) increases.

Why Only Lengths \(k \ge 3\) Matter

Every integer \(n \gt 2\) already has the trivial two-digit representation \(11_{n-1}\), because

$11_{n-1}=(n-1)+1=n.$

So a number is a strong repunit precisely when it has at least one additional repunit representation with \(k \ge 3\). That lets us skip all length-2 cases and enumerate only nontrivial representations. The value \(1\) is added separately because Project Euler explicitly includes it in the sample set of strong repunits.

Conversely, if \(n \gt 1\) is a strong repunit, then by definition it has some representation \(n=R_{b,k}\) with \(b \gt 1\) and \(k \ge 3\), so direct generation of all such pairs \((b,k)\) is complete.

Bounding the Base

For a fixed base \(b\), the smallest nontrivial repunit is the length-3 value

$R_{b,3}=1+b+b^2.$

If even this value is not below the limit, then every longer repunit in the same base is larger and can be ignored. Therefore we only need bases satisfying

$1+b+b^2 \lt L.$

Equivalently, \(b \le \left\lfloor\frac{\sqrt{4L-3}-1}{2}\right\rfloor\). In practice the code simply tests the inequality directly, which keeps the loop simple and safe.

Recurrence Used by the Code

After computing \(R_{b,3}\), the next repunit in the same base can be obtained without recomputing powers:

$R_{b,k+1}=bR_{b,k}+1.$

This follows immediately from the definition, since

$b(1+b+\cdots+b^{k-1})+1=1+b+\cdots+b^k.$

Operationally, multiplying by \(b\) shifts the base-\(b\) digits left, and adding 1 appends another trailing digit 1. This recurrence is the key reason the algorithm is fast.

Worked Example: \(L = 50\)

The admissible bases are those with \(1+b+b^2 \lt 50\), namely \(b=2,3,4,5,6\).

Base \(2\) gives \(7,15,31\). Base \(3\) gives \(13,40\). Base \(4\) gives \(21\). Base \(5\) gives \(31\) again. Base \(6\) gives \(43\). For \(b=7\), we already have \(1+7+49=57 \ge 50\), so the enumeration stops.

After deduplication and after inserting \(1\), the set is

$\{1,7,13,15,21,31,40,43\},$

exactly the sample from the statement. The duplicate \(31\) is a useful sanity check: \(31=11111_2=111_5\).

How the Code Works

The implementation first inserts \(1\) when \(L \gt 1\). Then it loops over bases starting from \(2\). The C++ and Java versions defensively stop if \(b^2\) could overflow, while the main structural stop condition is \(1+b+b^2 \ge L\).

For each base, the code starts with \(R_{b,3}\), repeatedly applies repunit = repunit * base + 1, and records every value below the limit. Before the multiplication, it checks whether repunit > (L-1)/base; if so, the next recurrence step would exceed the safe range, so the inner loop ends.

Because different \((b,k)\) pairs can yield the same number, the generated values must be deduplicated. The C++ version pushes candidates into a vector and later uses sort plus unique; the Python and Java versions use sets during generation and then sort the final collection before summing. The C++ file also includes checkpoints for the published examples: the list below \(50\) and the sum \(15864\) below \(1000\).

Complexity Analysis

The outer loop runs for only \(O(\sqrt{L})\) bases. For each fixed base \(b\), the recurrence produces about \(O(\log_b L)\) repunits before crossing the limit. Hence the total work is

$\sum_{b=2}^{O(\sqrt{L})} O(\log_b L),$

which is far smaller than testing all integers below \(L\). Memory usage is \(O(M)\), where \(M\) is the number of generated candidate values before or during deduplication.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=346
2. Repunit numbers: Wikipedia - Repunit
3. Geometric series: Wikipedia - Geometric series
4. Positional notation and base representations: Wikipedia - Positional notation