Nonhypotenuse number

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 (sequence A004144 in the OEIS)

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/√log x.^[1]

The nonhypotenuse numbers are those numbers that have no prime factors of the form 4k+1.^[2] 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 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.^[3]

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.^[4]

References

^ D. S.; Beiler, Albert H. (1968), "Albert Beiler, Consecutive Hypotenuses of Pythagorean Triangles", Mathematics of Computation, 22 (103): 690–692, doi:10.2307/2004563, JSTOR 2004563. This review of a manuscript of Beiler's (which was later published in J. Rec. Math. 7 (1974) 120–133, MR0422125) attributes this bound to Landau.
^ Shanks, D. (1975), "Non-hypotenuse numbers", Fibonacci Quarterly, 13 (4): 319–321, doi:10.1080/00150517.1975.12430618, MR 0387219.
^ Beiler, Albert (1966), Recreations in the Theory of Numbers: The Queen of Mathematics Entertains (2 ed.), New York: Dover Publications, p. 116-117, ISBN 978-0-486-21096-4
^ Dobkin, David; Lipton, Richard J. (1980), "Addition chain methods for the evaluation of specific polynomials", SIAM Journal on Computing, 9 (1): 121–125, doi:10.1137/0209011, MR 0557832

External links

[1] D. S.; Beiler, Albert H. (1968), "Albert Beiler, Consecutive Hypotenuses of Pythagorean Triangles", Mathematics of Computation, 22 (103): 690–692, doi:10.2307/2004563, JSTOR 2004563. This review of a manuscript of Beiler's (which was later published in J. Rec. Math. 7 (1974) 120–133, MR0422125) attributes this bound to Landau.

[2] Shanks, D. (1975), "Non-hypotenuse numbers", Fibonacci Quarterly, 13 (4): 319–321, doi:10.1080/00150517.1975.12430618, MR 0387219.

[3] Beiler, Albert (1966), Recreations in the Theory of Numbers: The Queen of Mathematics Entertains (2 ed.), New York: Dover Publications, p. 116-117, ISBN 978-0-486-21096-4

[4] Dobkin, David; Lipton, Richard J. (1980), "Addition chain methods for the evaluation of specific polynomials", SIAM Journal on Computing, 9 (1): 121–125, doi:10.1137/0209011, MR 0557832

[1]

[2]

[3]

[4]

See also

References

External links