<br><font size=2 face="sans-serif">When you say the steps start and end on an integer, you mean a point whose coordinates are each integers, don't you? In that case, a(4) = 6,</font>
<br><font size=2 face="sans-serif">since the first step is first from (0,0) to (3,4) with length 5, and the second step from (3,4) to (4,4) has length 1. The sequence should</font>
<br><font size=2 face="sans-serif">start out as 2,4,6,6,8,10,10,12,14,16,16,... I believe a(n) is asymptotic to $n\sqrt{2}$, since the steps are dominated by steps whose x and y displacements</font>
<br><font size=2 face="sans-serif">differ by 1. In fact, it may be the case that a(n) is the smallest even integer greater than $n\sqrt{2}$.</font>
<br>
<br><font size=2 face="sans-serif">Dave</font>
<br>
<br>
<br>
<br>
<br>
<table width=100%>
<tr valign=top>
<td>
<td><font size=1 face="sans-serif"><b>Roland Bacher <Roland.Bacher@ujf-grenoble.fr></b></font>
<p><font size=1 face="sans-serif">03/24/2005 01:10 AM</font>
<br>
<td><font size=1 face="Arial">        </font>
<br><font size=1 face="sans-serif">        To:        Gordon Royle <gordon@csse.uwa.edu.au></font>
<br><font size=1 face="sans-serif">        cc:        seqfan@ext.jussieu.fr</font>
<br><font size=1 face="sans-serif">        Subject:        Re: Shortest path sequence</font></table>
<br>
<br><font size=2 face="Courier New">On Thu, Mar 24, 2005 at 03:56:29PM +0800, Gordon Royle wrote:<br>
> <br>
> On 24/03/2005, at 2:30 PM, Roland Bacher wrote:<br>
> <br>
> >On Wed, Mar 23, 2005 at 12:59:25PM -0500, David Wilson wrote:<br>
> >>Let a(n) be the length of the shortest path from (0, 0) to (n, n)<br>
> >>whose steps are of integer length and start and end on integer<br>
> ><br>
> ><br>
> >A stupid answer is $n\sqrt{2}$ since you can  take $n$ steps $(1,1)$.<br>
> <br>
> <br>
> These steps are not of integral length are they?<br>
> <br>
> Gordon<br>
> <br>
> <br>
You are correct, I did not read carefully enough.<br>
<br>
Here probably the solution.<br>
<br>
One should consider rightangled triangles with integral side-lengths<br>
whose two shorter sides of length a,b have approximatively the same<br>
length. Dividing by the length c=\sqrt(a^2+b^2) of the hypothenuse,<br>
one gets thus a rational point (a/c,b/c) on the unit circle which is<br>
close to (\sqrt(2),\sqrt(2)).<br>
<br>
Using the rational parametrisation t\longmapsto<br>
(2t/(1+t^2),(1-t^2)/(1+t^2)) and the convergents of the continued<br>
fraction of $\sqrt(2)-1$ one gets the infinite list<br>
(0,1)<br>
(3,4)<br>
(20,21)<br>
(119,120)<br>
(696,697)<br>
(4059,4060)<br>
(23660,23661)<br>
(137903,137904)<br>
etc<br>
<br>
The solution of your problem (shortest path joining (0,0) to (n,n)<br>
and consisting of integral vectors having integral lengths)<br>
should now be given by the algorithm (a proof of this can probably<br>
easily be given using properties of convergents):<br>
<br>
Set w=(n,n)<br>
<br>
Choose the longest possible vector v_i in the above (infinite)<br>
list such that w-v_i has <br>
coordinates \geq 0.<br>
<br>
Set (u_1,u_2)=w-v_i and replace w by (u_2,u_1).<br>
<br>
iterate until you reach (0,0)<br>
<br>
add the lenghts of all vectors $v_i$ choosen.<br>
<br>
Best whishes,   Roland<br>
</font>
<br>
<br>