Shortest path sequence

[David C Terr]

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,
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
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
differ by 1. In fact, it may be the case that a(n) is the smallest even 
integer greater than $n\sqrt{2}$.

Dave






Roland Bacher <Roland.Bacher at ujf-grenoble.fr>
03/24/2005 01:10 AM

 
        To:     Gordon Royle <gordon at csse.uwa.edu.au>
        cc:     seqfan at ext.jussieu.fr
        Subject:        Re: Shortest path sequence

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


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20050324/2670a533/attachment-0001.htm>