Loading ...
Sorry, an error occurred while loading the content.

Complexity

Expand Messages
  • SWagler@aol.com
    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
    • 0 Attachment
      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]
    • Phil Carmody
      ... 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
      • 0 Attachment
        --- 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
      • David Broadhurst <d.broadhurst@open.ac.u
        ... 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
        • 0 Attachment
          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
        • Phil Carmody
          ... 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
          • 0 Attachment
            --- "David Broadhurst <d.broadhurst@...>" <d.broadhurst@...> wrote:
            > 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!?
            Yahoo! Mail Plus - Powerful. Affordable. Sign up now.
            http://mailplus.yahoo.com
          • David Broadhurst <d.broadhurst@open.ac.u
            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
            • 0 Attachment
              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
            • Phil Carmody
              ... 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
              • 0 Attachment
                --- "David Broadhurst <d.broadhurst@...>" <d.broadhurst@...> wrote:
                > 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.
                And it would be a 300% proof too, for free!

                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
              Your message has been successfully submitted and would be delivered to recipients shortly.