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

-1, 1, -3, 6, -5, 5, -7, 20, -9, 9, -11, 30, -13, 13, -15, 72, -17, 33, -19, 54, -21, 21, -23, 100, -25, 25, -27, 78, -29, 45, -31, 208, -33, 33, -35, 198, -37, 37, -39, 180, -41, 65, -43, 126, -45, 45, -47, 360, -49, 145, -51, 150, -53, 153, -55, 260, -57, 57, -59

Offset

1,3

Links

Michael S. Branicky, Table of n, a(n) for n = 1..10000

Project Euler, Problem 795: Alternating gcd sum, (2022)

Laszlo Toth, Weighted gcd-sum functions, J. Integer Sequences, 14 (2011), Article 11.7.7.

Formula

a(n) = Sum_{i=1..n} (-1)^i*gcd(n, i^2).

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

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

Maple

a:= n-> add((-1)^i*igcd(n, i^2), i=1..n):
seq(a(n), n=1..60);  # Alois P. Heinz, Jan 13 2023

Mathematica

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

Prog

(PARI) a(n) = sum(i=1, n, (-1)^i*gcd(n, i^2)); \\ Michel Marcus, May 10 2022
(PARI) a(n) = {
   if((n%2)==1, return(-n));
   my(s=0);
   fordivfactored(n, d,
      if((d[1]%2)==0,
         s+=eulerphi(d)*core(d, 1)[2]/d[1]));
   s*n;
} \\ Yurii Ivanov, Jun 20 2022
(Python)
from math import gcd
def a(n):
    return -n if n%2==1 else sum((-1)**k*gcd(n, k*k) for k in range(1, n+1))
print([a(n) for n in range(1, 60)]) # Michael S. Branicky, May 28 2022
(Python)
from sympy import sqrt, divisors, totient
from sympy.ntheory.factor_ import core
def a(n):
  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))
 # Darío Clavijo, Dec 29 2022

Crossrefs

Cf. A078430, A245717, A007913, A000010.

Sequence in context: A102370 A291050 A268981 * A245652 A106109 A275925

Adjacent sequences: A353906 A353907 A353908 * A353910 A353911 A353912

Keyword

sign

Author

Thomas Baeyens, May 10 2022

Status

approved