The Wedge

Distinct Elements in Arithmetic Tables

by Brian Almond

Prominent patterns show up in arithmetic tables when only distinct entries are shown. This page describes some interesting results, and a few unanswered questions, about these modified tables.

The Multiplication Table
The Division Table
The Totient Function
Acknowledgements

The Multiplication Table

Consider the simplest form of the ordinary multiplication table used to teach elementary-school children:

This table can be enlarged and modified in such a way as to include only distinct numbers. In the case of a commutative operation such as multiplication, the arithmetic table is symmetric with respect to the main diagonal extending from the upper-left corner to the lower-right one. We can then leave the entire lower-triangular portion of the modified table blank since the products in that region already appear in the upper-triangular portion of the table. The next-sized modified table would be:

where the "2" in the first column is omitted since it already has been written in the first row. Continuing this process for the next two sizes of the modified table, we have:

In the enlargement from one modified table to the next-sized one, the only table entries that need to be examined for distinctness fall in the last column of the table, and are all multiples of the final table size. For example, in the right-hand column of the 4 x 4 table, we start with the multiples of 4 through 4²: {4,8,12,16}, but exclude 4 since it already has appeared in the 2 x 2 table. Extending this result to a general N x N modified table, the Nth column would contain only multiples of N (through N²) that cannot be written as products of two factors both smaller than N.

A few things are immediately obvious about the modified table. First, any column associated with a prime factor will have all of its entries shown. The largest two products that can be formed using two factors from {1,...,N-1} are

(N-1)² and (N-1)(N-2)

The former differs by 1 from, and is therefore relatively prime to, the product N(N-2). The latter is strictly less than N(N-2) for N

3. Clearly, N(N-1) and N² cannot be expressed as the product of two factors that are both less than N. Therefore, another characteristic of the modified table is that the bottom three entries in any column (that is, N(N-2), N(N-1) and N²) will always be shown. In fact, the lower limit above which products in the last column will always appear in the modified table can probably be relaxed somewhat, as will be seen below.

Extending the modified table to larger dimensions produces some unexpected patterns. Here, we're interested more in the presence or absence of a table entry than in its particular value (except as needed to compute the next-sized table). Representing table entries by pixels, the 300 x 300 modified table is a wedge shape:

Let i denote rows from top to bottom and j columns from left to right. By inspection, it was found that the parabola

(shown in yellow in the figure above) defines a lower limit above which all column entries always appear in the modified table. A proof of this result remains to be found.

Other, shadow-like patterns occur along the lines

i = j / 3 and i = j / 2,

extensions of which are shown in green in the figure above. These lines seem to delimit areas in which the density of distinct table entries makes a quantum jump. Close examination of the modified table shows somewhat less evident density boundaries along other lines that converge on the yellow parabola.

Limiting Behavior of the Fraction of Distinct Elements

Even though entire table columns occasionally appear due to primes, trends toward sparseness continue in larger modified multiplication tables, for it can be shown that the fraction of distinct entries in a table approaches zero as the table size grows to infinity:

Let F(N) denote the number of distinct entries in the N x N multiplication table. Then

H(N) = F(N) / N²

is the fraction of distinct table entries. The first few values of F(N) and H(N) are:

	F(1) = 1	H(1) = 1
	F(2) = 3	H(2) = 3/4
	F(3) = 6	H(3) = 2/3
	F(4) = 9	H(4) = 9/16

Henceforth consider N

4. We've already shown that the last-column entries N², N(N-1) and N(N-2) in the N x N table are unique since they cannot be represented as a product of two factors in {1,...,N-1}, so the symmetry of the table gives

with equality on the right when N is prime. It immediately follows that

Due to the influence of primes, H has a locally-nonmonotonic behavior:

To examine the limiting behavior of H, we apply a modification of the sieve of Eratosthenes [1]. The N² entries in the N x N multiplication table are drawn from the set T = {1,2,...,N²} of consecutive integers. An element of T is "feasible" if it corresponds to an actual entry in the N x N multiplication table; that is, a feasible element is one that can be represented as the product of two factors from {1,...,N}. The modified sieve operates on T by removing all feasible multiples of each of the column indices 1,...,N. A method for overcounting these removals results in an upper bound for F(N).

Since each of the column indices 1,...,N is a multiple of some prime p N, we need consider only column numbers ip, where p N is a prime and i=1,...,[N/p] ([x] represents the greatest integer less than or equal to x). The first pass of the sieve, corresponding to column p in the table, removes p,2p,...,Np from T. The second pass (column 2p) removes from T those elements of {2p,4p,...,2Np} that were not removed in the first pass. The process continues up to column [N/p]p, with each pass removing only column elements that have not been removed in the preceding pass. In pass i, multiples of ip in [(i-1)Np+1,iNp] are removed, and the number of removals is

Let (x) represent the number of primes less than or equal to x, with (1)=1. Summing over all [N/p] columns associated with prime p, and over the (N) primes p_k N, an upper bound for F(N) is

since we have removed certain feasible elements of T more than once (for example, elements in columns of the form pq, where p and q are both prime). On the other hand, the sieve by its construction cannot have removed any infeasible elements of T.

Eliminating the greatest-integer function from the summand, we have

For j [1,N], the series term (N/j+1) appears once for each k such that j N/p_k, or equivalently,

p_k N/j
k (N/j);

that is to say, term (N/j+1) appears

(N/j) times for a prime-counting function

extended over the domain of real numbers. We may then write U₂(N) in the equivalent form

The corresponding upper bound for H(N) is

