A360480 a(n) = number of numbers k < n, with gcd(k, n) > 1, such that there is at least one prime divisor p | k that does not divide n, and at least one prime divisor q | n that does not divide k.

0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 3, 3, 0, 0, 3, 0, 5, 5, 6, 0, 6, 0, 8, 0, 9, 0, 5, 0, 0, 8, 11, 7, 10, 0, 13, 10, 13, 0, 12, 0, 16, 13, 17, 0, 16, 0, 18, 14, 20, 0, 19, 11, 21, 16, 23, 0, 19, 0, 25, 19, 0, 13, 25, 0, 27, 20, 27, 0, 27, 0, 30, 25, 31, 13, 32, 0, 32, 0, 34, 0, 33, 17, 36, 25, 37

Offset: 1

Author

Michael De Vlieger, Feb 28 2023

Keywords

• nonn

Comments

a(n) = 0 for prime powers, since the definition implies omega(n) >= 2.

a(n) is the cardinality of k in the cototient of n such that rad(k) mod rad(n) != 0 and rad(n) mod rad(k) != 0.

Examples

			a(6) = 0 since k = 1..5 are prime powers.
a(10) = 1 since only k = 6 is such that p = 3, q = 5, but gcd(6, 10) = 2.
a(14) = 3 since for k = 6, we have p = 3, q = 7, for k = 10, we have p = 5, q = 7, and for k = 12, we have the same situation as we have with 6, while 6, 10, 12, and 14 are even.
Table listing k <= n counted by row n = 10..22 of this sequence:
a(10) = 1:  6  .  .  .  .
a(11) = 0:  .  .  .  .  .  .
a(12) = 1:  .  .  .  .  10 .  .
a(13) = 0:  .  .  .  .  .  .  .  .
a(14) = 3:  6  .  .  .  10 .  12 .  .
a(15) = 3:  6  .  .  .  10 .  12 .  .  .
a(16) = 0:  .  .  .  .  .  .  .  .  .  .  .
a(17) = 0:  .  .  .  .  .  .  .  .  .  .  .  .
a(18) = 3:  .  .  .  .  10 .  .  .  14 15 .  .  .
a(19) = 0:  .  .  .  .  .  .  .  .  .  .  .  .  .  .
a(20) = 5:  6  .  .  .  .  .  12 .  14 15 .  .  18 .  .
a(21) = 5:  6  .  .  .  .  .  12 .  14 15 .  .  18 .  .  .
a(22) = 6:  6  .  .  .  10 .  12 .  14 .  .  .  18 .  20 .  .
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..10000
• Michael De Vlieger, Log log scatterplot of a(n), n = 1..2^16, ignoring zeros. Scatterplot resembles that of A051953.
• Michael De Vlieger, Log log scatterplot of a(n), n = 1..2^16, ignoring zeros, showing composite squarefree numbers (in A120944) in green, numbers neither prime powers nor squarefree (in A126706) in blue, highlighting numbers that are products of composite prime powers (in A286708) in large light blue, and primorials (in A002110) in magenta.
• Michael De Vlieger, Plot k = 1..n for n = 1..54, showing k counted by this sequence in large black, highlighting all k in row n otherwise in medium red for n in A024619, and for n that are prime powers, k in A024619 in dark blue.

Crossrefs

Cf. A007947, A010846, A024619, A051953, A243823, A272619.

Programs

Mathematica

rad[x_] := rad[x] = Times @@ FactorInteger[x][[All, 1]]; Table[k = rad[n]; Count[Range[n], _?(Nor[CoprimeQ[#1, n], Divisible[#2, k], Divisible[k, #2]] & @@ {#, rad[#]} &)], {n, 88}]

Formula

a(n) <= A243823(n).

a(n) = | { k < n : gcd(k,n) > 1 AND (rad(k)|rad(n) NOR rad(n)|rad(k)) } |.