Sequence needed for "Shortest path"

[Graeme McRae]

Ahh, yes.  I'm starting to get it now.  The triangles of the form

3,4,5
21,20,29
119,120,169
697,696,985

etc., are needed to find the shortest path, because these are the closest
integer triangles to the diagonal of the square formed by points (0,0) and
(n,n)

If you think of these triples as (r^2-s^2, 2rs, r^2+s^2) then these
near-diagonal triangles are generated by r,s pairs

2,1
5,2
12,5
29,12
70,29
169,70

These pairs are governed by a recurrence relation that isn't too hard to
discover.  Naturally, being a seqfan, I looked up the sequence and found it
was A000129, the Pell Numbers.

I found it interesting that this sequence is the denominators of the
continued fraction convergents to sqrt(2): 1.
And A000129(n)+A000129(n-1)=A001333(n) are the numerators of those
convergents, a fact that is noted in the descriptions of both sequences.

I'm in my manic phase now, so I'm too excited by this discovery to take the
time to understand how this relates to the shortest path from (0,0) to
(n,n).  Later, I'll be too down on myself to feel capable of making the
connection.  But maybe one of the other seqfans can connect the dots, so to
speak.

--Graeme

P.S. I was kidding about that manic depressive stuff -- truth is, I'm just
lazy!


----- Original Message ----- 
From: "Rob Pratt" <Rob.Pratt at sas.com>
To: <njas at research.att.com>; <seqfan at ext.jussieu.fr>
Sent: Friday, March 25, 2005 1:47 PM
Subject: RE: Sequence needed for "Shortest path"


> > -----Original Message-----
> > From: N. J. A. Sloane [mailto:njas at research.att.com]
> > Sent: Friday, March 25, 2005 4:13 PM
> > To: seqfan at ext.jussieu.fr
> > Cc: njas at research.att.com
> > Subject: Sequence needed for "Shortest path"
> >
> >
> > There have been a lot of postings on this problem, (the
> > Shortest path sequence) but my impression is that the actual
> > sequence hasn't yet been submitted to the OEIS?  If that's
> > so, would someone please send it in?  (And post it here too)
> >
> > Thanks!
> >
> > NJAS
>
>
> If appropriate, please link the new sequence to the one below, with a
comment like a(n) = 2*A049474(n).
>
> Rob
>
>
> ID Number: A049474
> URL:       http://www.research.att.com/projects/OEIS?Anum=A049474
> Sequence:  0,1,2,3,3,4,5,5,6,7,8,8,9,10,10,11,12,13,13,14,15,15,16,17,
>            17,18,19,20,20,21,22,22,23,24,25,25,26,27,27,28,29,29,30,31,
>            32,32,33,34,34,35,36,37,37,38,39,39,40,41,42,42,43,44,44,45,
>            46,46,47
> Name:      Ceiling(n/sqrt(2)).
> See also:  Adjacent sequences: A049471 A049472 A049473 this_sequence
A049475
>               A049476 A049477
>            Sequence in context: A066481 A067022 A003003 this_sequence
A076874
>               A007998 A029931
> Keywords:  nonn
> Offset:    0
> Author(s): njas
>
>