1
\$\begingroup\$

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*}$$

Your task is to find these solutions.

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.

Additionally, your answer may not fail due to floating point issues.

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)
  • Please provide testing instructions
  • If the language is obscure, or requires additional packages/modules, please provide a link to a page where I can download the interpreter

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.

\$\endgroup\$
1
  • \$\begingroup\$ Is there a name for this equation? \$\endgroup\$
    – Seggan
    May 10 at 14:42

1 Answer 1

2
\$\begingroup\$

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.

You can download PARI/GP here.

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

\$\endgroup\$
2
  • \$\begingroup\$ ATO is showing overflow in t_INT-->long assignment error for n=5,7,8,9 \$\endgroup\$
    – Saphereye
    May 10 at 9:39
  • 1
    \$\begingroup\$ @Saphereye There is no answer for those input. \$\endgroup\$
    – alephalpha
    May 10 at 9:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.