[seqfan] Re: Use of Easy keyword

[Charles Greathouse]

> 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
Analyst/Programmer
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/