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

Pages: 1 2

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: