Диофант - Арифметика

Второе условно поясни: из трех чисел a, b, c должны выполняться все три условия
a+b-c=квадрат
a+c-b=квадрат
b+c-a=квадрат

Или только одно из них?

переобозначаешь
a+b=x
d^2=D
e^2=E,

x+c=D
x-c=E,

x=(D+E)/2
c=(D-E)/2

перебираешь любые квадраты целых чисел D > E с условием, что они оба четные или нечетные, чтобы делилось на 2. Например,

D=121,
E=81

=> x = 101, c = 20
=> a+b - любые дающие в сумме 101, например a=4, b=97

Задача: написать программу, которая находит бесконечно много таких троек чисел, причем в целых числах

Не мучайся, реши перебором.

Похоже, что задача тривиально сводится к перечислению пифагоровых четвёрок, описанному даже в википедии. Но, мсье, почему этот вопрос здесь?

Лишь с одним из этих условий задача ещё более тривиальна. Должны быть выполнены все, конечно же.

О да, путь настоящего лиспера.

О да, путь настоящего лиспера

«When in doubt, use brute force» (с) Кен Томпсон. Учись сынок.

Про систему несовсем верно. Мы имеем след. систему уравнений:

{ a+b+c = k^2
{ a+b-c = q1^2
{ a+c-b = q2^2
{ b+c-a = q3^2

a+b+c = q1^2+q2^2+q3^2 = k^2

{ 2c = k^2-q1^2
{ 2b = k^2-q2^2
{ 2a = k^2-q3^2

Из первой следует, что нет таких четверок, в которых все числа нечетные. Тогда будем искать примитивные четверки, и домножать их на 2.

Вторая параметризация хорошо подходит для перебора. Для начала немного отвелчемся от задачи и будем думать, как составить алгоритм нахождения натуральных корней уравнения "a^2 + b^2 + c^2 = d^2" или их удвоенного значения. Пусть a и b будут разной четности, что облегчает наш перебор. Тогда пусть s = a^2+b^2, а p — такой делитель s, что p^2<s Тогда:

2c = s/p - p
2d = 2c + 2p

Вот прототип алгоритм на Python:

from math import sqrt

def alg(maxq1):
    for q1 in range(2, maxq1+1, 2):
        for q2 in range(1, q1, 2):
            s = q1*q1 + q2*q2
            for p in range(1, int(sqrt(s))):
                if s % p == 0:
                    q1 <<= 1; q1 = q1*q1
                    q2 <<= 1; q2 = q2*q2
                    q3 = (s//p) - p;
                    k = (q3 + (p<<1));
                    q3 = q3*q3; k = k*k
                    yield ((k-q1)>>1, (k-q2)>>1, (k-q3)>>1)

Прототип потому, что уже пятым числом выдает нечто отрицательное (может быть так и надо :D), ну и при вызове alg(6) или больше OverflowError. Пока сыро, но уже пол второго и я не в состоянии сейчас что-либо исправлять. Не знаю, как оценить сложность алгоритма, но это явно лучше чем тупой перебор за O(n^3) и это без учета поиска квадратов/корней.

Все, я написал нормально свой алгоритм. Вот два алгоритма:

def alg(maxq1):
    for q1 in range(2, maxq1+1, 2):
        q1 = q1*q1
        for q2 in range(1, q1+1, 2):
            q2 = q2*q2
            s = q1 + q2
            for p in range(1, int(sqrt(s)-0.0001)+1, 2):
                if s % p == 0:
                    q3 = ((s//p)-p)>>1
                    q3 = q3*q3
                    yield ((q1+q2)<<1, (q1+q3)<<1, (q2+q3)<<1)


def brute_alg(maxq1):
    L = []
    for q1 in range(2, maxq1+1, 2):
        q1 = q1*q1
        for q2 in range(2, q1+1, 2):
            q2 = q2*q2
            for q3 in range(2, q2+1, 2):
                q3 = q3*q3
                k = q1 + q2 + q3
                t = sqrt(k)
                if round(abs(t - int(t)), 6) == 0.0:
                    yield (k-q1)>>1, (k-q2)>>1, (k-q3)>>1

Кто говорил про Brute Force — для таких целей не катит никак. Вот что у меня получилось по времени:

alg(10) 0.1 | brute_alg(10) 0.54

alg(20) 0.12 | brute_alg(20) 40.67 (!!!)

Т.е. уже на 20 это ооочень долго, на 30 и дальше я уже не дождался. Но при этом alg(50) 1.2, т.е. разница колоссальна.

Буду рад если кто-нибудь оценит сложность алгоритма, т.к. тут не очень ясно как это сделать. ПС: Есть ли эффективные алгоритмы нахождения целой части квадрата числа?

Неа, задачка другая. См. мой пост выше, ТС не полностью написал систему.

В условии не сказано, что любые два должны превышать третье на квадрат. Такую интерпретацию можно предположить только из его примера.

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

Во-вторых, в аналогичных задачах по математике (целые и натуральные числа, комбинаторика) часто опускается слово любые, зато если подразумевается какой-то конкретный набор то всегда (из личного опыта) указывается «некоторые», «вполне определенные» и т.п.

В-третьих, если вы ознакомитесь с трудами самого Диофанта, то поймете, что имел он в виду именно ту систему, которую я описал выше.

В условии точно сказано и словами, и системой уравнений, что второму условию удовлетворяет одно число. А Диофант может предложить свои оригинальные формулировки и даже открыть новую тему :) Тем более что автор этой после создания не проявил к ней никакого интереса.

Словами точь в точь скопировано с русского перевода Арифметики. А про систему из 2ух уравнений — это домыслы ТС, в первоисточнике который и указывает сам ТС речь идет о *нувыпонели*.

Я специально привел не самую трудную задачу из Арифметики Диофанта.. У него есть задачи поинтереснее. Например - разложить квадрат на два квадрата. Все знают, что 25 можно разложить на 9 и 16. Но не все знают, что 25 можно разложить на два рациональных квадрата бесчисленным числом способов, например :

(40/17)^2 + (75/17)^2 = 25

(72/17)^2 + (135/17)^2 = 25 и т.д.

Кстати, сам Диофант приводит дробное решение: 16 = 256/25 + 144/25 Диофант не описывает алгоритм решения своих задач, создается впечатление, что они решены по наитию, но это конечно не так. Разложить квадрат на два квадрата можно например так:

for a in range(5,10):
     k=4
     x = Decimal(2*a*k)/Decimal((k**2) + 1) 
     y = Decimal(a * (((k**2)-1))/Decimal(((k**2)+1)))
     if Decimal(x**2) + Decimal(y**2) == a**2 and y > 0:
       print '%s x=%s/%s y=%s/%s x^2=%.2f y^2=%.2f' % (a**2, 2*a*k, k**2+1, a * (k**2-1), (k**2+1), x**2, y**2 )

Но не все знают, что 25 можно разложить на два рациональных квадрата бесчисленным числом способов

Не самое удивительное дело — взять a^2 + b^2 = c^2, разделить на c^2 и умножить на 25. Одно действие.