Detailed mathematical approach

Problem Summary

An Alexandrian integer is a positive integer obtained from an integer triple satisfying

$\frac{1}{x}+\frac{1}{y}+\frac{1}{z}=\frac{1}{xyz}.$

For positive Alexandrian values one may choose the generating triple with exactly one negative entry, and the reported number is \(A=\lvert xyz\rvert\). Problem 221 asks for the \(150000\)-th term when all such positive integers are listed in increasing order.

The crucial point is that the search is not over arbitrary triples. The reciprocal identity collapses to a rigid divisor condition, so every valid Alexandrian integer comes from factoring a number of the form \(p^2+1\). That is the mathematical reason the implementations can solve the problem without brute-forcing three independent variables.

Mathematical Approach

The derivation used by the implementations is a complete parameterization of the Alexandrian integers that can appear in the ordered sequence.

Rewriting the reciprocal identity

Take a valid triple in the form \((-p,q,r)\) with \(p,q,r>0\). Substituting it into the defining identity gives

$-\frac{1}{p}+\frac{1}{q}+\frac{1}{r}=\frac{1}{(-p)qr}=-\frac{1}{pqr}.$

Multiplying by \(pqr\) removes the denominators and leaves the Diophantine equation

$qr-pq-pr=1.$

So the reciprocal statement is equivalent to a very structured bilinear equation in the three integers.

From a Diophantine equation to divisor pairs

Add \(p^2\) to both sides of the previous relation:

$qr-pq-pr+p^2=p^2+1.$

The left-hand side factors immediately:

$(q-p)(r-p)=p^2+1.$

Now set

$d=q-p,\qquad e=r-p.$

Then \(de=p^2+1\). Moreover \(d\) and \(e\) must be positive. If, for example, \(q\le p\), then \(qr-pq-pr\le pr-pq-pr=-pq\lt 0\), contradicting \(qr-pq-pr=1\). Therefore every valid triple is of the form

$(-p,\;p+d,\;p+e)\qquad\text{with}\qquad de=p^2+1.$

The corresponding Alexandrian integer is

$A=\lvert (-p)(p+d)(p+e)\rvert=p(p+d)(p+e).$

The converse is just as important: if \(p\ge 1\) and \(d,e\) are positive divisors with \(de=p^2+1\), then \((-p,p+d,p+e)\) satisfies the defining identity. So this is not merely a source of examples; it is the full classification exploited by the code.

Why only divisors up to \(\sqrt{p^2+1}\) are needed

Once \(p\) is fixed, the only freedom is the divisor pair \((d,e)\) of \(p^2+1\). Swapping the two factors does not change the product, because

$p(p+d)(p+e)=p(p+e)(p+d).$

Hence it is enough to enumerate divisors \(d\le \sqrt{p^2+1}\) and recover the partner \(e=(p^2+1)/d\). This removes the trivial mirror duplication coming from \((d,e)\) and \((e,d)\).

Worked example: \(p=3\)

For \(p=3\) we have

$p^2+1=10.$

The divisor pairs are \((1,10)\) and \((2,5)\). They produce the triples

$(-3,4,13)\qquad\text{and}\qquad(-3,5,8),$

so the corresponding Alexandrian integers are

$3\cdot 4\cdot 13=156,\qquad 3\cdot 5\cdot 8=120.$

Indeed,

$-\frac{1}{3}+\frac{1}{4}+\frac{1}{13}=-\frac{1}{156},\qquad -\frac{1}{3}+\frac{1}{5}+\frac{1}{8}=-\frac{1}{120}.$

This example explains two implementation choices. A single value of \(p\) can generate several Alexandrian integers, and those values do not arrive in globally sorted order. The search therefore streams candidates into a structure that keeps only the smallest values seen so far.

A lower bound that makes termination safe

For every future parameter \(p'\) and every admissible divisor pair, we always have \(d\ge 1\) and \(e\ge 1\). Therefore every unseen candidate obeys

$A'=p'(p'+d)(p'+e)\ge p'(p'+1)^2.$

After all candidates for a given \(p\) have been processed, every later parameter \(p+1,p+2,\dots\) satisfies

$A'\ge (p+1)(p+2)^2.$

If the container holding the current smallest \(k\) candidates is already full and this lower bound is larger than its maximum element, then no future value can enter the smallest \(k\). At that point the search may stop, and the current maximum is exactly the \(k\)-th Alexandrian integer.

How the Code Works

The C++, Python, and Java implementations iterate upward over \(p=1,2,3,\dots\). For each \(p\), they form \(n=p^2+1\), enlarge an incremental prime table just enough to factor \(n\), and then recursively generate all divisors \(d\le \sqrt{n}\). Each such divisor determines the complementary divisor \(e=n/d\) and therefore one candidate \(A=p(p+d)(p+e)\).

Instead of storing every candidate ever seen, the implementations maintain a max-heap of fixed size \(k\). While that heap is not yet full, every new unique candidate is inserted. Once it is full, only candidates smaller than the current heap maximum can matter; larger values are discarded immediately. A companion hash set tracks the values currently present in the heap so that equal Alexandrian integers are not counted twice.

The three versions differ mainly in numeric representation, not in mathematics. The C++ implementation uses 128-bit arithmetic for the products, the Python implementation relies on arbitrary-precision integers, and the Java implementation uses big integers. After each completed value of \(p\), they apply the lower-bound test above. When that test proves that no later \(p\) can improve the heap, the current heap maximum is returned.

Complexity Analysis

Let \(P\) be the last parameter examined before the stopping criterion succeeds, let \(\tau(n)\) be the divisor-counting function, and let \(\pi(P)\) denote the number of stored primes up to \(P\). For each \(p\le P\), the algorithm factors \(p^2+1\) by trial division through the current prime table and then enumerates the relevant divisors. A faithful high-level bound is

$T(P)=O\!\left(\sum_{p=1}^{P}\bigl(\pi(p)+\tau(p^2+1)\log k\bigr)\right).$

The \(\pi(p)\) term reflects prime testing up to roughly \(\sqrt{p^2+1}\), and the \(\log k\) factor comes from possible heap updates when a candidate is admitted into the current best \(k\).

Memory usage is

$O\bigl(k+\pi(P)+\max_{p\le P}\tau(p^2+1)\bigr).$

The dominant stored objects are the bounded heap, the hash set of active values, the growing prime table, and a temporary divisor buffer for the current factorization. The whole method is efficient because it replaces a three-variable search with a one-parameter scan, divisor generation, and aggressive early stopping.

Footnotes and References

1. Project Euler problem page: Problem 221 - Alexandrian Integers
2. Alexandrian integers: Wikipedia - Alexandrian integer
3. Divisors and divisor counting: Wikipedia - Divisor
4. Enumerating divisors from a prime factorization: cp-algorithms - Number of divisors / sum of divisors
5. Diophantine equations: Wikipedia - Diophantine equation