Shortest path sequence

[Roland Bacher]

On Thu, Mar 24, 2005 at 03:56:29PM +0800, Gordon Royle wrote:
> 
> On 24/03/2005, at 2:30 PM, Roland Bacher wrote:
> 
> >On Wed, Mar 23, 2005 at 12:59:25PM -0500, David Wilson wrote:
> >>Let a(n) be the length of the shortest path from (0, 0) to (n, n)
> >>whose steps are of integer length and start and end on integer
> >
> >
> >A stupid answer is $n\sqrt{2}$ since you can  take $n$ steps $(1,1)$.
> 
> 
> These steps are not of integral length are they?
> 
> Gordon
> 
> 
You are correct, I did not read carefully enough.

Here probably the solution.

One should consider rightangled triangles with integral side-lengths
whose two shorter sides of length a,b have approximatively the same
length. Dividing by the length c=\sqrt(a^2+b^2) of the hypothenuse,
one gets thus a rational point (a/c,b/c) on the unit circle which is
close to (\sqrt(2),\sqrt(2)).

Using the rational parametrisation t\longmapsto
(2t/(1+t^2),(1-t^2)/(1+t^2)) and the convergents of the continued
fraction of $\sqrt(2)-1$ one gets the infinite list
(0,1)
(3,4)
(20,21)
(119,120)
(696,697)
(4059,4060)
(23660,23661)
(137903,137904)
etc

The solution of your problem (shortest path joining (0,0) to (n,n)
and consisting of integral vectors having integral lengths)
should now be given by the algorithm (a proof of this can probably
easily be given using properties of convergents):

Set w=(n,n)

Choose the longest possible vector v_i in the above (infinite)
list such that w-v_i has 
coordinates \geq 0.

Set (u_1,u_2)=w-v_i and replace w by (u_2,u_1).

iterate until you reach (0,0)

add the lenghts of all vectors $v_i$ choosen.

Best whishes,   Roland