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

Question

[AnanasMaks]

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

Comments

[AnanasMaks]

zero exception, https://kpolyakov.spb.ru/school/ege.htm

[AnanasMaks]

zero exception, да это егэ

Answer 1

[Vindicar]

Не пойму почему делаете так. Можно куда проще.
Можно сгенерировать список квадратов чисел:
squares = [i*i for i in range(1, 5001)]
При этом индекс элемента в списке i всегда будет на один меньше, чем число, чей квадрат находится по индексу i.
Теперь задача переформулируется таким образом: найти все пары чисел из этого списка, сумма которых тоже в этом списке.

for a,a2 in enumerate(squares, 1):
  for b,b2 in enumerate(squares[a:], a+1):
    if (a2+b2) in squares:
      c = squares.index(a2+b2) + 1
      print(a,b,c)

Работает не очень быстро, но работает.

EDIT: можно резко ускорить код, если учесть следующее: нам не обязательно искать сумму во всем списке. Мы знаем, что сумма будет больше чем b^2, т.е. будет иметь индекс больше чем b. Также мы знаем, что a^2 + b^2 < (a+b)^2, т.е. сумма будет иметь индекс меньше чем a+b. Отсюда:

for a,a2 in enumerate(squares, 1):
  for b,b2 in enumerate(squares[a:], a+1):
    if (a2+b2) in squares[b+1:a+b]:
      c = squares.index(a2+b2) + 1
      print(a,b,c)

Answer 2

[Сергей П]

Начните с самого простого не оптимизированного решения:
Вам нужно перебрать все целые A от 1 до 5000. Для каждого такого A вы можете перебрать все целые B от A+1 до 5000. Если корень из суммы их квадратов - целое число, то это, очевидно, тройка пифагора. Но вам нужно, чтобы C было меньше или равно 5000.
Для отимизации вы можете не спешить извлекать корень, а сперва проверить его на превышение 5000*"2. Так вы немного сэкономите. Ещё вы каждый раз можете вычислять правую границу внутреннего цикла, так вы будете искать решение среди вдвое меньшего количества вариантов.
Не знаю какие там требования сейчас по эффективности решения задачь, но для школьников такое решение я бы считал приемлемым. Да и не для школьников. Хотя н апитоне такая задача будет считаться с десяток секунд без оптимизаций. Однако временнЫе ограничения не были озвучены. Эдак и методом Монтекарло можно решать=)

Comments

[alexbprofit]

без оптимизации для 5000 задача будет решаться дня 3, уже посчитано

[Wataru]

alexbprofit, да ну... 125 миллиардов операций. Это пару минут. Ну, с запасом и тормозами - 10 минут максимум.

[Andy_U]

Внешний цикл можно делать не до 5000, а до int(5000/math.sqrt(2)). Чуть-чуть быстрее будет.

[Сергей П]

alexbprofit,
Да какие дня три?
Самый топорный способ у меня на ноуте 30 секунд работает.

In [22]: def task(lim=5000): 
    ...:     from math import sqrt 
    ...:     cnt = 0; maxsum = 0; maxc = None 
    ...:     for a in range(1, lim + 1): 
    ...:         for b in range(a + 1, lim + 1): 
    ...:             c = (a ** 2 + b ** 2) ** 0.5 
    ...:             if c <= lim and c - int(c) <  0.000000001: 
    ...:                 #print(a, b, c) 
    ...:                 cnt += 1 
    ...:                 if a + b + c > maxsum: 
    ...:                     maxsum = a + b + c; maxc=c 
    ...:     return cnt, maxc 
    ...:      
    ...:                                                                        

In [23]: %timeit task()                                                         
30.2 s ± 647 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

[Andy_U]

Сергей Паньков, А так:

import math


def main() -> None:

    count = 0
    max_abc = 0
    max_c = [0]

    for a in range(1, int(5000/math.sqrt(2))):
        a2 = a**2
        for b in range(a, 5001):
            c2 = a2+b**2
            if c2 > 25000000:
                break
            c = int(math.sqrt(c2)+0.5)
            if c**2 == c2:
                count += 1
                abc = a+b+c
                if max_abc < abc:
                    max_abc = abc
                    max_c = [c]
                elif max_abc == abc:
                    max_c.append(c)

    print()
    print(count)
    print(max_abc)
    print(max_c)


if __name__ == '__main__':
    import timeit
    print(timeit.timeit("main()", setup="from __main__ import main", number=1))

9 секунд на древнем i7 3770K.

А если применить pythran (давно хотел попробовать), то меньше секунды.

[Сергей П]

Andy_U, да это понятно. Я же хотел показать, что три дня никак не выходит, даже если решать максимально неэффективным способом.

[Andy_U]

Сергей Паньков, глядя на решения с тремя вложенными циклами, выходит.

Answer 3

[Alexandroppolus]

в википедии есть статья про пифагоровы тройки.
там приведена "формула евклида".
по ней можно быстро и беспощадно нагенерить примитивные тройки, которые потом ещё домножать на 2, 3, 4,...

https://ru.wikipedia.org/wiki/%D0%9F%D0%B8%D1%84%D...

Comments

[Wataru]

Даже не надо их генерировать. Достаточно перебрать n и m, найти k максимально возможное (поделив 5000 на c), прибавить к счетчику k. На максимум проверять надо 2km(m+n). У этого решения будет линейная сложность относительно ограничения на размер чисел.

[Alexandroppolus]

Wataru, точно, сами тройки и не нужны )
причем для перебора надо использовать m от 1 до sqrt(max), n от 1 по m-1.
и я подозреваю, что для тех чисел, которые требуются в ответе, можно смекнуть формулы и посчитать всё за O(1). Хотя нельзя сказать наверняка.

[Wataru]

Alexandroppolus, Я тоже сначала подумал про ответ за O(1). Даже какие-то формулы пытался выводить. Но там все не так просто, потому что надо, чтобы GCD(n,m) == 1, иначе тройки перебираются с повторами. Если и есть какая-то замкнутая формула, то там какой-нибудь ужас вроде дзетта-функции римана.

[Alexandroppolus]

Wataru, да, вы правы.. Получается, надо каждую пару (m,n) проверять на взаимную простоту. То есть линейной скорости не будет. Хотя можно поюзать линейное количество памяти, где для каждой взаимно простой пары (m,n) вычёркивать все (km,kn), тогда вроде получается O(N)

[Wataru]

Alexandroppolus, можно и с О(sqrt(5000)) памяти. Сначала решетом найти для всех чисел до корня минимальный простой делитель. А потом искать gcd сливая списки простых. Если аккуратно подсчитать сколько там суммарно простых делителей среди всех чисел - будет линия.

Answer 4

[alexbprofit]

# Брютфорс, найдите решение пооптимальнее
def get_all_thriads(size):
  res = []
  for i in range(1, size):
    for j in range(1, size):
      for k in range(1, size):
        if i**2 + j**2 == k**2:
          res.append([i, j, k])
  return res

# Тест (возможно наличие одинаковых троек но в разном порядке)
x = [print(el) for el in get_all_thriads(100)]

Comments

[alexbprofit]

например для числа 250 мое решение будет выполняться 25 секунд, а для 5000 - 3 дня

[Andy_U]

alexbprofit, А решение, предложенноое Сергеем Паньковым - меньше 10 секунд. Это без распараллеливания, использования Cython, numba, etc.

[Wataru]

alexbprofit, Ну не три дня ваше решение будет работать. Пару минут. Ну, 10 максимум. И, кстати, тройки по английски будет - triples а не triads.