Теорема Райли

13

С. Райли доказал следующую теорему в 1825 году:

Каждое рациональное число можно выразить как сумму трех рациональных кубов.

Вызов

Для некоторого рационального числа rQ найдите три рациональных числа a,b,cQ , для которых

r=a3+b3+c3,

Детали

Ваша заявка должна быть в состоянии вычислить решение для каждого входа, учитывая достаточно времени и памяти, это означает, что, например, наличие двух 32-битных, intпредставляющих дробь, недостаточно.

Примеры

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

flawr
источник
1
У меня было что-то вроде работы в Japt, но это часто приводило к ошибке "слишком много рекурсии". Возможно, потому что стратегия заключалась в том, чтобы «получить случайные числа, попробуйте еще раз, пока они не получат правильный ответ».
Камил Дракари
1
Требование поддержки bignum излишне исключает много языков и / или требует много потраченного впустую стандартного шаблона для их реализации
Sparr
2
@Sparr Это был преднамеренный выбор, поскольку выходные данные могут быть довольно «большими» даже для простых входных данных или в зависимости от того, какой метод вы используете, промежуточные значения в расчете также могут быть очень большими. Поэтому работа с произвольными точными числами была важным моментом для этой задачи (и, вероятно, довольно часто в других задачах теории чисел тоже).
Flawr
1
Будет ли это приемлемо для вывода [p1,p2,p3,q], интерпретируется как ? (p1q)3+(p2q)3+(p3q)3
Арно
Аналогичным образом, должны ли три выведенных рациональных числа быть в простейшей форме?
Quintec

Ответы:

10

Пари / ГП , 40 байт

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

Попробуйте онлайн!


Та же длина, та же формула:

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

Попробуйте онлайн!


Эта формула дана в: Ричмонд, Х. (1930). О рациональных решениях x3+y3+z3=R . Труды Эдинбургского математического общества, 2(2), 92-100.

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

Проверьте это онлайн!

alephalpha
источник
1
-5 байт, потому что вы можете изменить порядок слагаемых
Черная Сова Кай
1
27r3+9r127r2+9r1
8

Haskell , 95 89 76 69 68 байт

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

Попробуйте онлайн!

(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
источник
Что делает "долговая расписка"?
Соломон Уцко
@SolomonUcko Ничего особенного, это так же хорошо, как любой другой список длиной 3
Delfad0r
@ H.PWiz Я не смог найти консенсуса по поводу того, допустим ли допущение типизированного ввода, но я все же нашел способ сократить код без этого предположения. Благодарность!
Delfad0r
4
@ Delfad0r Существует «консенсус», что вам не нужно считать возможный импорт, который необходим только для создания необходимого типа, если вам явно не нужно ничего из этого импорта для определения вашей функции. (И вы можете предположить, что правильный тип передается вашей функции при вызове.)
flawr
1
Сохраните один байт с помощью[-n,1/n-n..n]
Christian Sievers
6

Шелуха , 14 байт

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

Простое решение грубой силы. Попробуйте онлайн!

объяснение

Деление в Husk по умолчанию использует рациональные числа, и декартовы произведения корректно работают для бесконечных списков, что делает эту программу очень простой.

ḟ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
источник
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

р[р3-648р2+77760р+37324872(р+72)2,12(р-72)р(р+72)2,-р2-720р+518472(р+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]

Попробуйте онлайн!

flawr
источник
1

perl -Mbigrat -nE, 85 байт

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

Вы можете сохранить 8 байтов (ведущий $_=eval;), если вы знаете, что ввод является целым числом; эта часть нужна для того, чтобы программа вводила данные формы 308/1728. Ввод читается из STDIN. Я использую формулу, заданную @alephalpha.


источник