xKVtor


http://algolist.manual.ru/maths/teornum/nod.php


Да, (смотрит в книжку еще раз) нужно еще чтобы p,q имели противоположную четность. Эти 3 условия (1. НОД(p,q)=1; 2. p>q; 3. p+q нечетное) - необходимые и достаточные.

ВСЕ ГОТОВО!!!

При lim=1000000 работает 0.171 сек. Не думаю, что можно будет придумать намного быстрее, т.к. здесь по-моему оптимизировано все что можно. Проверка на взаимную простоту наверное упрощена до предела...

xKVtor еще не прочитал твой пост - слишком много ты там намолотил...

theone
Вот счас всё закончите. А мне так и не ясно .. архитектурно: зачем это?
Если нужно найти все пифагоровы тройки и закатать их в массив, то зачем лимит времени (уж несколько дней совершенствуем, за это время на 386-м можно было-бы и спрограммировать по-тупому, и обсчитать).
Нужен ли этот массив сам-по-себе (как нам нужны таблицы Брадиса), или ещё какой то программный модуль (здесь не упомянутый) в нём шурует. Но неужели одному модулю целиком массив пифагоровых троек нужен ?
Или это учебная задача (тогда все вопросы снимаются, остаётся только негодование за тупой уч. процесс).

theone

Не думаю, что это быстрее алгоритма Евклида. По ссылке есть готовый С++ код , проверить легко.

xKVtor
Вроде все верно, но я не представляю как это можно применить на практике.
Насчет конструирования p и q из простых - интересная идея, но мне, если честно, не охота браться за ее реализацию. Не потому что она сложная, просто реализация будет громоздкой по сравнению с уже имеющимся вариантом, и я почти на 100% уверен, что быстрее она не будет.

Нельзя вводить такое ограничение, т.к. иногда нужно чтобы было a>b, а при выводе мы их просто поменяем местами если нужно.
Например, по ф-ле никак нельзя получить напрямую тройку [8;15;17], т.к. второе число 15 нельзя получить в виде 2*q*p. можно только получить аналогичную ей тройку [15;8;17], при p=4,q=1. Если мы введем ограничение p<q*(sqr(2)+1), то мы никогда не получим эту тройку, а она нам нужна, т.к. она простая и домножением мы ее получить не сможем.
Dometer

Просто учитель дал решить задачку (можно сказать просто на интерес, т.е. не за баллы), остальные сказали что сложная, я сказал что решу Все равно получилось интересно (по крайней мере для меня). Все начиналось c 9 сек. при lim=30000, а закончилось 0.171 сек. при lim=1000000, и меня это радует
vor
Еще не разбирался в этом алгоритме...

theone Похоже, объясняльщик из меня никудышний Постараюсь исправиться...

Попробую изложить материал немного по-другому.

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

АЛГОРИТМ:

Перебором p и q находим все тройки натуральных чисел a, b, c (все три числа <MAX) по формуле(-ам):

a=p^2-q^2
b=2*p*q
c=p^2+q^2

Если все числа в тройке четные, то делим их на два и полученную тройку запоминаем.
Если все числа в тройке нечетные, то эту тройку также запоминаем.

NB: Фактически в результате всех этих операций получаем взаимно простые тройки чисел.

Если требуется найти ВСЕ, а не только взаимно-простые решения уравнения a^2+b^2=c^2, то каждую полученные тройку a,b,c домножаем на натуральное число s, которое пробегает значения от 1 до (MAX/c).

Ограничения, налагаемые на p и q:

• p и q - взаимно простые натуральные;
• q<p<q*(sqrt(2)+1)
• p<sqrt(MAX)
• q<sqrt(MAX)
• p*q<MAX/2

Теперь самое интересное: откуда взялись упомянутые ограничения ?

q<p

a-натуральное => a>0 => a=p^2-q^2>0 (p>0, q>0) => p>q

p<sqrt(MAX)

a<MAX => a=p^2-q^2<MAX
c<MAX => c=p^2+q^2<MAX

a+c=(p^2-q^2)+(p^2+q^2)=2*p^2<2*MAX => p^2 < MAX => p<sqrt(MAX)

q<sqrt(MAX)

q<p => q<p<sqrt(MAX)

p*q<MAX/2

b<MAX => b=2*p*q<MAX (p>0, q>0) => p*q<MAX/2

p и q - взаимно простые

Из "теоремы" #1, которую я пытался доказать в своем прошлом суперпосте , следует, что тройки, полученные на основе p и q, имеющие общий делитель (частный случай: Н.О.Д.=d), можно получить простым домножением тройки, полученной на основе p'=p/d и q'=q/d, на (d^2).

Но это почти очевидно

А теперь самый спорный момент:

p<q*(sqrt(2)+1)

Для начала можно доказать еще одно утверждение:

'Теорема' #4:

Если тройка a,b,c образована на основе взаимнопростых p и q, то все числа этой тройки:

