[seqfan] Re: Use of Easy keyword

[Alex M]

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