cp's OEIS Frontend

A384655 a(n) = Sum_{k=1..n} A051903(gcd(n,k)).

%I A384655 #8 Jun 07 2025 08:18:30
%S A384655 0,1,1,3,1,4,1,7,4,6,1,11,1,8,7,15,1,14,1,17,9,12,1,25,6,14,13,23,1,
%T A384655 22,1,31,13,18,11,36,1,20,15,39,1,30,1,35,26,24,1,53,8,32,19,41,1,44,
%U A384655 15,53,21,30,1,59,1,32,34,63,17,46,1,53,25,46,1,81,1,38
%N A384655 a(n) = Sum_{k=1..n} A051903(gcd(n,k)).
%C A384655 The terms of this sequence can be calculated efficiently using the 1st formula. The value the of function f(n, k) is equal to the number of integers i from 1 to n such that gcd(i, n) is 1 if k = 1, or k-free if k >= 2 (k-free numbers are numbers that are not divisible by a k-th power other than 1). E.g., f(n, 1) = A000010(n), f(n, 2) = A063659(n), and f(n, 3) = A254926(n).
%H A384655 Amiram Eldar, <a href="/A384655/b384655.txt">Table of n, a(n) for n = 1..10000</a>
%F A384655 a(n) = Sum_{k=1..A051903(n)} (n - f(n, k)) = A051903(n) * n  - Sum_{k=1..A051903(n)} f(n, k), where f(n, k) is multiplicative for a given k, with f(p^e, k) = p^e - p^(e-k) if e >= k and f(p^e, k) = p^e if e < k.
%F A384655 a(n) = 1 if and only if n is prime.
%F A384655 a(n) >= 2 if and only if n is composite.
%F A384655 a(n) >= A051953(n) with equality if and only if n is squarefree.
%F A384655 a(n) >= 2*n - A000010(n) - A063659(n) with equality if and only if n is cubefree that is not squarefree (i.e., n in A067259, or equivalently, A051903(n) = 2).
%F A384655 a(p^e) = (p^e-1)/(p-1) for a prime p and e >= 1.
%F A384655 a(n) < c*n and lim sun_{n->oo} a(n)/n = c, where c is Niven's constant (A033150).
%F A384655 Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c = Sum{k>=1} (1-1/zeta(2*k)) = 0.49056393035179738598... .
%e A384655 a(4) = A051903(gcd(4,1)) + A051903(gcd(4,2)) + A051903(gcd(4,3)) + A051903(gcd(4,4)) = A051903(1) + A051903(2) + A051903(1) + A051903(4) = 0 + 1 + 0 + 2 = 3.
%t A384655 e[n_] := If[n == 1, 0, Max[FactorInteger[n][[;;, 2]]]]; a[n_] := Sum[e[GCD[n, k]], {k, 1, n}]; Array[a, 100]
%t A384655 (* or *)
%t A384655 f[p_, e_, k_] := p^e - If[e < k, 0, p^(e - k)]; a[n_] := Module[{fct = FactorInteger[n], emax, s}, emax = Max[fct[[;; , 2]]]; s = emax * n; Do[s -= Times @@ (f[#1, #2, k] & @@@ fct), {k, 1, emax}]; s]; a[1] = 0; Array[a, 100]
%o A384655 (PARI) e(n) = if(n == 1, 0, vecmax(factor(n)[,2]));
%o A384655 a(n) = sum(k = 1, n, e(gcd(n, k)));
%o A384655 (PARI) a(n) = if(n == 1, 0, my(f = factor(n), p = f[,1], e = f[,2], emax = vecmax(e), s = emax*n); for(k = 1, emax, s -= prod(i = 1, #p, p[i]^e[i] - if(e[i] < k, 0, p[i]^(e[i]-k)))); s);
%Y A384655 Cf. A000010, A033150, A005117, A050873, A051903, A051953, A063659, A067259, A254926, A357310, A383156, A384656 (unitary analog).
%K A384655 nonn
%O A384655 1,4
%A A384655 _Amiram Eldar_, Jun 06 2025