# Best performance on x/(y+z) + y/(x+z) + z/(x+y) = N

Consider the equation $$\frac x {y+z} + \frac y {x+z} + \frac z {x+y} = n$$ for positive integers $$\x, y, z\$$ and $$\n \ge 4\$$. Your code will receive $$\n\$$ as an input, and output three integers $$\x, y\$$ and $$\z\$$ such that the equation holds. You may assume that a solution always exists.

## Background

This equation is a little bit of a meme equation; it's famously difficult to solve, and even the lowest case of $$\n = 4\$$ took hundreds of years to do so. In this paper, the authors present maximum sizes (in digit lengths) for various different $$\n\$$s, all of which are crazy large. It's pretty clear that a standard brute force approach of iterating through all triples is never going to find the smallest solution for any $$\n\$$.

However, some pretty clever approaches using elliptic curves (a curve in the form $$\y^2 = x^3 + ax + b\$$ for constants $$\a, b\$$) managed to find a solution for $$\n = 4\$$:

\begin{align*} x & = 36875131794129999827197811565225474825492979968971970996283137471637224634055579 \\ y & = 154476802108746166441951315019919837485664325669565431700026634898253202035277999 \\ z & = 4373612677928697257861252602371390152816537558161613618621437993378423467772036 \end{align*}

## Challenge

Given some positive integer $$\n \ge 4\$$, you should output three positive integers $$\x, y, z\$$ such that

$$\frac x {y+z} + \frac y {x+z} + \frac z {x+y} = n$$

You may output any one solution, in any reasonable format and manner, but you must output exactly one solution. You may assume that you will only receive inputs where a solution exists.

## Scoring

This is a challenge, so you should aim for speed over conciseness. I will time each submission on my computer, so:

• You must use a freely available language (that's free as in beer)

My computer specifications are: MacBook Pro (16-inch, 2019). Processor: 2.3 GHz 8-Core Intel Core i9. Memory: 16 GB 2667 MHz DDR4. Graphics: AMD Radeon Pro 5500M 4 GB. Retina Display: 16-inch (3072 × 1920). Storage: 208 GB available.

Please test your submission on $$\n = 4\$$ before submitting, and include a preliminary time (which I will replace with an official score in due time).

### !! The only valid inputs for $$\n ≤ 10\$$ are supposedly 4, 6, and 10.

• Is there a name for this equation? May 10 at 14:42

# PARI/GP, 0.02s for n=4 on ATO

fromellpoint(n, x, y) = [ 8 * (n + 3) - x + y, 8 * (n + 3) - x - y, -8 * (n + 3) - 2 * (n + 2)* x]

{ findellpoint(e, n) =
my(s, h);
h = 1;
until(#s > 0,
h *= 10;
s = [ p | p <- ellratpoints(e, h), ellmul(e, p, 6) ]);
s[1]
}

{ f(n) =
my(e, x, y, a, b, c);
e = ellinit([0, 4 * n^2 + 12 * n - 3, 0, 32 * (n + 3), 0]);
[x, y] = g = findellpoint(e, n);
while([a, b, c] = fromellpoint(n, x, y);
a <= 0 || b <= 0 || c <= 0,
[x, y] = elladd(e, g, [x, y]));
[a, b, c] * denominator([a, b, c])
}

print(f(input))

Attempt This Online!

Not really optimized. PARI/GP has some built-in functions for elliptic curves, so I just use them.

When you test the code, just save the code into a file, e.g., a.gp, and run echo 4 | gp -fq a.gp (replace 4 with your input n).
• ATO is showing overflow in t_INT-->long assignment error for n=5,7,8,9 May 10 at 9:39