[seqfan] Re: easy and bref

franktaw at netscape.net franktaw at netscape.net
Fri Sep 30 19:07:25 CEST 2011

Well, consider A000043: Mersenne primes (p with 2^p-1 prime).

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 

Franklin T. Adams-Watters

-----Original Message-----
From: Charles Greathouse <charles.greathouse at case.edu>

> Interesting. My understanding of "hard" was just the opposite: that it
> should be used when it is known that calculating more terms is hard, 
but not
> when there might be an easier way to make the calculation, but none 
such is
> known.

I'm not sure when that would ever apply.  Would you give some examples?

Charles Greathouse
Case Western Reserve University

More information about the SeqFan mailing list