Project Euler Problem 221

Solution

Answer: 1884161251122450

Let

$$A=pqr$$

and suppose

$$\frac1A=\frac1p+\frac1q+\frac1r.$$

We seek the $150000^\text{th}$ positive integer $A$ satisfying this condition.

---

Step 1 — Algebraic transformation

Starting from

$$\frac1{pqr}=\frac1p+\frac1q+\frac1r,$$

multiply both sides by $pqr$:

$$1=qr+pr+pq.$$

So Alexandrian integers correspond to integer triples satisfying

$$pq+pr+qr=1.$$

We now parameterize all solutions.

---

Step 2 — Deriving a useful parametrization

Solve for $r$:

$$r(p+q) = 1-pq$$

so

$$r=\frac{1-pq}{p+q}.$$

We want integer solutions.

Following the standard Project Euler approach, let

$$p=a,\qquad q=-(a+d),$$

where $a>0$ and $d>0$.

Then

$$p+q=a-(a+d)=-d,$$

and

$$1-pq =1-a(-(a+d)) =1+a(a+d) =a^2+ad+1.$$

Therefore

$$r=\frac{a^2+ad+1}{-d} =-\left(a+\frac{a^2+1}{d}\right).$$

Thus $r$ is an integer exactly when

$$d \mid (a^2+1).$$

The Alexandrian integer becomes

$$A = pqr = a(a+d)\left(a+\frac{a^2+1}{d}\right).$$

Hence:

For every positive integer $a$ and every divisor $d\mid (a^2+1)$,

$$A=a(a+d)\left(a+\frac{a^2+1}{d}\right)$$

is an Alexandrian integer.

This generates all positive Alexandrian integers.

---

Step 3 — Checking the example

Take $a=5$.

Then

$$a^2+1=26.$$

Choose divisor $d=2$.

Then

$$p=5,\qquad q=-(5+2)=-7,$$

and

$$r=-\left(5+\frac{26}{2}\right)=-18.$$

Therefore

$$A=5\cdot(-7)\cdot(-18)=630,$$

matching the problem statement.

---

Step 4 — Efficient algorithm

We must find the $150000^\text{th}$ smallest distinct value.

Algorithm:

1. Loop over $a=1,2,3,\dots$
2. Compute $n=a^2+1$
3. Enumerate all divisors $d\mid n$
4. Generate

$$A=a(a+d)\left(a+\frac{n}{d}\right)$$ 5. Insert into a set 6. Sort all generated values 7. Take the $150000^\text{th}$

A bound around $a=150000$ is sufficient.

---

Python implementation

import math

LIMIT = 150000

# ------------------------------------------------------------
# Sieve of primes for fast factorization
# ------------------------------------------------------------
def prime_sieve(n):
    sieve = bytearray(b'\x01') * (n + 1)
    sieve[0:2] = b'\x00\x00'

    for i in range(2, int(n**0.5) + 1):
        if sieve[i]:
            sieve[i*i:n+1:i] = b'\x00' * (((n - i*i) // i) + 1)

    return [i for i, v in enumerate(sieve) if v]

primes = prime_sieve(500000)

# ------------------------------------------------------------
# Generate all divisors of n
# ------------------------------------------------------------
def divisors(n):
    factors = []
    temp = n

    for p in primes:
        if p * p > temp:
            break

        if temp % p == 0:
            e = 0
            while temp % p == 0:
                temp //= p
                e += 1
            factors.append((p, e))

    if temp > 1:
        factors.append((temp, 1))

    divs = [1]

    for p, e in factors:
        current = divs[:]
        mult = 1

        for _ in range(e):
            mult *= p
            for d in current:
                divs.append(d * mult)

    return divs

# ------------------------------------------------------------
# Generate Alexandrian integers
# ------------------------------------------------------------
alex = set()

MAX_A = 150000

for a in range(1, MAX_A + 1):
    n = a * a + 1

    for d in divisors(n):
        A = a * (a + d) * (a + n // d)
        alex.add(A)

# ------------------------------------------------------------
# Extract answer
# ------------------------------------------------------------
alex = sorted(alex)

print(alex[LIMIT - 1])

---

Code walkthrough

Prime sieve

prime_sieve(n)

Constructs all primes up to $500000$, enough to factor numbers of the form $a^2+1$.

---

Divisor generation

divisors(n)

Factors $n$ and recursively constructs all divisors from the prime powers.

---

Main generation loop

for a in range(1, MAX_A + 1):

For each $a$:

• compute $n=a^2+1$
• enumerate divisors $d\mid n$
• generate

$$A=a(a+d)\left(a+\frac{n}{d}\right)$$

• store in a set to avoid duplicates

---

Verification on small values

The generated ordered sequence begins:

$$6,\ 42,\ 120,\ 156,\ 420,\ 630,\dots$$

which matches the problem statement.

---

Final verification

The resulting value:

• is positive,
• appears in the generated Alexandrian sequence,
• and is exactly the $150000^\text{th}$ distinct element after sorting.

Therefore the required Alexandrian integer is:

Answer: 1884161251122450