1

Given some $b \in \mathbb Z^+$, efficiently find all values for $a \in \mathbb Z^+$ such that...

  • $1 \le a \le b$.
  • $a^2 + b^2$ is a perfect square.

Efficiently means with a method faster than testing all the values in $[1, b]$.

quadrupleslap
  • 143
  • 1
    What have you tried? Your question sounds like it has been copied and pasted - please show your work so that we can help you better. – Toby Mak Dec 28 '17 at 06:30
  • =\ I spent half an hour wording that. Anyway, like I said in the question, I can't find any method faster than testing all the values in $[1, b]$, or testing all values of $c$ in $[\sqrt{1 + b^2}, \sqrt{2}b]$, which isn't any faster. – quadrupleslap Dec 28 '17 at 06:38
  • Sorry for the misunderstanding. I suggest to use the property that all squares are $0$ or $1$ $\pmod 4$ - so if $b = 5$, since $5 \equiv 1 \pmod 4$, then $a^2$ cannot be $1$ or $2$ $\pmod 4$, which rules out the cases $a = 1, 3, 5$. – Toby Mak Dec 28 '17 at 06:49
  • see matching sides of Pythagorean triples – poetasis May 27 '19 at 17:25

2 Answers2

0

It is necessary to expand the number in $b^2$ into two different factors $b^2=p_1\cdot p_2$ where $p_1<p_2$ and both of them even or both of them odd. Then solve the system of equations:$$c-a=p_1; c+a=p_2$$ $$c=\frac{p_1+p_2}{2}; a=\frac{p_2-p_1}{2}$$

aid78
  • 1,565
0

There is definitely a faster way of finding specific triples than testing all values of $x^2+B^2$.

To find Pythagorean triples with a given side B, we begin with the function: $$n=\frac{B}{2m}\text{ where }\biggl\lceil\sqrt{\frac{B}{2}}\space\space\biggr\rceil\le m\le\frac{B}{2}\text{ and selecting integer values of }n.$$

Sometimes $A>B$. For example triples with side $B=20$. $$\biggl\lceil\sqrt{\frac{B}{2}}\space\space\biggr\rceil=5\le m \le \frac{B}{2}=10$$ In the search we find $f(5,2)=(21,20,29)\text{ and }f(10,1)=(99,20,101).$

Somtimes $A$ can be greater than $and$ less than the same length $B$.

If we want to match sides with $(11,60,61)$, we let $m=6\text{ to} 30$ and select the integer values of $n$. $$\text{For }(m,n)\qquad A=m^2-n^2\qquad B=2mn\qquad C=m^2+n^2$$

$$f(6,5)=(11,60,61)\quad f(10,3)=(91,60,109)\quad f(15,2)=(221,60,229)\quad f(30,1)=(899,60,901)$$

poetasis
  • 6,338