Problem 346: Strong Repunits

Project Euler Problem 346 Solution

EulerSolve provides an optimized solution for Project Euler Problem 346, Strong Repunits, with C++, Python, Java, and a step-by-step mathematical explanation.

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

Detailed mathematical approach

Problem Summary

A repunit in base $b$ is a positive integer whose base-$b$ digits are all $1$. The number $7$ is one twice over: $7=111_2$ and $7=11_6$. A positive integer is a strong repunit when it is a repunit in at least two bases $b\gt1$, so $7$ is strong. The statement gives two checkpoints: the $8$ strong repunits below $50$ are $\{1,7,13,15,21,31,40,43\}$, and those below $1000$ add up to $15864$. We must find the sum of all strong repunits below $10^{12}$. ^[1]

The whole solution in one sentence: every integer $n\ge3$ is already the two-digit repunit $11$ in base $n-1$, so a number above $1$ is strong exactly when it is also a repunit with three or more digits, and those are rare enough — about $\sqrt{L}$ below a limit $L$ — to be listed one by one, deduplicated and added up.

Mathematical Approach

1. Repunits in one base

Take $111_3=1+3+9=13$: each place is worth three times the place to its right. In general write $R_{b,k}$ for the number whose base-$b$ form is $k$ digits $1$. Its place values form a geometric sum, each term the previous one times $b$, so multiplying the sum by $b$ and subtracting it cancels the shared powers and leaves $(b-1)R_{b,k}=b^k-1$: ^[3]

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

This is the standard base-$b$ repunit. ^[2] Conversely, a string of $k$ digits $1$ is a legitimate base-$b$ numeral whenever $b\ge2$, since then each digit satisfies $1\le b-1$ and the leading digit is not $0$; and repeated division by $b$ peels the digits off one at a time, so a number has at most one base-$b$ numeral. For $b\ge2$, "$n$ is a repunit in base $b$" therefore means exactly $n=R_{b,k}$ for some $k\ge1$.

Base $2$ gives $R_{2,k}=2^k-1$, that is $1,3,7,15,31,63,\dots$, and base $3$ gives $1,4,13,40,121,\dots$. Raising $k$ adds the positive term $b^k$, and raising $b$ enlarges every positive power in the sum, so for $k\ge2$ the values grow strictly in both parameters.

2. Three sorts of representation

The length $k$ splits the problem into three cases.

$k=1$: $R_{b,1}=1$ in every base, so the single number $1$ is a repunit in all bases at once.
$k=2$: $R_{b,2}=b+1$. Read backwards, an integer $n$ is a two-digit repunit in exactly one base, $b=n-1$, and that base is allowed as soon as $n\ge3$.
$k\ge3$: here $R_{b,k}\ge R_{b,3}=1+b+b^2\ge7$. These carry the information.

3. Which numbers are strong

Claim. For $L\ge2$, the strong repunits below $L$ are the number $1$ together with the numbers $R_{b,k}\lt L$ for $b\ge2$ and $k\ge3$.

Proof. First, $1=R_{b,1}$ for every $b\ge2$, so $1$ is a repunit in infinitely many bases and is strong, as the statement's list confirms. Next take $n=R_{b,k}$ with $b\ge2$ and $k\ge3$, so $n\ge7$. Then $n$ is also the two-digit repunit $11$ in base $n-1$, an allowed base because $n-1\ge6$. The two bases differ: if $b=n-1$ we would get $n\ge1+b+b^2=n+(n-1)^2\gt n$, which is false. So $n$ is strong. Conversely let $n\gt1$ be strong. Each of its representations is of one of the three sorts above; $k=1$ yields only $n=1$, excluded here, and $k=2$ yields the single base $n-1$. Two different bases are impossible unless some representation has $k\ge3$. Q.E.D.

This also explains the first gaps: $2$ is a repunit in no base at all, since $k=1$ gives $1$, $k\ge3$ gives at least $7$ and $k=2$ would need the forbidden base $b=1$; and $3=11_2$ is a repunit only in base $2$. The numbers with a representation of length at least $3$ form a known sequence beginning $7,13,15,21,31,40,43,57$. ^[4]

4. How far the search goes

Only lengths $k\ge3$ must be generated, and the smallest such value in base $b$ is $R_{b,3}=1+b+b^2$. If $1+b+b^2\ge L$, base $b$ contributes nothing, and no larger base does either, since $R_{b,3}$ grows with $b$. The useful bases are those with $1+b+b^2\lt L$, that is

$$b\lt\frac{\sqrt{4L-3}-1}{2}\approx\sqrt{L}.$$

