Shortest path sequence

[Rob Pratt]

> -----Original Message-----
> From: David Wilson [mailto:davidwwilson at comcast.net] 
> Sent: Wednesday, March 23, 2005 12:59 PM
> To: Sequence Fans
> Subject: Shortest path sequence
> 
> 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 coordinates.
> 
> For example, we can always go from (0, 0) to (n, n) in two 
> steps, from (0, 0) to (0, n) to (n, n), so a(n) <= 2n.  Since 
> the path must be at least as long as the straight-line path 
> from (0, 0) to (n, n), we have a(n) < sqrt(2) n.  It is not 
> hard to construct examples with a(n) arbitrarily close to 
> sqrt(2) n, and I am sure that lim n->inf a(n)/n = sqrt(2).
> 
> So can we compute a(n) efficiently?
> 
> 
> 
> - David W. Wilson
> 
> "Truth is just truth -- You can't have opinions about the truth."
>    - Peter Schickele, from P.D.Q. Bach's oratorio "The Seasonings"


Let a(n,k) be the length of the shortest path from (0, 0) to (n, k) whose steps are of integer length and start and end on integer coordinates, so that a(n) = a(n,n).  Then a(n,k) satisfies the following recursion:

a(n,0) = n

a(0,k) = k

a(n,k) = min {a(i,j) + sqrt((n-i)^2 + (k-j)^2)},
where the minimum is taken over all neighbors (i,j) of (n,k) in the integer lattice.  Since a(n,k) <= n + k, this set of neighbors can be restricted to a finite set.

Conjecture: a(n,n) = 2 ceiling(n/sqrt(2)).


Rob Pratt