cp's OEIS Frontend

A353909 a(n) is the alternating sum of the sequence gcd(n, k^2), 1 <= k <= n.

%I A353909 #104 Jul 12 2023 11:53:03
%S A353909 -1,1,-3,6,-5,5,-7,20,-9,9,-11,30,-13,13,-15,72,-17,33,-19,54,-21,21,
%T A353909 -23,100,-25,25,-27,78,-29,45,-31,208,-33,33,-35,198,-37,37,-39,180,
%U A353909 -41,65,-43,126,-45,45,-47,360,-49,145,-51,150,-53,153,-55,260,-57,57,-59
%N A353909 a(n) is the alternating sum of the sequence gcd(n, k^2), 1 <= k <= n.
%H A353909 Michael S. Branicky, <a href="/A353909/b353909.txt">Table of n, a(n) for n = 1..10000</a>
%H A353909 Project Euler, <a href="https://projecteuler.net/problem=795">Problem 795: Alternating gcd sum</a>, (2022)
%H A353909 Laszlo Toth, <a href="https://www.cs.uwaterloo.ca/journals/JIS/VOL14/Toth/toth9.html">Weighted gcd-sum functions</a>, J. Integer Sequences, 14 (2011), Article 11.7.7.
%F A353909 a(n) = Sum_{i=1..n} (-1)^i*gcd(n, i^2).
%F A353909 a(n) = -n if n is odd.
%F A353909 a(n) = n * Sum_{d|n, d even} (phi(d) * sqrt(d/core(d)) / d), where phi = A000010, if n is even. - _Darío Clavijo_, Jan 13 2023
%p A353909 a:= n-> add((-1)^i*igcd(n, i^2), i=1..n):
%p A353909 seq(a(n), n=1..60);  # _Alois P. Heinz_, Jan 13 2023
%t A353909 a[n_] := Sum[(-1)^i * GCD[n, i^2], {i, 1, n}]; Array[a, 100] (* _Amiram Eldar_, May 10 2022 *)
%o A353909 (PARI) a(n) = sum(i=1, n, (-1)^i*gcd(n, i^2)); \\ _Michel Marcus_, May 10 2022
%o A353909 (PARI) a(n) = {
%o A353909    if((n%2)==1, return(-n));
%o A353909    my(s=0);
%o A353909    fordivfactored(n, d,
%o A353909       if((d[1]%2)==0,
%o A353909          s+=eulerphi(d)*core(d,1)[2]/d[1]));
%o A353909    s*n;
%o A353909 } \\ _Yurii Ivanov_, Jun 20 2022
%o A353909 (Python)
%o A353909 from math import gcd
%o A353909 def a(n):
%o A353909     return -n if n%2==1 else sum((-1)**k*gcd(n, k*k) for k in range(1, n+1))
%o A353909 print([a(n) for n in range(1, 60)]) # _Michael S. Branicky_, May 28 2022
%o A353909 (Python)
%o A353909 from sympy import sqrt, divisors, totient
%o A353909 from sympy.ntheory.factor_ import core
%o A353909 def a(n):
%o A353909   return -n if n & 1 == 1 else int(n * sum(totient(d) * sqrt(d // core(d)) / d for d in divisors(n) if d & 1 == 0))
%o A353909  # _Darío Clavijo_, Dec 29 2022
%Y A353909 Cf. A078430, A245717, A007913, A000010.
%K A353909 sign
%O A353909 1,3
%A A353909 _Thomas Baeyens_, May 10 2022