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

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.

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.

Formula

a(n) <= A243823(n).

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

Example

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

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

Crossrefs

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

Sequence in context: A179311 A309983 A342697 * A257094 A256004 A269707

Adjacent sequences: A360477 A360478 A360479 * A360481 A360482 A360483

Keyword

nonn

Author

Michael De Vlieger, Feb 28 2023

Status

approved