cp's OEIS Frontend

A385132 The number of integers k from 1 to n such that gcd(n, k) has an even maximum exponent in its prime factorization.

%I A385132 #11 Jun 25 2025 01:26:01
%S A385132 1,1,2,3,4,2,6,5,7,4,10,7,12,6,8,11,16,8,18,13,12,10,22,11,21,12,20,
%T A385132 19,28,8,30,21,20,16,24,24,36,18,24,21,40,12,42,31,29,22,46,25,43,22,
%U A385132 32,37,52,22,40,31,36,28,58,31,60,30,43,43,48,20,66,49,44
%N A385132 The number of integers k from 1 to n such that gcd(n, k) has an even maximum exponent in its prime factorization.
%H A385132 Amiram Eldar, <a href="/A385132/b385132.txt">Table of n, a(n) for n = 1..10000</a>
%F A385132 a(n) = Sum_{k=1..n} (1 - A051903(gcd(n, k)) mod 2).
%F A385132 a(n) = n - A385133(n).
%F A385132 a(n) = Sum_{k=1..kmax(n)} (-1)^(k+1) * Product_{i=1..r} f(p_i^e_i, k), for n >= 2; if n = Product_{i=1..r} p_i^e_i, r = omega(n) = A001221(n), then emax(n) = max(e_i) = A051903(n), kmax(n) = emax(n)+1 if emax(n) is even, and emax(n) otherwise, f(p^e, k) = p^e - p^(e-k) if e >= k, and f(p^e, k) = p^e if e < k.
%F A385132 Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c = 1 - Sum_{k>=1} (-1)^(k+1)*(1-1/zeta(2*k)) = 0.670205512710945303002... .
%t A385132 e[n_] := If[n == 1, 0, Max[FactorInteger[n][[;; , 2]]]]; a[n_] := Sum[Boole[EvenQ[e[GCD[n, k]]]], {k, 1, n}]; Array[a, 100]
%t A385132 (* second program: *)
%t A385132 a[n_] := Module[{f = FactorInteger[n], p, e, emax, kmax}, p = f[[;;, 1]]; e = f[[;;, 2]]; emax = Max[e]; kmax = emax + 1 - Mod[emax, 2]; Sum[(-1)^(k+1) * Product[p[[i]]^e[[i]] - If[e[[i]] < k, 0, p[[i]]^(e[[i]]-k)], {i, 1, Length[p]}], {k, 1, kmax}]]; a[1] = 1; Array[a, 100]
%o A385132 (PARI) q(n) = if(n == 1, 1, !(vecmax(factor(n)[,2]) % 2));
%o A385132 a(n) = sum(k = 1, n, q(gcd(n, k)));
%o A385132 (PARI) a(n) = if(n == 1, 1, my(f = factor(n), p = f[,1], e = f[,2], emax = vecmax(e), kmax = emax + 1 - emax % 2); sum(k = 1, kmax, (-1)^(k+1) * prod(i = 1, #p, p[i]^e[i] - if(e[i] < k, 0, p[i]^(e[i]-k)))));
%Y A385132 Cf. A001221, A051903, A368714, A384655, A385133.
%K A385132 nonn,easy
%O A385132 1,3
%A A385132 _Amiram Eldar_, Jun 24 2025