OFFSET
1,2
COMMENTS
The cototient of n consists of numbers 1 < m <= n that are not coprime to n, i.e., gcd(m,n) > 1. These numbers have at least one prime divisor p that also divides n. The cototient of n contains the divisors d of n; the remaining nondivisors in the cototient of n are listed in A133995. The counting function of A133995 is A045763(n). There are two species of numbers in the nondivisor-cototient of n: those in row n of A272618, of which A243822(n) is counting function, and those in row n of A272619, of which A243823(n) is the counting function. The former species divides n^e for integer e > 1, while the latter does not divide any integer power of n.
A045763(p) = 0 for p prime, therefore there are no primes in a(n).
Except for prime terms (i.e., 2), A002110 is a subset as primorials minimize the totient function. The divisor counting function is increasingly vanishingly small compared to the totient function for A002110(i) as i increases, and A002110(i) for 1 < i <= 9 is observed in a(n).
Conjectures based on 1255 terms of a(n) < 36,000,000:
1. There are no prime powers p^e > 1 in a(n), i.e., the intersection of a(n) and A000961 is {1}.
2. A293555 is a subset of A300859. Numbers that have a lot of nondivisors m | n^e with e > 1 (i.e., in row n of A272618 and counted by A243822(n)) tend to reduce the totient and increasingly have fewer divisors than highly composite numbers, widening the nondivisor-cototient.
3. A300156 is a subset of A300859. Numbers that have more nondivisors m | n^e with e > 1 (i.e., in row n of A272618 and counted by A243822(n)) than divisors tend to reduce the totient and have fewer divisors than highly composite numbers (i.e., those n in A002182), widening the nondivisor-cototient.
REFERENCES
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, p. 352 (sixth edition), see Theorem 327.
LINKS
Michael De Vlieger, Table of n, a(n) for n = 1..1735
Michael De Vlieger, Decomposition of terms in A300859 and Related Sequences.
EXAMPLE
6 is in the sequence because there is 1 nondivisor in the cototient of 6 (i.e., 4), and that total exceeds 0 for all smaller positive numbers.
10 follows 6 because there are 3 nondivisors in the cototient (4, 6, 8), and this exceeds the total of 1 for n = 6, 8, and 9.
MATHEMATICA
With[{s = Array[1 + # - EulerPhi@ # - DivisorSigma[0, #] &, 10^3]}, Map[FirstPosition[s, #][[1]] &, Union@ FoldList[Max, s]]]
DeleteDuplicates[Table[{n, n+1-DivisorSigma[0, n]-EulerPhi[n]}, {n, 600}], GreaterEqual[#1 [[2]], #2 [[2]]]&][[;; , 1]] (* Harvey P. Dale, Mar 29 2023 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Michael De Vlieger, Mar 15 2018
STATUS
approved