## Diophantine Reciprocals

### September 19, 2014

Career Cup claims that Amazon asked this as an interview question; it is also Problem 108 at Project Euler:

In the following equation

x,yandnare positive integers: 1 /x+ 1y= 1 /n. Forn= 4 there are exactly three distinct solutions: 1/5 + 1/20 = 1/6 + 1/12 = 1/8 + 1/8 = 1/4. What is the least value ofnfor which the number of distinct solutions exceeds one thousand?

Your task is to solve Amazon’s question; you might also like to make a list of the *x*, *y* pairs that sum to a given *n*. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Here’s another way to solve this (taking the problem to be finding the smallest number whose square has at least 2000 divisors).

A number of the form (p1^a1)..(pn^an), for primes p1,…pn, has (a1+1)…(an+1) divisors and its square has (2a1+1)…(2an+1) divisors. For a given a1…an, which we can assume to be in non-increasing order, the smallest such number is where p1 = 2, p2 = 3 etc. Therefore by generating all such smallest numbers in order and checking the number of divisors, we will find the solution we seek. So, we need to generate all non-increasing sequences a1,a2,a3,… in order of (2^a1)(3^a2), and we can do this by using a variant of Dijkstra’s shortest path algorithm on a graph of sequences, with edges (a1,…,an) -> (a1,…,an,1) and (a1,…,ai,…,an) -> (a1,…,ai+1,…an) (as long as that is non-increasing), so, for example, ()->(1)->(2)->(2 1)->(2 2)->(3 2)->(3 2 1) is a path in the graph, representing 1->2->4->12->36->72->360. We maintain a queue of unvisited sequences and each stage we output the smallest unvisited sequence/number and add its successors into the queue (if they aren’t already there).

Here’s a C++ implementation using STL heap operations to manage the queue and an STL set to keep track of seen items, runtime is about 4 ms.

Erlang solution, factoring is done by a 2,3,5,7 factor wheel.

Here’s another solution: if n = (p^k)m where p is prime and doesn’t divide m, then divisors(n) = (k+1)*divisors(m), with m < n, so for each n, we just need to apply trial division until we have found a single prime power factor, then apply the recurrence with a table lookup:

#include

#include

const int K = 2; // We want divisors of n^2

int divisors(int n, const std::vector &a)

{

// Find a prime power factor, reduce n and

// apply recurrence.

int k = 0;

for (int p = 2; p*p 0) return (1+K*k)*a[n];

}

return 1+K; // n is prime

}

int main()

{

int N = 2000;

std::vector a;

a.push_back(0); a.push_back(1);

for (int n = 2; ; n++) {

a.push_back(divisors(n,a));

if (a[n] >= N) {

std::cout << n << "\n";

break;

}

}

}

Don’t know what happened to the formatting there, let’s try again: