Shortest path sequence

[Paul C. Leopardi]

On Thu, 24 Mar 2005 04:59 am, 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
> 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?

Related questions would be, for each n:
1. The number of distinct shortest length paths of this type.
2. The minimum number of steps of a shortest length path of this type.
3. The number of distinct shortest length paths of this type having minimum 
length.

To see that the number of steps of a shortest length path is not unique,
consider paths for (0,0) to (8,8):

(0,0) to (0,2) to (8,8) (2 steps: 2+10=12) vs
(0,0) to (3,4) to (5,4) to (8,8) (3 steps: 5+2+5=12) vs
(0,0) to (3,4) to (4,4) to (8,7) to (8,8) (4 steps: 5+1+5+1=12).

All three paths are of length 12. 
This is minimal, since sqrt(2)*8 > 11.

There are 3 other shortest paths with 2 steps, which are obtained by various 
combinations of reflections:
(0,0) to (2,0) to (8,8) (2 steps: 2+10=12),
(0,0) to (6,8) to (8,8) (2 steps: 10+2=12),
(0,0) to (8,6) to (8,8) (2 steps: 10+2=12).