## Complexity

Expand Messages
• It apears to me that Mersenne primes are the simplest prime numbers because in binary notation they are just strings of ones. How would you define complexity
Message 1 of 6 , Dec 29, 2002
It apears to me that Mersenne primes are the simplest prime numbers because
in binary notation they are just strings of ones. 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?

Steve Wagler

[Non-text portions of this message have been removed]
• ... 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
Message 2 of 6 , Dec 29, 2002
--- 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!?
http://mailplus.yahoo.com
• ... The announcement compressed it to less than 5000 digits: http://listserv.nodak.edu/scripts/wa.exe?A2=ind0212&L=nmbrthry&P=R2
Message 3 of 6 , Dec 30, 2002
Phil:
> 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 announcement compressed it to less
than 5000 digits:
http://listserv.nodak.edu/scripts/wa.exe?A2=ind0212&L=nmbrthry&P=R2
• ... Ah yes. The short ones are closer to full size, minus the primorial, the double sized one is a simple derivative of the short ones. And of course you re
Message 4 of 6 , Dec 30, 2002
> Phil:
> > 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 announcement compressed it to less
> than 5000 digits:
> http://listserv.nodak.edu/scripts/wa.exe?A2=ind0212&L=nmbrthry&P=R2

Ah yes. The short ones are closer to full size, minus the primorial, the
double sized one is a simple derivative of the short ones. And of course
you're not carrying the big modulus from your CRT around with you after
you've found the result. I wonder what time of day I posted my message...

Hmmm, even my random prime subset-orial can be compressed down to just the
bit-vector of the i's. It's hard programattically to inject entropy into
these things (i.e. impossible).

Didn't someone create a proth-proof chain that consisted of
P_{i+1} = c_i.P_{i} +/- 1
for small c_i, and all P_i prime? (just like ECPP, but with out the elliptic
curves!)
That I think would be pretty close to explicit number's size == entropy.
(the entropy would be that of an ordered list of c_i, and maybe a extra bit
for the +/- if there was a choice.
However, there must be /no/ simple rule to generate the c_i, such as
c_i is the smallest number which makes the expression prime
or
c_i is the largest number < P_i which makes the expresion prime
otherwise your entropy collapses to almost nothing again.

Phil

=====
The answer to life's mystery is simple and direct:
Sex and death. -- Ian 'Lemmy' Kilminster

__________________________________________________
Do you Yahoo!?
http://mailplus.yahoo.com
• One way to get a provable prime with large entropy is to iterate P_{n+1}=P_{n}*Q_{n}+/-1 where P_{n} is prime and Q_{n} = O(P_{n}^2) is random. Since OpenPFGW
Message 5 of 6 , Dec 30, 2002
One way to get a provable prime with
large entropy is to iterate
P_{n+1}=P_{n}*Q_{n}+/-1
where P_{n} is prime and Q_{n} = O(P_{n}^2) is random.
Since OpenPFGW ABC format now accepts long lines,
such a perverse exercise require only cycles
and (for me) cut'n'paste or (for you) Perl.
When Chris Caldwell's new system is in place
it might be fun to do this?
David
• ... There are easier ways to get maximum entropy and yet remain provable. Grab many vast primes from the middles of ECPP proofs, preferably of random
Message 6 of 6 , Dec 30, 2002
> One way to get a provable prime with
> large entropy is to iterate
> P_{n+1}=P_{n}*Q_{n}+/-1
> where P_{n} is prime and Q_{n} = O(P_{n}^2) is random.
> Since OpenPFGW ABC format now accepts long lines,
> such a perverse exercise require only cycles
> and (for me) cut'n'paste or (for you) Perl.
> When Chris Caldwell's new system is in place
> it might be fun to do this?

There are easier ways to get maximum entropy and yet remain provable.
Grab many vast primes from the middles of ECPP proofs, preferably of
'random' numbers, and accumulate them. The number of subsets of a
large set is immense, some subset will yield a prime.