Найдите все пифагоровы тройки, в которых все числа находятся в диапазоне [1; 5000]

Question

Пифагоровой тройка назовём тройку чисел (a, b, c), такую что a ≤ b ≤ с и a²+b²=c². Найдите все пифагоровы тройки, в которых все числа находятся в диапазоне [1; 5000]. Запишите в ответе количество подходящих троек, а затем – значение c для тройки, в которой сумма a+b+c максимальна.

Помогите пожалуйста, код нужен на python, в ответе к заданию (5681 4988)

k = 0
for m in range(1, 5000+1):
    if (a < 5000) and (a ** 2 + b ** 2 == c ** 2):
        print(a,b,c)
        k += 1
print(k)

Answer 1

Ну, я написал код, но пока вам его не покажу - это всё-таки учебное задание. Но дам подсказки:

перебирайте в цикле a в указанном вам диапазоне [1,5000]
перебирайте в цикле b, учитывая, что оно тоже должно быть в диапазоне [1,5000] и кроме того, что a <= b
c перебирать не нужно, его можно вычислить зная a и b из уравнения, которое вам дано
вычисленное c нужно проверить на попадание в диапазон и на то, что получилось вообще целое число
если c получилось подходящее - увеличивайте счётчик, кроме того, сравните получающееся a+b+c с ранее запомненным значением (сначала запомните 0, как и в счётчик), если оно больше - запомните его и запомните c
после окончания циклов выведите значение счётчика и запомненного c

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

Вот если бы было три вложенных цикла по 5000 значений, то это бы работало конкретно долго.

P.S. Ответ у меня сошёлся с указанным в задании.

Ну раз GrAnd выложил код, добавлю и я свой. Он прям "в лоб" написан, без особых оптимизаций, разве что из цикла я вынес a ** 2 и перебор b прерываю, если c вышло из диапазона. В функцию вынесено, чтобы можно было при желании обернуть в numba.njit:

def find():
    count = 0
    max3 = 0
    max_c = 0
    for a in range(1, 5001):
        a2 = a * a
        for b in range(a, 5001):
            b2 = b * b
            c = (a2 + b2) ** 0.5
            if c > 5000:
                break
            if c == int(c):
                count += 1
                if a+b+c > max3:
                    max3 = a+b+c
                    max_c = c
    return count, int(max_c)

print(find())

Answer 2

Используя генерацию Пифагоровых троек, вот что у меня получилось:

MAX = 5000

triplets = set()
for n in range(1, int((MAX+1)**0.5)+1):
    for m in range(n+1, MAX+1, 2):
        for k in range(1, MAX+1):
            c = k * (m*m + n*n)
            if c > MAX: break
            b = k * 2 * m * n
            a = k * (m*m - n*n)
            triplets.add(tuple(sorted((a,b,c))))
        if k == 1:
            break

print(len(triplets), max((a+b+c, c) for a,b,c in triplets)[1])

В Google Colab отработало за 0.009 секунды

Answer 3

До кучи:

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

maxsum = 0
maxc = 0
cnt = 0
for m in range(2, 72):
    mm = m * m
    n = m - 1
    while (n > 0):
        if mm + n*n <= 5000 and gcd(n,m)==1:
            a = mm - n * n
            b = 2 * n * m
            c = n*n + mm
            for k in range(1, 5000//c+1):
                aa = k * a
                bb = k * b
                cc = k * c
                if aa + bb + cc > maxsum:
                    maxc = cc
                    maxsum = aa + bb + cc
                cnt += 1
        n -= 2

print(cnt, maxc)

БЛОГ НА HUSL

Найдите все пифагоровы тройки, в которых все числа находятся в диапазоне [1; 5000]

Ответы (3 шт):