by Michael Thomas De Vlieger, 5 September 2014, St. Louis, Missouri.
This paper concerns OEIS A244052.
The numbers A244052(n) that set records for the number of regular m ≤ n are
This paper concerns arithmetic relationships between nonzero positive integers m ≤ n and n. The divisor counting function σ0(n) enumerates all divisors m | n and the Euler totient function φ(n) counts all m ≤ n that are coprime to n. This paper investigates the set of “neutral numbers,” composites m that are neither divisors of composites n nor coprime to n. Two types of neutral numbers are proved to exist. Methods of construction and quantification of such neutral numbers m ≤ n are introduced.
There are two kinds of neutral numbers, those positive integers a that neither divide b nor are coprime to a larger integer b. This brief explains the two kinds of neutral numbers a with respect to b, and the neutral arithmetic relationship. The neutral numbers a < b for b = 10 appear in the number line shown in Figure 1.
Figure 1: Neutral a < b = 10 |
|||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
In order to get started, you need to know what a prime and composite number is, and that 1 is neither prime nor composite. The number 1 is simply an empty product. You also need to know about divisibility. A number a that divides b is a divisor; a / b results in an integer. A number a coprime (or relatively prime) to b has no prime divisors in common with b. You should understand the Fundamental Theorem of Arithmetic and prime decomposition.
A number a may only divide b or be coprime to b if either or both are prime. There are only two alternatives if either or both a and b are prime. If both a and b are composite and b > 4, a may be neutral to b.
There are three principal arithmetic relationships. An arithmetic relationship is one that involves two positive integers a and b, comparing the sets of prime divisors of a to that of b.
The coprime relationship is when a and b have no primes in common; their only common factor is the empty product 1. We can use the greatest common divisor (highest common factor) to test for coprimality. If a and b are coprime, then gcd(a, b) = 1. As a consequence, no prime p that divides a will divide b, and no prime q that divides b will divide a. The numbers {1, 3, 7, 9} are coprime to b = 10. A number a < b that is coprime to b is called a totative. This name is related to the notion of totalling up the numbers a < b that are coprime to b, as we do when we use the Euler totient function φ(b) to count the totatives of b. Numbers a that are larger than b may also be coprime to b; these are simply called coprimes, since totatives by definition must be smaller than b. See OEIS A000010 for the number of totatives of b (i.e., the Euler totient function φ). Figure 2 shows the totatives of b = 10 in blue.
Figure 2: Totatives a of b = 10 |
|||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
The second principal arithmetic relationship is regularity. The number a is said to be regular to b if all the prime divisors p of a also divide b. This doesn't necessarily work the other way around; b is regular to a if and only if a and b have a common set of distinct prime divisors. An example is a = 6, b = 12. Both have the distinct prime divisors {2, 3}. The divisor is a special case of a regular number a with respect to b. A divisor a has multiplicities of primes p that do not exceed the respective multiplicities for p in b. The divisors of 10 are {1, 2, 5, 10}; none of these numbers has a multiplicity for a prime 2 or 5 that exceeds the corresponding multiplicity in 10. We can calculate the number of divisors of b using the divisor counting function τ(b), sometimes written as σ0(b). Figure 3 shows the divisors of b = 10 in red.
Figure 3: Divisors a of b = 10 |
|||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
There are nondivisor regular numbers a < b for many composite b. These are called semidivisors, since they do divide a regular multiple of b. The semidivisors of 10 are {4, 8}. Semidivisors are too rich in multiplicity of at least one prime divisor p to divide b. For example, 4 does not divide 10 because it is 2² while 10 = 2 × 5. Generally, the term semidivisor applies to nondivisor regular a < b. All the regular numbers a > b are nondivisors. The smallest semidivisor is a = 4 for b = 6. Semidivisors are nearly as rare as divisors. See OEIS A010846 for the number of regular numbers a ≤ b, OEIS A000005 for the number of divisors of b (i.e., the divisor counting function τ), and OEIS A243822 for the number of semidivisors of b. In terms of integer sequences at OEIS, A010846(b) = A000005(b) + A243822(b). The regular numbers a < b for b = 10 are shown in Figure 4. Divisors are in red, semidivisors in orange.
Figure 4: Regulars a < b of b = 10 |
|||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
Finally, the last principal arithmetic relationship is semicoprimality. The number a is semicoprime to b if a has at least one prime factor p that also divides b, and at least one prime factor q that is coprime to b. When a < b is semicoprime to b, we call them semitotatives. The semitotative of 10 is 6, as it is the product of a prime divisor 2 and a prime totative 3. For b = 16, there are 4 semitotatives: {6, 10, 12, 14}. The smallest semitotative is a = 6 for b = 8. Semitotatives are rare when b is small, but eventually become either the commonest or second most common relationship between a and b. See OEIS A243823 for the number of semitotatives of b. Figure 5 shows the semitotative of b = 10. Figure 6 shows the 4 semitotatives of b = 16.
Figure 5: Semicoprime a < b of b = 10 |
|||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
Figure 6: Semicoprime a < b of b = 16 |
|||||||||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
The neutral relationship includes only two of these basic arithmetic relationships. We can prove this by considering that neutral numbers a are composite with respect to composite numbers b. We are dealing with composite numbers only, and need not regard prime values for a or b.
The simplest conception of a composite number is the product of at least two primes. Suppose prime p divides b and prime q is coprime to b. We have three alternatives to consider:
pp, pq, qq.
The last case is the easiest to consider. The product a = qq is coprime to b. Neither prime factor q divides b, thus no divisor of b is brought into the composite qq. The number b and qq have nothing in common, gcd(qq, b) = 1, thus qq is simply a composite number coprime to b, therefore case qq is not neutral to b by definition. Totatives a < b are coprime and by definition, not neutral to b.
The case a = pq is a product of at least one prime p that divides b and one prime q that is coprime to b. It matches the description of a semicoprime number a with respect to b. The number pq cannot divide b because q is coprime to b. It can't be coprime to b since p divides b; gcd(pq, b) = p, and 1 < p < pq. Thus case pq is a neutral number a semicoprime to b. Semitotatives a < b are thus one kind of neutral number.
The case a = pp is a product whose prime divisors also divide b, thus it is regular. However, divisors are regular numbers; we must distinguish whether pp itself divides b. If so, pp is a divisor of b and not neutral. Only the cases of pp that do not divide b are neutral to b.
We are out of cases, thus there are only two kinds of neutral number, there are no further possible types to consider. However we should examine the special case of a = 1. The number 1 is special. It is an empty product. Because it divides b, it is regular to b, however it also is coprime to b, since gcd(1, b) = 1. Instead of being neutral to b, it is both a divisor and a totative of b at the same time. Because of this, some refer to 1 as a "unit".
Thus, the number of neutral numbers a ≤ b (see OEIS A045763) is the sum of the number of semidivisors of b and the number of semitotatives of b. In terms of integer sequences at OEIS, A045763(b) = A243822(b) + A243823(b). Figure 7 shows a map of all the relationships the numbers a ≤ b have with b = 10. In this map, the unit is purple, divisors red, semidivisors orange, semitotatives yellow, and totatives are gray.
Figure 7: a < b of b = 10 |
|||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
Figure 8 shows the neutral numbers a ≤ b for 2 ≤ b ≤ 16. Semidivisors appear in orange and semitotatives in yellow. An expanded map that covers 2 ≤ b ≤ 30 can be found here. This map clearly shows neutral numbers a for small numbers b, but how can we know that b = 1200, say, has neutrals?
| Regular m < n of n | |||||||||||||||||
|
|||||||||||||||||
| 2 | 1 | 2 | |||||||||||||||
| 3 | 1 | 2 | 3 | ||||||||||||||
| 4 | 1 | 2 | 3 | 4 | |||||||||||||
| 5 | 1 | 2 | 3 | 4 | 5 | ||||||||||||
| 6 | 1 | 2 | 3 | 4 | 5 | 6 | |||||||||||
| 7 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | ||||||||||
| 8 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |||||||||
| 9 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ||||||||
| 10 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |||||||
| 11 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | ||||||
| 12 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |||||
| 13 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | ||||
| 14 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | |||
| 15 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | ||
| 16 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | |
Key: ■ Unit, ■ Divisor, ■ Semidivisor, ■ Nonregular
Neutral numbers a ≤ b are the province of composite a and composite b; both must be composite, as we stated before. If one or the other—or both are prime, there can be no neutral relationship. Because neither a nor b can be prime, the minimum possible value for either to have a neutral relationship is 4.
Let's look at the smallest of each kind of neutral number. If we look at a map of the numbers a ≤ b for b = 4 (see Figure 9) we have "no room" for neutrals. Two of the numbers a ≤ b are prime, and the other two are divisors. Since the miminum possible value for a neutral a is 4, and since 4 divides 4, b = 4 cannot have neutral a ≤ b.
However, a = 4 can be neutral to a larger b. The next highest even number, b = 6, is divisible by the prime divisors of 4, thus 4 is regular but does not itself divide 6. The number 4 is a semidivisor of 6; it is the smallest semidivisor possible. Figure 10 is a map of the arithmetic relationships for b = 6.
|
|
||||||||||||||||||||
We've found the minimum case of a and b that support a semidivisor.
What is the minimum case for a and b that supports a semitotative? Remember that a semitotative is the product of at least one prime p that divides b and at least one prime q that is coprime to b. If we want a minimum case, then we want one each of p and q in the product. The primes p and q cannot be the same prime, otherwise the number would be a prime power, and the prime divisor would have to either divide b or be coprime to b—there is no middle ground. We would want p and q to be small primes so the product pq would be small as possible. If these prime divisors have to be different and small, we might look at {2, 3} as the factors. This implies the minimum semitotative would be a = 6, but for which value of b? If b is a composite product of p = 2 or 3, and we know 4 and 6 do not have semitotatives, we might try 8 or 9, the cube of 2 and the square of 3, respectively. The number b = 8 is smaller than 9, not divisible by q = 3, but the cube of p = 2. Thus a = 6 for b = 8 is the smallest case of the semitotative.
Looking at Figure 8, we can see our observations for the smallest semidivisor and smallest semitotative are true. We can also see that b = 10 is the smallest value of b to have both semidivisors and semitotatives. Looking at the expanded map of neutrals, we can see that a = 12 is the smallest value of a that generates semidivisors and semitotatives as b varies.
Looking at the expanded map, we can see that there is more of a pattern in the columns of constant values of a than there are in the patterns we see in the rows of constant values of b. Let's look at a few of these patterns.
First, prime values of a or b have no neutrals and it is clear that there can be no neutrals when a prime is concerned.
Looking at constant b (rows), especially at the expanded map, we see that (perfect) prime powers can have no semidivisors. This stands to reason, because a prime power like 8, 9, or 16 has a single distinct prime divisor, 2, 3, and 2 respectively. You either have all or none of these distinct primes in any subset. A semidivisor must have "too much" of a prime divisor p of b. Suppose b = pα, with α > 1. If we have a regular number a = pδ with "too much" of the prime p, i.e., with δ > α, then a > b and we are out of bounds. There are regular numbers for prime powers b, but they are larger than b. Any regular number a ≤ b divides a prime power b.
All prime powers except 4 have at least one semitotative, even if they have no semidivisors. Consider that the smallest primes are much smaller than prime powers. Even the second prime, 3, is smaller than the square of the first prime, 4, but not small enough for pq to be less than 4. The next prime power in the sequence of perfect prime powers (see OEIS A025475) is 8; it is larger than pq, and as the prime power pα increases either via p or multiplicity α, pq remains relatively small. It is safe to say that a prime power b = pα > 4 has no semidivisors and will have at least one semitotative.
For b that are squarefree semiprimes, products of two dissimilar primes like 6, 10, 14 (see OEIS A006881), we will have at least one semidivisor. Suppose we have an enormous semiprime b = p1p2, with p2 = p1 + 2, i.e, minimally distinct prime divisors. This implies that p1 is slightly less than the square root of p1p2. Even if p1² = p1p2 − 1, there will be a p1² < p1p2. This square of p1 must be a semidivisor, since its multiplicity for p1² exceeds that of p1p2. If we multiply by additional factors, we are only making the smallest prime divisor proportionally smaller, therefore "easier" to obtain a square that is less than b. This guarantees that we will have semidivisors for any composite that is not a prime power.
Finally, we will have semitotatives for all composite numbers except 4 and 6. We examined the concept of the minimum semitotative above. Looking at the set of distinct prime divisors of any number b, especially if b is large, we see that we get a lot from so few distinct prime divisors. We can make the smallest semitotative a = pq for any b simply by multiplying the minimum prime divisor p of b with the minimum prime totative q of b. The smallest composite, b = 4, is too small for semitotatives, since the smallest semicoprime a is 6, which exceeds 4. The minimum prime totative q = 5 for b = 6 making the smallest semicoprime pq too large. When b is larger than 8, however, the minimum p and q are increasingly small relative to b, and we easily have at least one semitotative. Check out a large map of arithmetic relationships here to see for yourself that semitotatives are very common for large b.
Looking at columns, that is, with constant values of a, the maps of arithmetic relationship are more patterned. Generally, we have semitotatives for any multiple of a prime divisor p of composite a. If a is a prime power pα, we have semidivisors for every multiple of p, but no semitotatives, the opposite of the case for b = pα. If the multiplicity of any prime divisor p of composite a exceeds 1, then we will have semidivisors for any multiple of the set of distinct prime divisors of a.
When we explored the 3 kinds of arithmetic relationship, we described methods of calculating the number of totatives and the number of divisors of b. These formulas are well-known and described in detail in any elementary number theory book. The Euler totient function φ (Wikipedia, MathWorld) counts the number of totatives given the set of distinct prime divisors of b. See OEIS A000010 for tables of values of φ(b). The divisor counting function τ (Wikipedia, MathWorld, where it appears as σ0) requires both the distinct prime divisors and their multiplicities. See OEIS A000005 for tables of values of τ(b).
The quantity of neutral numbers as a whole (i.e., without distinguishing semidivisors and semitotatives) for b are easily computed by the following formula:
ξ(b) = b - [τ(b) + (φ(b) − 1)]
In other words, subtract 1 from the number of totatives, add the number of divisors, and subtract this sum from b itself to get the number of neutrals of b. See OEIS A045763 for tables of values of ξ(b).
I am not sure there are ways to compute the number of semidivisors or semitotatives. Perhaps if there were a way to calculate the number of regular numbers a ≤ b of b, then we could subtract τ(b) and get the number of semidivisors, then subtract the number of semidivisors from the number of neutrals to get the number of semitotatives. The reason why I am not confident about computing the number of regulars is that this quantity depends on the spacing of primes, a big open question in mathematics. There are ways of estimating regulars but these are too complicated for this brief.
Algorithms for generating and counting neutrals.
I've written a set of Wolfram Mathematica functions that generate semidivisors and semitotatives for any b, and quantify them. These algorithms use "brute force" computation; they uncover instances of semidivisors and semitotatives by actually sifting them from among the range of numbers a ≤ b, then comparing their prime divisors with those of b. Thus they are effective for small values of b (say, in the thousands maximum).
Testing for semidivisors. The first algorithm that I wrote for producing semidivisors involved a quality of regular numbers called richness. The newest algorithm avoids this and simply examines the set of prime divisors of a for elements q that do not divide b evenly.
nondivisorRegularQ[m_Integer, n_Integer] := Module[{a = First /@ FactorInteger @ m },
If[Length[Select[a, Divisible[n, #] &]] == Length[a] && ! Divisible[n, m], True, False]]
Generating semidivisors. This algorithm will produce a list of semidivisors of b:
semidivisorSet[n_Integer] := Flatten[Position[Thread[nondivisorRegularQ[Range[1, n], n]], True]];
Counting semidivisors. This Wolfram script will count the number of semidivisors of b.
semidivisors[n_Integer] := Count[Thread[nondivisorRegularQ[Range[1, n], n]], True];
Using these scripts, I contributed OEIS sequence A243822 (the semidivisor counting function ξd(b)) in June 2014.
Testing for semitotatives. The first algorithm relied on a negative value from the richness module, a quality that has nothing to do with semitotatives. The newest algorithm avoids this and simply examines the set of prime divisors of a for elements q that do not divide b evenly. In order to be completely valid, the algorithm ensures that the number a is neutral to b using the fact that neutrals have 1 < gcd(a, b) < a. The algorithm is thus reliant on my proof that there are only two kinds of neutral numbers; one the product of primes p that also divide b, and the other the product of primes p, but also at least one prime q coprime to b. The output of both the old and new algorithms is identical for b ≤ 10,000 (higher values have been tested but they are not contiguous with this range.)
semicoprimeQ[m_Integer, n_Integer] := Module[{a = First /@ FactorInteger @ m },
If[Length[Select[a, Divisible[n, #] &]] < Length[a] && 1 < GCD[m, n] < m, True, False]]
Generating semitotatives. This algorithm will produce a list of semitotatives of b:
semitotativeSet[n_Integer] := Flatten[Position[Thread[semicoprimeQ[Range[1, n], n]], True]];
Counting semitotatives. This Wolfram script will count the number of semidivisors of b.
semitotatives[n_Integer] := Count[Thread[semicoprimeQ[Range[1, n], n]], True];
These scripts facilitated OEIS sequence A243823 (the semidivisor counting function ξt(b)) of June 2014.
We've already discussed the neutral counting function and its relationship to the Euler totient function and divisor counting function. Let's look at the neutral counting function and the semidivisor and semitotative counting functions. Because there are two kinds of neutral relationship, we can write
ξ(b) = ξd(b) + ξt(b)
That is, the number of neutrals equals the number of semidivisors plus the number of semidivisors. In terms of the OEIS,
A045763(b) = A243822(b) + A243823(b)
Because there are two types of regular relationship, we can write:
g(b) = τ(b) + ξd(b)
i.e., the number of regulars a < b equals the number of divisors plus the number of semidivisors. In terms of the OEIS,
A010846(b) = A000005(b) + A243822(b)
Now that we've examined the possibility that neutrals exist, shown that there are only two kinds, explored the circumstances for both types, and described ways of constructing and quantifying these types of neutrals, we can integrate them into the "bigger picture". The following chart shows neutrals, divisors, and totatives for b ≤ 16. Click here to see an expanded map.
| Arithmetic Relationship of m < n to n | |||||||||||||||||
|
|||||||||||||||||
| 2 | 1 | 2 | |||||||||||||||
| 3 | 1 | 2 | 3 | ||||||||||||||
| 4 | 1 | 2 | 3 | 4 | |||||||||||||
| 5 | 1 | 2 | 3 | 4 | 5 | ||||||||||||
| 6 | 1 | 2 | 3 | 4 | 5 | 6 | |||||||||||
| 7 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | ||||||||||
| 8 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |||||||||
| 9 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ||||||||
| 10 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |||||||
| 11 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | ||||||
| 12 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |||||
| 13 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | ||||
| 14 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | |||
| 15 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | ||
| 16 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | |
Key: ■ Unit, ■ Divisor, ■ Semidivisor, ■ Semitotative, ■ Totative
This concludes our exploration of neutral numbers a less than or equal to b.
(13 August 2014)
