13
\$\begingroup\$

S. Ryley proved following theorem in 1825:

Every rational number can be expressed as a sum of three rational cubes.

Challenge

Given some rational number \$r \in \mathbb Q \$ find three rational numbers \$a,b,c \in \mathbb Q\$ such that $$r= a^3+b^3+c^3.$$

Details

Your submission should be able to compute a solution for every input given enough time and memory, that means having for instance two 32-bit int representing a fraction is not sufficient.

Examples

$$ \begin{align} 30 &= 3982933876681^3 - 636600549515^3 - 3977505554546^3 \\ 52 &= 60702901317^3 + 23961292454^3 - 61922712865^3 \\ \frac{307}{1728} &= \left(\frac12\right)^3 + \left(\frac13\right)^3 + \left(\frac14\right)^3 \\ 0 &= 0^3 + 0^3 + 0^3 \\ 1 &= \left(\frac12\right)^3 + \left(\frac23\right)^3 + \left(\frac56\right)^3\\ 42 &= \left(\frac{1810423}{509232}\right)^3 + \left(\frac{-14952}{10609}\right)^3 + \left(\frac{-2545}{4944}\right)^3 \end{align}$$

Improve this question
\$\endgroup\$
8
  • 1
    \$\begingroup\$ I had something that kind-of worked in Japt, but it often ran into a "too much recursion" error. Probably because the strategy was "get random numbers, try again until they're a correct answer". \$\endgroup\$
    – Kamil Drakari
    Nov 4, 2018 at 2:54
  • 1
    \$\begingroup\$ Requiring bignum support unnecessarily excludes a lot of languages, and/or requires a lot of wasted boilerplate to implement them \$\endgroup\$
    – Sparr
    Nov 4, 2018 at 5:54
  • 2
    \$\begingroup\$ @Sparr This was a deliberate choice, as the output could be quite "large" even for simple inputs, or depending on what method you use, the intermediate values in the calculation could also be very large. So working with arbitrary precision numbers was an important point for this challenge (and probably quite often in other number-theory-challenges too). \$\endgroup\$
    – flawr
    Nov 4, 2018 at 9:12
  • 1
    \$\begingroup\$ Would it be acceptable to output [p1,p2,p3,q], interpreted as \$\left(\frac{p_1}{q}\right)^3+\left(\frac{p_2}{q}\right)^3+\left(\frac{p_3}{q}\right)^3\$? \$\endgroup\$
    – Arnauld
    Nov 4, 2018 at 13:58
  • \$\begingroup\$ Along a similar vein, do the three rational numbers outputted have to be in simplest form? \$\endgroup\$
    – Quintec
    Nov 4, 2018 at 14:36

7 Answers 7

Reset to default
13
\$\begingroup\$

PARI/GP, 35 bytes

r->[x=r+1/3,-x+r/3/d=x^2-r,1/9/d-1]

Attempt This Online!

PARI/GP, 40 bytes

r->[x=27*r^3+1,9*r-x,z=9*r-27*r^2]/(3-z)

Attempt This Online!

This formula is given in: Richmond, H. (1930). On Rational Solutions of \$x^3+y^3+z^3=R\$. Proceedings of the Edinburgh Mathematical Society, 2(2), 92-100.

$$r=\left(\frac{27r^3+1}{27r^2-9r+3}\right)^3+\left(\frac{-27r^3+9r-1}{27r^2-9r+3}\right)^3+\left(\frac{-27r^2+9r}{27r^2-9r+3}\right)^3$$

Check it online!

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ -5 bytes because you can change the order of the summands \$\endgroup\$
    – Kateba
    Nov 4, 2018 at 8:42
  • 1
    \$\begingroup\$ @BlackOwlKai The numerator of the second summand is \$-27r^{\color{Red}3}+9r-1\$, not \$-27r^{\color{Red}2}+9r-1\$. \$\endgroup\$
    – alephalpha
    Nov 4, 2018 at 12:42
8
\$\begingroup\$

Haskell, 95 89 76 69 68 bytes

f x=[w|n<-[1..],w<-mapM(\_->[-n,1/n-n..n])"IOU",x==sum((^3)<$>w)]!!0

Try it online!

