a graph puzzle

[Maximilian Hasler]

On Fri, Apr 4, 2008 at 6:53 AM, Max Alekseyev <maxale at gmail.com> wrote:
>  The graph represents a mapping between integer pairs of co-prime
>  integers: (p,q) -> (a,b), where (a,b) is the ordered pair of the
>  absolute values of "smallest" Bezout coefficients for the pair (p,q).
>  { ab(p,q) = contfracpnqn(contfrac(p/q))[,2]~ }

note that this gives [1,0] instead of [0,1] for (1,1)

>  So, my question remains the same - is this mapping present in OEIS in
>  either form?

At least it is not there in the form

a(n) = index of  ab(CP[n])  in CP (where CP = seq. of coprime pairs {p,q})
= [0, 0, 0, 1, 0, 1, 0, 2, 2, 1, 0, 1, 0, 3, 2, 2, 4, 1, 0, 3, 4, 1,
0, 5, 2, 2, 6,...]
(where I use CP[0]=[0,1] ; if this is CP[1], then  a(n) => a(n)+1,
i.e. a(n)=[1, 1, 1, 2, 1, 2, 1, 3, 3, 2, 1, 2, 1, 4, 3, 3, 5, 2.,..)

neither in the form

a(n) = index of  ab(AP[n]) in AP (where AP = seq. of all pairs {p,q})
= [1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 4, 4, 2, 1, 1, 1,
1, 1, 2, 2, ...]

I put PARI code at the end of the mail.

Since I already spammed Neil with lots of sequences these days, I'm
reluctant to submit these, unless I get some encouragement...

>  P.S. My original concern was about pairs below given N, having the
>  longest path to (0,1), but they seem to be simply consecutive
>  Fibonacci numbers (as in Lame's theorem about Euclidean algorithm).

This seems not strange, knowing that the ratio of such pairs tends to
the Golden Ratio having contfrac = 1,1,1,1,1,... (of course this
argument is not a proof)

Maximilian

in PARI:
/* list of coprime couples, starting with [1,1]
 (we imagine that element #0 of this seq. should be [0,1]
*/
#cp=concat(vector(50,n,t=-1;vector(eulerphi(n),i,while(gcd(t++,n)!=1,);[t,n])))
/*
 i.e. cp = [[1, 1], [1, 2], [1, 3], [2, 3], [1, 4], [3, 4], [1, 5],
[2, 5], [3, 5], [4, 5],...]
*/
\\define MaxAl map for a couple
ma(pq) = contfracpnqn(contfrac(pq[1]/pq[2]))[,2]~
\\apply it to the couples
vector(#cp,i,ma(cp[i]))
\\now convert back into numbers (indices)
vector(#%,i,if(%[i][1],t=0;while( t<#cp & %[i]!=cp[t++],);t))
% = [774, 0, 0, 1, 0, 1, 0, 2, 2, 1, 0, 1, 0, 3, 2, 2, 4, 1, 0, 3, 4,
1, 0, 5...]
/* the 774 means "not found" for [1,0] which should be [0,1] => 0 */
%+vector(#%,i,1) \\ shifting indices by 1
% = [775, 1, 1, 2, 1, 2, 1, 3, 3, 2, 1, 2, 1, 4, 3, 3, 5, 2.,..]

\\ the "all pairs" variant: (ap=[0,1],[1,1],[0,2],[1,2],[2,2],[0,3]...)
#ap=concat(vector(50,n,vector(1+n,i,[i-1,n])))
\\here, the position of (a,b) is a+b(b+1)/2:
ap[4+7*(7+1)/2]
%=[4, 7]
vector(#ap,i, i=ma(ap[i]); i[1]+i[2]*(i[2]+1)/2))
% = [1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 4, 4, 2, 1, 1, 1,
1, 1, 2, 2, 1, 1, 1, 7, 4, 4, 8, 2, 1, 1, 1, 1, 7, 1, 8, 2, 2, 1, 1,
1, 11, 1, 4, 4, 2, 13, 2, 1, 1, 1, 1, 7, 4, 1, 4...]