<br><font size=2 face="sans-serif">I like your solution. In fact, I just thought of it myself! Note that your solution consists of a series of flattened staircases, with the most flattened one</font>
<br><font size=2 face="sans-serif">starting at (0,0) and becoming less flat approaching (n,n). I wonder what the solution is for a hexagonal lattice.</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/23/2005 10:30 PM</font>
<br>
<td><font size=1 face="Arial">        </font>
<br><font size=1 face="sans-serif">        To:        David Wilson <davidwwilson@comcast.net></font>
<br><font size=1 face="sans-serif">        cc:        Sequence Fans <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 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>
> coordinates.<br>
> <br>
> For example, we can always go from (0, 0) to (n, n) in two<br>
> steps, from (0, 0) to (0, n) to (n, n), so a(n) <= 2n.  Since<br>
> the path must be at least as long as the straight-line path from<br>
> (0, 0) to (n, n), we have a(n) < sqrt(2) n.  It is not hard to<br>
> construct examples with a(n) arbitrarily close to sqrt(2) n, and<br>
> I am sure that lim n->inf a(n)/n = sqrt(2).<br>
> <br>
> So can we compute a(n) efficiently?<br>
> <br>
> <br>
> <br>
> - David W. Wilson<br>
> <br>
> "Truth is just truth -- You can't have opinions about the truth."<br>
>   - Peter Schickele, from P.D.Q. Bach's oratorio "The Seasonings"<br>
<br>
<br>
By your comment you want steps containing no integral intermediate<br>
points<br>
<br>
A stupid answer is $n\sqrt{2}$ since you can  take $n$ steps $(1,1)$.<br>
<br>
I guess you don't like this one. The correct answer is then<br>
something like<br>
<br>
$\sqrt{\lfloor (n-1)/2\rfloor^2+\lfloor (n+1)/2\rfloor^2}+<br>
\sqrt{(n-\lfloor (n-1)/2\rfloor)^2+(n-\lfloor (n+1)/2\rfloor)^2}$<br>
<br>
(geometrically, go in two steps from (0,0) to (n,n) by making<br>
a stop at (one of the four) integral points which are closest<br>
and different from (n/2,n/2) )<br>
This is obviously the shortest such path which is not straight.<br>
<br>
 <br>
Best whishes,   Roland Bacher<br>
</font>
<br>
<br>