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

0, 1, 4, 7, 16, 19, 37, 49, 70, 82, 127, 145, 208, 235, 277, 325, 433, 472, 607, 667, 757, 832, 1030, 1102, 1291, 1399, 1582, 1708, 2023, 2119, 2479, 2671, 2911, 3103, 3409, 3571, 4084, 4327, 4669, 4909, 5539, 5737, 6430, 6760, 7162, 7525, 8353, 8641, 9415, 9787

Offset: 1

Author

N. J. A. Sloane, Jun 22 2021

Keywords

• nonn

Comments

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

It would be nice to have b-files for this and related sequences (as listed in cross-references). The present sequence is especially interesting. What is its rate of growth?

Crossrefs

Cf. A345415-A345434.

Programs

Maple

mygcd:=proc(a,b) local d,s,t; d := igcdex(a,b,`s`,`t`); [a,b,d,s,t]; end;
ansu:=[]; ansv:=[]; ansb:=[];
for N from 1 to 80 do
tu:=0; tv:=0; tb:=0;
for x from 1 to N do
for y from 1 to N do
if igcd(x,y)=1 then
   tu:=tu+abs(mygcd(x,y)[4]);
   tv:=tv+abs(mygcd(x,y)[5]);
   tb:=tb+mygcd(x,y)[4]^2 + mygcd(x,y)[5]^2;
fi;
od: od:
ansu:=[op(ansu),tu];
ansv:=[op(ansv),tv];
ansb:=[op(ansb),tb];
od:
ansu; # the present sequence
ansv; # A345430
ansb; # A345431
# for A345432, A345433, A345434, omit the "igcd(x,y)=1" test

Python

from sympy.core.numbers import igcdex
def A345429(n): return sum(abs(u) for u, v, w in (igcdex(x,y) for x in range(1,n+1) for y in range(1,n+1)) if w == 1) # Chai Wah Wu, Jun 22 2021