Twierdzenie Ryleya

13

S. Ryley udowodnił następujące twierdzenie w 1825 roku:

Każda liczba wymierna może być wyrażona jako suma trzech wymiernych kostek.

Wyzwanie

Biorąc pod uwagę pewną liczbę wymierną rQ znajdź trzy liczby wymierne a,b,cQ takie, że

r=a3+b3+c3.

Detale

Twoje zgłoszenie powinno być w stanie obliczyć rozwiązanie dla każdego wejścia, biorąc pod uwagę wystarczającą ilość czasu i pamięci, co oznacza, że ​​na przykład dwa 32-bity intreprezentujące ułamek nie są wystarczające.

Przykłady

30=3982933876681363660054951533977505554546352=607029013173+2396129245436192271286533071728=(12)3+(13)3+(14)30=03+03+031=(12)3+(23)3+(56)342=(1810423509232)3+(1495210609)3+(25454944)3

wada
źródło
1
Miałem coś takiego w Japt, ale często występował błąd „zbyt dużej rekurencji”. Prawdopodobnie dlatego, że strategia polegała na „otrzymywaniu liczb losowych, spróbuj ponownie, aż będą one poprawną odpowiedzią”.
Kamil Drakari
1
Wymaganie wsparcia bignum niepotrzebnie wyklucza wiele języków i / lub wymaga dużo zmarnowanej płyty kotłowej do ich wdrożenia
Sparr
2
@Sparr Był to celowy wybór, ponieważ dane wyjściowe mogą być dość „duże”, nawet dla prostych danych wejściowych, lub w zależności od zastosowanej metody wartości pośrednie w obliczeniach mogą być również bardzo duże. Dlatego praca z dowolnymi liczbami dokładności była ważnym punktem tego wyzwania (i prawdopodobnie dość często również w innych wyzwaniach teorii liczb).
flawr
1
Czy wyjście byłoby dopuszczalne [p1,p2,p3,q], interpretowane jako ? (p1q)3+(p2q)3+(p3q)3
Arnauld,
Czy w podobny sposób trzy wyprowadzane racjonalne liczby muszą być w najprostszej formie?
Quintec,

Odpowiedzi:

10

Pari / GP , 40 bajtów

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

Wypróbuj online!


Ta sama długość, ta sama formuła:

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

Wypróbuj online!


Ta formuła jest podana w: Richmond, H. (1930). Racjonalnych roztworów x3+y3+z3=R . Proceedings of Edinburgh Mathematical Society, 2 (2), 92-100.

r=(27r3+127r29r+3)3+(27r3+9r127r29r+3)3+(27r2+9r27r29r+3)3

Sprawdź to online!

alephalpha
źródło
1
-5 bajtów, ponieważ możesz zmienić kolejność sum
Black Owl Kai
1
27r3+9r1, not 27r2+9r1.
alephalpha
8

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

(a1n,a2n,a3n)with nainn.

  • We can always assume that the three rational numbers have the same denominator, since
    (a1n1,a2n2,a3n3)=(a1n2n3n1n2n3,a2n1n3n1n2n3,a3n1n2n1n2n3).
  • We can always assume that nainn, since
    ain=aiNnN
    for any arbitrarily large integer N.
Delfad0r
źródło
What does the "IOU" do?
Solomon Ucko
@SolomonUcko Nothing special, it's as good as any other list of length 3
Delfad0r
@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
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
1
Save one byte by using [-n,1/n-n..n]
Christian Sievers
6

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.
Zgarb
źródło
2

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 pq=(p1q1)3+(p2q2)3+(p3q3)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.

Arnauld
źródło
2

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[r3648r2+77760r+37324872(r+72)2,12(r72)r(r+72)2,r2720r+518472(r+72)]

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!

flawr
źródło
1

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.


źródło