Shortest path sequence

[Roland Bacher]

It is easy to prove that $a(n)/n$ tends to $\sqrt{2}$ for $n$
going to infinity: The number of steps with indices $\leq k$
in the algorithm is easily seen to be bounded and steps 
with high indices are more and more parallel to then vector (1,1).

It is also easy to prove that you cannot do better: this follows
from properties of convergents of continued fractions. 

Perhaps more interesting are analogous problems in higher
dimensions (say from $(0,0,0)$ to (n,n,n)$ in $Z^3$): higher
dimensional analgues of continued fractions are a delicate topic
which is not very well understood to my nowledge.

Roland




On Thu, Mar 24, 2005 at 09:32:50AM -0800, David C Terr wrote:
> 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
> 
>