Shortest path sequence

[Joshua Zucker]

On Wed, 23 Mar 2005 12:59:25 -0500, David Wilson
<davidwwilson at comcast.net> 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.  

I think you flipped the inequality here.

> 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

Nice question!
I wrote a quickie inefficient program to do this, with the assumption
that the shortest path never leaves the square.  I'm not completely
sure that's true, but it seems plausible anyway that if a shortest
path left the square, there would also exist some reflection of it
that didn't, but I'm not completely convinced (for example, that in
some big square  you might want to go to (4, -3) and then straight to
(n,n) if (n-4)^2 + (n+3)^2 happens to be a perfect square ... hm.

Rob Pratt points out that there are still only finitely many points to
consider because of the lower and upper bounds you give, so that's
good.

As for his conjecture:
the lower bound is already awfully close to this.
Using (3,4) vectors of length 5, you can get an upper bound that's not
too far from this, either... but for large n it's not obvious to me
that there are always enough pythagorean triples around.


For the first 400 terms, I get
0 2 4 6 6 8 10 10 12 14 16 16 18 20 20 22 24 26 26 28 30 30 32 34 34
36 38 40 40 42 44 44 46 48 50 50 52 54 54 56 58 58 60 62 64 64 66 68
68 70 72 74 74 76 78 78 80 82 84 84 86 88 88 90 92 92 94 96 98 98 100
102 102 104 106 108 108 110 112 112 114 116 116 118 120 122 122 124
126 126 128 130 132 132 134 136 136 138 140 142 142 144 146 146 148
150 150 152 154 156 156 158 160 160 162 164 166 166 168 170 170 172
174 174 176 178 180 180 182 184 184 186 188 190 190 192 194 194 196
198 198 200 202 204 204 206 208 208 210 212 214 214 216 218 218 220
222 224 224 226 228 228 230 232 232 234 236 238 238 240 242 242 244
246 248 248 250 252 252 254 256 256 258 260 262 262 264 266 266 268
270 272 272 274 276 276 278 280 282 282 284 286 286 288 290 290 292
294 296 296 298 300 300 302 304 306 306 308 310 310 312 314 314 316
318 320 320 322 324 324 326 328 330 330 332 334 334 336 338 338 340
342 344 344 346 348 348 350 352 354 354 356 358 358 360 362 364 364
366 368 368 370 372 372 374 376 378 378 380 382 382 384 386 388 388
390 392 392 394 396 396 398 400 402 402 404 406 406 408 410 412 412
414 416 416 418 420 422 422 424 426 426 428 430 430 432 434 436 436
438 440 440 442 444 446 446 448 450 450 452 454 454 456 458 460 460
462 464 464 466 468 470 470 472 474 474 476 478 480 480 482 484 484
486 488 488 490 492 494 494 496 498 498 500 502 504 504 506 508 508
510 512 512 514 516 518 518 520 522 522 524 526 528 528 530 532 532
534 536 536 538 540 542 542 544 546 546 548 550 552 552 554 556 556
558 560 562 562 564 566 566

and if people are curious about the triangle (that is, a(x,y) instead
of a(n,n)) I can provide those terms as well.

These terms do all fit the conjecture that a(n,n) = n*sqrt(2) after
rounding up to the next larger even integer: that is,
2*ceil(n/sqrt(2)).

Also Roland's proposed algorithm, greedily using only triples (0,1)
(3,4) (20 21) (119 120) and so on, gives the same answers at least up
to n = 400 ... so I'm pretty convinced experimentally that he was
right and my more brute-force approach was stupid and unnecessary.


--Joshua Zucker