(Necessarily composite nondivisors in the cototient of n)
by Michael Thomas De Vlieger, 22 October 2011, condensed 13 August 2014, code revised 24 October 2017, St. Louis, Missouri.
(This is a brief and elementary version of the original paper, with additional materials in the Appendix that pertain to further studies of the subject.)
Consider divisors d | n and “totatives,” positive integers t < n coprime to n, i.e., gcd(k, n) = 1. The “cototient” of n consists of all numbers m ≤ n that are not totatives, i.e., gcd(k, n) > 1, while a nondivisor is a number that does not divide n evenly. Consider numbers in the cototient of n, listed in row n of A121998 and enumerated by A051953(n). For composite n > 4, there are nondivisors m in the cototient, listed in row n of A133995 and enumerated by A045763(n). Of these m, there are precisely 2 species. The first is m that divide ne with integer e > 1, while the latter do not divide ne. These are listed in row n of A272618 and A272619 respectively, and counted by A243822(n) and A243823(n), respectively. We shall call the former species a “semidivisor” and the latter species a ”semitotative“ of n. We know that 1 | n and gcd(n, 1) = 1, therefore 1 is both a divisor and a totative of n. With this exception, the range 1 ≤ k ≤ p (with p prime or 4) consists of divisors and totatives; range 1 ≤ k ≤ pe (with pe in A000961, i.e., a perfect prime power > 4) of divisors, totatives, and semitotatives, and for all other composite n of divisors, totatives, semidivisors, and semitotatives. An exception to the last clause is that for n = 6, we have only divisors, totatives, and 1 semidivisor. This paper investigates the set of “neutral numbers,” necessarily composite nondivisors m in the cototient of n (We use “neutral” here for concision). 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. (See OEIS A133995 for listings of neutral numbers less than n.)
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.
This paper regards three basic arithmetic relationships. For the purposes of this paper, 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. (See OEIS A038566 for totatives of n.)
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. (See OEIS A027750 for divisors of n.)
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. (See OEIS A162306 for numbers k ≤ n regular to n. For nondivisor regulars shown in orange, see A262618.)
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 called "semicoprimality" in this paper. 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. (See OEIS A262619 for numbers k < n semicoprime to n.)
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”.
Let’s look at distinguishing numbers a neutral to b a different way. Nondivisors a in the cototient of b either divide be with e > 1 or they do not. The first species is the semidivisor while the nondivisor of be is the semitotative. A method of testing whether a number a is a semidivisor is finding an exponent k such that a | bk. We know that if a given number m divides nj, then m also divides n(j + 1), therefore we can select a “sure-fire” exponent k such that a | bk. The smallest prime is 2: therefore we can use b(log²(n)) (mod a) ≡ 0 to test for a regular number a ≤ b with respect to b. Nondivisor regulars must be semidivisors; those nondivisors in the cototient that are non-regular are semitotatives. This method is handy because it avoids decomposing a and b. (A test for regulars a > b may use the less-efficient ba (mod a) ≡ 0).
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?
| Figure 8: Neutral a ≤ b for b = 10 | ||||||||||||||||||
Key: ■ Semidivisor, ■ Semitotative, ■ Non-neutral |
||||||||||||||||||
| 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 | ||
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.
Figure 9 |
|||
| 1 | 2 | 3 | 4 |
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.
Figure 10 |
|||||
| 1 | 2 | 3 | 4 | 5 | 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 directly. 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.
I've written a set of Wolfram Mathematica functions that generate semidivisors and semitotatives for any n, 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 m ≤ n, then comparing their prime divisors with those of n. Thus they are effective for small values of n (say, in the thousands maximum). Algorithms that use the more complicated regular counting function r(n) approach construct numbers m regular to n and are generally faster. Let's start with that efficient r(n) function. The code that depends on this definition will be shown last in all the cases that follow.
The most efficient method of counting regular numbers m ≤ n. This algorithm generates all regular m less than or equal to n. It is effective up to primorial A002110(9). The function r(n) = A010846(n) is handy to have and is not easy to generate as n increases.
r[n_] := Block[{w},
If[Length@ # == 1, 1 + #[[1, -1]] - Boole[n == 1],
Function[w, 1 + Last@
ToExpression@
StringJoin["Module[{n = ", ToString@ n, ", k = 0}, Flatten@ Table[k++, ", 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@ #]} &, #[[All, 1]] ]] &@ FactorInteger@ n]
This function generates the regular numbers m of n:
regulars[n_] := r[n_] := Block[{w },
If[Length@ # == 1, 1 + #[[1, -1]] - Boole[n == 1],
Sort@ ToExpression@
Function[w,
StringJoin["Module[{n = ", ToString@ n, ", k = 0}, Flatten@ Table[",
StringJoin@ Riffle[Map[ToString@ #1 <> "^" <> ToString@ #2 & @@ # &,
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@ #]} &, #[[All, 1]] ]] &@ FactorInteger@ n]]
Testing for semidivisors. The first algorithm that I wrote for producing semidivisors involved a quality of regular numbers called richness. This algorithm takes advantage of the fact that m regular to n divides ne with power 0 < e < m.
nondivisorRegularQ[m_Integer, n_Integer] := PowerMod[n, m, m] == 0
This approach might presesnt memory problems in some environments and large values of m or n. An alternative is this:
nondivisorRegularQ[m_Integer, n_Integer] :=
Or[Abs@ m == 1,
SubsetQ[FactorInteger[n][[All, 1]], FactorInteger[m][[All, 1]]]]
Using the regulars[n] function:
nondivisorRegularQ[m_Integer, n_Integer] := MemberQ[regulars[n], m]
Generating semidivisors. This algorithm will produce a list of semidivisors of b:
semidivisorSet[n_Integer] := Select[Range@ n, And[PowerMod[n, #, #] == 0, ! Divisible[n, #]] &]
(This code was optimized 24 October 2017 and is more efficient than the former revised code.)
Using the regulars[n] function:
semidivisorSet[n_Integer] := Complement[regulars@ n, Divisors@ n]
OEIS A272618 is an irregular table of the semidivisors of n.
Counting semidivisors. This Wolfram script will count the number of semidivisors of b.
semidivisors[n_Integer] := Count[Range@ n, _?(And[PowerMod[n, #, #] == 0, ! Divisible[n, #]] &)]
(This code was optimized 24 October 2017 and is more efficient than the former revised code)
Using the r[n] function:
semidivisors[n_Integer] := r[n] - DivisorSigma[0, n]
These scripts facilitated OEIS sequence A243822 (the semidivisor counting function ξd (b)) of 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 },
Length[Select[a, Divisible[n, #] &]] < Length[a] && 1 < GCD[m, n] < m]
This method is more efficient but might present memory problems in some environments for large values:
semicoprimeQ[m_Integer, n_Integer] := And[PowerMod[n, #, #] > 0, ! CoprimeQ[n, #]] &]
Using the regulars[n] function:
semicoprimeQ[m_Integer, n_Integer] := And[MemberQ[regulars@ n, m], ! CoprimeQ[n, #]] &]
Generating semitotatives. This algorithm will produce a list of semitotatives of b:
semitotativeSet[n_Integer] := Flatten[Position[Thread[semicoprimeQ[Range[1, n], n]], True]];
Using the regulars[n] function:
semitotativeSet[n_Integer] := With[{R = Range@ n}, Complement[R, Union[regulars@ n, Select[R, CoprimeQ[#, n] &]]]]
OEIS A272619 is an irregular table of the semitotatives of n.
Counting semitotatives. This Wolfram script will count the number of semidivisors of b.
semitotatives[n_Integer] := Count[Thread[semicoprimeQ[Range[1, n], n]], True];
Using the r[n] function:
semitotatives[n_Integer] := n - (r[n] + EulerPhi[n] - 1)
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 semitotatives. 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, i.e., necessarily composite nondivisors in the cototient of b.
The following table lists OEIS sequences that pertain to the entities discussed in this work. “Construction” here means listing all the numbers that comprise the set of a given entity; e.g., row n of A027750 lists the divisors d of n. A counting function enumerates all 1 ≤ k ≤ n that have the pertinent qualities; e.g., the divisor counting function A000005(n) = τ(n) gives the number of divisors of n. A characteristic function shows 1 when a number qualifies, but 0 when it does not qualify as an entity; e.g., A010051 is the characteristic function of the primes. Record-setting numbers in the counting function show us the smallest number n that sets a record for the number of entities. The “highly composite numbers“, A002182, shows that 2 sets a record at 2 divisors, bested by 4 for 3, then 6 for 4, and 12 for 8 divisors, etc. The records appear in A002183. Bold A-numbers are sequences I'd contributed. Asterisks denote sequences in draft.
| Entity | Construction | Counting function | Characteristic function | Record-setting numbers | Counting function records | |
| ■■ | Divisors: | A027750 | A000005 | A051731 | A002182 | A002183 |
| Nondivisors: | A173540 | A049820 | — | A000040 | A040976 | |
| ■■ | Totatives: | A038566 | A000010 | A054521 | A000040 | A006093 |
| Cototatives: | A121998 | A051953 | — | A065385 | A065386 | |
| ■■■ | Regulars: | A162306 | A010846 | A304569 | A244052 | A244053 |
| ■■ | Neutrals: | A133995 | A045763 | A304571* | A300859 | (A300914)* |
| ■ | Semidivisors: | A272618 | A243822 | A304570* | A293555 | A293556 |
| ■ | Semitotatives: | A272619 | A243823 | A304572* | A292867 | A292868 |
The sequence A244052 (highly regular numbers) and the necessary-but-not-sufficient conditions for inclusion of A288813 (or in aggregate, A288784) in A244052, has been the subject of my study between June 2014 and June 2017. More recently, the numbers that set records in the semidivisor, semitotative, and neutral counting functions have been studied with less resolution. The "dominance" studies, considering the regular numbers and comparing the semidivisor vs. divisor counting functions, and the neutral numbers and comparing the semitotative vs. semidivisor counting functions, have also seen some analysis. Descriptions and sequences associated with these studies appear after the data briefs below.
Data briefs.
These are papers in text that focus on data, analysing prime decomposition and interrelationships between various sequences. Observations and conjectures are written following tables of data. Many appear at the OEIS as a-files at several sequences. Some data briefs share Mathematica code.
Michael De Vlieger, “On the graph of highly composite numbers as products of primorials.”, 31 March 2018. (web page)
Michael De Vlieger, “On the regular counting function applied to the highly composite numbers: a(n) = A010846(A002182(n)).”, 28 March 2018. (web page, pre-press text)
Michael De Vlieger, “Concordance across A002110, A002182, A244052, A293555, A300156, A292867, A300860, and A300859”, 16 March 2018. (local text)
Michael De Vlieger, “Decomposition of terms in A300859 and Related Sequences.”, 15 March 2018. (text)
Michael De Vlieger, “Decomposition of terms in A300860 and Related Sequences”, 14 March 2018. (text)
Michael De Vlieger, “Examination of the relationships of the species of numbers enumerated in A010846”, 26 February 2018. (text)
Michael De Vlieger, “Prime decomposition of terms in A295221” (Numbers n such that 2 × A243823(n) = n), 22 November 2017. (text)
Michael De Vlieger, “Records A293556 and their indices A293555 in A243822”, 17 November 2017. (text)
Michael De Vlieger, “Analysis of Records (A292868) and Indices of Records (A292867) in A243823”, 17 November 2017.
(text).
Michael De Vlieger, “Maximum “Distension’ i Given ‘Tier’ m and ‘Depth’ j (for terms in A288813)”, 26 June 2017. (local text)
Michael De Vlieger, “Number of terms of A288813 that have j = m − π(A053669(A288813(m))) + 1”, 26 June 2017. (local text)
Michael De Vlieger, “Relations between A288813, A288784, A002110, and A244052”, 15 July 2017. (text)
Michael De Vlieger, “Tree associated with computation of terms of A288813 via directed iteration of A287352(A002110(n))”, 26 June 2017. (local text)
Michael De Vlieger, “Relations between A288784, A002110, A060735, and A244052”, 2 July 2014, updated 21 June 2017. (text)
Michael De Vlieger, “Highly regular numbers (A244052)”, 19 June 2017. (local text)
Michael De Vlieger, “Multiplicities of primes for FactorInteger[A244052(n)]”, 2 July 2014, updated 10 February 2015 (text superseded, see immediately above)
Auxiliary sequences.
I use two sequences as tools that help show patterns in the prime decomposition of record-setters (A244052, A293555, A292867, etc.).
A054841:
multiplicity notation (MN, employed via influence from Achim Flammenkamp). For n = Product(prime(i)e), write each e in the (i + 1)-th place. The OEIS sequence attempts to write a "decimal-like" number of this, but I prefer to write a little-endian number that lists powers of the primes in order of the magnitude of the prime. Example: 84 = 2² × 3 × 7 → 2101. In cases where we have an exponent greater than 9, the first instance of which is 210 = 2048, we can write a comma-delimited list. In computation I do not catenate the exponents in a decimal-like number, but instead let the list remain as such. This sequence is good for numbers that are products of a compact set of the smallest primes. Flammenkamp applied it to A002182; I applied it to A244052 and it helped see patterns in the prime decomposition of the terms.
A287352: “π-code” — (PC or pi-code): list the prime divisors p of n with multiplicity, least to greatest; convert each prime p → π(p), then writing the first prime index, follow with the first differences of the converted list. Example: 84 = 2 × 2 × 3 × 7 → {1, 1, 2, 4} → 1012. Again, the number need not be catenated to form a "decimal-like" code. This is more convenient for more widely-separated prime factors where none of the multiplicities are large and is often shorter than multiplicity notation.
Study of the records in A010846.
The “highly regular number” sequence, A244052 (indices of records in A010846) and A244053 (records in A010846) were the subjects of a paper I wrote on the necessary but not sufficient condition A288784 for A244052. Several sequences resulted: A288813 “turbulent candidates” for A244052 (the complement of A288784 and the union of A002110 and A060735), A289171 “depth-distension” correlation for A002110(n). The paper showed how A002110 organizes A244052 into “tiers” and A060735 into “levels” within each tier. The sequence A020900 also has an effect on A244052.
Comparison of the two species of regular numbers: semidivisors vs. divisors.
Since A010846(n) = A000005(n) + A243822(n), the sequence A299990 examines the balance of the two components among "regular" numbers. Value of A299990 is generally less frequently negative as n increases. A299990(1) = −1. For primes p, A299990(p) = −2 since 1 | p and the cototient is restricted to the divisor p. For perfect prime powers pe, A299990(pe) = −(e + 1), since all m < pe in the cototient of pe that do not have a prime factor q coprime to pe are powers pk with 1 < pk ≤ pe; all such pk divide pe. Generally for n with A001221(n) = 1, A299990(n) = −1 × A000005(n), since the cototient is restricted to divisors, and in the case of pe > 4, divisors and numbers in A272619(pe) not counted by A010846(pe). Observations: for m ≥ 3, A299990(A002110(m)) is positive, and for m ≥ 9, A299990(A244052(m)) is positive. This sequence leads us to consider the following:
A299990: a(n) = A243822(n) − A000005(n).
A299991: Numbers n for which A243822(n) > A000005(n).
A299992: Composite n with A001221(n) > 1 for which A243822(n) < A000005(n).
A300155: Numbers n for which A243822(n) = A000005(n).
A300156: Indices of records in A299990.
A300157: Records in A299990.
Examination of the number of divisors and regulars in highly composite numbers, and numbers that set records for A010846(n)/τ(n).
A301892: A010846(A002182(n)), i.e., the regular counting function of highly composite numbers.
A301893: Numbers that set records for the ratio A010846(n)/A000005(n), i.e., regular divided by divisor counting function.
Examination of the “dominance” of semitotatives.
The semitotative is perhaps the most common entity in the range 1 ≤ k ≤ n for composite n > 6 (and for all positive integers, greater than n). These sequences examine the
A294575: Numbers n such that 2 × A243823(n) > n.
A294576: Odd numbers n such that 2 × A243823(n) > n.
A295221: Numbers n such that 2 × A243823(n) = n.
Observations:
1. There is a large gap between A295221(19) and A295221(20).
2. Products 25 × prime(i), with 3 ≤ i ≤ 17, are in the sequence.
3. Products 26 × prime(j), with 43391 ≤ j ≤ 82025, are in the sequence.
4. A295221(1) = 2² × 3 × 13, and terms 190, 286, and 578 are even, but do not follow the pattern of 2h × p prime.
Comparison of the two species of neutral numbers: semitotatives vs. semidivisors.
This sequence is the difference between the latter and the former species of nondivisors in the cototient of n. Since A045763(n) = A243822(n) + A243823(n), this sequence examines the balance of the two components among nondivisors in the cototient of n. For positive n < 6 and for p prime, A300858(n) = A300858(p) = 0, thus A300858(A046022(n)) = 0. For prime powers pe, A300858(pe) = A243823(pe), since A243822(pe) = 0, thus A300858(n) = A243823(n) for n in A000961. Value of A300858(n) is generally nonnegative; A300858(n) is negative for n = {6, 10, 12, 18, 30}; A300858(30) = −5, but A300858(n) = −1 for the rest of the aforementioned numbers. These five numbers are a subset of A295523.
A300858: a(n) = A243823(n) − A243822(n).
A300860:
Indices of records in A300858.
A300861: Records in A300858.
A295523: Nonprime numbers n such that A243822(n) ≥ A243823(n). {1, 4, 6, 10, 12, 18, 30}.
Work on the “extended regular counting function” ercf(n, lim) applied to terms in A288784 was done 27 March 2018; it may be expanded and some sequences might derive from it. Such work promises to examine the “deficiency” of turbulent terms k × m with m in tier t of A288813 and 1 ≤ k < p(t + 1).
Comparison of the semitotative and totative to come in April 2018.
Interrelationship of all record-setter sequences A244052, A293555, A292867, and A300859 will follow this spring pending acceptance of all the associated sequences. Some work toward this has already begun with the concordance study.
Note: I maintain large datasets for many sequences I’ve produced, as well as for A010846. This last sequence is not easy to compute, with a million terms requiring a couple hours. Many of the sequences I wrote depend on it. For A010846 I have generated 36,000,000 terms, and A243822, A243823, have been extended to that scale. Record transforms on these sequences employ the large dataset. I am willing to share the dataset with anyone interested in analyzing these sequences; they are half a gigabyte text files apiece, in the OEIS b-file format. I may extend A010846 to A002110(9) - 223 million - terms.
Thanks to Mr. Reid Bingham for pointing out an error in “Relationships among the counting functions”.
(Updated 29 May 2018)
