[Fwd: Re: [Fwd: SEQ+# A135929 FROM Artur Jasinski]]

Fri Dec 7 14:31:28 CET 2007

Artur,

The web page shows the complete bipartite graph K_n_n with 2n vertices.

http://mathworld.wolfram.com/CompleteBipartiteGraph.html
http://reference.wolfram.com/mathematica/Combinatorica/ref/CompleteGraph.html

Also, your two definitions disagree about a(1).  Travelling salesmen
are allowed to repeat roads to get the minimal distance, so they have a
route for n=1 and that sequence is A010790.  You should contribute a
comment for A010790.

Martin

--- Artur <grafix at csl.pl> wrote:

> 
> > Date: Thu, 06 Dec 2007 22:18:33 +0100
> From: Artur <grafix at csl.pl>
> To: Mitch Harris <maharri at gmail.com>
> Subject: Re: [Fwd: SEQ+# A135929 FROM Artur Jasinski]
> 
> Mitch
> See:
>
http://reference.wolfram.com/mathematica/Combinatorica/tutorial/Combinatorica.html
> and later search In[62]: <javascript:input('i_123')>
> ARTUR
> 
> 
> Mitch Harris pisze:
> > On Dec 6, 2007 1:00 PM, Artur <grafix at csl.pl> wrote:
> >   
> >> %I A135929
> >> %S A135929 0, 2, 12, 144, 2880
> >> %N A135929 Number of different Hamiltonian cycles in complete n
> vertices graph (also number of different roads in traveling salesman
> problem)
> >> %C A135929 A Hamiltonian cycle of a graph G is a cycle that visits
> every vertex in G exactly once, as opposed to an Eulerian cycle that
> visits each edge exactly once. K_n_n for n>1 are the only
> Hamiltonian complete bipartite graphs.
> >> %e A135929 a(3)=12 because different cycles in 3 Graph are
> >> {{1, 4, 2, 5, 3, 6, 1}, {1, 4, 2, 6, 3, 5, 1}, {1, 4, 3, 5, 2, 6,
> 1}, {1, 4, 3, 6, 2, 5, 1}, {1, 5, 2, 4, 3, 6, 1}, {1, 5, 2, 6, 3, 4,
> 1}, {1, 5, 3, 4, 2, 6, 1}, {1, 5, 3, 6, 2, 4, 1}, {1, 6, 2, 4, 3, 5,
> 1}, {1, 6, 2, 5, 3, 4, 1}, {1, 6, 3, 4, 2, 5, 1}, {1, 6, 3, 5, 2, 4,
> 1}}
> >> %t A135929 << DiscreteMath`Combinatorica`
> >> Table[a = Length[HamiltonianCycle[CompleteGraph[n, n], All]];
> Print[a], {n, 1, 10}] (*Artur Jasinski*)
> >>     
> >
> > Your description and implementation are inconsistent.
> >
> > # of hamilton cycles (what you call your sequence): pick node as
> > arbitrary start in n ways. next node there are n-1 left, next n-2
> left
> > etc... total n! ways (and since a cycle doesn't really have a start
> > node, divide by n for
> >
> >   (n-1)!  (http://www.research.att.com/~njas/sequences/A000142)
> >
> > # hamilton cycles of n,n complete bipartite graph (what you compute
> > with maple, and the #'s given) pick start 2n ways, next node n
> ways,
> > next node n-1, next n-1, next n-2, next n-2, etc  = 2 n! n!, cycle
> > doesn't have a start node (divide by 2n) for total:
> >
> >  n!(n-1)!  (or http://www.research.att.com/~njas/sequences/A010790
> as Max said)
> >
> > Instead of a new sequence (for either) you should add the
> appropriate
> > separate comments to these two sequences via the comment web page
> >
> >    http://www.research.att.com/~njas/sequences/Submit.html
> >
> > (I checked, neither of these sequences mentions Hamiltonian cycles
> on
> > K_n or K_{n,n} respectively)
> >
> > Mitch
> >
> > __________ NOD32 Informacje 2701 (20071204) __________
> >
> > Wiadomosc zostala sprawdzona przez System Antywirusowy NOD32
> > http://www.nod32.com lub http://www.nod32.pl 
> >
> >
> >
> >   
> 
> 

njas> From seqfan-owner at ext.jussieu.fr  Thu Dec  6 21:17:19 2007
njas> Return-Path: <seqfan-owner at ext.jussieu.fr>
njas> Date: Thu, 6 Dec 2007 15:17:01 -0500
njas> From: "N. J. A. Sloane" <njas at research.att.com>
njas> To: dean at math.ucdavis.edu, martin_n_fuller at btinternet.com,
njas>         seqfan at ext.jussieu.fr
njas> Subject: Re: Abundant numbers of form n^a+n+1
njas> Cc: jb at brennen.net, pxp at rogers.com, simon.plouffe at sympatico.ca
njas> 
njas> mf> Martin said:
njas> mf> Another solution is n=19581212842 which has
njas> mf> n^2+n+1 = 3*7^2*13*19*31*37*43*61*79*97*103*4447
njas> mf> sigma(n^2+n+1)/(n^2+n+1) = 2.0031147...
njas> 
njas> Me:  That almost brings the problem within range
njas> of a brute force search.  If 100 seqfans searched
njas> for 100 days using ...  What IS the fastest program
njas> for this sort of thing?  Mathematica, Pari, Sage?
njas> Simon, what do you think?
njas> (The question is, what is the smallest amicable 
njas> number of the form n^2+n+1 ?)
njas> 
njas> Neil

I've searched through the first 55 files out of 999 in the Pedersen collection
of known
amicable numbers, http://amicable.adsl.dk/aliquot/c2/c2_3.txt to c2_55.txt ,
overview in http://amicable.homepage.dk/knwnc2.htm :
there is no number of the form n^2+n+1 (n integer) in there.
The interpretation depends on how far one is confident that these scans are
complete. If they are, the n^2+n+1 has more than 55 digits, whereas
the n^2+n+1 derived from n=19581212842 quoted above has only 21.

Richard

rjm> From seqfan-owner at ext.jussieu.fr  Fri Dec  7 16:16:54 2007
rjm> Return-Path: <seqfan-owner at ext.jussieu.fr>
rjm> Date: Fri, 7 Dec 2007 16:14:52 +0100
rjm> From: Richard Mathar <mathar at strw.leidenuniv.nl>
rjm> To: seqfan at ext.jussieu.fr
rjm> Subject: Re^2: Abundant numbers of form n^a+n+1
rjm> 
rjm> njas> From seqfan-owner at ext.jussieu.fr  Thu Dec  6 21:17:19 2007
rjm> njas> Return-Path: <seqfan-owner at ext.jussieu.fr>
rjm> njas> Date: Thu, 6 Dec 2007 15:17:01 -0500
rjm> njas> From: "N. J. A. Sloane" <njas at research.att.com>
rjm> njas> To: dean at math.ucdavis.edu, martin_n_fuller at btinternet.com,
rjm> njas>         seqfan at ext.jussieu.fr
rjm> njas> Subject: Re: Abundant numbers of form n^a+n+1
rjm> njas> Cc: jb at brennen.net, pxp at rogers.com, simon.plouffe at sympatico.ca
rjm> njas> 
rjm> njas> mf> Martin said:
rjm> njas> mf> Another solution is n=19581212842 which has
rjm> njas> mf> n^2+n+1 = 3*7^2*13*19*31*37*43*61*79*97*103*4447
rjm> njas> mf> sigma(n^2+n+1)/(n^2+n+1) = 2.0031147...
rjm> njas> 
rjm> njas> Me:  That almost brings the problem within range
rjm> njas> of a brute force search.  If 100 seqfans searched
rjm> njas> for 100 days using ...  What IS the fastest program
rjm> njas> for this sort of thing?  Mathematica, Pari, Sage?
rjm> njas> Simon, what do you think?
rjm> njas> (The question is, what is the smallest amicable 
rjm> njas> number of the form n^2+n+1 ?)
rjm> njas> 
rjm> njas> Neil
rjm> 
rjm> I've searched through the first 55 files out of 999 in the Pedersen collection
rjm> of known
rjm> amicable numbers, http://amicable.adsl.dk/aliquot/c2/c2_3.txt to c2_55.txt ,
rjm> overview in http://amicable.homepage.dk/knwnc2.htm :
rjm> there is no number of the form n^2+n+1 (n integer) in there.
rjm> The interpretation depends on how far one is confident that these scans are
rjm> complete. If they are, the n^2+n+1 has more than 55 digits, whereas
rjm> the n^2+n+1 derived from n=19581212842 quoted above has only 21.
rjm> 
rjm> Richard

I should add that this was steering of the main thread and a search
for *amicable* numbers of the form n^2+n+1, whereas the original problem
dealt with *abundant* numbers. No discrepancy arises so far. In addition,
the Pedersen tables are explicitly commented to be complete for up to 14 digits.
The only strong conclusion so far is that there is no *amicable* number
of the form n^2+n+1 with 14 digits or less, and in the Pedersen compilation
there is no amicable number of this form with 67 digits or less (67 now,
larger than the 55 in my previous posting, because my program is still
running...)

Richard

> I should add that this was steering of the main thread and a search
> for *amicable* numbers of the form n^2+n+1, whereas the original  
> problem
> dealt with *abundant* numbers.

Indeed. Although Neil wrote amicable, I'm sure he meant abundant,  