Shortest path sequence

[David Wilson]

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"