Square Number

A square number, also called a perfect square, is a figurate number of the form , where is an integer. The square numbers for , 1, ... are 0, 1, 4, 9, 16, 25, 36, 49, ... (OEIS A000290).

A plot of the first few square numbers represented as a sequence of binary bits is shown above. The top portion shows to , and the bottom shows the next 510 values.

The generating function giving the square numbers is

The st square number is given in terms of the th square number by

since

which is equivalent to adding a gnomon to the previous square, as illustrated above.

The th square number is equal to the sum of the st and th triangular numbers,

as can seen in the above diagram, in which the st triangular number is represented by the white triangles, the th triangular number is represented by the black triangles, and the total number of triangles is the square number (R. Sobel, pers. comm.).

Square numbers can also be generated by taking the product of two consecutive even or odd numbers and adding 1. The result obtained by carrying out this operation is then the square of the average of the initial two numbers,

As a part of the study of Waring's problem, it is known that every positive integer is a sum of no more than 4 positive squares (; Lagrange's four-square theorem), that every "sufficiently large" integer is a sum of no more than 4 positive squares (), and that every integer is a sum of at most 3 signed squares (). Actually, the basis set for representing positive integers with positive squares is , so 49 need never be used. Furthermore, since an infinite number of require four squares to represent them, the least integer such that every positive integer beyond a certain point requires squares is given by .

The number of representation of a number by squares, distinguishing signs and order, is denoted and called the sum of squares function. The minimum number of squares needed to represent the numbers 1, 2, 3, ... are 1, 2, 3, 1, 2, 3, 4, 2, 1, 2, ... (OEIS A002828), and the number of distinct ways to represent the numbers 1, 2, 3, ... in terms of squares are 1, 1, 1, 2, 2, 2, 2, 3, 4, 4, ... (OEIS A001156). A brute-force algorithm for enumerating the square partitions of is repeated application of the greedy algorithm. However, this approach rapidly becomes impractical since the number of representations grows extremely rapidly with , as shown in the following table.

The th nonsquare number is given by

where is the floor function, and the first few are 2, 3, 5, 6, 7, 8, 10, 11, ... (OEIS A000037).

The only numbers that are simultaneously square and pyramidal (the cannonball problem) are and , corresponding to and (Ball and Coxeter 1987, p. 59; Ogilvy 1988; Dickson 2005, p. 25), as conjectured by Lucas (1875, 1876) and proved by Watson (1918). The cannonball problem is equivalent to solving the Diophantine equation

(Guy 1994, p. 147).

The only numbers that are square and tetrahedral are , , and (giving , , and ), as proved by Meyl (1878; cited in Dickson 2005, p. 25; Guy 1994, p. 147). In general, proving that only certain numbers are simultaneously figurate in two different ways is far from elementary.

To find the possible last digits for a square number, write for the number written in decimal notation as (, , 1, ..., 9). Then

so the last digit of is the same as the last digit of . The following table gives the last digit of for , 1, ..., 9 (where numbers with more that one digit have only their last digit indicated, i.e., 16 becomes _6). As can be seen, the last digit can be only 0, 1, 4, 5, 6, or 9.

We can similarly examine the allowable last two digits by writing as

so

so the last two digits must have the last two digits of . Furthermore, the last two digits can be obtained by considering only , 1, 2, 3, and 4, since

has the same last two digits as (with the one additional possibility that in which case the last two digits are 00). The following table (with the addition of 00) therefore exhausts all possible last two digits.

The only 22 possibilities are therefore 00, 01, 04, 09, 16, 21, 24, 25, 29, 36, 41, 44, 49, 56, 61, 64, 69, 76, 81, 84, 89, and 96, which can be summarized succinctly as 00, , , 25, , and , where stands for an even number and for an odd number. Additionally, a necessary (but not sufficient) condition for a number to be square is that its digital root be 1, 4, 7, or 9. The digital roots of the first few squares are 1, 4, 9, 7, 7, 9, 4, 1, 9, 1, 4, 9, 7, ... (OEIS A056992), while the list of number having digital roots 1, 4, 7, or 9 is 1, 4, 7, 9, 10, 13, 16, 18, 19, 22, 25, ... (OEIS A056991).

This property of square numbers was referred to in a "puzzler" feature of a March 2008 broadcast of the NPR radio show "Car Talk." In this Puzzler, a son tells his father that his computer and math teacher assigned the class a problem to determine if a number is a perfect square. Each student is assigned a particular number, and the students are supposed to write a software program to determine the answer. The son's assigned number was . While the father thinks this is a hard problem, a bystander listening to the conversation states that the teacher gave the son an easy number and the bystander can give the answer immediately. The question is what does this third person know? The answer is that the number ends in the digit "2," which is not one of the possible last digits for a square number.

The following table gives the possible residues mod for square numbers for to 20. The quantity gives the number of distinct residues for a given .

In general, the odd squares are congruent to 1 (mod 8) (Conway and Guy 1996). Stangl (1996) gives an explicit formula by which the number of squares in (i.e., mod ) can be calculated. Let be an odd prime. Then is the multiplicative function given by

is related to the number of quadratic residues in by

for (Stangl 1996).

For a perfect square , or 1 for all odd primes where is the Legendre symbol. A number that is not a perfect square but that satisfies this relationship is called a pseudosquare.

In a Ramanujan conference talk, W. Gosper conjectured that every sum of four distinct odd squares is the sum of four distinct even squares. This conjecture was proved by M. Hirschhorn using the identity

