what sequences most need extending?

[Pfoertner, Hugo]

-----Original Message-----
From: N. J. A. Sloane [mailto:njas at research.att.com] 
Sent: Monday, May 23, 2005 23:08
To: seqfan at ext.jussieu.fr
Cc: njas at research.att.com
Subject: what sequences most need extending?



Dear Seqfans,  I got email asking me to propose
a sequence that a group of programmers could
work on as a challenge.  The following
constraints were suggested:



1) It must be NP-complete
2) It must be simple to describe
3) It should not have been widely explored
4) A solution must be easy to check (= it doesn't require a lot of 
computation)
5) It has to be computed from N=8 to at most 64


Does anyone have a good suggestion?

NJAS

----------------------------------------------------------------

Neil, SeqFans,

of course I agree that
http://www.research.att.com/projects/OEIS?Anum=A004137
Sequence:  0,1,3,6,9,13,17,23,29,36,43,50,58,68,79,90,101,112,123,138,153,
Name:      Maximal number of edges in a graceful graph on n nodes.

as suggested by Rainer might be an excellent choice, although it does not
fulfill criterion 3)

Some others of my personal favorites:

-------------

Confirm Daren Casella's results for

The Snake or Coil in the Box Problem:
 
http://www.research.att.com/projects/OEIS?Anum=A000937
2,4,6,8,14,26,48
Name: Length of longest simple cycle without chords in the n-dimensional
hypercube graph. Also called n-coil or closed n-snake-in-the-box problem.
After 48, lower bounds on the next terms are 96,180,344,630,1236. -
Darren Casella (artdeco42(AT)yahoo.com), Mar 04 2005

http://www.research.att.com/projects/OEIS?Anum=A099155
Sequence:  1,2,4,7,13,26,50
Name: Maximum length of a simple path with no chords in the n-dimensional
hypercube, also known as snake-in-the-box problem.
After 50, lower bounds on the next terms are 97,186,358,680,1260. -
Darren Casella (artdeco42(AT)yahoo.com), Mar 04 2005

-----------

Find an extension of
http://www.research.att.com/projects/OEIS?Anum=A087725
Sequence:  0,6,31,80
Name:      Maximum number of moves required for the n X n generalization of
Sam
           Loyd's Fifteen Puzzle.

As a "warm-up" for this the research group could complete
http://www.research.att.com/projects/OEIS?Anum=A089484
Sequence:  1,2,4,10,24,54,107,212,446,946,1948,3938,7808,15544,30821,
           60842,119000,231844,447342,859744
Name:      Number of configurations of Sam Loyd's sliding block 15-puzzle
that
           require a minimum of n moves to be reached, starting with the
empty
           square in one of the corners.
and the related
http://www.research.att.com/projects/OEIS?Anum=A090164 and
http://www.research.att.com/projects/OEIS?Anum=A090165

-----------

http://www.research.att.com/projects/OEIS?Anum=A085000
Sequence:  1,10,412,40800,6839492,1865999570
Name:      Maximal determinant of an n X n matrix using the integers 1 to
n^2.

I have spent more than 2 years of CPU time to get a current lower bound for
a(7)>=762140212575 and much less time for
a(8)>=440857916120379
but it seems impossible to fulfill criterion 4) (easy to check) for this
sequence

------------

Similar problems dealing with the spectrum of determinants:

http://www.research.att.com/projects/OEIS?Anum=A089472
Sequence:  2,3,5,7,11,19,43
Name:      Number of different values taken by the determinant of a real
           (0,1)-matrix of order n.

and some of the sequences X-linked in A089472.

Hugo