login
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|.
2

%I #17 Jul 13 2021 14:48:05

%S 0,1,4,7,16,19,37,49,70,82,127,145,208,235,277,325,433,472,607,667,

%T 757,832,1030,1102,1291,1399,1582,1708,2023,2119,2479,2671,2911,3103,

%U 3409,3571,4084,4327,4669,4909,5539,5737,6430,6760,7162,7525,8353,8641,9415,9787

%N 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|.

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

%C 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?

%p mygcd:=proc(a,b) local d,s,t; d := igcdex(a,b,`s`,`t`); [a,b,d,s,t]; end;

%p ansu:=[]; ansv:=[]; ansb:=[];

%p for N from 1 to 80 do

%p tu:=0; tv:=0; tb:=0;

%p for x from 1 to N do

%p for y from 1 to N do

%p if igcd(x,y)=1 then

%p tu:=tu+abs(mygcd(x,y)[4]);

%p tv:=tv+abs(mygcd(x,y)[5]);

%p tb:=tb+mygcd(x,y)[4]^2 + mygcd(x,y)[5]^2;

%p fi;

%p od: od:

%p ansu:=[op(ansu),tu];

%p ansv:=[op(ansv),tv];

%p ansb:=[op(ansb),tb];

%p od:

%p ansu; # the present sequence

%p ansv; # A345430

%p ansb; # A345431

%p # for A345432, A345433, A345434, omit the "igcd(x,y)=1" test

%o (Python)

%o from sympy.core.numbers import igcdex

%o 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

%Y Cf. A345415-A345434.

%K nonn

%O 1,3

%A _N. J. A. Sloane_, Jun 22 2021