Rational decomposition a = xyz(x+y+z)

21

4

Write functions x(a), y(a) and z(a) such that for any rational a all functions return rational numbers and x(a)*y(a)*z(a)*(x(a) + y(a) + z(a)) == a. You may assume a ≥ 0.

You do not need to use rational types or operations in your program, as long as your program is mathematically sound. E.g. if you use a square root in your answer you must show that its argument is always a square of a rational number.

You may write three named functions x, y, z or write three programs instead if functions are cumbersome or nonexistent for your language. Alternatively you may also write a single program/function that returns three numbers x, y, z. Finally, if you so prefer you may input/output the rational numbers as a pair of numerator/denominator. Your score is the total size of the three functions or three programs in bytes. Smallest score wins.

Brute forcing is not allowed. For any a = p/q where p, q ≤ 1000 your program should run in under 10 seconds.


An example (this does not mean your decomposition has to give these numbers):

x = 9408/43615
y = 12675/37576
z = 1342/390
x*y*z*(x+y+z) = 1

orlp

Posted 2017-04-28T12:14:00.843

Reputation: 37 067

Can we write one function which outputs all of them together (say, in an array)? – Leaky Nun – 2017-04-28T12:20:07.090

Can we input the numerator and the denominator as two numbers? – Leaky Nun – 2017-04-28T12:21:22.877

@LeakyNun Yes and yes. – orlp – 2017-04-28T12:40:30.037

1Is it provably doable for any a? – Fatalize – 2017-04-28T13:12:21.413

@Fatalize I wouldn't have made this challenge otherwise.

– orlp – 2017-04-28T13:20:13.160

2I assume you don't want to show a proof because it would give away a solution, but your word is not really a proof. – Fatalize – 2017-04-28T13:25:29.320

@Fatalize, I think this was inspired by a recent answer to a question on another stack, which mentions that Euler exhibited a triple of such functions in a letter to Goldbach. – Peter Taylor – 2017-04-28T15:45:30.397

I assume on the basis of the example and the lack of explicit statement otherwise that the output (numerator, denominator) don't have to be coprime? – Peter Taylor – 2017-04-28T17:04:45.857

@PeterTaylor Correct, the fraction doesn't have to be reduced. In fact, your answer can use floating point if you so desire, just your answer needs to be mathematically sound. If a rational type would get input into your function it should still function correctly (even if your language of choice doesn't actually have a rational type). – orlp – 2017-04-28T17:27:19.640

Answers

10

CJam (59 bytes)

{[WZ~C24X8TT]f*[4XGYC6 4Y].+_0=!>2%Z65135Zb+:(3/.f#:.*)W*+}

This is an anonymous block (function) which takes an integer or double on the stack and produces an array with three doubles. It has two cases internally to handle all non-negative inputs, since with only one case it would break on either 0.25 or 4. It still breaks for inputs -12 and -1.3333333333333333, but the spec allows that...

The online demo executes it and then adds up the values, prints all four, and multiplies them to show that it gets the original value (modulo rounding error).

Mathematical background

Following Noam Elkies we define the auxiliary \$w = - x - y - z\$. Then \$x + y + z + w = 0\$ and \$-xyzw = a\$ or \$xyzw + a = 0\$. This has lots of symmetry; any solution will have four formulae and we can pick the three golfiest ones.

Elkies gives four families of sets of solutions. Euler's:

$$\begin{eqnarray*} x & = & \frac{6ast^3(at^4-2s^4)^2}{(4at^4+s^4)(2a^2t^8 + 10as^4t^4 - s^8)} \\ y & = & \frac{3s^5(4at^4+s^4)^2}{2t(at^4-2s^4)(2a^2t^8+10as^4t^4-s^8)} \\ z & = & \frac{2(2a^2t^8+10as^4t^4-s^8)}{3s^3t(4at^4+s^4)} \\ w & = & \frac{-(2a^2t^8+10as^4t^4-s^8)}{6s^3t(at^4-2s^4)} \end{eqnarray*}$$

One related to Euler's:

$$\begin{eqnarray*} x & = & \frac{(8s^8+a^2)(8s^8-88as^4-a^2)}{12s^3(s^4-a)(8s^8+20as^4-a^2)}\\ y & = & \frac{(8s^8+a^2)(8s^8-88as^4-a^2)}{12s^3(8s^4+a)(8s^8+20as^4-a^2)}\\ z & = & \frac{192as^5(s^4-a)^2(8s^4+a)^2}{(8s^8+a^2)(8s^8-88as^4-a^2)(8s^8+20as^4-a^2)}\\ w & = & \frac{-3s(8s^8+20as^4-a^2)^3}{4(s^4-a)(8s^4+a)(8s^8+a^2)(8s^8-88as^4-a^2)}\\ \end{eqnarray*}$$

A simpler one:

$$\begin{eqnarray*} x & = & \frac{(s^4-4a)^2}{2s^3(s^4+12a)} \\ y & = & \frac{2a(3s^4+4a)^2}{s^3(s^4-4a)(s^4+12a)} \\ z & = & \frac{s^5+12as}{2(3s^4+4a)} \\ w & = & \frac{-2s^5(s^4+12a)}{(s^4-4a)(3s^4+4a)} \\ \end{eqnarray*}$$

And one related to that one:

$$\begin{eqnarray*} x & = & \frac{s^5(s^4-3a)^3}{2(s^4+a)(s^{12}+12as^8-3a^2s^4+2a^3)} \\ y & = & \frac{s^{12}+12as^8-3a^2s^4+2a^3}{2s^3(s^4-3a)(3s^4-a)} \\ z & = & \frac{2a(s^4+a)^2(3s^4-a)^2}{s^3(s^4-3a)(s^{12}+12as^8-3a^2s^4+2a^3)} \\ w & = & \frac{-2s(s^{12}+12as^8-3a^2s^4+2a^3)}{(s^4-3a)(s^4+a)(3s^4-a)} \end{eqnarray*}$$

Observe that every family has at least two denominators of the form \$ps^4 - qa\$ for positive \$p\$ and \$q\$: since all the terms involved are rational, that means that there's some positive \$a\$ for which we get division by zero. Therefore we must use at least two sets of solutions which have their singularities at different values of \$a\$. Intuitively it's going to be golfiest to choose two sets from the same family. I've chosen the simplest family (the third one) with parameters \$s=1\$ and \$s=2\$.

Peter Taylor

Posted 2017-04-28T12:14:00.843

Reputation: 41 901

1

Axiom, 191 bytes

f(s,a)==(b:=s^4-4*a;c:=s^4+12*a;x:=3*s^4+4*a;[b^2/(2*c*s^3),2*a*x^2/(b*c*s^3),s*c/(2*x)])
g(a:FRAC INT):List FRAC INT==(s:=1;repeat(s^4=4*a or s^4=-12*a or 3*s^4=4*a=>(s:=s+1);break);f(s,a))

It is the traslation of the formula Peter Taylor report in this page with some code would make the denominators not be 0. one test

(7) -> y:=g(1)
          9   98 13
   (7)  [--,- --,--]
         26   39 14
                                              Type: List Fraction Integer
(8) -> y.1*y.2*y.3*(y.1+y.2+y.3)
   (8)  1
                                              Type: Fraction Integer

RosLuP

Posted 2017-04-28T12:14:00.843

Reputation: 3 036