A345428 For 1<=x<=n, 1<=y<=n, write gcd(x,y) = u*x+v*y with u,v minimal; a(n) = sum of the values of u+v.

1, 4, 7, 12, 15, 22, 23, 32, 33, 38, 41, 54, 41, 54, 55, 60, 65, 64, 47, 70, 53, 60, 69, 102, 47, 36, 35, 22, 41, 70, 47, 80, 13, -4, 15, -8, -49, -22, -49, -46, -53, -36, -141, -32, -57, -76, -63, -66, -205, -298, -275, -252, -289, -298

Offset

1,2

Comments

Minimal means minimize u^2+v^2. We follow Maple, PARI, etc., in setting u=0 and v=1 when x=y.

Links

Robert Israel, Table of n, a(n) for n = 1..2500

Maple

T:= proc(x, y) option remember; local g, u0, v0, t0, t1, t2;
   g:= igcd(x, y);
   if g > 1 then return procname(x/g, y/g) fi;
   v0:= y^(-1) mod x;
   u0:= (1-y*v0)/x;
   t0:= (v0*x-u0*y)/(x^2+y^2);
   t1:= floor(t0);
   if t0 < t1 + 1/2 then u0+v0 + t1*(y-x)
   else u0+v0 + (t1+1)*(y-x)
   fi
end proc:
R:= 1: v:= 1:
for n from 2 to 100 do v:= v+1+2*add(T(i, n), i=1..n-1); R:= R, v od:
R; # Robert Israel, Mar 28 2023

Mathematica

T[x_, y_] := T[x, y] = Module[{u, v}, MinimalBy[{u, v} /. Solve[u^2 + v^2 <= x^2 + y^2 && u*x + v*y == GCD[x, y], {u, v}, Integers], #.# &]];
a[n_] := a[n] = Sum[T[x, y][[1]]//Total, {x, 1, n}, {y, 1, n}];
Table[Print[n, " ", a[n]]; a[n], {n, 1, 54}] (* Jean-François Alcover, Mar 28 2023 *)

Prog

(Python)
from sympy.core.numbers import igcdex
def A345428(n): return sum(u+v for u, v, w in (igcdex(x, y) for x in range(1, n+1) for y in range(1, n+1))) # Chai Wah Wu, Jun 24 2021

Crossrefs

Cf. A345415-A345427.

Sequence in context: A310776 A310777 A310778 * A350244 A061503 A134659

Adjacent sequences: A345425 A345426 A345427 * A345429 A345430 A345431

Keyword

sign

Author

N. J. A. Sloane, Jun 22 2021

Status

approved