Project Euler Problem 346

Solution

Answer: 336108797689259276

1. Mathematical analysis

A repunit in base $b>1$ is a number of the form

$$111\ldots111_b$$

with only digit $1$'s.

If the repunit has $k$ digits, then its value is the geometric sum

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

We are asked for numbers that are repunits in at least two different bases.

Key observation

Every integer $n>2$ is automatically a repunit of length $2$:

$$n = 11_{n-1}.$$

Indeed,

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

So for a number to be a strong repunit, it suffices that it also has a repunit representation with at least 3 digits.

Thus we only need to generate numbers of the form

$$1+b+b^2+\cdots+b^{k-1}, \qquad k\ge 3,$$

below $10^{12}$, and take the union of all such values (plus $1$, which the problem explicitly counts as strong).

Bounding the search

We need

$$1+b+b^2 < 10^{12}$$

for the smallest allowed length $k=3$.

Since

$$b^2 < 10^{12},$$

we only need

$$b \le \sqrt{10^{12}} = 10^6.$$

For each base $b$, we repeatedly extend the repunit:

$$1+b+b^2,; 1+b+b^2+b^3,; \ldots$$

until exceeding $10^{12}$.

Because the same number may arise from different bases, we store results in a set.

2. Python implementation

LIMIT = 10**12

# 1 is explicitly counted as a strong repunit
strong_repunits = {1}

# Maximum base comes from the k=3 case: 1 + b + b^2 < LIMIT
max_base = int(LIMIT**0.5)

for b in range(2, max_base + 1):
    # Start with repunit length 3: 1 + b + b^2
    value = 1 + b + b * b
    power = b * b

    while value < LIMIT:
        strong_repunits.add(value)

        # Add next power of b to extend repunit length
        power *= b
        value += power

# Compute final sum
answer = sum(strong_repunits)

print(answer)

3. Code walkthrough

Initialization

LIMIT = 10**12
strong_repunits = {1}

We store strong repunits in a set to avoid duplicates.

The problem counts $1$, so we include it immediately.

Maximum base

max_base = int(LIMIT**0.5)

The shortest nontrivial repunit has length $3$:

$$1+b+b^2.$$

So $b^2 < 10^{12}$, giving $b \le 10^6$.

Generate repunits

for b in range(2, max_base + 1):

Try every possible base.

We begin with

value = 1 + b + b * b
power = b * b

which corresponds to the 3-digit repunit:

$$111_b = 1+b+b^2.$$

Then repeatedly extend:

power *= b
value += power

This produces

$$1111_b,;11111_b,\ldots$$

until exceeding the limit.

Remove duplicates automatically

strong_repunits.add(value)

Some numbers appear in multiple bases, e.g.

$$31 = 11111_2 = 111_5.$$

The set ensures we count each number only once.

Small-example verification

For LIMIT = 50, the set becomes:

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

matching the problem statement.

For LIMIT = 1000, the program returns:

$$15864$$

also matching the given check value.

4. Final verification

We include all repunits of length $\ge 3$.
Every integer $>2$ is already a 2-digit repunit in base $n-1$, so this exactly characterizes strong repunits.
Duplicate representations are removed via a set.
Verified against both provided examples ($<50$ and $<1000$).

Answer: 336108797689259276