Balmoral Software
This table can be modified in such a way as to include only distinct numbers, shown in darker text above. Duplicate products are excluded from the modified table; for example, the entry of 20 in row 2 and column 10 is not shown since it appears in row 4 and column 5 of a smaller table, closer to the diagonal.
A consistent selection criterion can be established for all arithmetic operators that identifies distinct entries in the associated tables. This criterion consists of picking an entry occurring in the smallest square table, which in most cases is equivalent to selecting entries with row and column indices that are closer together than any others producing the same table entry. For commutative operators, the arithmetic table is symmetric with respect to the main diagonal extending from the upper-left corner to the lower-right one. By convention, entries in the lower-triangular portion of arithmetic tables for commutative operators are excluded from consideration as distinct entries since they already appear in the upper region. Excluding the upper-triangular region instead would produce the same patterns, but with rows and columns transposed.
The selection criterion described above can be applied to table entries in any order, producing the same result.
Let R and C denote the row and column indices in an N x N arithmetic table,
Multiplication: A distinct product in the table selected to minimize the associated row and column indices has R and C closer together than any other factor pair having a product equal to RC. Equivalently, R and C are central divisors, as defined below.
Division: A quotient in lowest terms satisfies the selection criterion, since any other fraction with the same value has both numerator and denominator that are larger multiples of those in the lowest-terms formulation, and therefore farther apart. The row and column indices of a distinct table entry have no common factors; that is, their greatest common divisor (gcd) is 1.
Addition: As with the preceding operations, a distinct sum in the
addition table selected to minimize the associated row and column indices has R
and C closer together than any other factor pair having the same sum
Subtraction: A distinct entry in the subtraction table is selected to minimize both of the associated row and column indices since the difference between the indices is fixed. This occurs when the row or column index is at its minimum value of 1. As a result, distinct entries occur in the first row and first column of the table.
Summary:
| Operation | Selection criterion for distinct entries |
|---|---|
| Multiplication | {R,C} are central divisors |
| Division | gcd(R,C) = 1 |
| Addition | C - R is 0 or 1 |
| Subtraction | min{R,C} = 1 |
We'll explore these patterns in the sections below.
As the factor x increases towards its limit
, its paired factor N/x
decreases towards the same limit. Therefore, the central divisors of N have
the property that they are closer together than any other factor pair of N.
For example, {18,20} are the central divisors of their product 360. But {6,74}
are not the central divisors of 444 since 12 x 37 = 444 and {12,37} are closer
together.
The factors a and N/a above are referred to as the lesser central divisor (LCD) and greater central divisor (GCD) of N. Capital letters are always used in this paper for these acronyms, to avoid confusion with greatest common divisor (gcd). By convention, the row index is the LCD and the column index the GCD of any product present in the MMT. LCDs and GCDs are listed as OEIS sequences A033676 and A033677, respectively. The frequency distributions of LCDs and GCDs are discussed in a subsequent section.
A factor pair {a,b} is a set independent of the size order of its elements, but we usually apply the convention of listing the smaller factor first when the relative factor sizes are known.
Obviously, {a,b} are always central divisors when a = b. Another result is that
{1,p} are central divisors if and only if
(a - 1)(b - 1) + 1 = (1 - 1/a)ab - a + 2,then by Lemma 4, any column index with a as its LCD will have an unbroken segment of dark pixels starting at the line
R = (1 - 1/a)C - a + 2and extending vertically down to the main diagonal R = C. For a ≥ 2, the slopes of these lines are 1/2, 2/3, 3/4, 4/5 and so on, as shown by the yellow annotations in the preceding and following diagrams. In the case of a prime-numbered column, we have
When C is a square, a reaches its maximum value of
and the top of the vertical
segment of dark pixels occurs at row
By Lemma 4 and Lemma 9, this minimum value of R is greater than or equal to the lower limit for R for non-square values of C, so there is always a solid band of entries in the MMT between the main diagonal and a narrow parabola above it.
Analogously for a row R with central divisors {a,b}, a ≤ b,
(a + 1)(b + 1) - 1 = (1 + 1/a)ab + a,and any row index R with a as its LCD will have an unbroken segment of dark pixels extending horizontally from the main diagonal and ending at the line
C = (1 + 1/a)R + a,which can be written
R = [1 - 1/(a + 1)]C - a2/(a + 1)These lines have the same slopes and nearly the same intercepts as those for the column segments:
|
|
Next, we consider columns that are multiples of 3. To exclude the shadow line already considered in the first example, we'll examine columns that are odd multiples of 3
Applying Lemma 10 with a = R, b = C and k = 3, all MMT entries are blank in the top third of the table where
R ≤ C/3 - 1A shadow line is apparent at R = (2/3)C - 1 due to significantly more numerous central divisors in the third of the table closest to the diagonal than in the middle third. For the subset of column indices that are triples of a prime, all entries below the shadow line are central divisors, and exactly half of the entries above the line:
Proof. Let C = 3p for a prime p and consider the lowest third of the MMT:
2C/3 - 1 ≤ R ≤ CSince {3,p} are central divisors by Lemma 3 and the above inequality is contained within2p - 1 ≤ R ≤ 3p
2p - 1 ≤ R ≤ 4p + 3,then the conditions of Lemma 4 are met with a = 3, b = p and m = R, and so {R,3p} are central divisors.
In the adjacent middle third of the table, we have
C/3 ≤ R ≤ 2C/3 - 2By Lemma 12, {R,3p} are central divisors if and only if R is odd, QED.p ≤ R ≤ 2p - 2
Additional shadow lines can be identified in a similar manner for other divisors of C, but they become increasingly faint since more columns are excluded in order to mask the shadow lines from previous selections.
The entries identified in both sections above account for more than 90% of the entries in the MMT and its most significant patterns:
Let F(N) denote the number of entries in the N x N MMT (tabulated as OEIS sequence A027424). Then
H(N) = F(N)/N2is the fraction of table entries that are distinct. The first few values of F(N) and H(N) are:
The mathematician Paul Erdős proved in 1955 [1,2] that
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
The convergence is relatively slow, as can be seen in the chart below. Due to the influence of primes, H has a locally non-monotonic behavior:
A result by Ford [3] shows that H(N) is bounded by
for N ≥ 3, where δ = 1 - (1 + log log 2)/log 2 = 0.08607. These bounds are shown in the preceding diagram with
Only quotients created from relatively-prime numerator and denominator are shown in the MDT, equivalent to them having a greatest common divisor (gcd) of 1. As a result, there is an obvious symmetry in the table with respect to the main diagonal. Extending the MDT to larger sizes produces a repetitious complexity. Again representing table entries by dark pixels, the
This is a plan view of Euclid's orchard.
Entries described in the preceding two sections are shown below for the
600 x 600
The points (R,C) form ascending diagonals of included entries over the entire
MDT. As p increases from 2 to N, then
If |R - C| = 1, then the entry R/C = R/(R ± 1) is in lowest terms since
the
numerator and denominator are consecutive integers and therefore coprime. As a
result, all entries on the two diagonals adjacent to the main diagonal are
included.
If |R - C| is a prime p, then p < N and the table entry is
The entries described in the preceding two sections are shown below for the
Let F(N) denote the number of distinct entries in the N x N MDT. Equivalently,
F(N) is the number of lowest-terms quotients of the natural numbers 1,...,N,
with
Tail Values
When
Proof. We have
Now assume
The second interval can be written
Upper Bounds
Tight upper bounds for fN(a) can be piecewise defined based on known
characteristics of sequences of central divisors having the same LCD. Not
surprisingly, these upper bounds are established by local maxima occurring at
prime LCD values. In fact, most of the upper bounds described here are exact
values of fN(p) for prime p. The values of fN(1) and
fN(2) were determined above, so we henceforth assume p ≥ 3.
If a is a prime and n complies with the limits in
Lemma 7, then {a,n} are central divisors. However, if a
is composite and n is subject to the same limits, there often can exist rational
numbers r such that
Consider the factor pair {p,n} for a prime p ≥ 3. Since n cannot exceed N in
the MMT, then by Lemma 7, {p,n} are central divisors for
all primes
For p < N/2, we have 2p + 1 ≤ N and by
Lemma 19, {n,p} are central divisors for odd values of
n in the range
For p < N/3, we have 3p + 1 ≤ N and by
Lemma 20, {n,p} are central divisors for values of n
such that
= 2⌊ N/6 ⌋ + ⌊ [(N mod 6) + 3]/4 ⌋ - p
UfN(⌈ (N - 1)/2 ⌉) = ⌊ (N + 3)/2 ⌋
UfN(2 ⌊ (N + 3)/2 ⌋ - 4 ⌊ N/6 ⌋
- 2 ⌊ [(N mod 6) + 3]/4 ⌋ - 3) =
⌊ (N + 3)/2 ⌋
UfN(1) = 2 + 2 ⌊ N/6 ⌋ + ⌊ [(N mod 6) +
3]/4 ⌋
Uf500(250) = 251
Uf500(165) = 251
Uf500(1) = 169
When
Lower Bound
Now assume
Substituting ⌊ N2/a ⌋ for N in the
table above, we have
Lower Bound
As can be seen in a previous diagram, central
divisors occur for composite column indices C at prime-numbered rows beginning
at
Upper Bound
Since a prime-numbered column of the MMT is completely filled with central
divisors down to the main diagonal, an upper bound for hN(b) is
Proof. Without loss of generality, we can take a ≤ b and c ≤ d. From
(13), we have
(c2 - a2)(c2 - b2) = 0
c = a and/or c = b
Proof. If p = 1, {1,1} are trivially central divisors. If p is a prime, then
{1,p} is the only divisor pair of p and therefore its central divisors.
Conversely, if
2 ≤ p/k ≤ p/2
Proof. The divisor pairs of pq are {1,pq} and {p,q}. The first pair cannot be
central divisors by Lemma 2 since pq is composite, so
{p,q} are central divisors.
Proof. Under construction.
Proof. Without loss of generality, assume p ≥ q so that
Proof. {1,p} are central divisors by Lemma 2. The
result follows from Lemma 4 with
For a proof independent of Lemma 4, note that when
Otherwise, let k be any proper divisor of n. The divisor pairs of np are
{1,np}, {k,pn/k}, {pk,n/k} and the reference pair {n,p}. The first pair cannot
be central divisors by Lemma 2 since np is composite.
Next, we have
Now assume that n = 2p + 1. Since n is odd, k ≥ 3 and
Proof. {p,q} are central divisors by Lemma 3. The
result follows by Lemma 4 with
Proof. The divisor pairs of pqr are {1,pqr}, {q,pr}, {r,pq} and the reference
pair {p,qr}. The first cannot be central divisors by
Lemma 2 since pqr is composite. We have
Proof. Let n be even. Then n/2 < p from (16), so
(3n/2 - 2p)2 < (n - 3p)2
Next, let p = 2. Then n = 2 is even and {n,3p} = {2,6} are not central
divisors.
Now let n = p ≥ 3, so that n is odd. Then {n,3p} = {max{p,3},3p} are central
divisors by Lemma 6.
Therefore, we can henceforth assume that
Finally, let n be an odd composite. From (16), we have n < 3p and every proper
divisor k of n is subject to the constraint
Case 1: {1,3np} cannot be central divisors by Lemma 2
since 3np is composite.
Case 2: Since 3p/k > n/k > 1, we have 3pn/k > n and 3pn/k > 3p, so 3pn/k is
greater than both reference factors. Therefore, {k,3pn/k} cannot be central
divisors by Lemma 5.
Case 3: Since k ≤ n/3 < p, we have p/k > 1 and so pn/k > n. If n/k = 3, then
{3k,pn/k} is the same as the reference pair. Otherwise,
Case 4: Since n/k ≥ 3 > 3/p, we have 3 < pn/k, and so {3,np} are not central
divisors by Lemma 10 with
Case 5: We have n > p and 3n > n, so 3n > 3p and 3n is therefore bigger than
both reference factors. As a result, {p,3n} cannot be closer together than the
reference pair by Lemma 5.
Case 6: If k = 3, {kp,3n/k} is the same as the reference pair. Otherwise,
Case 7: Since n < 3p < 3kp, we have 3p > n/k, and so {3kp,n/k} are not central
divisors by Lemma 10 with
Proof. Since p is prime and n < p, n and p cannot have any common factors other
than 1, so
Proof. Since c is composite, it has a factor k between 2 and
(n2k2 - c2)(k2 - 1) < 0
(nk - c/k)2 < (n - c)2
Note that the converse does not hold; for example, if a = 1 and b = 5, then
{a,b} are Central Divisors but neither (17) nor (18) hold.
Proof. By Lemma 2, {1,p2n+1} cannot be
central divisors since the latter factor is composite. The remaining factor
pairs of p2n+1 are {pk,p2n+1-k} for
p2n+1-k > pn+1 > pn,
Proof. Since m is the smallest proper divisor of n, n/m is its largest, so for
all proper divisors k of n, we have
If p | n, then n/p ≤ m; otherwise, n/p < m ≤ k. In the former case, we
can exclude
Finally, since k < kp and pn/k > n/k, {k,pn/k} are farther apart than {kp,n/k}
and also cannot be central divisors, QED.
Proof. If n is prime, then {n,p} are central divisors by
Lemma 3. Otherwise, n is composite and its smallest
proper divisor is at least 3 since it is odd. The result follows from
Lemma 18 with
Proof. If n is prime, then {n,p} are central divisors by
Lemma 3. Otherwise, n is composite and of the form
Proof. Let N = ab. Since {a,b} are the central divisors of N, then a minimizes
Proof. Let {a,N/a} be the central divisors of N, and {b,N/b} a different factor
pair of the same product,
Proof. Let m ∈ {-1,0,1,2,3}. Then
Proof under construction. A valid range for n exists only when q ≤ p + 1.
For a proof of the converse, assume q - 1 | n. Then
n/(q - 1) ≤ p - 1 < p
[p(q - 1) - nq/(q - 1)]2 < (pq - n)2,
It remains to prove that if {n,pq} are not central divisors, then n is divisible
by
Proof under construction. Cf. my
StackExchange
posting.
Proof of the second part: Let {a,b} be central divisors and {c,d} another
factor pair of
d + c > b + a
(c + 1)(d + 1) > (a + 1)(b + 1)
(c - 1)(d - 1) < (a - 1)(b - 1)
Proof when a = b. {a,a} are trivially central divisors, and (22) becomes
Proof when a = 1. Based on the previous result, we can assume
Proof when a = 2. By Lemma 3, {2,b} are central divisors
when b is prime. When
The results for the first few values of b can be confirmed by inspection:
Let k be a proper divisor of m, so that 2 ≤ k ≤ m/2 and
Case 1: Since p ≥ 5, we have from (23):
k ≤ m/2 < 2p
2pm/k > m
2pm/k > 2p,
Case 2: We have
Case 3: If k = m/2, then {2k,pm/k} is the same as the reference pair.
We can therefore exclude
Assume for the moment that k ≥ p. Then
p ≤ k ≤ p + 2/3,
Thus, we have k < p. Then
pm/k > 2p,
Case 4: We have
Case 5: If k = 2, then {pk,2m/k} is the same as the reference pair, so
we have
When m = 3p, k is 3 or p. In the former case, {pk,2m/k} is the same as the
reference pair {3p,2p}, so we must have
p2 - 6 > p,
Case 6: Since p > 2, we have
It remains to prove Lemma 4 for 3 ≤ a ≤ b - 1.
[2] P. Erdős, An asymptotic inequality in the theory of numbers (in
Russian), Vestnik Leningrad. Univ., v. 15 (1960) p. 13, 41-49; MR0126424
(23 #A3720), cited in Finch, S. (2018), Mathematical Constants II (Encyclopedia
of Mathematics and Its Applications), p. 33. Cambridge: Cambridge University
Press. doi:10.1017/9781316997741, available from
OEIS
[3] K. Ford, The distribution of integers with a divisor in a given interval,
Ann. of Math. 168 no. 2 (2008) pp. 367-433, cited in Koukoulopoulos and
Thiel, op. cit., p. 448.
[4] Weisstein, Eric W. "Relatively Prime." From MathWorld--A Wolfram Web
Resource.
https://mathworld.wolfram.com/RelativelyPrime.html
[5] Wikipedia Coprime integers
[6] M. Abramowitz & I. A. Stegun (eds.), Handbook of Mathematical Functions,
National Bureau of Standards, 1964, p. 826.
[7] R. Sedgewick, Algorithms, second ed., Addison-Wesley, 1988, p. 12.
[8] Wikipedia
Greatest common divisor
Thanks to Nigel Boston, Harold Diamond, Martin Huxley and Daniel
Fischer for constructive feedback.
This paper is a revision and expansion of a paper first posted on this site in
1993.
Copyright © 1993-1998, 2020, 2022 by Balmoral Software. All rights
reserved.
Ascending Diagonals
Ascending diagonals associated with primes are included in the MDT. Assume
Descending Diagonals
If R = C, then all entries on the main diagonal except (1,1) are excluded from
the MDT since their quotients are 1.
which cannot be a quotient of integers since
. Therefore, R/C is in lowest
terms. However, if
so the table entry is not in lowest terms. Therefore, the entries on
prime-numbered descending diagonals are included, except at intervals of p.
The behavior of descending diagonals accounts for the
fuzziness adjacent to the main diagonal, where
first every table entry is present 
Entries classified in all of the previous sections are shown here for the
Limiting Behavior of the Fraction of Distinct
Quotients
The fraction of distinct entries in the MDT approaches 6/π2 =
60.8% as the table size grows to infinity. This limit is the probability of a
quotient of random integers being in lowest terms [4,5].
F(N) - F(N-1) = 2φ(N),
since each lowest-terms fraction appears in the MDT along with its reciprocal.
The solution to this difference equation is
As before, the fraction of distinct table entries is
(1)
H(N) = F(N)/N2
The first few values of F(N) and H(N) are:
From [6], we have φ(1) = 1 and
F(1) = 1 H(1) = 1 F(2) = 3 H(2) = 3/4 F(3) = 7 H(3) = 7/9 F(4) = 11 H(4) = 11/16
so from (1) and (2),
(2)
The convergence of H(N) to its limit is considerably faster for the MDT than in
the MMT. Due to relatively larger values of φ(N) for prime N, H(N) has a
locally non-monotonic behavior:
Numerical values of H(N) may be computed for small N using an application of a
gcd algorithm for φ(i) [7]:
If storage is available for all primes p ≤ N, computation of φ for larger
N is much faster using
Euler's product formula:
where the product is taken over all primes p dividing N. This formula can be
implemented iteratively with the following steps:
(3)
input: N
φ ← N
for all primes p ≤ N do
if p | N, then φ ← (φ/p)(p - 1)
output: φ
The Addition and Subtraction Tables
A modified addition table constructed in the same way as the preceding tables
has distinct entries on the main diagonal and first superdiagonal only:
A modified subtraction table where the row is subtracted from the column has
distinct entries in the first row and first column only:
In both cases, the modified N x N table has F(N) = 2N - 1 entries, and the
fraction of distinct entries converges to zero:
Since the modified addition and subtraction tables are not affected by primes,
the H(N) function is smooth:
The Totient Function
When plotted versus its argument on an inverted vertical scale like in the
arithmetic tables above, the totient function itself exhibits shadow lines
similar to those in the MMT:
These shadow lines occur because in (3), the relative value φ(N)/N is
frequently dominated by the largest factors in the product, which are associated
with powers of the smallest primes 2 or 3 in the prime factorization of N. For
example, if N is even but not a multiple of 3, then φ(N)/N is less than or
equal to (and often near) the value 
These proportions remain consistent for larger values of N.
Near N/3 line: 102 11% Near N/2 line: 188 21% Near 2N/3 line: 96 11% Near N-1 line: 182 20% Remainder: 332 37%
Frequency Distribution of Central Divisors
We turn now to the distribution of LCDs (row numbers) of the distinct entries in
the multiplication table. Subsequent sections discuss the frequency
distributions of LCDs in the general case where the paired GCD is not
constrained, and of GCDs in the MMT.
Lesser Central Divisor (Modified Multiplication
Table)
Let fN(a) denote the number of occurrences of a as the LCD of the
entries in the
{2,p} are central divisors for all primes p, 2 ≤ p ≤ N, by
Lemma 3
Therefore,
{2,4} are central divisors by inspection
{2,c} are not central divisors for all composite c, 6 ≤ c ≤ N by
Lemma 14 with n = 2
fN(1) = fN(2) = π(N) + 1,
where π is the
prime
counting function. In general, the central divisors counted in
fN(a) are {a,n}, where
The left inequality ensures that a is the lesser of the central divisors {a,n},
and the right inequality that both divisors are within the range found in the
MMT. A histogram of f500(a) is shown below, along with upper and
lower bounds defined in the following sections:
a ≤ n ≤ N
(4)
This frequency distribution has the same general shape for all values of N.
the exact value of fN(a) is
fN(a) = N - a + 1
This corresponds to the solid band of entries in the MMT
adjacent to the main diagonal.
so all values of n satisfying (4) are within the range (17) of
Lemma 15, and thus correspond to central divisors, QED.
so that the range of n covers two intervals:
The first interval can be written
and contains 
values of n, all
of which are central divisors by Lemma 15.
We consider only prime values of n in this interval to establish a lower bound
for fN(a). Additional central divisors may exist for composite n.
Since 
Including both intervals, a lower bound for fN(a) thus is
A list of lower bound values for N = 500 is tabulated here.
The value n = 2p + 1 is excluded so that the interval (5) will juxtapose
subsequent intervals described below. Applying Lemma 16
with
p ≤ n ≤ min{2p,N}, p ≤ N
(5)
Applying Lemma 16 with i = 2p + 1, j = min{3p,N}, k = 2,
2p + 1 ≤ odd n ≤ min{3p,N}, p < N/2
(6)
3p + 1 ≤ n ≤ min{5p,N} and n mod 6 = ±1
If p ≥ N/5, then min{5p,N} = N. But if p < N/5 and we continue to use N as
the maximum value of n (rather than the smaller 5p), we are overcounting the
values of n to provide an upper bound for fN(p). This approach is
used for simplicity since the exact range for n when
3p + 1 ≤ n ≤ N when n mod 6 = 1, p < N/3
and
(7)
3p + 1 ≤ n ≤ N when n mod 6 = 5, p < N/3
Applying Lemma 16 twice with i = 3p + 1, j = N, k = 6,
⌊ (N - 1)/6 ⌋ - ⌈ p/2 ⌉
+ ⌊ (N - 5)/6 ⌋ - ⌈ (3p - 4)/6 ⌉ + 2
The results (5), (6) and (7) cover adjacent intervals for n over its full range
of possible values, and can be summarized as follows:
Summing the number of values in each range, we have the following piecewise
definition for an upper bound UfN(a) of fN(a) for all a:
Range of p Range(s) of n Quantity of n values p ≥ N/2 p ≤ n ≤ N (5) N - p + 1 N/3 ≤ p < N/2 p ≤ n ≤ 2p (5) p + 1 2p + 1 ≤ odd n ≤ N (6) ⌊ (N + 1)/2 ⌋ - p p < N/3 p ≤ n ≤ 2p (5) p + 1 2p + 1 ≤ odd n ≤ 3p (6) (p + 1)/2 3p + 1 ≤ n ≤ N & n mod 6 = ±1 (7) 2 ⌊ N/6 ⌋ + ⌊ [(N mod 6) + 3]/4 ⌋ - p
Since {N,N} is the only factor pair when a = N, we have fN(N) = 1.
From right to left, the consecutive points of the polygonal upper bound are:
Range of a UfN(a) Description a ≥ N/2 N - a + 1 Line of slope -1 N/3 ≤ a < N/2 ⌊ (N + 3)/2 ⌋ Horizontal line a < N/3 ⌊ (a + 3)/2 ⌋ + 2 ⌊ N/6 ⌋ + ⌊ [(N mod 6) + 3]/4 ⌋ Line of slope 1/2
UfN(N) = 1
For example, at N = 500 the points are:
Uf500(500) = 1
Lesser Central Divisor (General Case)
Let gN(a) denote the number of occurrences of a as the LCD of
all of the natural numbers 1,...,N2, rather than just the
subset of those numbers occurring in the
so that the product an is within range. For example, the central divisors
comprising gN(1) are {1,1} and {1,p} for all primes p in the range
2,...,N2, by Lemma 2. It follows that
a ≤ n ≤ N2/a,
(8)
gN(1) = π(N2) + 1
A histogram of g500(a) is shown below, along with upper and lower
bounds defined in the following sections:
Tail Values
the exact value of gN(a) is
(9)
gN(a) = 2(N - a) + 1
Proof. We have
Rewriting (9),
(10)
so all values of n satisfying (8) are within the range (17) of
Lemma 15, and thus correspond to central divisors. The
number of values of n in (8) is
From (9),
⌊ N2/a ⌋ - a + 1
(11)
Adding both sides of the previous two inequalities, we have
We can write
(12)
By (12), the fractional portion is between 0 and 1, so
⌊ N2/a ⌋ = 2N - a
From (11), we have
Working downwards from a = N, gN takes on increasing odd values until
the limit (9) is reached.
so that the range of n covers two intervals as in the preceding
section. The results in that section apply with
N replaced by 
Upper Bounds
A list of values of g500(a), Lg500(a) and
Ug500(a) is tabulated here.
Range of a UgN(a) 
⌊ N2/a ⌋ - a + 1 
⌊ (N2/a + 3)/2 ⌋ 
⌊ (a + 3)/2 ⌋ + 2 ⌊ N2/(6a) ⌋ + ⌊ [(⌊ N2/a ⌋ mod 6) + 3]/4 ⌋ Greater Central Divisor
Let hN(b) denote the number of occurrences of b as the GCD of the
entries in the
Although the GCD frequency distribution has a general appearance similar to the
totient function, and a difference
of just 1 at prime values of b, nearly all of the other values of the functions
differ significantly.
(C - 1)/2 ≤ prime R ≤ C
or
R > ⌈ (C - 3)/2 ⌉
This result is established in Lemma 7 with C ≤ 2R + 1.
By Lemma 15, central divisors occur at every row
above the parabola
or for every R satisfying
Additional central divisors can occur elsewhere in column C, so the preceding
ranges form a lower bound for hN(C) that also applies to prime
columns. The number of primes up to the parabola is:
and the total number of values above the parabola is
so the lower bound is the sum
It is conjectured that a tighter lower bound for hN(C) is simply
π(C).
UhN(b) = b
Appendix 1: Mathematical Results
Many of these results involve central divisors.
Lemma 1
If a,b,c,d ∈ ℕ such that
and
ab = cd
(13)
then
| a - b | = | c - d |
(14)
a = c and b = d.
It follows that a pair of central divisors are uniquely defined by their product
and their unsiqned (or squared) difference. Equivalently, if there are two
divisor pairs of a natural number with the same unsigned difference, then they
are the same pair.
d = ab/c
Substituting in (14) and squaring,
(a - b)2 = (c - ab/c)2
If c = b, then ab = bd by (13), so d = a. But then the assumption c ≤ d is
equivalent to Lemma 2
{1,p} are central divisors if and only if p = 1 or p is a prime.
2 ≤ k ≤ p/2
Combining these two inequalities, we have
|k - p/k| ≤ p/2 - 2 < p - 1
Therefore, {1,p} cannot be central divisors since they are farther apart than
{k,p/k}, QED.
Lemma 3
{p,q} are central divisors for any primes p and q.
Lemma 4
If {a,b} are central divisors, then so are {m,ab} for all natural numbers m such
that
(a - 1)(b - 1) < m < (a + 1)(b + 1)
These limits are closer together for central divisors {a,b} than for any other
factor pair of the product ab.
Lemma 5
For a,b,c,d ∈ ℕ with ab = cd, {c,d} are farther apart than {a,b},
and therefore are not central divisors, when either
c > a and c > b
or
d > a and d > b
Proof. Let N = ab, so that b = N/a. The first condition above is equivalent to
Lemma 6
For primes p and q, {max{p,q},pq} are central divisors.
p2 > p and p2 > pq,
p2 is greater than both reference factors, and therefore
{q,p2} are not central divisors by Lemma 5.
The remaining factor pair Lemma 7
If p is a prime and n is a natural number such that
n ≤ 2p + 1,
then {n,p} are central divisors.
k ≤ n/2 ≤ p + 1/2
If k = p, then {k,pn/k} is the same as the reference pair, so we can assume
pn/k > n and pn/k > p,
so pn/k is greater than both reference factors, and therefore {k,pn/k} cannot
be central divisors by Lemma 5.
n/p = 2 + 1/p < 3 ≤ k,
or pk > n. If n = 2p, then {n,p} = {p,2p} are central divisors by
Lemma 6. Otherwise, we have
n/p ≤ 2 - 1/p < 2 ≤ k,
so again pk > n. Since
pk ≥ 2p > p,
pk is greater than both reference factors, and so {pk,n/k} cannot be central
divisors by Lemma 5, QED.
Lemma 8
If p and q are primes and n is a natural number such that
(p - 1)(q - 1) < n < (p + 1)(q + 1)
then {n,pq} are central divisors.
Lemma 9
For natural numbers a and b,
Proof. Clearly,
We have
From (15), we also have
(15)
Lemma 10
Let a and b be natural numbers, with b composite and k a proper divisor of b.
If a < b/k, then {a,b} are not central divisors.
Proof. Since k ≥ 2, we have
If a > b/k, then {ka,b/k} are not central divisors.
so the factor pair {a,b} is farther apart than {ka,b/k}, or conversely.
Lemma 11
For primes p, q and r, {p,qr} are central divisors when p > q and p > r.
Lemma 12
If p is a prime and n is a natural number such that
then {n,3p} are central divisors if and only if n is odd.
p ≤ n ≤ 2(p - 1),
(16)
5n2/4 < 5p2
Since {3n/2,2p} are closer together than {n,3p}, the latter cannot be central
divisors.
3 ≤ p < n ≤ 2(p - 1)
Next, let n ≥ 5 be prime and thus odd. Since n > 3 and n > p, {n,3p} are
central divisors by Lemma 11.
3 ≤ k ≤ n/3 < p,
whence n/k ≥ 3. The divisor pairs of 3np are:
Case 1: {1,3np}
and the reference pair {n,3p}.
Case 2: {k,3pn/k}
Case 3: {3k,pn/k}
Case 4: {3,np}
Case 5: {p,3n}
Case 6: {kp,3n/k}
Case 7: {3kp,n/k}
Lemma 13
If p is a prime and n < p is a natural number, then n and p - n are coprime.
Lemma 14
For a natural number n and all composite numbers c > n2, {n,c} are
not central divisors.
inclusive.
We have 
so
k < c/n
and therefore {nk,c/k} are closer together than {n,c}, QED.
Lemma 15
If a and b are natural numbers such that
then {a,b} are central divisors. The condition is symmetric in a and b; (17) is
equivalent to
(17)
Proof. Assume {a,b} are not the central divisors of ab. Then there
exist other natural numbers c and d such that
(18)
b - a > d - c ≥ 0
Now 4ab = 4cd, so adding that quantity to both sides, we have
(b - a)2 > (d - c)2
(19)
(b + a)2 > (d + c)2
Using (18),
b + a > d + c
(20)
d + c ≤ b + a - 1
(21)
By (21),
a contradiction. Therefore, {a,b} are Central Divisors when inequality (17)
holds, QED.
Lemma 16
For integers i, j, k, m and n such that 0 ≤ m < k ≤ i ≤ j, the quantity
of values of n such that
⌊ (j - m)/k ⌋ - ⌈ (i - m)/k ⌉ + 1
Proof. Due to the requirement that n mod k = m, the values to be counted are at
intervals of k. Since
i - m ≤ k ⌊ n/k ⌋ ≤ j - m
and consider only multiples of k in the interval. The smallest multiple of k
that is at least as large as the lower bound is
k⌈ (i - m)/k ⌉ ≤ k ⌊ n/k ⌋ ≤
k ⌊ (j - m)/k ⌋
Dividing by k,
⌈ (i - m)/k ⌉ ≤ ⌊ n/k ⌋ ≤
⌊ (j - m)/k ⌋
and the result follows.
Lemma 17
For a prime p and a natural number n, {pn,pn+1} are
central divisors.
2n + 1 - k > n + 1
so p2n+1-k is greater than both reference factors for all given
values of k, and therefore {pk,pLemma 18
If m is the smallest proper divisor of a composite natural number n, p is a
prime, and
m ≤ k ≤ n/m ≤ p
The divisor pairs of np are {1,np}, {kp,n/k}, {k,pn/k} and the reference pair
{n,p}. {1,np} cannot be central divisors by Lemma 2
since np is composite.
Lemma 19
{n,p} are central divisors for prime p and odd natural numbers n such
that Lemma 20
{n,p} are central divisors for prime p and natural numbers n such that n ≤ 5p
and Lemma 21
If {a,b} are central divisors and d | gcd(a,b), then {a/d,b/d} are also central
divisors. For example, {18,20} are central divisors of 360 and
(a - N/a)2/d2 = (a/d - (N/a)/d)2
is also minimized for all such d. Therefore, {a/d,b/d} are central divisors of
N/d2.
Lemma 22
Central divisors have the minimum arithmetic mean amongst all factor pairs with
the same geometric mean.
.
Then the geometric mean of both factor pairs is
and
b < a ≤ N/a < N/b
By (20) of Lemma 15,
Lemma 23
For any natural number n ≥ 2, {n,n - 1}, {n,n}, {n,n + 1}, {n,n + 2} and
so the inequality in Lemma 15 is satisfied for a = n
and 
Hyperbolas in the multiplication table
If the products in the multiplication table are color-coded according to their
magnitude, hyberbolas of the form
RC = constant
produce a rainbow effect:
This image is included simply for its visual impact.
Appendix 2: Unfinished Problems
Generalization of Lemma 12
If p and q ≤ p + 1 are primes and n is a natural number such that
p(q - 2) ≤ n ≤ (p - 1)(q - 1),
then {n,pq} are central divisors if and only if n is not divisible by q - 1.
n ≤ (p - 1)(q - 1)
so {p(q - 1),qn/(q - 1)} are closer together than {n,pq}, and therefore {n,pq}
are not central divisors.
Proof of Lemma 4
If {a,b} are central divisors, then so are {m,ab} for all natural numbers m such
that
These limits are closer together for central divisors {a,b} than for any other
factor pair of the product ab.
(a - 1)(b - 1) < m < (a + 1)(b + 1)
(22)
d - c > b - a
and similarly,
-(d + c) < -(b + a)
Therefore, the limits in (22) for {c,d} are farther apart than for {a,b}, QED.
(a - 1)2 < m < (a + 1)2
Then {m,a2} are central divisors by
Lemma 15 with
0 = (1 - 1)(p - 1) < m < (1 + 1)(p + 1) = 2(p + 1),
or
1 ≤ m ≤ 2p + 1
This is established in the alternate proof of Lemma 7,
QED.
Henceforth, we can assume b is a prime p ≥ 5, and (22) becomes
b Range of m in (22) ab {m,ab} are central divisors 2 2 ≤ m ≤ 8 4 for all 7 values of m 3 3 ≤ m ≤ 11 6 for all 9 values of m 4 4 ≤ m ≤ 14 8 for all 11 values of m
p ≤ m ≤ 3p + 2
If m = p, then {m,ab} = {p,2p} are central divisors by
Lemma 6. Therefore,
If m is prime, then m > p ≥ 5 > 2 by (23), so {m,ab} = {m,2p} are central
divisors by Lemma 11. We can henceforth assume m is
composite.
p + 1 ≤ m ≤ 3p + 2
(23)
Case 1: {k,2pm/k}
and the reference pair {m,2p}.
Case 2: {2,mp}
Case 3: {2k,pm/k}
Case 4: {p,2m}
Case 5: {pk,2m/k}
Case 6: {2pk,m/k}
m ≤ 3p + 2 < 3p + p = 4p
and
k ≤ m/2 < m
so 2pm/k is greater than both reference factors, and therefore {k,2pm/k} are not
central divisors by Lemma 5.
mp ≥ 5m > m
and
mp ≥ (p + 1)p ≥ 6p > 2p,
so mp is greater than both reference factors, and therefore {2,mp} are not
central divisors by Lemma 5.
3 ≤ m/k ≤ m/p ≤ 3 + 2/p < 4
by (23), so m/k must be 3. It follows that
m = 3k ≤ 3p + 2
so k = p, and {2k,pm/k} is again the same as the reference pair.
pm/k > m
and
m/k > 2
so pm/k is greater than both reference factors, and therefore {2k,pm/k} are not
central divisors by Lemma 5.
2m > m
and
2m ≥ 2(p + 1) > 2p,
so 2m is greater than both reference factors, and therefore {p,2m} are not
central divisors by Lemma 5.
m/p ≤ 3 + 2/p < 4 ≤ k, or pk > m
If m ≤ 3p - 1, then
m/p ≤ 3 - 1/p < 3 ≤ k, or pk > m
Since pk ≥ 3p > 2p, we have shown that if m ≠ 3p, then pk exceeds both
reference factors, and therefore {pk,2m/k} are not central divisors by
Lemma 5.
(p - 3)(p + 2) > 0
so {pk,2m/k} = {p2,6} are farther apart than the reference pair
m ≤ 3p + 2 < 3p + p = 4p = 2p(2) ≤ 2pk
and
2pk ≥ 2p(2) > 2p,
so 2pk is greater than both reference factors, and therefore {2pk,m/k} are not
central divisors by Lemma 5, QED.
References & Acknowledgements
[1] P. Erdős, Some remarks on number theory, Riveon Lematematika 9
(1955) 45-48, cited in D. Koukoulopoulos and J. Thiel, Arrangements of stars on
the American flag, The American Mathematical Monthly 119, No. 6 (2012), p. 447;
available at
https://www.maa.org/sites/default/files/pdf/pubs/monthly_june12-stars.pdf
MathSite
