интерактивный курс: введение в программирование на PARI/GP

[wrest]

kotenok gav в сообщении #1443915 писал(а):

Так у меня вопрос про пиф. тройки в PARI. Там есть встроенный алгоритм?

А что вообще имеется в виду под "встроенным алгоритмом пифагоровых троек"?
В общем, встроенного нет, но например вот вам функция которая тупо проверяет является ли тройка пифагоровой
is_pt(a,b,c)=my(v=[a,b,c]);v=vecsort(v);if(v[3]^2==v[1]^2+v[2]^2,1,0)
без проверки на натуральность чисел. Вот функция, которая проверяет является ли тройка пифагоровой и при этом примитивной
is_ppt(a,b,c)=my(v=[a,b,c]);v=vecsort(v);if(v[3]^2==v[1]^2+v[2]^2,if(gcd(v[1],v[2])==1,1,0),0)
и т.п.

[kotenok gav]

Я спрашиваю про их генерацию.

[dmd]

еще проверка на целостность if(n==floor(n),

[wrest]

kotenok gav в сообщении #1443995 писал(а):

Я спрашиваю про их генерацию.

Нет, встроенного генератора пифагоровых троек в pari/gp не имеется.

[VAL]

А стандартная генерация делается так:
Пусть $u>v$ - натуральные числа, причем $u$ и $v$ взаимно просты и разной четности. Тогда $a=u^2-v^2, b=2uv, c=u^2+v^2$ - примитивная пифагорова тройка. И все примитивные пифагоровы тройки получаются так.

[kotenok gav]

Не, это ясно. Как взаимнопростые числа генерировать?

-- 10 мар 2020, 21:04 --

Хотя... Вроде ясно, просто циклом перебираем квадраты меньшие c.

[wrest]

kotenok gav
Для проверки, является ли c гипотенузой примитивного пифагорова треугольника, вот вам функция:
is_primitive_hypotenuse(c)=Set(factor(c)[,1]%4)==[1]
Взято из A008846

Для разложения числа в сумму двух квадратов натурпльных чисел, насколько мне известно, простых путей нет.

[Dmitriy40]

(Оффтоп)

wrest
А почему 25 является примитивной гипотенузой? Ведь она же имеет общий множитель 5 со всеми сторонами. Или имелось в виду что она может быть в треугольнике (7,24,25)?
Ну и ещё мне кажется проверить gcd трёх чисел проще/быстрее факторизации, хотя конечно надо бы проверять.

[wrest]

Dmitriy40 в сообщении #1444178 писал(а):

Ну и ещё мне кажется проверить gcd трёх чисел проще/быстрее факторизации, хотя конечно надо бы проверять.

Вот это я не понял к чему.

[Dmitriy40]

(Оффтоп)

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

Dmitriy40 в сообщении #1444178 писал(а):

Ну и ещё мне кажется проверить gcd трёх чисел проще/быстрее факторизации, хотя конечно надо бы проверять.

Вот это я не понял к чему.

Разве не так определяется примитивность тройки чисел и в частности гипотенузы? ОК, значит я не прав с понятием примитивности гипотенузы.
Как я понял эта функция всего лишь проверяет что число раскладывается на простые вида $4k+1$ в любой степени, не более того. Связь этого с примитивностью хоть треугольника, хоть гипотенузы, мне не видна.

[wrest]

Dmitriy40 в сообщении #1444185 писал(а):

Связь этого с примитивностью хоть треугольника, хоть гипотенузы, мне не видна.

См. Лемму 1 тут: https://planetmath.org/primefactorsofpy ... ypotenuses

[Dmitriy40]

Хм, но по ссылке оттуда на mathworld.wolfram.com прямо сказано что примитивным треугольником является треугольник со сторонами, GCD которых равен 1. Что я и сказал, что gcd проще факторизации. Да и проверять можно лишь две стороны.
Про лемму ничего сказать не могу, с простыми в кольце разбираться лень. Впрочем в условие $4k+1$ верю (небольшого контрпримера не нашёл).

[RIP]

Dmitriy40 в сообщении #1444245 писал(а):

gcd проще факторизации

Дана только «гипотенуза» $c$ и спрашивается, можно ли подобрать «катеты» $a,b$, чтобы получилась примитивная пифагорова тройка. Это можно сделать тогда и только тогда, когда все простые делители числа $c$ имеют вид $4k+1$.

[Dmitriy40]

Всех приветствую.
При написании программы по алгоритму Andrey A столкнулся с необходимостью раскладывать некое вещественное число (точнее квадратный корень из него если это чем-то поможет) в цепную дробь, а также получать из неё подходящие (вики называет их так) дроби в виде $P/Q$. Порыскав по документации к PARI/GP нашёл функции contfrac для первого и contfracpnqn для второго. Засада с ними в том что они требуют точного указания числа членов разложения, а мне в программе было бы удобнее (и быстрее!) раскладывать итерационно, получая член за членом и останавливаясь когда станет достаточно (пока не знаю как это заранее оценить). Делать разложение руками невыгодно, слишком медленно (на порядок).

Потому вопрос номер раз: нет ли готовой встроенной функции для разложения числа в цепную дробь рекурентно/итерационно? Возможно я что-то не нашёл или не понял в доке.

Вопрос номер два: а как попроще получить (понятно что примерно) исходное вещественное число из заданной цепной дроби? Руками собирать обратно это извращение, пока могу лишь натравить на неё contfracpnqn и взять любое приближение. Нет ли способа проще и быстрее?

Вопрос номер три:

? \p
   realprecision = 28 significant digits
? contfrac(sqrt(176),2)
%1 = [13, 3]
? contfrac(sqrt(176),3)
%2 = [13, 4]
? contfrac(sqrt(176),4)
%3 = [13, 3, 1, 3]
? contfrac(sqrt(176),5)
%4 = [13, 3, 1, 3, 26]
? contfrac(sqrt(176),6)
%5 = [13, 3, 1, 3, 26, 3]

Почему вместо трёх элементов функция вернула лишь два?! Нет, понятно, что-то там с округлением, но почему не вернула $[13,3,1]$, оно же равно $[13,4]$? Это просто мрак!

[iifat]

Dmitriy40 в сообщении #1490309 писал(а):

$[13,3,1]$, оно же равно $[13,4]$?

Оно-то равно, но показанная вами неоднозначность характерна для всех чисел, по каковой причине в определение (ссылки не нашёл, но точно помню) дроби включено требование, чтоб последний элемент был больше единицы.
Кстати говоря, вы помните, что непрерывные дроби квадратных корней натурального периодичны? Это могло б помочь. Может быть.

-- 02.11.2020, 03:37 --

И да, что там может быть с округлением? У вас исключительно целые участвуют в вычислениях!