A295523 Nonprime numbers n such that A243822(n) >= A243823(n).

1, 4, 6, 10, 12, 18, 30

Offset: 1

Author

Michael De Vlieger, Nov 23 2017

Keywords

• nonn
• easy
• fini
• full

Comments

Consider numbers m that are nondivisors in the cototient of n, listed in row n of A133995 and counted by A045763(n). This sequence lists numbers n for which there are more m such that m | n^e with e >= 0 than there are m that are products of at least one prime divisor p of n and one nondivisor prime q. The former species of m are "semidivisors" listed in row n of A272618 and counted by A243822(n), while the latter are "semitotatives" listed in row n of A272619 and counted by A243823(n). These two species constitute the only species of nondivisors in the cototient of n.

Primes p have no nondivisors in the cototient, i.e., A045763(p) = 0, therefore A243822(p) and A243823(p) also are 0. The equality of these latter two sequences is trivial in the case of primes.

Prime powers p^e except for p^e = 4 have A243823(p^e) > A243822(p^e), since A243822(p^e) = 0. All powers p^k with 0 <= k <= e divide p^e.

The sequence is finite because there exist a lot more nondivisor primes q than p | n as n increases. Therefore there are more numbers m in row n of A272619 than there are in row n of A272618, since the former are products p*q and the latter are products only of p.

Examples

			1 is in the sequence because it is not prime and there are no nondivisors in the cototient, therefore A243822(1) = A243823(1) = 0.
4 is in the sequence because it is the very smallest composite; nondivisors in the cototient of n are composite and since 4 | 4, both A243822(4) and A243823(4) = 0.
6 is in the sequence because it is the only number for which A243822(6) = 1 but A243823(6) = 0. A272618(6) = 4; 4 | 6^2.
10 is in the sequence because it has 2 semidivisors 4 | 10^2 and 8 | 10^3, while only 1 semitotative 6 = 2 * 3.
14 is not in the sequence since it has 2 semidivisors (4 and 8) but 3 semitotatives (6, 10, and 12).
List of terms n followed by row n of A272618 and A272619:
   1, {}, {}
   4, {}, {}
   6, {4}, {}
  10, {4,8}, {6}
  12, {8,9}, {10}
  18, {4,8,12,16}, {10,14,15}
  30, {4,8,9,12,16,18,20,24,25,27}, {14,21,22,26,28}
		

Links

• M. De Vlieger, Exploring Number Bases as Tools, ACM Inroads, March 2012, Vol. 3, No. 1, pp. 4-12.

Crossrefs

Cf. A000005, A000010, A010846, A045763, A243822, A243823.

Programs

Mathematica

Select[Range@ 30, Function[n, And[! PrimeQ@ n, #2 - #1 >= n - (#2 + #3 - 1)] & @@ {DivisorSigma[0, n], Count[Range@ n, _?(PowerMod[n, #, #] == 0 &)], EulerPhi@ n}]]