Teorema de Ryley

13

S. Ryley demostró el siguiente teorema en 1825:

Cada número racional se puede expresar como una suma de tres cubos racionales.

Desafío

Dado un número racional rQ encuentre tres números racionales a,b,cQ tales que

r=a3+b3+c3.

Detalles

Su envío debe poder calcular una solución para cada entrada con suficiente tiempo y memoria, lo que significa que tener, por ejemplo, dos 32 bits que intrepresentan una fracción no es suficiente.

Ejemplos

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

falla
fuente
1
Tenía algo que funcionaba en Japt, pero a menudo se encontraba con un error de "demasiada recursividad". Probablemente porque la estrategia era "obtener números aleatorios, intente nuevamente hasta que sean una respuesta correcta".
Kamil Drakari el
1
Requerir soporte de Bignum excluye innecesariamente muchos idiomas y / o requiere una gran cantidad de desperdicios para implementarlos
Sparr
2
@Sparr Esta fue una elección deliberada, ya que la salida podría ser bastante "grande" incluso para entradas simples, o dependiendo del método que utilice, los valores intermedios en el cálculo también podrían ser muy grandes. Por lo tanto, trabajar con números de precisión arbitrarios fue un punto importante para este desafío (y probablemente con bastante frecuencia en otros desafíos de teoría de números también).
falla
1
¿Sería aceptable la salida [p1,p2,p3,q], interpretada como ? (p1q)3+(p2q)3+(p3q)3
Arnauld el
En una línea similar, ¿los tres números racionales emitidos tienen que estar en la forma más simple?
Quintec

Respuestas:

10

Pari / GP , 40 bytes

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

Pruébalo en línea!


La misma longitud, la misma fórmula:

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

Pruébalo en línea!


This formula is given in: Richmond, H. (1930). On Rational Solutions of x3+y3+z3=R. Proceedings of the Edinburgh Mathematical Society, 2(2), 92-100.

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

Check it online!

alephalpha
fuente
1
-5 bytes because you can change the order of the summands
Black Owl Kai
1
@BlackOwlKai The numerator of the second summand is 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
fuente
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
fuente
2

Haskell , 70 bytes

En Una introducción a la teoría de los números (por Hardy y Wright) hay una construcción que incluso incluye un parámetro racional. Para fines de golf, simplemente configuré este parámetro en 1 e intenté reducir lo más posible. Esto da como resultado la fórmula

r[r3-648r2+77760r+37324872(r+72)2,12(r-72)r(r+72)2,-r2-720r+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]

Pruébalo en línea!

falla
fuente
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

Puede guardar 8 bytes (el principal $_=eval;) si sabe que la entrada es un número entero; Esta parte es necesaria para que el programa obtenga una entrada del formulario 308/1728. La entrada se lee desde STDIN. Estoy usando la fórmula dada por @alephalpha.


fuente