Multiplication table problem

Sometimes mathematics problems that are interesting to the professional mathematician can arise out of the simplest questions. We all learned a multiplication table in school, which lists all 100 products of integers from 1 * 1 to 10 * 10. I've been told that in England, students are required to memorize up to 12 * 12. In the multiplication table for 1 to 10, there are 100 products, but it is only necessary to learn 55, because of the commutative property. In other words, we only need to learn the products a * b, where a ≤ b, and the number of such products is 1 + 2 + ... + 10 = T(10) = (11)(10)/2, where T(n) is the n-th triangular number, (n + 1) * n / 2. Therefore, the number of different products is at most 55. Actually it is less. For example, 6 appears twice in the triangular table, as 1 * 6 and as 2 * 3. The number of different products in a 10 by 10 multiplication table is 42. (Shades of Douglas Adams!)

A mathematician would naturally be interested in knowing how many different products there are in an n by n multiplication table, in other words, the number of different products of the form ab, where a and b are positive integers less than or equal to n. Call this sequence a(n). Then a(n) ≤ T(n), so the lim sup of a(n)/n^2 as n goes to infinity is less than or equal to 1/2. In fact, Erdös gave a very nice proof that the limit is 0, and he and others obtained more accurate asymptotic formulas for a(n).

See the Online Encyclopedia of Integer Sequences, where a(n) is given as sequence A027424. Links provide much information about the sequence. Also, the question of how many different numbers appear in a multiplication table could be given to students at almost any level.