  |
Tau vs. RCFGlossary |
On the Divisor and Regular Counting Functions
Consider the divisor counting function τ(n) = [4: A000005], the number of divisors d of an integer n, i.e., all d | n, gcd(d, n) = d. [1]
Recall that we can rewrite any integer n > 1 in the standard form of prime power decomposition. Let p be a distinct prime divisor of n, and ε > 0 be the exponent or multiplicity of p in n:
n = p1ε1 · p2ε2 · … · pkεk
with p1 < p2 < … pk
Each p is distinct, i.e., different from any other p in the formula. Computation of the number of divisors of n depends on the multiplicities ε of each distinct prime divisor p | n. [2, 3, 5, 6]
τ(n) = (ε1 + 1)(ε2 + 1)…(εk+ 1)
The divisor counting function τ(n), charted
We can chart the divisors of n to illustrate this formula. Let’s consider examples of n = {10, 12, 16, 60}. The charts situate each distinct prime divisor p of n on its own axis, running the non-negative integer exponents ε of each p linearly along the axis. Sixteen has one distinct prime divisor p = 2, requiring one axis. The numbers 10 and 12 have two distinct prime divisors p = {2, 5} and {2, 3}, respectively; these require two axes. Lastly, 60 has three distinct prime divisors p = {2, 3, 5} and needs three axes. The charts simply place the products r of the powers ε of each p in cells much like a multiplication table. Only the values of 0 < r ≤ n appear in the table. Thus the table includes all regular numbers 0 < r ≤ n. Divisors are special cases of regular numbers r that divide n evenly. The nondivisor r are shown in orange (■), those that are divisors d > 1 are colored red (■), and the number 1 is colored purple (■). Together, the number 1 ■ and other divisors ■ comprise the set of divisors D of r, while nondivisor regular digits ■ (semidivisors) are not part of this set.
| n = 10: | n = 12: | n = 16: | |||||||||||||||||||||||||||||||||
|
|
|
n = 60:
| 50 | 51 | |||||||||||||||||||||||||
|
|
We can see from the chart for n = 16 that τ(16) = 5. Note that it includes a divisor for each of the four nonzero exponents of the prime divisor 2, plus 1 for ε = 0. For n = {10, 12}, we have two axes, one for each of the 2 distinct prime divisors of the bases. In the decimal case, 10 is an even semiprime, thus it has multiplicities of 1 for both its distinct prime divisors. Again, there is a divisor for each nonzero exponent of each distinct prime, and one for the zero exponent. These 2-divisor axes multiply to yield 4 divisors total. Base 12 has different multiplicities, 2 for the prime 2, and 1 for the prime 3. These multiply to yield 6 divisors in all. Lastly, 60 has three distinct prime divisors, each with its own axis. We can use the formula
τ(n) = (ε1 + 1)(ε2 + 1)(ε3+ 1)
= (2 + 1)(1 + 1)(1 + 1) = 3 × 2 × 2
to arrive at 12 divisors.
We can write a program that produces all the divisors in a chart like the ones above in a line-by-line fashion. Such a program appears at [4: A275055].
Extending the chart to include all n-regular numbers
It is clear that we could make such charts for an infinite prime power range, i.e., an axis for each prime that included all nonzero positive integers as exponents. Indeed, this would be an infinite table that would contain all the n-regular numbers! The number of n-regular numbers r is infinite, since despite having a finite number ω(n) of distinct prime divisors p, we may take the product of any number of prime divisors in any positive multiplicity to produce an n-regular number. Indeed we know that the cardinality of the number of n-regular numbers is ℵ0, since the tables contain distinct terms and the terms can be sorted. Let us call this infinite ω(n)-dimensional table of n-regular numbers R (a tensor of rank ω(n)).
Further, since the prime power ranges are dependent only upon the distinct prime divisors p | n, we note that certain numbers have the very same infinite tensor R. For instance, for n = {6, 12}, R is the same infinite table, since both 6 and 12 have the distinct prime divisors {2, 3}. Indeed, 6 is the squarefree kernel of 12. We can find the squarefree kernel of any number n by selecting its largest composite squarefree divisor or by taking the product of the distinct prime divisors of n [4: A007947]. Thus, we might instead refer to the table common to {6, 12, 18, 24, 36, …}, i.e. any such that the distinct prime divisors are {2, 3} [4: A033845], as R6.
The regular counting function RCF(n)
The regular counting function RCF(n) can be regarded analogously to the divisor counting function τ(n). The bounding of the function τ(n) to include d ≤ n is natural, since divisors cannot exceed n. It is less natural perhaps to consider the regular numbers r ≤ n, since there are an infinite number of semidivisors larger than n. There are some interesting properties of RCF(n) that perhaps underscore a purpose for the bound. Primes n = p and perfect prime powers n = pε do not have semidivisors r < n. Numbers 1 ≤ k ≤ p must either divide or be coprime to p in the first case, and all regular 1 ≤ k ≤ pε, are divisors in the second case as they are themselves perfect prime powers pm with 0 ≤ m ≤ ε. Of course, n itself is n-regular, and as stated, divisors, a special case of n-regular number, may not exceed n. For this reason, people have determined a motivation to create a counting function for regulars r ≤ n. Indeed the regular counting function RCF(n) is tantamount to [4: A010846].
We can chart regular numbers (including semidivisors) merely by taking that portion of the infinite table R, and including only those numbers that do not exceed n. The tables below pertain to the smallest 4 numbers n that have R6 as the infinite table of regular numbers. We note that the “red box” of divisors that is defined by 1 at upper left and n in the lower right changes between each table. Also, we see that more of the infinite table R6 is admitted into R as n increases, and that R(6) (written thus to distinguish the trimmed version from the infinite R6) is fully contained in R(12), which is in turn fully contained in R(18), etc.
For these numbers that have 2 distinct prime divisors, we have a 2-dimensional table (a rank-2 tensor) and the “cut” is a jagged diagonal line. For 3 distinct primes, we have a corner of the tensor that has 3 axes, like sawing off a corner of a cardboard box, the sawed-off surface being jagged like a Minecraft hill turned upside down. This is an effect of the discrete bound at n. It would seem that there is no easy method of writing a formula for RCF(n) that is as elegant as τ(n).
| n = 6: | n = 12: | n = 18: | n = 24: | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
Returning to the first-introduced numbers {10, 12, 16, 60}, we have charts like below:
| n = 10: | n = 12: | n = 16: | ||||||||||||||||||||||||||||||||||||||||||
|
|
|
n = 60:
| 50 | 51 | 52 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
The most efficient regular counting function algorithm
We can write an algorithm that employs the prime power ranges and bound to efficiently construct the finite table R(n). The algorithm appears at [4: A275280].
We can use the property of the tensor R(n) of regular numbers as the tensor product of the prime power ranges p0 … pfloor(logp n) such that p | n to most efficiently compute RCF(n). In short, we can generate a table of all the products less than n of the powers of the distinct primes of n, then count the products, rather than search all numbers in the range 1 ≤ k ≤ n for r | nε with ε > 0. This method is the most efficient because the value of RCF(n) is rather small compared to n as n increases. This approach involves the construction of R(n).
The most conspicuous problem to which this method has been applied is that of the famous “Hamming number” problem put forth by Edsger W. Dijkstra. In this application, we are asked to create a table of the 60-regular numbers, i.e., the 5-smooth numbers, in their order. In Wolfram Language, Robert G. Wilson V wrote the following script to generate [4: A051037] which lists the 5-smooth numbers in their order:
f[n_]:= Sort@ Flatten@ Table[ 2^a * 3^b * 5^c,
{a, 0, Log[2, n]},
{b, 0, Log[3, n/2^a]},
{c, 0, Log[5, n/(2^a * 3^b)]}]
We can generalize this code to fit any positive integer n merely by obtaining a list of the distinct prime divisors of n. This program writes a statement that it executes, given such a list:
f[n_] := Function[w,
Length@ ToExpression@
StringJoin["With[{n = ", ToString@ n, "},
Flatten@ Table[", ToString@
InputForm[Times @@ Map[Power @@ # &, w]], ", ",
Most@ Flatten@ Map[{#, ", "} &, #], "]]"] &@
MapIndexed[Function[p,
StringJoin["{", ToString@ Last@ p, ", 0, Log[",
ToString@ First@ p, ", n/(", ToString@
InputForm[Times @@ Map[Power @@ # &,
Take[w, First@ #2 - 1]]], ")]}"]]@
w[[First@ #2]] &, w]]@
Map[{#,
ToExpression["p" <> ToString@ PrimePi@ #]} &,
FactorInteger[n][[All, 1]]]
Given an input of 2310, for example, the script writes the statement:
With[{n = 2310}, Flatten@ Table[
2^p1 * 3^p2 * 5^p3 * 7^p4,
{p1, 0, Log[2, n/(1)]},
{p2, 0, Log[2, n/(2^p1)]},
{p3, 0, Log[5, n/(2^p1 * 3^p2)]},
{p4, 0, Log[7, n/(2^p1 * 3^p2 * 5^p3)]}]]
and the statement Length counts the 68 terms in the table. Thus, RCF(2310) = 68.
This program finds RCF(p8#) in 1¼, RCF(p9#), RCF(p10#) in 24, and RCF(p11#) in 105 seconds. We can project that it would require about 10, 50, and 240 minutes to calculate RCF(p12#), RCF(p13#), and RCF(p14#), respectively. The same algorithm, compiled on other machines, might calculate these figures in very much less time.
We have demonstrated how the divisor counting function τ(n) and the regular counting function RCF(n) are related, and how to calculate both.
References
Links to the glossary contain further references.
Concerns OEIS sequences A000005, A007947, A010846, A033845, A051037, A275055, A275280.
[1] Dudley 1969, Section 7, “The divisors of an integer”, page 50, specifically:
“Let n be a positive integer. Let d(n) denote the number of positive divisors of n (including 1 and n), and let σ(n) denote the sum of the positive divisors of n. That is, d(n) = ∑_(d ∣ n) 1 and σ(n) = ∑_(d ∣ n) d. ∑_(d ∣ n) means the sum over the positive divisors of n.”
[2] Dudley 1969, Section 7, “The divisors of an integer”, page 51−52, specifically:
“If p1e1 p2e2 … pkek is the prime-power decomposition of n, then d(n) = d(p1e1)d(p2e2)…d(pkek)” and the ensuing proof.
[3] Dudley 1969, Section 7, “The divisors of an integer”, page 53, specifically:
“If p1e1 p2e2 … pkek is the prime-power decomposition of n, then σ(n) = σ(p1e1)σ(p2e2)…σ(pkek)” and the ensuing proof.
[4] Sloane, Neil, The On-Line Encyclopedia of Integer Sequences, Retrieved June 2019.
[5] Ore 1948, Chapter 5, “The aliquot parts”, page 86, specifically, Equation 5-4:
“Theorem 5-1. The number of divisors of a number N in the form [N = p1α1 p2α2 … prαr] is ν(N) = (α1 + 1)(α2 + 1)…(αr+ 1)”
[6] Weisstein, Eric W. “Divisor Function”, Wolfram MathWorld. Retrieved October 2012.