For $L=10^{12}$ the right-hand side is $999999.49999\dots$, so the bases are $2,\dots,999999$: base $999999$ still contributes $R_{999999,3}=999999000001$, while base $10^6$ would start at $1000001000001$. The longest repunit comes from the smallest base, as $R_{2,39}=549755813887$ is below $10^{12}$ and $R_{2,40}=1099511627775$ is not, so no length beyond $39$ occurs.

5. Appending a digit

Within one base the next repunit need not be rebuilt from scratch:

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

Multiplying by $b$ shifts the base-$b$ digits one place left, and adding $1$ writes a further digit $1$ into the freed place; in formulas, $b(1+\cdots+b^{k-1})+1=1+\cdots+b^{k}$. One multiplication and one addition thus walk through a base from $R_{b,3}$ on: in base $2$ this reads $7\to15\to31\to63$.

6. Worked example: the eight numbers below $50$

Let $L=50$. The admissible bases are those with $1+b+b^2\lt50$, namely $b=2,3,4,5,6$, because $b=7$ already gives $1+7+49=57$. Walking each base with the recurrence gives:

base $2$: $7,15,31$, then $63$ is too large;
base $3$: $13,40$, then $121$;
base $4$: $21$, then $85$;
base $5$: $31$, then $156$;
base $6$: $43$, then $259$.

The value $31$ is produced twice, as $11111_2$ and as $111_5$, and must be counted once. With the special value $1$ this leaves $\{1,7,13,15,21,31,40,43\}$: eight numbers of sum $171$, exactly the statement's list. The same walk below $1000$ yields $47$ numbers of sum $15864$, the second checkpoint.

7. How often is a value produced twice?

A number with two representations of length at least $3$ satisfies

$$\frac{x^m-1}{x-1}=\frac{y^n-1}{y-1}$$

with $x\gt y\gt1$ and $m,n\ge3$. This is the Goormaghtigh equation; the conjecture that its only solutions are $31=11111_2=111_5$ and $8191=1111111111111_2=111_{90}$ is still open. ^[5] A search has found no further solution below $2^{44}=17592186044416$, ^[4] so below $10^{12}$ the enumeration meets exactly two duplicates. The algorithm does not rely on the conjecture: discarding repeated values is correct whatever happens higher up.

8. The size of the list and of the sum

For a fixed length $k$ the condition $R_{b,k}\lt L$ is roughly $b^{k-1}\lt L$, so about $L^{1/(k-1)}$ bases qualify and the number of pairs $(b,k)$ is close to $\sqrt{L}+L^{1/3}+L^{1/4}+\cdots$. The first term dominates: length $3$ alone gives $\sqrt{L}+O(1)$ pairs by Section 4, while $k\ge4$ forces $b^3\le R_{b,k}\lt L$, and $R_{b,k}\ge2^k-1$ leaves only $O(\log L)$ lengths, so all longer lengths together contribute $O(L^{1/3}\log L)$ pairs. At $L=10^{12}$ the counts are $999998$ pairs of length $3$, then $9998$, $998$, $249$, $98$ and $50$, down to one pair for each length from $26$ to $39$: $1011530$ in all. Two are the duplicates of Section 7, leaving $1011528$ distinct values, so with the number $1$ there are $1011529$ strong repunits below $10^{12}$.

Each is below $10^{12}$, so the sum is below $1011529\cdot10^{12}$, hence below $1.02\cdot10^{18}$. As $2^{63}-1$ is about $9.22\cdot10^{18}$, a signed $64$-bit accumulator keeps a factor of roughly $9$ in reserve.

How the Code Works

One function returns the sorted strong repunits below a limit; in C++ it is strong_repunits_below. ^[7] It stores the value $1$ when the limit exceeds $1$, the exceptional case of Section 3, then loops over base and stops once 1 + base + square >= limit — the rule of Section 4, as a plain inequality, so no square root is needed. An earlier guard, base > (max - 1) / base, would stop it before $b^2$ could overflow an unsigned $64$-bit integer, but never triggers at this limit.

For a fixed base, the inner loop starts at repunit $=1+b+b^2$ and repeats repunit = repunit * base + 1, the recurrence of Section 5, storing every value below the limit. Before each multiplication it tests repunit > (limit - 1) / base in integer arithmetic. Passing that test is equivalent, for $b\ge2$, to $rb+1\le L$, so the product never exceeds $L$ and cannot overflow; it breaks only when $rb+1\gt L$, and in the boundary case $rb+1=L$ the multiplication still runs, after which the while condition rejects the value — with $L=15$, $b=2$ and $r=7$ the update produces $15$ and stores nothing. The two tests together keep exactly the values below the limit.

Because one number can arise from two bases, the values must be deduplicated. C++ collects them in a std::vector, sorts it, then calls std::unique and erase; std::unique removes only consecutive equal elements, which is why the sort comes first. ^[6] Python inserts into a set and Java into a HashSet of Long, copied into an ArrayList and sorted: a hash set drops duplicates on insertion but keeps no order, so that sort only shapes the returned list.