Simple bruteforce solution. It tests all triples of rational numbers of the form $$ \left(\frac{a_1}{n},\frac{a_2}{n},\frac{a_3}{n}\right)\qquad\text{with }-n\le\frac{a_i}{n}\le n. $$

  • We can always assume that the three rational numbers have the same denominator, since $$ \left(\frac{a_1}{n_1},\frac{a_2}{n_2},\frac{a_3}{n_3}\right)=\left(\frac{a_1n_2n_3}{n_1n_2n_3},\frac{a_2n_1n_3}{n_1n_2n_3},\frac{a_3n_1n_2}{n_1n_2n_3}\right). $$
  • We can always assume that \$-n\le\frac{a_i}{n}\le n\$, since $$ \frac{a_i}{n}=\frac{a_iN}{nN} $$ for any arbitrarily large integer \$N\$.
Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ What does the "IOU" do? \$\endgroup\$
    – Solomon Ucko
    Nov 3, 2018 at 21:54
  • \$\begingroup\$ @SolomonUcko Nothing special, it's as good as any other list of length 3 \$\endgroup\$
    – Delfad0r
    Nov 3, 2018 at 21:57
  • \$\begingroup\$ @H.PWiz I couldn't find any consensus on Meta on whether assuming typed input is accepted, but I still found a way to shorten the code without that assumption. Thanks! \$\endgroup\$
    – Delfad0r
    Nov 3, 2018 at 22:13
  • 4
    \$\begingroup\$ @Delfad0r There is a "consensus" that you do not have to count a possible import, that is only needed to construct the type needed, if you do not explicitly need anything from that import for defining your function. (And you can assume that the correct type is passed to your function, when it is called.) \$\endgroup\$
    – flawr
    Nov 3, 2018 at 22:14
  • 1
    \$\begingroup\$ Save one byte by using [-n,1/n-n..n] \$\endgroup\$
    – Christian Sievers
    Nov 4, 2018 at 13:10
7
\$\begingroup\$

Husk, 14 bytes

ḟo=⁰ṁ^3π3×/NİZ

Simple brute force solution. Try it online!

Explanation

Division in Husk uses rational numbers by default and Cartesian products work correctly for infinite lists, making this a very straightforward program.

ḟo=⁰ṁ^3π3×/NİZ
            İZ  Integers: [0,1,-1,2,-2,3,-3...
           N    Natural numbers: [1,2,3,4,5...
         ×/     Mix by division: [0,1,0,-1,1/2,0,2,-1/2,1/3...
                This list contains n/m for every integer n and natural m.
       π3       All triples: [[0,0,0],[0,0,1],[1,0,0]...
ḟ               Find the first one
    ṁ^3         whose sum of cubes
 o=⁰            equals the input.
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

JavaScript (Node.js), 73 bytes

Takes input as (p)(q), where \$p\$ and \$q\$ are BigInt literals.

Returns [[p1,q1],[p2,q2],[p3,q3]] such that \$\frac{p}{q}=\left(\frac{p_1}{q_1}\right)^3+\left(\frac{p_2}{q_2}\right)^3+\left(\frac{p_3}{q_3}\right)^3\$.

p=>q=>[x=p*(y=p*(p*=9n*q*q)*3n/q)/q+(q*=q*q),p-x,p-=y].map(x=>[x,3n*q-p])

Try it online!

Derived from H. W. Richmond (1930), On Rational Solutions of x3 + y3 +z3 = R.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Haskell, 70 bytes

In An introduction to the Theory of Numbers (by Hardy and Wright) there is an construction that even includes a rational parameter. For golfing purposes I just set this parameter to 1, and tried reducing as much as possible. This results in the formula

$$r \mapsto \left[ {{r^3-648\,r^2+77760\,r+373248}\over{72\,\left(r+72\right)^2 }} , {{12\,\left(r-72\right)\,r}\over{\left(r+72\right)^2}} , -{{r^2 -720\,r+5184}\over{72\,\left(r+72\right)}} \right] $$

f r|t<-r/72,c<-t+1,v<-24*t/c^3,a<-(v*t-1)*c=((a+v*c+c)/2-)<$>[a,v*c,c]

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

perl -Mbigrat -nE, 85 bytes

$_=eval;($a,$b)=($_*9,$_**2*27);$c=$b*$_;say for map$_/($b-$a+3),$c+1,-$c+$a-1,-$b+$a

You can save 8 bytes (the leading $_=eval;) if you know the input is an integer; this part is needed to have the program grok an input of the form 308/1728. Input is read from STDIN. I'm using the formula given by @alephalpha.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Maxima, 62 bytes

A port of @alephalpha's Pari/GP code in Maxima.

Try it online!

lambda([r],block([x:27*r^3+1,z:9*r-27*r^2],[x,9*r-x,z]/(3-z)))
Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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