Сверхъестественные пифагоровы тройки до 100 разрядов

[mathpath]

Ende
Выделено из темы «интерактивный курс: введение в программирование на PARI/GP»

В проекте эйлера лежит Задача 835
https://euler.jakumo.org/problems/view/835.html

Нужно найти все т.н. сверъестественные пифагоровы тройки, у которых периметр укладыватеся вплоть до 100 разрядов
Тут достаточно перебрать примитивные пифагоровы тройки, используя формулу Евклида
Я честно запустил вложенный цикл и понял, что результат буду ждать до второго пришествия
А как бы вы решили эту задачу ?

Ниже прилагаю код на питоне:

(Оффтоп)

import math 

sum = 0
count = 0
for m in range(1,1000000):
    for n in range(1,1000000):
        if math.gcd(m, n) == 1:
            a =  (m**2 - n**2)
            if a <= 0:
                continue
            b =  (2*m*n)
            c =  (m**2 + n**2)
            if abs(a - b) == 1 or abs(b - c) == 1:
                    p = a+b+c
                    count += 1
                    print('count=%s m=%s n=%s    %s² + %s² = %s² p=%s' %(count, m, n,  a, b, c, p))

[wrest]

mathpath в сообщении #1660516 писал(а):

Я честно запустил вложенный цикл и понял, что результат буду ждать до второго пришествия

Ну у меня пустой цикл (в кором только делается c++) идёт со скоростью 4 млн/с.
Соотвественно, пустой цикл на $10^{12}$ повторений будет идти около 70 часов...

[wrest]

В качестве вспоможения.
Сумма периметров треугольников, у которых катет и гипотенуза отличаются на единицу, даётся формулой
$S_1(n)=n(4n^2 + 15n + 17)/3$ где $n$ - порядковый номер такого треугольника, 1-й треугольник $3,4,5$ и $S_1(1)=12$, $S_1(2)=42$ -- сумма периметров $(3+4+5)+(5+12+13)$
Периметры треугольников, у которых два катета отличаются на единицу, даётся формулой:
$P_2(n)=2a+1+\sqrt{2a^2+2a+1}$ где $a(n)=\dfrac{(3+2\sqrt{2})^n - (3-2\sqrt{2})^n}{ 2\sqrt{2}}$ - меньший катет.
Периметр второго типа достигает $10^{100}$ примерно при $n=130$
Возможно формулу для периметра второго типа как-то можно упростить и вывести сумму. Но если и нет, суммировать придётся не более чем около 130 раз.
Для программирования подойдёт рекуррентная формула $P_2(n) = 6P_2(n-1) - P_2(n-2)$ где $P_2(0)=0$ ; $P_2(1)=2$.
В обе категории попадает только египетский треугольник, и $P_2(2)=12$ - соответствует египетскому треугольнику $3,4,5$, а $P_2(3)=70$ соответствует следующему такому треугольнику $20,21,29$
То что хотят найти, $S(100)=S_1(4)+P_2(3)=288$; $S(10000)=S_1(49)+P_2(3)+P_2(4)+P_2(5)=172004$

А... погодите, вам же надо периметры в $10^{10}$ знаков? Тут нужен другой подход.

[wrest]

wrest в сообщении #1660546 писал(а):

где $a(n)=\dfrac{(3+2\sqrt{2})^n - (3-2\sqrt{2})^n}{ 2\sqrt{2}}$ - меньший катет

Тут кажись ошибка. Но далее рекуррентнкя формула для периметра -- верная.

[wrest]

mathpath в сообщении #1660516 писал(а):

А как бы вы решили эту задачу ?

Итого.
Есть две последовательности нужных треугольников.
Первая последовательность - треугольники вида $a^2+b^2=(b+1)^2$
Их периметры нумеруются по возрастанию такой формулой $P_1(n)=4n^2+6n+2$, нумерация с $n=1$.
Соответственно, вам надо найти такое $n$, что $P_1(n)\le N$, после чего подставить его в формулу суммы $S_1(n)$ и вычислить сумму по нужному модулю $S_1(n) \pmod {1234567891}$

Вторая последовательность - треугольники вида $a^2+(a+1)^2=c^2$
Формула для периметра дана ранее. Здесь то же самое -- найти такое $m$ что периметр $ P_2(m)\le N$
Тут будет посложнее т.к. формула периметра рекуррентная (а прямая формула - это числа с плавающей точкой, можно и ими, но нужна чрезвычайно высокая точность плавающей точки) и замкнутой формулы суммы периметров пока нет.
Учтите что тут нумерация начинается с $m=3$. Ну и дальше просуммировать $S_2(m)\equiv \sum \limits_{i=3}^{m}P_2(i) \pmod {1234567891}$ по модулю.

Потом две полученные суммы сложить по модулю, ответ будет $S(N)\equiv S_1(n)+ S_2(m) \pmod {1234567891}$
Как написано ранее, для $N=10^4$ получаются $n=49,m=5$

P.S. Учтите, что в задаче просят $N=10^{10^{10}}=10^{10000000000}$ а не гугол $N=10^{100}$

[wrest]

Upd В общем, если запрограммируете, то для проверки, $S(10^{100}) \equiv 587822899 \pmod {1234567891}$ и
$n=5\cdot 10^{49}-1$
$m=131$
Наверное