[seqfan] Re: Use of Easy keyword

Charles Greathouse charles.greathouse at case.edu
Tue Dec 6 04:12:00 CET 2011

> I think "easy" would make sense applied if, say... A(n) can be computed in
> O(n^k) for some k. That is, polynomial in the number, not the number of
> bits (as things are often defined in comp sci).

That would make the majority of sequences in the OEIS "easy", though.
A narrower definition is probably more useful.

Also I think that sequences can be easy even if their terms are long.
For example, 10^(2^n) just requires listing the appropriate number of
0s after a 1.  The number of zeros may be large but it's hard to
imagine calling it hard on that account alone.  For this reason I
usually think of easy in terms of difficulty of listing a certain
number of bytes of a sequence: I can give 100 MB of that sequence
quite easily, faster than my hard drive could store it in fact.  So
for me that makes it easy.

Charles Greathouse
Case Western Reserve University

On Mon, Dec 5, 2011 at 10:03 PM, Alex M <timeroot.alex at gmail.com> wrote:
> I think "easy" would make sense applied if, say... A(n) can be computed in
> O(n^k) for some k. That is, polynomial in the number, not the number of
> bits (as things are often defined in comp sci). Factorization of n *can* be
> done in polynomial time of n. Even perhaps the slowest algorithm, trial
> division, operates in O(sqrt(n)). Using more advanced methods this is
> actually reduced to sub-polynomial in n. By this definition, some examples
> of what would be easy, what wouldn't be:
> Easy
> -Number of divisors-A000005 (as stated above, O(sqrt(n)), and easily
> subpolynomial)
> -Sum of divisors-A000023 (a maximum of log(n) divisors can be added in
> polynomial time)
> -Factorial-A000142 (n multiplications of log(n)-digit numbers; O(n
> log(n)^2))
> -Digits of pi-A0000796 (O(n log(n)^2 log(log(n)) with Salamin-Brent
> algorithm)
> -Fibonacci sequence-A000045 (adding n O(n)-digit numbers -> O(n^2) time)
> Borderline:
> -Prime Fibonacci numbers-A005478 (F(k) can be checked for primality in
> O(k^6) with AKS; their density is ~ 1/ln(phi^k) = C/k. Roughly k will have
> to be checked for the next prime, giving O(k^7). This is a high exponent,
> and so should perhaps not be easy.)
> Not necessarily easy (unless you get some trick, perhaps)
> -Mersenne exponents-A000043 (Successful exponents have density of log(n),
> so you need to check primes up to O(2^n), giving O(2^n / n) - greatly
> superpolynomial.)
> -Conway's Look-and-say sequence-A005150 (dealing with O(1.3035^n)-digit
> numbers requires the same amount of time. This may some counter-intuitive,
> but look at a(1000) - that would be horrendous to compute, compared with
> the 1000th digit of pi.)
> I'm hoping that some kind of exact criterion could be worked out, then;
> O(n^4) or faster, perhaps?
> ~6 out of 5 statisticians say that the
> number of statistics that either make
> no sense or use ridiculous timescales
> at all has dropped over 164% in the
> last 5.62474396842 years.
> On Mon, Dec 5, 2011 at 4:53 PM, David Wilson <davidwwilson at comcast.net>wrote:
>> I find the "hard" keyword useful. It more or less says that it would be a
>> challenge to compute many
>> more terms than are already in the OEIS.
>> I find "easy" less useful. It has many potential meanings: easy to
>> understand, easy to write (a
>> possibly inefficient) program, easy to obtain small elements, easy to
>> obtain large elements, etc.
>> From a conceptual standpoint, simple functions of the n's prime
>> factorization are easy. Also, given
>> that OEIS b-files rarely exceed 10^4 elements, it would be easy to extend
>> the OEIS database for
>> these functions. For example, A000010(n) = phi(n) is a simple function of
>> the prime factorization,
>> and the b-file includes a whopping 10^5 elements, still, a straightforward
>> computer program
>> could churn out values of phi(n) up to 10^10 almost continuously.
>> Conceptually, A000142(n) = n! has an extremely simple definition that does
>> not involve factorization.
>> However, in computing n!, one runs into problems far sooner than with most
>> simple functions of
>> the prime factorization of n. Still, it would be quite easy to extend the
>> OEIS database, which only
>> goes up to a(100).
>> The only real use I could see for "easy" would be as an invitation to
>> extend the sequence.  But we
>> already have "more" for that, and there are many "easy" sequences that
>> don't bear extension
>> because they are reasonably complete. I would move that the "easy" keyword
>> be deprecated
>> on the grounds of ill-definition and uncertain utility.
>> If there is any value to the easy keyword, I would say that "easy" is an
>> invitation for the OEIS to
>> support programmatic generation of sequences. If the OEIS supported, say,
>> JavaScript or PHP
>> programs that could be run client-side to generate sequence values, then
>> numerous bulky b-files
>> could be dispensed with in favor of short programs. Just saying.
>> On 12/3/2011 12:03 PM, Ed Jeffery wrote:
>>> Seqfans,
>>> I keep running across sequences in OEIS with simple
>>> descriptions or definitions but which, in one way
>>> or another, depend on factorization of n. The problem
>>> of factorization is still hard (or intractable) for
>>> arbitrarily large n, but many of these sequences have
>>> been given the EASY keyword which seems to be a bit
>>> misleading. Should this keyword be dropped for such
>>> sequences?
>>> Ed Jeffery
>>> ______________________________**_________________
>>> Seqfan Mailing list - http://list.seqfan.eu/
>> ______________________________**_________________
>> Seqfan Mailing list - http://list.seqfan.eu/
> _______________________________________________
> Seqfan Mailing list - http://list.seqfan.eu/

More information about the SeqFan mailing list