Sequence needed for "Shortest path"

[Roland Bacher]

There remains perhaps to find a proof that the two sequences are
indeed identical.

Perhaps one should try to understand the following more general
problem:

(a,b)\in N^2 an integral vector 
denote by s(a,b)\in N the minimal sum $\sum_ \sqrt(a_i^2+b_i^2)$
where $a_1,\dots,b_1,\dots,\in N$,
$a_i^2+b_i^2$ a square and $a=\sum a_i,\ b=\sum b_i$ (and the minimum
is of course taken over all such decomposition). Again,
the number $s(a,b)$ can be computed using continued fractions.

When does the equality

$s(a,b)=ceiling(\sqrt(a^2+b^2))$ 

hold?

Roland


On Fri, Mar 25, 2005 at 04:47:42PM -0500, Rob Pratt wrote:
> > -----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
>