solve adds the values up, in a u64 in C++, a long in Java and an arbitrary-precision integer in Python; Section 8 shows the fixed-width accumulators suffice. Only the C++ file is configurable and self-checking: it accepts --limit= and --skip-checkpoints, rejects a limit below $2$, and in run_checkpoints compares the list below $50$ with the statement's eight values and checks that solve(1000) is $15864$. Python and Java write $10^{12}$ into solve and carry no checks; Java guards the signed range with base > Long.MAX_VALUE / base.

Complexity and Verification

The outer loop examines about $\sqrt{L}$ bases, and at $L=10^{12}$ the inner body runs $1011530$ times: each run stores a candidate and evaluates the division guard, and those that pass it also multiply. Treating arithmetic on machine words as constant work, generation costs $\Theta(\sqrt{L})$ operations by the count of Section 8. Sorting the $1011531$ stored C++ values adds $O(\sqrt{L}\log L)$ comparisons, and Python and Java spend an expected $O(\sqrt{L})$ on hash-set insertions before sorting, so all three are $O(\sqrt{L}\log L)$ overall. Memory is $\Theta(\sqrt{L})$: the stored C++ values take $8$ bytes each, $8092248$ bytes in all, with a measured peak resident size of $18$ MB; Python's integer objects and Java's boxed values need more. A full run took $0.02$ seconds in C++, $0.31$ in Java and $0.47$ in Python on one desktop machine.

The following was verified by computation for this article.

The C++ checkpoints pass, and the three generators return identical lists at the limits $50$, $1000$, $10^4$, $10^6$ and $10^8$: the sums $171$, $15864$, $450740$, $372810163$ and $348635395606$ over $8$, $47$, $141$, $1172$ and $10671$ numbers. Only the C++ program takes a limit on the command line, so Python's strong_repunits_below and Java's strongRepunitsBelow were called from a small harness.
Two digit-inspecting tests agree, both counting $1$ as strong by its one-digit form. The first tries every base from $2$ to $n-1$ for each $n\ge2$, keeping $n$ when two bases give only digits $1$; it reproduces the generator's output for every limit up to $3000$ ($81$ numbers of sum $80094$), checking Section 3 case by case. The second inspects, for each $2\le n\lt10^7$, the bases $b\le\sqrt{n}$, adds the base $n-1$ when $n\ge3$ and again requires two bases, finding the same $3501$ numbers, of sum $11302817869$.
The guard of the inner loop loses nothing: removing it changes the generated set for no limit below $6000$, nor for $10^9$, $10^{12}$ or $2^{40}$.
The overflow guards leave room for the step after them: the last base C++ accepts is $4294967295$, where $1+b+b^2=18446744069414584321$ still fits in an unsigned $64$-bit integer, and Java's is $3037000499$, where $1+b+b^2$ likewise stays inside the signed range.
The accumulators need the separate bound of Section 8, which covers this limit and every smaller one; neither fixed-width version checks its additions. Java's long would overflow if its fixed limit were raised to $10^{13}$, and C++ already accepts --limit=100000000000000, where its unsigned sum wraps. Python's integers do not.

Footnotes and References

The references supply the background facts. The characterisation of Section 3, the bounds of Section 4, the counts of Section 8 and every number in the examples were derived and checked for this article.

Project Euler 346 — Strong Repunits. The official statement defines a strong repunit as a positive integer that is a repunit in at least two bases b > 1, lists the eight below 50 and the sum 15864 of those below 1000, and asks for the sum of all strong repunits below 10¹².
Wikipedia — Repunit. The base-b repunit of length n is 1 + b + ⋯ + b^(n−1) = (b^n − 1)/(b − 1), consisting of n copies of the digit 1 in base b.
Wikipedia — Geometric series gives the partial sum with ratio r ≠ 1 as a(1 − r^(n+1))/(1 − r), which for a = 1 yields the closed form of Section 1. Wikipedia — Positional notation gives the digit set {0, …, b − 1} of radix b and the place value of each digit.
OEIS A053696, "numbers that can be represented as a string of three or more 1's in a base >= 2", that is (b^n − 1)/(b − 1) with n > 2 and b > 1: 7, 13, 15, 21, 31, 40, 43, 57. With 1 these are the strong repunits. OEIS A119598 keeps 1 as an exceptional first term and lists after it those with more than one such representation, 31 and 8191; its comments record a search by R. Chandler finding no further term below 2⁴⁴ = 17592186044416.
Wikipedia — Goormaghtigh conjecture: the equation (x^m − 1)/(x − 1) = (y^n − 1)/(y − 1) with x > y > 1 and m, n > 2 should have only the solutions 31 = 111₅ = 11111₂ and 8191 = 111₉₀ = 1111111111111₂. Among the partial results listed is the theorem of Davenport, Lewis and Schinzel (1961) that fixed exponents leave finitely many solutions.
cppreference — std::unique coalesces consecutive equivalent elements and returns the new logical end, so sorting first is what brings all equal values together, and the unused tail is then erased. Java — HashSet gives constant-time insertion and lookup with a well-dispersing hash function and no iteration order, as does Python — set types, an unordered collection of distinct hashable objects.
C++ — Euler346.cpp. The linked immutable revision contains strong_repunits_below, solve, the argument parsing and run_checkpoints, and is the implementation record for this article; the independent tests above are not part of it.

