Ryley's Theorem
up vote
14
down vote
favorite
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(frac12right)^3 + left(frac13right)^3 + left(frac14right)^3 \
0 &= 0^3 + 0^3 + 0^3 \
1 &= left(frac12right)^3 + left(frac23right)^3 + left(frac56right)^3\
42 &= left(frac{1810423}{509232}right)^3 + left(frac{-14952}{10609}right)^3 + left(frac{-2545}{4944}right)^3
end{align}$$
code-golf math number-theory rational-numbers polynomials
|
show 3 more comments
up vote
14
down vote
favorite
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(frac12right)^3 + left(frac13right)^3 + left(frac14right)^3 \
0 &= 0^3 + 0^3 + 0^3 \
1 &= left(frac12right)^3 + left(frac23right)^3 + left(frac56right)^3\
42 &= left(frac{1810423}{509232}right)^3 + left(frac{-14952}{10609}right)^3 + left(frac{-2545}{4944}right)^3
end{align}$$
code-golf math number-theory rational-numbers polynomials
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".
– Kamil Drakari
Nov 4 at 2:54
Requiring bignum support unnecessarily excludes a lot of languages, and/or requires a lot of wasted boilerplate to implement them
– Sparr
Nov 4 at 5:54
1
@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).
– flawr
Nov 4 at 9:12
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$?
– Arnauld
Nov 4 at 13:58
Along a similar vein, do the three rational numbers outputted have to be in simplest form?
– Quintec
Nov 4 at 14:36
|
show 3 more comments
up vote
14
down vote
favorite
up vote
14
down vote
favorite
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(frac12right)^3 + left(frac13right)^3 + left(frac14right)^3 \
0 &= 0^3 + 0^3 + 0^3 \
1 &= left(frac12right)^3 + left(frac23right)^3 + left(frac56right)^3\
42 &= left(frac{1810423}{509232}right)^3 + left(frac{-14952}{10609}right)^3 + left(frac{-2545}{4944}right)^3
end{align}$$
code-golf math number-theory rational-numbers polynomials
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(frac12right)^3 + left(frac13right)^3 + left(frac14right)^3 \
0 &= 0^3 + 0^3 + 0^3 \
1 &= left(frac12right)^3 + left(frac23right)^3 + left(frac56right)^3\
42 &= left(frac{1810423}{509232}right)^3 + left(frac{-14952}{10609}right)^3 + left(frac{-2545}{4944}right)^3
end{align}$$
code-golf math number-theory rational-numbers polynomials
code-golf math number-theory rational-numbers polynomials
edited Nov 3 at 20:20
asked Nov 3 at 19:33
flawr
26k562181
26k562181
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".
– Kamil Drakari
Nov 4 at 2:54
Requiring bignum support unnecessarily excludes a lot of languages, and/or requires a lot of wasted boilerplate to implement them
– Sparr
Nov 4 at 5:54
1
@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).
– flawr
Nov 4 at 9:12
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$?
– Arnauld
Nov 4 at 13:58
Along a similar vein, do the three rational numbers outputted have to be in simplest form?
– Quintec
Nov 4 at 14:36
|
show 3 more comments
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".
– Kamil Drakari
Nov 4 at 2:54
Requiring bignum support unnecessarily excludes a lot of languages, and/or requires a lot of wasted boilerplate to implement them
– Sparr
Nov 4 at 5:54
1
@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).
– flawr
Nov 4 at 9:12
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$?
– Arnauld
Nov 4 at 13:58
Along a similar vein, do the three rational numbers outputted have to be in simplest form?
– Quintec
Nov 4 at 14:36
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".
– Kamil Drakari
Nov 4 at 2:54
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".
– Kamil Drakari
Nov 4 at 2:54
Requiring bignum support unnecessarily excludes a lot of languages, and/or requires a lot of wasted boilerplate to implement them
– Sparr
Nov 4 at 5:54
Requiring bignum support unnecessarily excludes a lot of languages, and/or requires a lot of wasted boilerplate to implement them
– Sparr
Nov 4 at 5:54
1
1
@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).
– flawr
Nov 4 at 9:12
@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).
– flawr
Nov 4 at 9:12
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$?– Arnauld
Nov 4 at 13:58
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$?– Arnauld
Nov 4 at 13:58
Along a similar vein, do the three rational numbers outputted have to be in simplest form?
– Quintec
Nov 4 at 14:36
Along a similar vein, do the three rational numbers outputted have to be in simplest form?
– Quintec
Nov 4 at 14:36
|
show 3 more comments
6 Answers
6
active
oldest
votes
up vote
9
down vote
Pari/GP, 40 bytes
r->[x=27*r^3+1,9*r-x,z=9*r-27*r^2]/(3-z)
Try it online!
The same length, the same formula:
r->d=9*r^2-3*r+1;[x=r+1/3,3*r/d-x,1/d-1]
Try it 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(dfrac{27r^3+1}{27r^2-9r+3}right)^3+left(dfrac{-27r^3+9r-1}{27r^2-9r+3}right)^3+left(dfrac{-27r^2+9r}{27r^2-9r+3}right)^3$
Check it online!
1
-5 bytes because you can change the order of the summands
– Black Owl Kai
Nov 4 at 8:42
1
@BlackOwlKai The numerator of the second summand is $-27r^{color{Red}3}+9r-1$, not $-27r^{color{Red}2}+9r-1$.
– alephalpha
Nov 4 at 12:42
add a comment |
up vote
8
down vote
Haskell, 95 89 76 69 68 bytes
- -18 bytes thanks to H.PWiz
- -1 byte thanks to Christian Sievers
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)qquadtext{with }-nlefrac{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 $-nlefrac{a_i}{n}le n$, since
$$
frac{a_i}{n}=frac{a_iN}{nN}
$$
for any arbitrarily large integer $N$.
What does the "IOU" do?
– Solomon Ucko
Nov 3 at 21:54
@SolomonUcko Nothing special, it's as good as any other list of length 3
– Delfad0r
Nov 3 at 21:57
@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!
– Delfad0r
Nov 3 at 22:13
4
@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.)
– flawr
Nov 3 at 22:14
1
Save one byte by using[-n,1/n-n..n]
– Christian Sievers
Nov 4 at 13:10
add a comment |
up vote
6
down vote
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.
add a comment |
up vote
2
down vote
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.
add a comment |
up vote
2
down vote
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+72right)^2
}} , {{12,left(r-72right),r}over{left(r+72right)^2}} , -{{r^2
-720,r+5184}over{72,left(r+72right)}} 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!
add a comment |
up vote
1
down vote
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.
add a comment |
6 Answers
6
active
oldest
votes
6 Answers
6
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
9
down vote
Pari/GP, 40 bytes
r->[x=27*r^3+1,9*r-x,z=9*r-27*r^2]/(3-z)
Try it online!
The same length, the same formula:
r->d=9*r^2-3*r+1;[x=r+1/3,3*r/d-x,1/d-1]
Try it 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(dfrac{27r^3+1}{27r^2-9r+3}right)^3+left(dfrac{-27r^3+9r-1}{27r^2-9r+3}right)^3+left(dfrac{-27r^2+9r}{27r^2-9r+3}right)^3$
Check it online!
1
-5 bytes because you can change the order of the summands
– Black Owl Kai
Nov 4 at 8:42
1
@BlackOwlKai The numerator of the second summand is $-27r^{color{Red}3}+9r-1$, not $-27r^{color{Red}2}+9r-1$.
– alephalpha
Nov 4 at 12:42
add a comment |
up vote
9
down vote
Pari/GP, 40 bytes
r->[x=27*r^3+1,9*r-x,z=9*r-27*r^2]/(3-z)
Try it online!
The same length, the same formula:
r->d=9*r^2-3*r+1;[x=r+1/3,3*r/d-x,1/d-1]
Try it 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(dfrac{27r^3+1}{27r^2-9r+3}right)^3+left(dfrac{-27r^3+9r-1}{27r^2-9r+3}right)^3+left(dfrac{-27r^2+9r}{27r^2-9r+3}right)^3$
Check it online!
1
-5 bytes because you can change the order of the summands
– Black Owl Kai
Nov 4 at 8:42
1
@BlackOwlKai The numerator of the second summand is $-27r^{color{Red}3}+9r-1$, not $-27r^{color{Red}2}+9r-1$.
– alephalpha
Nov 4 at 12:42
add a comment |
up vote
9
down vote
up vote
9
down vote
Pari/GP, 40 bytes
r->[x=27*r^3+1,9*r-x,z=9*r-27*r^2]/(3-z)
Try it online!
The same length, the same formula:
r->d=9*r^2-3*r+1;[x=r+1/3,3*r/d-x,1/d-1]
Try it 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(dfrac{27r^3+1}{27r^2-9r+3}right)^3+left(dfrac{-27r^3+9r-1}{27r^2-9r+3}right)^3+left(dfrac{-27r^2+9r}{27r^2-9r+3}right)^3$
Check it online!
Pari/GP, 40 bytes
r->[x=27*r^3+1,9*r-x,z=9*r-27*r^2]/(3-z)
Try it online!
The same length, the same formula:
r->d=9*r^2-3*r+1;[x=r+1/3,3*r/d-x,1/d-1]
Try it 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(dfrac{27r^3+1}{27r^2-9r+3}right)^3+left(dfrac{-27r^3+9r-1}{27r^2-9r+3}right)^3+left(dfrac{-27r^2+9r}{27r^2-9r+3}right)^3$
Check it online!
edited Nov 4 at 10:30
answered Nov 4 at 4:42
alephalpha
20.9k32888
20.9k32888
1
-5 bytes because you can change the order of the summands
– Black Owl Kai
Nov 4 at 8:42
1
@BlackOwlKai The numerator of the second summand is $-27r^{color{Red}3}+9r-1$, not $-27r^{color{Red}2}+9r-1$.
– alephalpha
Nov 4 at 12:42
add a comment |
1
-5 bytes because you can change the order of the summands
– Black Owl Kai
Nov 4 at 8:42
1
@BlackOwlKai The numerator of the second summand is $-27r^{color{Red}3}+9r-1$, not $-27r^{color{Red}2}+9r-1$.
– alephalpha
Nov 4 at 12:42
1
1
-5 bytes because you can change the order of the summands
– Black Owl Kai
Nov 4 at 8:42
-5 bytes because you can change the order of the summands
– Black Owl Kai
Nov 4 at 8:42
1
1
@BlackOwlKai The numerator of the second summand is $-27r^{color{Red}3}+9r-1$, not $-27r^{color{Red}2}+9r-1$.
– alephalpha
Nov 4 at 12:42
@BlackOwlKai The numerator of the second summand is $-27r^{color{Red}3}+9r-1$, not $-27r^{color{Red}2}+9r-1$.
– alephalpha
Nov 4 at 12:42
add a comment |
up vote
8
down vote
Haskell, 95 89 76 69 68 bytes
- -18 bytes thanks to H.PWiz
- -1 byte thanks to Christian Sievers
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)qquadtext{with }-nlefrac{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 $-nlefrac{a_i}{n}le n$, since
$$
frac{a_i}{n}=frac{a_iN}{nN}
$$
for any arbitrarily large integer $N$.
What does the "IOU" do?
– Solomon Ucko
Nov 3 at 21:54
@SolomonUcko Nothing special, it's as good as any other list of length 3
– Delfad0r
Nov 3 at 21:57
@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!
– Delfad0r
Nov 3 at 22:13
4
@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.)
– flawr
Nov 3 at 22:14
1
Save one byte by using[-n,1/n-n..n]
– Christian Sievers
Nov 4 at 13:10
add a comment |
up vote
8
down vote
Haskell, 95 89 76 69 68 bytes
- -18 bytes thanks to H.PWiz
- -1 byte thanks to Christian Sievers
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)qquadtext{with }-nlefrac{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 $-nlefrac{a_i}{n}le n$, since
$$
frac{a_i}{n}=frac{a_iN}{nN}
$$
for any arbitrarily large integer $N$.
What does the "IOU" do?
– Solomon Ucko
Nov 3 at 21:54
@SolomonUcko Nothing special, it's as good as any other list of length 3
– Delfad0r
Nov 3 at 21:57
@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!
– Delfad0r
Nov 3 at 22:13
4
@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.)
– flawr
Nov 3 at 22:14
1
Save one byte by using[-n,1/n-n..n]
– Christian Sievers
Nov 4 at 13:10
add a comment |
up vote
8
down vote
up vote
8
down vote
Haskell, 95 89 76 69 68 bytes
- -18 bytes thanks to H.PWiz
- -1 byte thanks to Christian Sievers
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)qquadtext{with }-nlefrac{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 $-nlefrac{a_i}{n}le n$, since
$$
frac{a_i}{n}=frac{a_iN}{nN}
$$
for any arbitrarily large integer $N$.
Haskell, 95 89 76 69 68 bytes
- -18 bytes thanks to H.PWiz
- -1 byte thanks to Christian Sievers
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)qquadtext{with }-nlefrac{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 $-nlefrac{a_i}{n}le n$, since
$$
frac{a_i}{n}=frac{a_iN}{nN}
$$
for any arbitrarily large integer $N$.
edited Nov 4 at 13:19
answered Nov 3 at 21:07
Delfad0r
1,248315
1,248315
What does the "IOU" do?
– Solomon Ucko
Nov 3 at 21:54
@SolomonUcko Nothing special, it's as good as any other list of length 3
– Delfad0r
Nov 3 at 21:57
@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!
– Delfad0r
Nov 3 at 22:13
4
@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.)
– flawr
Nov 3 at 22:14
1
Save one byte by using[-n,1/n-n..n]
– Christian Sievers
Nov 4 at 13:10
add a comment |
What does the "IOU" do?
– Solomon Ucko
Nov 3 at 21:54
@SolomonUcko Nothing special, it's as good as any other list of length 3
– Delfad0r
Nov 3 at 21:57
@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!
– Delfad0r
Nov 3 at 22:13
4
@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.)
– flawr
Nov 3 at 22:14
1
Save one byte by using[-n,1/n-n..n]
– Christian Sievers
Nov 4 at 13:10
What does the "IOU" do?
– Solomon Ucko
Nov 3 at 21:54
What does the "IOU" do?
– Solomon Ucko
Nov 3 at 21:54
@SolomonUcko Nothing special, it's as good as any other list of length 3
– Delfad0r
Nov 3 at 21:57
@SolomonUcko Nothing special, it's as good as any other list of length 3
– Delfad0r
Nov 3 at 21:57
@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!
– Delfad0r
Nov 3 at 22:13
@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!
– Delfad0r
Nov 3 at 22:13
4
4
@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.)
– flawr
Nov 3 at 22:14
@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.)
– flawr
Nov 3 at 22:14
1
1
Save one byte by using
[-n,1/n-n..n]– Christian Sievers
Nov 4 at 13:10
Save one byte by using
[-n,1/n-n..n]– Christian Sievers
Nov 4 at 13:10
add a comment |
up vote
6
down vote
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.
add a comment |
up vote
6
down vote
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.
add a comment |
up vote
6
down vote
up vote
6
down vote
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.
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.
answered Nov 5 at 7:48
Zgarb
26.2k460228
26.2k460228
add a comment |
add a comment |
up vote
2
down vote
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.
add a comment |
up vote
2
down vote
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.
add a comment |
up vote
2
down vote
up vote
2
down vote
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.
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.
edited Nov 4 at 15:07
answered Nov 4 at 13:54
Arnauld
67.7k584288
67.7k584288
add a comment |
add a comment |
up vote
2
down vote
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+72right)^2
}} , {{12,left(r-72right),r}over{left(r+72right)^2}} , -{{r^2
-720,r+5184}over{72,left(r+72right)}} 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!
add a comment |
up vote
2
down vote
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+72right)^2
}} , {{12,left(r-72right),r}over{left(r+72right)^2}} , -{{r^2
-720,r+5184}over{72,left(r+72right)}} 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!
add a comment |
up vote
2
down vote
up vote
2
down vote
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+72right)^2
}} , {{12,left(r-72right),r}over{left(r+72right)^2}} , -{{r^2
-720,r+5184}over{72,left(r+72right)}} 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!
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+72right)^2
}} , {{12,left(r-72right),r}over{left(r+72right)^2}} , -{{r^2
-720,r+5184}over{72,left(r+72right)}} 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!
edited Nov 4 at 22:23
answered Nov 4 at 22:16
flawr
26k562181
26k562181
add a comment |
add a comment |
up vote
1
down vote
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.
add a comment |
up vote
1
down vote
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.
add a comment |
up vote
1
down vote
up vote
1
down vote
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.
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.
answered Nov 4 at 13:20
Abigail
39717
39717
add a comment |
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f175201%2fryleys-theorem%23new-answer', 'question_page');
}
);
Post as a guest
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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".
– Kamil Drakari
Nov 4 at 2:54
Requiring bignum support unnecessarily excludes a lot of languages, and/or requires a lot of wasted boilerplate to implement them
– Sparr
Nov 4 at 5:54
1
@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).
– flawr
Nov 4 at 9:12
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$?– Arnauld
Nov 4 at 13:58
Along a similar vein, do the three rational numbers outputted have to be in simplest form?
– Quintec
Nov 4 at 14:36