A243823 Quantity of "semitotatives," numbers m < n that are products of at least one prime divisor p of n and one prime q coprime to n.

0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 3, 3, 4, 0, 3, 0, 5, 5, 6, 0, 6, 3, 8, 6, 9, 0, 5, 0, 11, 8, 11, 7, 11, 0, 13, 10, 14, 0, 12, 0, 16, 14, 17, 0, 18, 5, 19, 14, 20, 0, 21, 11, 22, 16, 23, 0, 19, 0, 25, 20, 26, 13, 25, 0, 27, 20, 27, 0, 31, 0, 30, 27, 31, 13, 32, 0, 35, 23, 34, 0, 33, 17, 36, 25, 38, 0, 35, 15, 39, 27, 40, 19, 45, 0, 44, 32, 46

Offset: 1

Author

Michael De Vlieger, Jun 11 2014

Keywords

• nonn

Comments

Semitotatives m < n have a regular factor that is the product of prime divisors of n, and a coprime factor that is the product of primes q that are coprime to n.

The unit fractions of semitotatives have a mixed recurrent expansion in base n (See Hardy & Wright).

Examples

			For n = 10 with prime divisors {2, 5} and prime totatives {3, 7}, the only semitotative is 6. For n = 16, with the prime divisor 2 and the prime totatives {3, 5, 7, 11, 13}, there are four semitotatives {6, 10, 12, 14}.
		

References

• G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Sixth Edition, Oxford University Press, 2008, pages 144-145 (last part of Theorem 136).

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..10000
• M. De Vlieger, Exploring Number Bases as Tools, ACM Inroads, March 2012, Vol. 3, No. 1, pp. 4-12.

Crossrefs

Cf. A045763, A243822.

Programs

Maple

f:= n -> n + 1 - numtheory:-phi(n) - add(numtheory:-mobius(k)*floor(n/k), k=select(t -> igcd(n,t)=1, [$1..n])):
map(f, [$1..100]); # Robert Israel, May 10 2016

Mathematica

Table[n + 1 - EulerPhi@ n - Total[MoebiusMu[#] Floor[n/#] &@ Select[Range@ n, CoprimeQ[#, n] &]], {n, 120}] (* Michael De Vlieger, May 10 2016 *)

Formula

a(n) = A045763(n) - A243822(n).

a(n) = n + 1 - phi(n) - Sum_{1 <= k <= n, gcd(n, k) = 1} mu(k)*floor(n/k). - Michael De Vlieger, May 10 2016, after Benoit Cloitre at A010846.