cp's OEIS Frontend

A384039 The number of integers k from 1 to n such that gcd(n,k) is a powerful number.

%I A384039 #12 May 18 2025 04:34:21
%S A384039 1,1,2,3,4,2,6,6,7,4,10,6,12,6,8,12,16,7,18,12,12,10,22,12,21,12,21,
%T A384039 18,28,8,30,24,20,16,24,21,36,18,24,24,40,12,42,30,28,22,46,24,43,21,
%U A384039 32,36,52,21,40,36,36,28,58,24,60,30,42,48,48,20,66,48,44
%N A384039 The number of integers k from 1 to n such that gcd(n,k) is a powerful number.
%C A384039 The number of integers k from 1 to n such that the powerfree part (A055231) of gcd(n,k) is 1.
%H A384039 Amiram Eldar, <a href="/A384039/b384039.txt">Table of n, a(n) for n = 1..10000</a>
%F A384039 Multiplicative with a(p^e) = (p^2-p+1)*p^(e-2) if e >= 2, and p-1 otherwise.
%F A384039 a(n) >= A000010(n), with equality if and only if n is squarefree (A005117).
%F A384039 Dirichlet g.f.: zeta(s-1) * Product_{p prime} (1 - 1/p^s + 1/p^(2*s)).
%F A384039 Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c = Product_{p prime} (1 - 1/p^2 + 1/p^4) = 0.66922021803510257394... .
%t A384039 f[p_, e_] := If[e == 1, p-1, (p^2-p+1)*p^(e-2)]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100]
%o A384039 (PARI) a(n) = {my(f = factor(n)); prod(i = 1, #f~, if(f[i,2] == 1, f[i,1]-1, (f[i,1]^2-f[i,1]+1)*f[i,1]^(f[i,2]-2)));}
%Y A384039 Cf. A000010, A001694, A005117, A050873, A055231, A063658, A206369.
%Y A384039 The number of integers k from 1 to n such that gcd(n,k) is: A026741 (odd), A062570 (power of 2), A063659 (squarefree), A078429 (cube), A116512 (power of a prime), A117494 (prime), A126246 (1 or 2), A206369 (square), A254926 (cubefree), A372671 (3-smooth), this sequence (powerful), A384040 (cubefull), A384041 (exponentially odd), A384042 (5-rough).
%K A384039 nonn,easy,mult
%O A384039 1,3
%A A384039 _Amiram Eldar_, May 18 2025