Now there exists a constant A > 0 such that

for all x > 1 [2], so we may write

Since the summand numerator 1 + j/N < 2 over the summation limits 1 to N-1, we have

where

If we consider j to be a continuous variable ranging from 1 to N-1, the summand 1/(j²ln(N/j)) is a continuous unimodal function decreasing from 1/lnN at j=1 to 2e/N² at j=, then increasing for larger values of j. Thus, we may upper-bound the series terms in (3) by the integral

Making the change of variable y=ln(N/j), we have

Now

so V₄(N) is of the indeterminant form . By L'Hôpital's rule,

Since the limits of integration are continuous and differentiable functions of N on and the integrand is continuous between the limits of integration [3], the derivative of the integral is

Then

by L'Hôpital's rule. From (3) and the definition of V₄(N),

Since V₃(N) consists only of positive terms, we have V₃(N) = 0. Consequently, as N , V₂(N) by (2) and H(N) by (1).

Numerical computation of H(N) may be optimized by examining a few characteristics of the table. Assume F(N-1) is known and consider the potentially-new entries iN, i=1,...,N-3, forming most of the Nth column of the table. Now iN is not new in the N x N table if there exist k,m [1,N-1] such that iN = km. Without loss of generality, k m; we therefore have

i < k m < N.

Clearly k

, so iN is new if iN mod k is nonzero for all k

[i+1,[

]]. Furthermore, if p

[2,N] is a prime dividing N,

i < N/p iN = (ip)(N/p) is not new,

so computations are reduced by excluding lower values of i when N has a small prime factor (benefits diminish for larger primes). This computation procedure is presented in the following example flowchart:

The Division Table

An analogous modification can be made for the N x N division table, where all entries are reduced to lowest terms. As in the modified multiplication table, only heretofore unseen quotients are shown in the table as each new row and column are added. For example, the modified 4 x 4 division table is:

Only a quotient created from relatively-prime numerator and denominator will be shown in the modified table, so there will be an obvious symmetry with respect to the main diagonal. Extending the modified table to larger dimensions produces a repetitious complexity, but apparently none of the shadow lines or other boundaries present in the modified multiplication table. Again representing table entries by pixels, the 300 x 300 modified division table is the lace-like pattern:

Limiting Behavior of the Fraction of Distinct Elements

It can be shown that the fraction of distinct entries in the modified division table approaches as the table size grows to infinity:

The number of distinct real numbers formed by all possible quotients of the integers 1,...,N is

where (i) is the Euler totient function defining the number of integers in {1,...,i-1} that are relatively prime to i (with 1 always considered relatively prime to i). As before, the fraction of distinct table entries is

H(N) = F(N) / N²

and we will show

H(N) =

Let

S_N = {distinct ratios i / j | i,j [1,N]};

we wish to show the cardinality of S_N is given by (4). Now card S₁ = 1 = F(1), so assume N

2. If we let V_N be the set of all quotients whose numerator or denominator (or both) is N:

V_N = {1/N,2/N,...,N/N,N/(N-1),...,N/1},

then

S_N = S_N-1 V_N.

Let x

V_N. If x is not in lowest terms, then its lowest-terms representation is i/j, where i < N and j < N. Thus, x

S_M for some M < N. Conversely, if x

V_N is in lowest terms, it cannot be a member of any S_M, M < N, since the numerator or denominator of x is N and no ratios involving N appear in any S_M when M < N. Thus,

S_N = S_N-1 + W_N,

where

W_N = {members of V_N that are in lowest terms}.

Now N/N is never in lowest terms, so

card W_N = 2 card {those of 1/N,...,(N-1)/N that are in lowest terms}

due to the symmetry of the elements of V_N. The latter cardinality is simply the totient function of N [4]:

card W_N = 2 (N)
card S_N = card S_N-1 + card W_N
F(N) = F(N-1) + 2 (N).

Since

by [4], the result for H(N) follows. Due to relatively larger values of (N) for prime N, H(N) has a locally nonmonotonic behavior:

Numerical values of H(N) may be computed using a simple application of a g.c.d. algorithm for (i) [5]:

The Totient Function

The involvement of the totient function in the results for the modified division table suggests a possible connection with the modified multiplication table as well. After plotting the totient function versus its argument on an equivalent 300 x 300 grid, more "shadow lines" can be seen, particularly near

j = i, j = 2i / 3 and j = i / 2.

By loosening the nearness criteria to, say, within 2% of i, three lines of pixels emerge:

We would expect a few pixels directly on these lines because, for example,

(N) = N - 1 for prime N,
(N) = N / 2 if N is a power of 2,
(N) = 2N / 3 if N is a power of 3

and in general,

for distinct primes p_k dividing N. Other cases that fall near the shadow lines may be explained by the presence of factors that are twin primes; for example,

which is close to 1.

Acknowledgements

References

[1] W. Narkiewicz, Number Theory, World Scientific, 1983, p. 147.

[2] H. N. Shapiro, Introduction to the Theory of Numbers, John Wiley & Sons, 1983, p. 336.

[3] R. S. Burington, Handbook of Mathematical Tables and Formulas, McGraw-Hill, 1973, p. 113.

[4] M. Abramowitz & I. A. Stegun (eds.), Handbook of Mathematical Functions, National Bureau of Standards, 1964, p. 826.

[5] R. Sedgewick, Algorithms, Addison-Wesley, 1983, p. 12.

Links

Totient Function

Finding Primes and Proving Primality

Numericon

Thanks to Nigel Boston, Harold Diamond and Martin Huxley for constructive feedback.

Home