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
Examples
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.
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.
Programs
-
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}] -
PARI
a(n) = #select(x->(ispowerful(x) && gcd(x,n)==1), [1..n-1]); \\ Michel Marcus, Apr 11 2025
Formula
a(n) > 0 for n > 1, since 1 is powerful, smaller than n > 1, and coprime to n >= 1.
Comments