login
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.
22

%I #25 May 10 2016 18:14:02

%S 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,

%T 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,

%U 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

%N 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.

%C 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.

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

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

%H Michael De Vlieger, <a href="/A243823/b243823.txt">Table of n, a(n) for n = 1..10000</a>

%H M. De Vlieger, <a href="http://dx.doi.org/10.1145/2077808.2077809">Exploring Number Bases as Tools</a>, ACM Inroads, March 2012, Vol. 3, No. 1, pp. 4-12.

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

%F 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.

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

%p f:= n -> n + 1 - numtheory:-phi(n) - add(numtheory:-mobius(k)*floor(n/k), k=select(t -> igcd(n,t)=1, [$1..n])):

%p map(f, [$1..100]); # _Robert Israel_, May 10 2016

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

%Y Cf. A045763, A243822.

%K nonn

%O 1,14

%A _Michael De Vlieger_, Jun 11 2014