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

%I #104 Jul 12 2023 11:53:03

%S -1,1,-3,6,-5,5,-7,20,-9,9,-11,30,-13,13,-15,72,-17,33,-19,54,-21,21,

%T -23,100,-25,25,-27,78,-29,45,-31,208,-33,33,-35,198,-37,37,-39,180,

%U -41,65,-43,126,-45,45,-47,360,-49,145,-51,150,-53,153,-55,260,-57,57,-59

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

%H Michael S. Branicky, <a href="/A353909/b353909.txt">Table of n, a(n) for n = 1..10000</a>

%H Project Euler, <a href="https://projecteuler.net/problem=795">Problem 795: Alternating gcd sum</a>, (2022)

%H 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 a(n) = Sum_{i=1..n} (-1)^i*gcd(n, i^2).

%F a(n) = -n if n is odd.

%F 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 a:= n-> add((-1)^i*igcd(n, i^2), i=1..n):

%p seq(a(n), n=1..60); # _Alois P. Heinz_, Jan 13 2023

%t a[n_] := Sum[(-1)^i * GCD[n, i^2], {i, 1, n}]; Array[a, 100] (* _Amiram Eldar_, May 10 2022 *)

%o (PARI) a(n) = sum(i=1, n, (-1)^i*gcd(n, i^2)); \\ _Michel Marcus_, May 10 2022

%o (PARI) a(n) = {

%o if((n%2)==1, return(-n));

%o my(s=0);

%o fordivfactored(n, d,

%o if((d[1]%2)==0,

%o s+=eulerphi(d)*core(d,1)[2]/d[1]));

%o s*n;

%o } \\ _Yurii Ivanov_, Jun 20 2022

%o (Python)

%o from math import gcd

%o def a(n):

%o return -n if n%2==1 else sum((-1)**k*gcd(n, k*k) for k in range(1, n+1))

%o print([a(n) for n in range(1, 60)]) # _Michael S. Branicky_, May 28 2022

%o (Python)

%o from sympy import sqrt, divisors, totient

%o from sympy.ntheory.factor_ import core

%o def a(n):

%o 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 # _Darío Clavijo_, Dec 29 2022

%Y Cf. A078430, A245717, A007913, A000010.

%K sign

%O 1,3

%A _Thomas Baeyens_, May 10 2022