Problem 346 source code

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <limits>
#include <string>
#include <vector>

namespace {

using u64 = std::uint64_t;

struct Options {
    u64 limit = 1'000'000'000'000ULL;
    bool run_checkpoints = true;
};

bool parse_u64_after_prefix(const std::string& arg, const std::string& prefix, u64& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    u64 parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        const u64 digit = static_cast<u64>(c - '0');
        if (parsed > (std::numeric_limits<u64>::max() - digit) / 10ULL) {
            return false;
        }
        parsed = parsed * 10ULL + digit;
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_u64_after_prefix(arg, "--limit=", options.limit)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.limit >= 2ULL;
}

std::vector<u64> strong_repunits_below(const u64 limit) {
    std::vector<u64> values;
    if (limit > 1ULL) {
        values.push_back(1ULL);
    }

    for (u64 base = 2ULL;; ++base) {
        if (base > (std::numeric_limits<u64>::max() - 1ULL) / base) {
            break;
        }
        const u64 square = base * base;
        if (1ULL + base + square >= limit) {
            break;
        }

        u64 repunit = 1ULL + base + square;  // Length 3.
        while (repunit < limit) {
            values.push_back(repunit);
            if (repunit > (limit - 1ULL) / base) {
                break;
            }
            repunit = repunit * base + 1ULL;
        }
    }

    std::sort(values.begin(), values.end());
    values.erase(std::unique(values.begin(), values.end()), values.end());
    return values;
}

u64 solve(const u64 limit) {
    const std::vector<u64> values = strong_repunits_below(limit);
    u64 sum = 0ULL;
    for (const u64 v : values) {
        sum += v;
    }
    return sum;
}

bool run_checkpoints() {
    const std::vector<u64> sample = strong_repunits_below(50ULL);
    const std::vector<u64> expected = {1ULL, 7ULL, 13ULL, 15ULL, 21ULL, 31ULL, 40ULL, 43ULL};
    if (sample != expected) {
        std::cerr << "Checkpoint failed for limit=50 strong repunits list" << '\n';
        return false;
    }
    if (solve(1000ULL) != 15864ULL) {
        std::cerr << "Checkpoint failed for limit=1000 sample sum" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }
    std::cout << solve(options.limit) << '\n';
    return 0;
}

Python

def strong_repunits_below(limit):
    values = set()
    if limit > 1:
        values.add(1)
        
    base = 2
    while True:
        square = base * base
        if 1 + base + square >= limit:
            break
            
        repunit = 1 + base + square
        while repunit < limit:
            values.add(repunit)
            if repunit > (limit - 1) // base:
                break
            repunit = repunit * base + 1
            
        base += 1
        
    return sorted(list(values))

def solve():
    limit = 1000000000000
    values = strong_repunits_below(limit)
    ans = sum(values)
    return str(ans)

if __name__ == '__main__':
    print(solve())

Java

import java.util.*;

public class Euler346 {

    static List<Long> strongRepunitsBelow(long limit) {
        Set<Long> values = new HashSet<>();
        if (limit > 1) {
            values.add(1L);
        }

        for (long base = 2;; base++) {
            // Stop if base * base could overflow or exceed limit structurally
            if (base > Long.MAX_VALUE / base)
                break; // Won't happen for 10^12

            long square = base * base;
            if (1 + base + square >= limit) {
                break;
            }

            long repunit = 1 + base + square;
            while (repunit < limit) {
                values.add(repunit);
                if (repunit > (limit - 1) / base) {
                    break;
                }
                repunit = repunit * base + 1;
            }
        }

        List<Long> sortedValues = new ArrayList<>(values);
        Collections.sort(sortedValues);
        return sortedValues;
    }

    public static String solve() {
        long limit = 1000000000000L;
        List<Long> values = strongRepunitsBelow(limit);
        long sum = 0;
        for (long v : values) {
            sum += v;
        }
        return String.valueOf(sum);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}