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,14

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).

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.

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.

Example

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}.

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 *)

Crossrefs

Cf. A045763, A243822.

Sequence in context: A230811 A371274 A117032 * A281141 A078911 A353417

Adjacent sequences: A243820 A243821 A243822 * A243824 A243825 A243826

Keyword

nonn

Author

Michael De Vlieger, Jun 11 2014

Status

approved