---

SWagler@... wrote:

> It apears to me that Mersenne primes are the simplest prime numbers because

> in binary notation they are just strings of ones.

Yes, they are Generalised Repunits, i.e. strings of 1s in a base other than

10. The recent record GRU by Andy Steward reported here by David Broadhurst

is such a beast - that's what 'GRU' stands for.

> How would you define

> complexity for other primes? By the number of changes in digits? By the

> number of different patterns of repeated digits? Is there a measure of

> complexity in numbers? If so, what would be the most complex prime? The most

> complex prime would be the least compressible wouldn't it?

I'm with Chaitin on this one, and think that the length of the smallest

string which uniquely, unambiguously, defines the number is a valid measure

of the complexity. You have to agree in advance what operations are

permitted, and after that it's just a case of building an expression that

represents your number. The concept of compressibilty is an abstract one

though. If you don't know that for example a number of the form a^b+b^a+1 is

actually ofthat form, you've got pretty much no way of working it out (apart

from brute force trial and error to see if you get a match). So to someone

who doesn't know the form it's incompressible, but to someone who does it's

compressible to only a dozen or so characters.

I think the current record holder for complexity is David Broadhurst's 3rd

factor in his record 3-carmichael. I can't see how it can be expressed in

much less than about 30000 digits.

The complexity of a number based on this descrition bears little relation to

the complexity of proving teh number prime. Some very simple expressions,

sucj as (2^p+1)/3 are nightmarish to prove, and some very

complicated expressions such as Product{i=0..100000}( prime(i)^r_i ) +1

where the r_i are a purely random stream of bits, would be trivial to prove.

Hence the concept isn't used much.

Phil

=====

The answer to life's mystery is simple and direct:

Sex and death. -- Ian 'Lemmy' Kilminster

__________________________________________________

Do you Yahoo!?

Yahoo! Mail Plus - Powerful. Affordable. Sign up now.

http://mailplus.yahoo.com