THE SUM-PRODUCT PUZZLE: Number of Distinct Entries Patterns

In 1983 the prolific conjecturer Paul Erdős posed a math problem: Take any set of numbers you like. These could be the whole numbers from 1 to 12, the first 10,000 prime numbers, or the dates of every birthday in your extended family. Arrange these numbers in a square grid, with your list of numbers arranged both across the top and up one side. Then fill in the grid with either the sums or the products of the crosswise pairs. Sum means adding. Product means multiplying (if you think you do not know multiplication yet, just use repeated addition; 3 times 4 = 3 + 3 + 3 + 3 = 4 + 4 + 4 = 12). 

Erdős and his collaborator on the problem, Endre Szemerédi, were interested in the number of distinct entries in such a grid. (By “distinct,” they meant different; so if a number appears twice — for instance, if the number 4 appears as a product of both 1 × 4 and 2 × 2 — you only count it once.) They conjectured that the number of distinct entries in either the sum or the product grid (or both) must be at least a certain value. They even established an exact threshold that the number of distinct sums or distinct products always had to meet.

The most familiar grid in arithmetic is the times table. Write out the numbers 1 to 6 along the top and up the side and fill out the grid accordingly. If you compare the grid of products with the grid of sums, you might notice that there are many more distinct products than distinct sums.

Erdős and Szemerédi certainly did. At the same time they proposed their conjecture, they solved a special case of the problem. They showed that whenever the numbers used to generate the grid are consecutive or arithmetic (such as 1 through 6 or 2,5,8,11…), the number of distinct sums will be 2N − 1, where N stands for the number of numbers used to generate the grid. 

Arithmetic sequences are sets of numbers with a common difference (d) such as consecutive even or odd numbers {0,2,4,6...} or {1,3,5,7...} with a d=2 or {2,7,12,17...} with a d=5.The most familiar grid in arithmetic is the times table. The number of distinct products, however, will be much larger — more on the order of a constant value times N^2 (N squared).

In fact, when I tried many of these arithmetic sequences with product grids, I generated distinct entries which are triangular numbers {1,3,6,10,15…}. The formula for triangular numbers is: (n^2 + n)/2

Now, try this yourself and see if the 2N - 1 formula works for sums and if cN^2 works for products. Since we chose 6 numbers, we let N=6; so 2x6-1 should be the number of distinct sums, in this case 11.

Conversely, when I used geometric sequences with the sum grid, I generated distinct entries which were triangular numbers and the product grid distinct entries were in the order of 2N - 1. I am not sure that this works for each case. I asked the Mathletes to help me prove this.

Geometric sequences are sets of numbers with a common ratio (r) such as powers of 2 {1,2,4,8...} with a r =2 or powers of 3 {1,3,9,27...} with a r =3.

Also, for random number sequences such as your birthday or weight or street address, I have yet to find any correlation between the number of distinct entries for sums and product grids.

Random sequences are sets of numbers with no pattern such as my birthday {7,1,7,6,2} or prime numbers (numbers only divisible by 1 and itself {2,3,5,7…}.

For K-2nd grade, I only challenged the Mathletes to compute the sum grids, but some of the children may want to try the product grids as well. Remember, multiplication is just repeated addition. For example, 3 x 4 = 3 times 4 = 3 + 3 + 3 + 3 = 4 + 4 + 4 = 12).