[seqfan] Re: easy and bref

[D. S. McNeil]

> Currently, we don't know any very efficient way of calculating these.
> (Better than primality testing for other numbers of the magnitude 2^p, but
> still very expensive as a function of p.) However, no one has proved that
> there isn't an efficient way to compute these. (The list might even be
> finite, in which case there is a very efficient calculation.)

How many "isn't an efficient way to compute these" proofs are there,
though?  We can't even show P != NP..

I can imagine sequences I'd give "hard" to for which someone could
find a generating function at which point it'd be easy.  Counting
graphs with certain properties, for example.  So anything which
_could_ have a generating function or formula can't have the keyword
hard?

I guess I don't see "hard" as a permanent property but as a
description of our state of knowledge.  Right now, A060843 -- the busy
beaver problem -- only has four known terms, and not for lack of
interest.  Why only four?  Because the sequence is hard in the
colloquial sense.  If someone comes up with a formula and we suddenly
had lots of terms, we'd simply remove "hard", like we remove "obsc"
after someone cleans up a sequence in bad shape.


Doug