Nonhypotenuse number

{{Short description|Number whose square is not the sum of 2 non-zero squares}}

File:Triangle345.svg

In mathematics, a nonhypotenuse number is a natural number whose square cannot be written as the sum of two nonzero squares. The name stems from the fact that an edge of length equal to a nonhypotenuse number cannot form the hypotenuse of a right angle triangle with integer sides.

The numbers 1, 2, 3, and 4 are all nonhypotenuse numbers. The number 5, however, is not a nonhypotenuse number as $5^2\; =\; 3^2\; +\; 4^2$.

The first fifty nonhypotenuse numbers are:

:1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 14, 16, 18, 19, 21, 22, 23, 24, 27, 28, 31, 32, 33, 36, 38, 42, 43, 44, 46, 47, 48, 49, 54, 56, 57, 59, 62, 63, 64, 66, 67, 69, 71, 72, 76, 77, 79, 81, 83, 84 {{OEIS|id=A004144}}

Although nonhypotenuse numbers are common among small integers, they become more-and-more sparse for larger numbers. Yet, there are infinitely many nonhypotenuse numbers, and the number of nonhypotenuse numbers not exceeding a value x scales asymptotically with x/{{radic|log x}}.{{citation|author=D. S.|last2=Beiler|first2=Albert H.|title=Albert Beiler, Consecutive Hypotenuses of Pythagorean Triangles|jstor=2004563|journal=Mathematics of Computation|volume=22|issue=103|year=1968|pages=690–692|doi=10.2307/2004563}}. This review of a manuscript of Beiler's (which was later published in J. Rec. Math. 7 (1974) 120–133, {{MR|0422125}}) attributes this bound to Landau.

The nonhypotenuse numbers are those numbers that have no prime factors of the form 4k+1.{{citation|first=D.|last=Shanks|authorlink=Daniel Shanks|title=Non-hypotenuse numbers|journal=Fibonacci Quarterly|volume=13|issue=4|year=1975|pages=319–321|doi=10.1080/00150517.1975.12430618 |mr=0387219}}. Equivalently, they are the number that cannot be expressed in the form $K(m^2+n^2)$ where K, m, and n are all positive integers. A number whose prime factors are not {{em|all}} of the form 4k+1 cannot be the hypotenuse of a primitive integer right triangle (one for which the sides do not have a nontrivial common divisor), but may still be the hypotenuse of a non-primitive triangle.{{citation|last1=Beiler|first1=Albert|title=Recreations in the Theory of Numbers: The Queen of Mathematics Entertains|url=https://archive.org/details/recreationsinthe0000beil|url-access=registration|date=1966|publisher=Dover Publications|location=New York|isbn=978-0-486-21096-4|page=[https://archive.org/details/recreationsinthe0000beil/page/116 116-117]|edition=2}}

The nonhypotenuse numbers have been applied to prove the existence of addition chains that compute the first $n$ square numbers using only $n+o(n)$ additions.{{citation|last1=Dobkin|first1=David|author1-link=David P. Dobkin|last2=Lipton|first2=Richard J.|author2-link=Richard Lipton|doi=10.1137/0209011|issue=1|journal=SIAM Journal on Computing|mr=557832|pages=121–125|title=Addition chain methods for the evaluation of specific polynomials|volume=9|year=1980}}