where , , , and are positive or negative integers. Hirschhorn also showed that every sum of four distinct oddly even squares is the sum of four distinct odd squares.

A prime number can be written as the sum of two squares iff is not divisible by 4 the (Fermat's 4n+1 theorem). An arbitrary positive number is expressible as the sum of two squares iff, given its prime factorization

none of is divisible by 4 (Conway and Guy 1996, p. 147). This is equivalent the requirement that all the odd factors of the squarefree part of are equal to 1 (mod 4) (Hardy and Wright 1979, Finch). The first few numbers that can be expressed as the sum of two squares are 1, 2, 4, 5, 8, 9, 10, 13, 16, 17, 18, 20, 25, 26, ... (OEIS A001481). Letting be the fraction of numbers that are expressible as the sum of two squares,

and

where is the Landau-Ramanujan constant.

Numbers expressible as the sum of three squares are those not of the form for (Nagell 1951, p. 194; Wells 1986, pp. 48 and 56; Hardy 1999, p. 12).

The following table gives the first few numbers which require , 2, 3, and 4 squares to represent them as a sum (Wells 1986, p. 70).

Fermat's 4n+1 theorem guarantees that every prime of the form is a sum of two square numbers in only one way.

There are only 31 numbers that cannot be expressed as the sum of distinct squares: 2, 3, 6, 7, 8, 11, 12, 15, 18, 19, 22, 23, 24, 27, 28, 31, 32, 33, 43, 44, 47, 48, 60, 67, 72, 76, 92, 96, 108, 112, 128 (OEIS A001422; Guy 1994; Savin 2000). The following numbers cannot be represented using fewer than five distinct squares: 55, 88, 103, 132, 172, 176, 192, 240, 268, 288, 304, 368, 384, 432, 448, 496, 512, and 752, together with all numbers obtained by multiplying these numbers by a power of 4. This gives all known such numbers less than (Savin 2000). All numbers can be expressed as the sum of at most five distinct squares, and only

and

require six distinct squares (Bohman et al. 1979; Guy 1994, p. 136; Savin 2000). In fact, 188 can also be represented using seven distinct squares:

The following table gives the numbers that can be represented in different ways as a sum of squares. For example,

can be represented in two ways () by two squares ().

The least numbers that are the sum of two squares in exactly different ways for , 2, ... are given by 2, 50, 325, 1105, 8125, 5525, 105625, 27625, 71825, 138125, 5281250, ... (OEIS A016032; Beiler 1966, pp. 140-141; Rubin 1977-78; Culberson 1978-79; Hardy and Wright 1979; Rivera).

The product of four distinct nonzero integers in arithmetic progression is square only for (, , 1, 3), giving (Le Lionnais 1983, p. 53). It is possible to have three squares in arithmetic progression, but not four (Dickson 2005, pp. 435-440). If these numbers are , , and , there are positive integers and such that

where and one of , , or is even (Dickson 2005, pp. 437-438). Every three-term progression of squares can be associated with a Pythagorean triple ) by

(Robertson 1996).

Catalan's conjecture states that 8 and 9 ( and ) are the only consecutive powers (excluding 0 and 1), i.e., the only solution to Catalan's Diophantine problem. This conjecture has not yet been proved or refuted, although R. Tijdeman has proved that there can be only a finite number of exceptions should the conjecture not hold. It is also known that 8 and 9 are the only consecutive cubic and square numbers (in either order).

The numbers that are not the difference of two squares are 2, 6, 10, 14, 18, ... (OEIS A016825; Wells 1986, p. 76).

A square number can be the concatenation of two squares, as in the case and giving . The first few numbers that are neither square nor the sum of a square and a prime are 10, 34, 58, 85, 91, 130, 214, ... (OEIS A020495).

It is conjectured that, other than , and , there are only a finite number of squares having exactly two distinct nonzero digits (Guy 1994, p. 262). The first few such are 4, 5, 6, 7, 8, 9, 11, 12, 15, 21, ... (OEIS A016070), corresponding to of 16, 25, 36, 49, 64, 81, 121, ... (OEIS A018884).

The following table gives the first few numbers which, when squared, give numbers composed of only certain digits. The values of such that contains exactly two different digits are given by 4, 5, 6, 7, 8, 9, 10, 11, 12, 15, 20, ... (OEIS A016069), whose squares are 16, 25 36, 49, 64, ... (OEIS A018885).

For three digits, an extreme example containing only the digits 7, 8, and 9 is

No squares are known containing only the digits 013 or 678. Unique solutions are known for 019, 039, 056, 079, 568, and 789. The longest known is

with 52 digits. A list of known solutions to the 3-digit square problem is maintained by Mishima.

Brown numbers are pairs of integers satisfying the condition of Brocard's problem, i.e., such that

where is a factorial. Only three such numbers are known: (5,4), (11,5), (71,7). Erdős conjectured that these are the only three such pairs.

Either or has a solution in positive integers iff, for some , , where is a Fibonacci number and is a Lucas number (Honsberger 1985, pp. 114-118).

The smallest and largest square numbers containing the digits 1 to 9 are

The smallest and largest square numbers containing the digits 0 to 9 are

(Madachy 1979, p. 159). The smallest and largest square numbers containing the digits 1 to 9 twice each are

and the smallest and largest containing 1 to 9 three times are

(Madachy 1979, p. 159).

Madachy (1979, p. 165) also considers numbers that are equal to the sum of the squares of their two "halves" such as

in addition to a number of others.