21
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Can we write one function which outputs all of them together (say, in an array)? \$\endgroup\$ – Leaky Nun Apr 28 '17 at 12:20
  • \$\begingroup\$ Can we input the numerator and the denominator as two numbers? \$\endgroup\$ – Leaky Nun Apr 28 '17 at 12:21
  • \$\begingroup\$ @LeakyNun Yes and yes. \$\endgroup\$ – orlp Apr 28 '17 at 12:40
  • 1
    \$\begingroup\$ Is it provably doable for any a? \$\endgroup\$ – Fatalize Apr 28 '17 at 13:12
  • 2
    \$\begingroup\$ I assume you don't want to show a proof because it would give away a solution, but your word is not really a proof. \$\endgroup\$ – Fatalize Apr 28 '17 at 13:25
10
\$\begingroup\$

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\$.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$

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.