A382770 Number of powerful k < n such that k and n are coprime.

0, 1, 1, 1, 2, 1, 2, 1, 3, 2, 4, 1, 4, 2, 3, 2, 5, 1, 5, 2, 4, 2, 5, 1, 5, 3, 5, 4, 7, 1, 7, 4, 6, 4, 7, 2, 9, 4, 6, 3, 9, 2, 9, 4, 5, 4, 9, 2, 9, 4, 7, 5, 10, 3, 9, 4, 7, 5, 10, 2, 10, 5, 6, 5, 10, 3, 11, 5, 8, 3, 11, 3, 12, 5, 7, 5, 11, 3, 12, 4, 8, 6, 13, 2

Offset

1,5

Comments

First differs from A304574 at n = 73: a(73) = 12, A304574(n) = 11, because 72 = 2^3 * 3^2 is powerful but not a perfect power (i.e., an Achilles number in A052486).

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, where red represents prime n, gold represents proper prime power n, green represents squarefree composite n, and blue and purple represent n that is neither squarefree nor a prime power, where purple represents a powerful n that is not a prime power. Large green dots represent composite primorials n.

Formula

a(n) > 0 for n > 1, since 1 is powerful, smaller than n > 1, and coprime to n >= 1.

Example

Let s = A001694, the sequence of powerful numbers.
a(1) = 0 since the smallest powerful number is 1 itself.
a(2) = 1 since s(1) = 1 is smaller than and coprime to 2.
a(3) = 1 since s(1) = 1 is smaller than and coprime to 3.
a(4) = 1 since s(1..2) = {1, 4}; 1 is smaller than and coprime to 4, but 4 = 4.
a(5) = 2 since s(1..2) = {1, 4}, both smaller than and coprime to 5.
a(6) = 1 since s(1..2) = {1, 4}; 1 is smaller than and coprime to 6, but gcd(4,6) > 1.
a(8) = 1 since s(1..3) = {1, 4, 8}; 1 and 4 are both smaller than and coprime to 8, but 8 = 8.
a(9) = 3 since s(1..3) = {1, 4, 8} are all smaller than and coprime to 9.
a(73) = 12 since s(1..12) = {1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 72}, all coprime to prime 73. All except 72 are perfect powers, thus A304574(73) = 11, etc.

Mathematica

nn = 120; q = 1; rad[x_] := Times @@ FactorInteger[x][[All, 1]]; {0}~Join~Rest@ Table[Set[{c, i}, {0, 1}]; If[Divisible[n, rad[n]^2], t[q] = n; q++]; While[i < q, If[CoprimeQ[t[i], n], c++]; i++]; c, {n, nn}]

Prog

(PARI) a(n) = #select(x->(ispowerful(x) && gcd(x, n)==1), [1..n-1]); \\ Michel Marcus, Apr 11 2025

Crossrefs

Cf. A001694, A304574.

Sequence in context: A054065 A194868 A304574 * A139024 A394187 A217317

Adjacent sequences: A382767 A382768 A382769 * A382771 A382772 A382773

Keyword

nonn,easy

Author

Michael De Vlieger, Apr 05 2025

Status

approved