* либо взаимнопросты (в случае если суммы p+q и p-q нечетны),
* либо четны (в случае если суммы p+q и p-q четны).

Док-во:

Пусть: x,y - натуральные

(p+q)=2*x
(p-q)=2*y

a=p^2-q^2=(p^2+2*p*q+q^2)-2*p*q-2*q^2=(p+q)^2-2*q*(p+q)=2*2*x^2-2*q*x=2*x*(2*x^2-q) - четное
b=2*q*p - четное
c=p^2+q^2=p^2+q^2+2*q*p-2*q*p=(p+x)^2-2*q*p=2*2*x^2-2*q*p=2*(2*x^2-q*p) - четное# {хватит пока такого доказательства }

Примечание:
Поскольку p и q у нас взаимнопростые (и одновременно четными быть не могут), то сумма (p+q) будет:
* четной, когда оба числа p,q -- нечетные
* нечетной, если одно из чисел четное, а другое -- нет.

Итак, если у нас (p+q)-четное, то получаем тройку a1,b1,c1 вида:

a1=2*b2
b1=2*a2
c1=2*c2

По теореме, обратной 'теореме' #2, из исходной тройки получаем дополнительную a2,b2,c2, обладающую интересными свойствами:

1. она состоит из взаимнопростых чисел.
2. a2>b2, следовательно эта тройка принадлежит другому диапазону(#2): p>q*(sqrt(2)+1);

Напомню: как доказывалось в 'теореме' #3, для того, чтобы:

a<b => p<q*(sqrt(2)+1); {диапазон#1}
a>b => p>q*(sqrt(2)+1); {диапазон#1}

Эти два неравенства образуют два диапазона: #1 и #2.

Чтобы получить эту тройку (a2,b2,c2) простым перебором чисел во втором диапазоне, нам потребовалось бы несколько итераций. А тут мы ее нахаляву получаем из первого диапазона. Неплохая экономия вычислительных ресурсов и времени

На всякий случай приведу формулирвку теоремы, обратной 'теореме' #2:

Если на основе взаимнопростых p1 и q1 найдена тройка a1,b1,c1, такая, что все ее элементы кратны числу k (a1=k*b2,b1=k*a2,c1=k*c2), то тройка a2,b2,c2 так же будет удовлетворять условию a2^2+b2^2=c2^2 и ее элементы будут являться взаимно простыми (ее основа при k=2: p2=(p1+q1)/2; q2=(p1-q1)/2).

{Эта обратная теорема доказывается аналогично прямой, но набивать лениво}

Ну, на сегодня хватит, пожалуй.
Жду вопросов. Признаюсь, у самого есть небольшие смутные подозрения...

ЗЫ:На практике еще не проверял. Надо будет попробовать.

xKVtor

Эффективнее взять q<=sqrt(MAX/2), т.к. из q>sqrt(MAX/2) => qq>MAX/2 => 2qq>MAX => qq+pp>MAX (т.к. qq<pp), т.е. q, большие чем sqrt(MAX/2), нам не нужны.

Эффективнее взять p<=sqrt(MAX-pp), т.к. из p>sqrt(MAX-pp) => pp>MAX-qq => qq+pp>MAX, т.е. p, большие чем sqrt(MAX-pp), нам не нужны.

Опечатка - a=pp-qq=...=2x(2x-2p)

Опечатка - не (p+x)^2, а x^2, или (p+q)^2.

По-моему лишнее условие.

Твоя главная ошибка. Всегда сначала доказываются дополнительные теоремы, а потом на основе их выводится главная. Дополнительные при этом, вроде бы, называются леммами. На правильность основной теоремы это не влияет, но такой порядок ОЧЕНЬ облегчает понимание. Все дополниетельные ограничения тоже налагаются перед теоремой.

Ты доказываешь теорему только когда (p+q) и (p-q) - четные, и дальнейшие свои рассуждения ты ведешь только при (p+q) - четном. Но, я уже приводил тебе пример: p=4,q=1 (кстати p+q=5 - НЕчетное) - тройка [15;8;17]. Ты, введя ограничение p<q*(sqrt(2)+1), НИКОГДА не получишь эту тройку, НИКАКИМ домножением и НИКАКИМИ перестановками a и b (т.к. тройку [8;15;17] ты тоже НИКОГДА не найдешь по формуле (причина выше)).

Тройка [15;8;17] принадлежит второму диапазону, т.к. 4>1*(sqrt(2)+1). Как ты ее собираешься получать из 1-го диапазона, я не представляю.

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

Не понял: pp это p*p=p^2 ? Тогда это условие лучше не проверять, т.к придется каждый раз для нового (MAX-p*p) заново высчитывать корень -- лишние расходы ресурсов -- быстрее высчитать a,b,c


Сорри за очепятки -- печатал под утро, очень спать хотелось, поэтому мессагу отослал без проверки
Кстати, будет все таки: 2x(2x-2q)


Кстати, условие не такое уж и лишнее.
Из p*q<MAX/2 и q<p => q*q<p*q<MAX/2 => q<sqrt(MAX/2)
Спасибо за наводку.

Сорри, я уж лет десять как никаких дел с теоремами и леммами не имею. Изъяснялся как мог. Если какие-то непонятки возникнут, постараюсь объяснить более подробно. Только спрашивайте


Если (p+q) - четное, то и (p-q) так же будет четным.
Доказательства теоремы для (p-q)-- аналогичны.



При переборе чисел из "диапазона #1" мне попадется парочка взаимнопростых p=5, q=3:

{5<3*(sqrt(2)+1)~3*2.41=7.23 => p,q принадлежат диапазону №1}

p=5, q=3 => a=25-9=16; b=2*5*3=30; c=25+9=34

Поскольку (p+q)=(5+3)=8 и (p-q)=(5-3)=2 -- четные,
то элементы полученной тройки делим на 2.
Получаем (16/2, 30/2; 34/2) => (8; 15; 17)

Попутно замечаем, что ту же самую тройку (точнее, (15; 8; 17)) мы нашли бы, если бы перебирали числа p',q' во втором диапазоне и нарвались на p'=(p+q)/2=(5+3)/2=4 и q'=(p-q)/2=(5-3)/2=1. Но как теперь уже, надеюсь, всем ясно, перебирать второй диапазон нет никакой необходимости


См. выше

Добавлено спустя 45 минут, 4 секунды:
Кстати, не обязательно выбирать в качестве основного именно Диапазон№1. Можно вести поиск только во втором. Даже нужно, если в нем число проверяемых ограничительных условий будет меньше.

Вообще, наиболее выгодный диапазон перед поиском лучше выбрать по графику p(q), на который нанесены все упомянутые ограничения.

ЗЫ: Естественно, во время работы алгоритма диапазон менять уже нельзя Выбор диапазона осуществляется только перед началом поиска. Но это я так, напомнил на всякий случай

PPS: Как показывает практика, бесплатного сыра не бывает Так и тут. Упустил из вида одну деталь: в случае четного (p+q) после деления на 2 полученной тройки числа a,b,c при указанных условиях никогда не будут превышать половины диапазона (MAX).

Так что наверное проще считать по обоим диапазонам, а результаты при четном (p+q) не искать вовсе Ну, теперь хоть прояснилось, почему их надо пропускать...

xKVtor

Опечатка конечно: не pp (p*p), а qq (q*q).
Зато такие ограничения (q<=sqrt(MAX/2), p<=sqrt(MAX-q*q)) позволяют не беспокоиться о том, что c может превысить MAX, т.к. при таких p и q: c=p*p+q*q<=MAX => проверка c<=MAX не нужна. Хотя все это, конечно, не очень важно.

Теперь понятно. Наконец-то до меня дошло

Вот-вот. Попробовал реализовать твой алгоритм, и ответ получился неверным - получается меньше троек, и, скорее всего, из-за этой детали.

Правильно В этом случае при использовании алгоритма Евклида программа работает 0.015-0.031 сек. при lim=1000000. Быстрее, я думаю, уже вряд ли получится.

А вот и конечный код:

Кстати, если считать только кол-во троек (как в программе), то проверка c<=MAX вообще не нужна, и даже если случайно завысить пределы p и q, то ошибки не будет, т.к. если p*p+q*q>MAX (MAX=lim), то счетчик не будет расти по причине того, что целая часть от [b]lim/(p*p+q*q)[/q] будет равна 0.

theone

Не пробовал максимальный возможный лимит определить ? А то один жалкий миллион -- несерьезно как-то
Вот 4 миллиарда (2^32) уже впечатлило бы...

Сколько, кстати, в итоге получилось троек ? (простых и после домножения, в пределах лимона и при MAX->2^32)

Думаю, тем кто пойдет по твоим стопам, подобная информация пригодилась бы для самопроверки.

Нехилый разброс, аж в 2 раза... А почему бы не прогнать этот алгоритм пару сотен раз, а затем полученное время не поделить на число прогонов ?

xKVtor

Пробовал только миллиард (около 2^30) - работает 35 сек.

lim --- кол-во всех троек -- кол-во простых троек --- время работы (сек.)

1.000.000.000 --- 3.080.075.432 --- 159.154.994 --- 35
100.000.000 --- 271.360.653 --- 15.915.492 --- 3,25
10.000.000 --- 23.471.475 --- 1.591.579 --- 0,281
1.000.000 --- 1.980.642 --- 159.139 --- 0,0247
10.000 --- 12.471 --- 1.593 --- 0

Кстати, можно заметить, что приблизительно
s=lim*k
где s - кол-во простых троек, k=0,15915 (приблизительно). Т.е. между lim и s почти прямопропорциональная зависимость.