[seqfan] Re: easy and bref

franktaw at netscape.net franktaw at netscape.net
Sat Oct 1 01:14:59 CEST 2011

Don't forget the "more" keyword. In an ideal world, the sequences 
marked as "hard" under an expansive definition ought to be the same as 
the ones marked "more". In practice, there are sequences marked "more" 
that certainly are not hard.

I guess I would favor a middle ground. Which corresponds pretty well 
with what we have; with the usual share of misapplications, of course.

Franklin T. Adams-Watters

-----Original Message-----
From: Marc LeBrun <mlb at well.com>

>="D. S. McNeil" <dsm054 at gmail.com>
> I guess I don't see "hard" as a permanent property but as a
> description of our state of knowledge... If someone comes up with a 
> and we suddenly had lots of terms, we'd simply remove "hard", like we 
> "obsc" after someone cleans up a sequence in bad shape.

>="franktaw at netscape.net" <franktaw at netscape.net>
> Where I object to its use is the case where someone basically says, 
> know how to calculate this, so we'll call it hard." There should
be at least
> some theory suggesting that it really is hard.

>="Charles Greathouse" <charles.greathouse at case.edu>
> That's a pretty hefty requirement; I don't think we should limit hard
> to just such cases.
> ...
> But I think I agree that it would be best to use it only when the
> problem is known (in some sense) to be hard.

Heh.  I surely agree with some of this, but deciding in which sense is 

I propose that we continue to interpret a bare "hard" keyword to signify
Not-Known-to-be-Easy, AND, for the rare Known-to-be-Difficult cases,
recommend it be supplemented with comments or references documenting 

Certainly "hard" should be used if the sequence is known to be hard in 
technical sense.  Of course if this is known then it's reasonable to 
ask for
this knowledge to be shared via comments, references or the like.

However I also think it's constructive to simply tag something as 
"hard" if
the submitter, after making some reasonable amount of sincere effort, is
unable to come up with anything significantly better than some brutish

For one thing this might wave a red flag in front of someone with better
power tools, motivating them to gain eternal glory by adding more terms 
the OEIS and clearing the "hard" keyword!

For example one of the first sequences I ever sent Neil is A006585.  I
obtained up to a(7) by turning an old 286 into a space-heater, and John
Dethridge has only extended it to a(8) in 2004.  I think the "hard" 
seems at least provisionally plausible simply by the test of time.  But 
haven't the slightest clue how to even begin proving that it is hard, 
in any
technical sense (eg some Conway-Egyptian-Fractran machine equivalence?)

On the other hand, for a long time I've personally suspected that 
might be hard in some technical sense, but haven't set the flag because 
lingering fantasies that some unidentified future expert in some field I
don't even know the name of might someday be able to easily extend it.

Which approach do you think is the most likely to spur progress--the
provocative or the timid?  I'd rather risk having some false "hards" 
out to be stimulating challenges, than reserve "hard" only for a 
and tough-to-justify "do not enter--further progress is hopeless" sign.


Seqfan Mailing list - http://list.seqfan.eu/


More information about the SeqFan mailing list