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

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, 19, 28, 8, 30, 21, 20, 16, 24, 24, 36, 18, 24, 21, 40, 12, 42, 31, 29, 22, 46, 25, 43, 22, 32, 37, 52, 22, 40, 31, 36, 28, 58, 31, 60, 30, 43, 43, 48, 20, 66, 49, 44

Offset: 1

Author

Amiram Eldar, Jun 24 2025

Keywords

• nonn
• easy

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A001221, A051903, A368714, A384655, A385133.

Programs

Mathematica

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]
(* second program: *)
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]

PARI

q(n) = if(n == 1, 1, !(vecmax(factor(n)[,2]) % 2));
a(n) = sum(k = 1, n, q(gcd(n, k)));

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)))));

Formula

a(n) = Sum_{k=1..n} (1 - A051903(gcd(n, k)) mod 2).

a(n) = n - A385133(n).

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.

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