Abundant numbers of form n^a+n+1

[N. J. A. Sloane]

sigma(n^2+n+1)/(n^2+n+1) = 2.0031147...
Me:  That almost brings the problem within range
Return-Path: <martin_n_fuller at btinternet.com>
X-Ids: 166
DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws;
  s=s1024; d=btinternet.com;
  h=X-YMail-OSG:Received:Date:From:Subject:To:Cc:In-Reply-To:MIME-Version:Content-Type:Content-Transfer-Encoding:Message-ID;
  b=uNi8qzu62MMovoLLMqZLoZGXeJtxu1r06UXidhO0/w6PcS/EzFwbZbk/pHJC+OxiUySXGRUqJe6Bd11zXvCPJZkvyIqq5ZbwOFzFxZS6hd22R882mg19POzsueTgaGTurPprUV+b3aPhxyjxTezTrpzV2/lwGlQAI0IoZsgTUco=;
X-YMail-OSG: ir693twVM1lNYlsFfTHD50lhXlFHQyhgSWdqXMO.B7ToMNk7FqM0GHsqvU1GgqzUJKcz6omJQSeirr1mgeruuifmaZIPLDoTdIG_QI5h5UFF
Date: Thu, 6 Dec 2007 19:51:06 +0000 (GMT)
From: Martin Fuller <martin_n_fuller at btinternet.com>
Subject: Re: A109094 maximum salesman path in K_n
To: Mitch Harris <maharri at gmail.com>,
   Richard Mathar <mathar at strw.leidenuniv.nl>
Cc: seqfan at ext.jussieu.fr, rpropper at mail.strw.leidenuniv.nl,
   stanford.edu at mail.strw.leidenuniv.nl
In-Reply-To: <553db06d0712060816w2d049202o6779239f352d0750 at mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: 8bit
Message-ID: <969734.3597.qm at web86612.mail.ird.yahoo.com>
X-Greylist: Delayed for 01:00:00 by milter-greylist-3.0 (shiva.jussieu.fr [134.157.0.166]); Thu, 06 Dec 2007 21:51:09 +0100 (CET)
X-Virus-Scanned: ClamAV 0.88.7/5022/Thu Dec  6 19:53:06 2007 on shiva.jussieu.fr
X-Virus-Status: Clean
X-Miltered: at shiva.jussieu.fr with ID 475860BC.002 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)!


--- Mitch Harris <maharri at gmail.com> wrote:

> On Dec 6, 2007 7:53 AM, Richard Mathar <mathar at strw.leidenuniv.nl>
> wrote:
> >
> > A109094 looks for a longest path along the edges of the complete
> graph
> > with n vertices.
> ...
> > The total number of edges is n(n-1)/2. Traveling each at most once
> > and not allowing return to the starting vertex gives an upper bound
> > a(n) < n(n-1)/2 for n>2. Heuristically, this seems to be actually
> achieved for
> > all odd n, and I presume that there is a "template" path argument
> to prove
> > this case looking for some pattern in the paths listed above.
> >
> > There is also a simple argument why the upper bound is not reached
> for
> > cases of even n: the connectivity of each vertex is n-1, an odd
> number.
> > Since the path subtracts 2 (an even number) from the connectivity
> each
> > time it passes a vertex, for n-2 vertices (all but the first and
> last)
> > one edge is not used and remains dangling (as people in surface
> chemistry
> > would say). So the additional deficiency in the edge count is
> (n-2)/2
> > (at least) for even n, where the division by 2 means that there is
> one edge
> > left over for each pair of vertices not connected by an element of
> the path.
> 
> The problem is more related to Euler paths (covering all -edges-)
> rather than Hamilton paths (covering all nodes, whose weighted
> version
> is called the traveling salesman problem).
> 
> Following reasoning similar to what you gave above, K_{2n+1} -always-
> has an Euler cycle ,one that goes all edges (in this case n(2n+1)
> edges), and since we're working on complete graphs, removing the last
> edge gives the longest -path- sought. So
> 
>   a(2n+1) = n(2n+1) - 1  (or a(k) = k(k-1)/2 - 1, where k is odd =
> 2n+1)
> 
> 
> Now the more interesting problem is a maximal edge covering path in
> K_{2n}, because by similar reasoning just mentioned, it -never- has
> an
> Euler path (much less an Euler cycle) for n>1.
> 
> A simple upper bound is of course n(2n-1) - 1 as you say (the total
> number of edges) but since that cannot be reached, there must be a
> better bound. At worst, n - 1 edges cannot be used (2n - 2 nodes have
> all but 1 edge covered, the remaining 2 nodes have all edges covered)
> this results in an upper bound of
> 
>   n(2n-1) - n + 1 = 2n^2 -2n + 1 (or k(k-1)/2 - k/2 + 1 where k is
> even = 2n)
> 
> (I'm not saying this is a(k) for even k on purpose, even though it
> mght work out that way)
> 
> This gives:
> 
>   1, 2, 5, 9, 13, 20, 25, 35, 41, 54, 61, 77, 85, 104, 113, 135, 145,
> 170
> 
> which only differs from your examples starting at odds from 61.
> 
> But this is a simple upper bound, given without a construction.Off
> the
> top of my head I can't think of one. Any ideas? Can one connect 2n-1
> disjoint n-cycles, such that there are n left over disconnected
> edges?
> That seems the way to go but I just can't visualize enforcing the
> leftover edges being disconnected.
> 
> Mitch
> 

The even upper bound is also achievable.

 From MathWorld: "A connected graph has an Eulerian trail iff it has at
most two graph vertices of odd degree."
http://mathworld.wolfram.com/EulerPath.html

Start from the complete graph, and pair up the k-2 vertices that are
not the chosen end points.  Ignore the connecting edge for each pair.
1. This graph has k(k-1)/2 - k/2 + 1 edges, matching the upper bound.
2. The end points are adjacent to everything else, so it is connected.
3. Only the 2 end points have odd degree.

So there is an Euler path.

Artur's question was to find the length of the shortest path along the
edges of the complete graph with n vertices.  For odd n the answer is
n*(n-1)/2, for even n it is n^2/2-1.  This is A128223(n-1).

Martin Fuller