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

Re: A question

Expand Messages
  • Dimiter Skordev
    ... No, I have not gone even to that depth.
    Message 1 of 12 , Sep 30, 2011
    • 0 Attachment
      --- In primenumbers@yahoogroups.com, "Mark" <mark.underwood@...> wrote:
      >
      >
      >
      >
      >
      >
      >
      >
      >
      >
      > --- In primenumbers@yahoogroups.com, "Dimiter Skordev" <skordev@> wrote:
      > >
      > > Let A be the least set of natural numbers with the following two properties:
      > > (i) the number 1 belongs to A;
      > > (ii) whenever x belongs to A, and y is a prime divisor of x+1, the product x*y also belongs to A.
      > > Let us call a prime number Euclid-style accessible if it is a divisor of some number belonging to A. Are there prime numbers that are not Euclid-style accessible, and if there are such ones, which is the least among them?
      > >
      >
      > I can't think of a reason why any prime would be excluded from being a factor of numbers in the set. I've only gone 5 'deep', and thus far 19 is the only prime < 29 that hasn't shown up yet. 11 and 17 were late to the party, but they eventually surfaced at depth 5. Have you gone further?
      >
      > Mark
      >

      No, I have not gone even to that depth.
    • mikeoakes2
      ... I agree. ... A is defined recursively so, rather than your depth (which I m not sure I understand) I favour a measure recursion_depth , which would
      Message 2 of 12 , Oct 1, 2011
      • 0 Attachment
        --- In primenumbers@yahoogroups.com, "Mark" <mark.underwood@...> wrote:
        >
        > --- In primenumbers@yahoogroups.com, "Dimiter Skordev" <skordev@> wrote:
        > >
        > > Let A be the least set of natural numbers with the following two properties:
        > > (i) the number 1 belongs to A;
        > > (ii) whenever x belongs to A, and y is a prime divisor of x+1, the product x*y also belongs to A.
        > > Let us call a prime number Euclid-style accessible if it is a divisor of some number belonging to A. Are there prime numbers that are not Euclid-style accessible, and if there are such ones, which is the least among them?
        > >
        >
        > I can't think of a reason why any prime would be excluded from being a factor of numbers in the set.

        I agree.

        > I've only gone 5 'deep', and thus far 19 is the only
        > prime < 29 that hasn't shown up yet. 11 and 17 were
        > late to the party, but they eventually surfaced at depth 5.

        A is defined recursively so, rather than your "depth" (which I'm not sure I understand) I favour a measure "recursion_depth", which would enumerate the elements of A in order of their appearance as follows:-
        x*y recursion_depth
        1 1
        1*2 2
        2*3 3
        6*7 4
        42*43 5
        1806*13 6
        1806*139 6
        etc.

        Going to recursion_depth=13, pari_GP take a couple of minutes to find that all primes < 271 are Euclid-style accessible.

        2621 elements have been inserted into A at this recursion_depth; but 86 others have not been inserted, since they exceed the size limit of 10^64 which I imposed on numbers so that they can be factorised in at most a few seconds.

        Mike
      • mikeoakes2
        ... Here are the results of running pari-GP on a single Intel core @ 1.8 GHz:- depth first_inaccessible card(A) time 1 2 1 0 secs 2
        Message 3 of 12 , Oct 1, 2011
        • 0 Attachment
          --- In primenumbers@yahoogroups.com, "mikeoakes2" <mikeoakes2@...> wrote:
          >
          > > > Let A be the least set of natural numbers with the following two properties:
          > > > (i) the number 1 belongs to A;
          > > > (ii) whenever x belongs to A, and y is a prime divisor of x+1, the product x*y also belongs to A.
          > > > Let us call a prime number Euclid-style accessible if it is a divisor of some number belonging to A. Are there prime numbers that are not Euclid-style accessible, and if there are such ones, which is the least among them?
          >
          > x*y recursion_depth
          > 1 1
          > 1*2 2
          > 2*3 3
          > 6*7 4
          > 42*43 5
          > 1806*13 6
          > 1806*139 6
          > etc.
          >
          > Going to recursion_depth=13, pari_GP take a couple of minutes
          > to find that all primes < 271 are Euclid-style accessible.
          >

          Here are the results of running pari-GP on a single Intel core @ 1.8 GHz:-

          depth first_inaccessible card(A) time
          1 2 1 0 secs
          2 3 2 0 secs
          3 5 3 0 secs
          4 5 4 0 secs
          5 5 5 0 secs
          6 5 7 0 secs
          7 11 11 0 secs
          8 11 20 0 secs
          9 19 44 0 secs
          10 19 96 0.05 secs
          11 47 261 0.28 secs
          12 103 808 15.71 secs
          13 271 2621 161.9 secs
          14 827 8151 788.2 secs
          15 1913 23884 3779.3 secs

          At depth 12, 13, 14, 15, the number of elements of A > 10^64 (and so left unfactorised) were 4, 86, 780, 3894, respectively.

          Mike
        • Dimiter Skordev
          ... After the work Mark and Mike did, it really seems that any prime number is Euclid-style accessible. Unfortunately, I have no idea how this could be proved.
          Message 4 of 12 , Oct 1, 2011
          • 0 Attachment
            --- In primenumbers@yahoogroups.com, "mikeoakes2" <mikeoakes2@...> wrote:
            > > I can't think of a reason why any prime would be excluded from being a factor of numbers in the set.
            >
            > I agree.
            After the work Mark and Mike did, it really seems that any prime number is Euclid-style accessible. Unfortunately, I have no idea how this could be proved.

            > > I've only gone 5 'deep', and thus far 19 is the only
            > > prime < 29 that hasn't shown up yet. 11 and 17 were
            > > late to the party, but they eventually surfaced at depth 5.
            >
            > A is defined recursively so, rather than your "depth" (which I'm not sure I understand) I favour a measure "recursion_depth", which would enumerate the elements of A in order of their appearance as follows:-
            > x*y recursion_depth
            > 1 1
            > 1*2 2
            > 2*3 3
            > 6*7 4
            > 42*43 5
            > 1806*13 6
            > 1806*139 6
            > etc.
            I also would understand the notion of depth in this way. When I wrote "No, I have not gone even to that depth", I actually meant I did not go to a depth at which, for instance, 11 and 17 are already shown to be Euclid-style accessible.

            In addition to this notion of accessibility, maybe a stronger one also deserves some attention, namely the one we get when we replace "y is a prime divisor of x+1" with "y is the least prime divisor of x+1" in the definition of the set A.

            Dimiter
          • mikeoakes2
            ... In this case, of course, the tree degenerates into a list, and so is more straightforward to program; and we have simply card(A)=recursion_depth. Defining
            Message 5 of 12 , Oct 1, 2011
            • 0 Attachment
              --- In primenumbers@yahoogroups.com, "Dimiter Skordev" <skordev@...> wrote:
              >
              > In addition to this notion of accessibility, maybe a stronger one also deserves some attention, namely the one we get when we replace "y is a prime divisor of x+1" with "y is the least prime divisor of x+1" in the definition of the set A.
              >

              In this case, of course, the tree degenerates into a list, and so is more straightforward to program; and we have simply
              card(A)=recursion_depth.

              Defining the function s(m), for integer m, to be its smallest prime factor, your set A is the set {u[n]}, with the (monotonically increasing) sequence u[] being defined by:
              u[1] = 1
              u[n] = u[n-1] * s(u[n-1]+1), n >= 2

              As with the earlier definition, I can see no reason why all primes should not be accessible.

              I removed any restriction on size of integer to (attempt to) factorise.

              For 14 <= recursion_depth <= 28, the first inaccessible prime is 19.

              I have now run into a brick wall:
              u[28]=326408399720836161014262419152749\
              231088487789442706259494316079679210912\
              54869713984092316692981590
              and pari-Gp is struggling to factorise the 98-digit integer (u[28]+1).

              ecm anyone?

              Mike
            • Bernardo Boncompagni
              ... PRP27 = 643679794963466223081509857 PRP28 = 2496022367830647867616317307 PRP44 = 20316223246552213835636779619145529457704309 [Non-text portions of this
              Message 6 of 12 , Oct 1, 2011
              • 0 Attachment
                >
                > I have now run into a brick wall:
                > u[28]=326408399720836161014262419152749\
                > 231088487789442706259494316079679210912\
                > 54869713984092316692981590
                > and pari-Gp is struggling to factorise the 98-digit integer (u[28]+1).
                >

                PRP27 = 643679794963466223081509857
                PRP28 = 2496022367830647867616317307
                PRP44 = 20316223246552213835636779619145529457704309


                [Non-text portions of this message have been removed]
              • mikeoakes2
                ... Thanks, Bernardo. Now do you feel like factorising the 98+27=125-digit integer (u[29]+1) ... Mike
                Message 7 of 12 , Oct 1, 2011
                • 0 Attachment
                  --- In primenumbers@yahoogroups.com, Bernardo Boncompagni <RedGolpe@...> wrote:
                  >
                  > >
                  > > I have now run into a brick wall:
                  > > u[28]=326408399720836161014262419152749\
                  > > 231088487789442706259494316079679210912\
                  > > 54869713984092316692981590
                  > > and pari-Gp is struggling to factorise the 98-digit integer (u[28]+1).
                  > >
                  >
                  > PRP27 = 643679794963466223081509857
                  > PRP28 = 2496022367830647867616317307
                  > PRP44 = 20316223246552213835636779619145529457704309
                  >

                  Thanks, Bernardo.

                  Now do you feel like factorising the 98+27=125-digit integer (u[29]+1)
                  :-)

                  Mike
                • elevensmooth
                  ... Somebody has been here before, carried it up to 256 digits, and saved it all in the factordb http://factorization.ath.cx/index.php?id=1100000000024656542
                  Message 8 of 12 , Oct 1, 2011
                  • 0 Attachment
                    --- In primenumbers@yahoogroups.com, "mikeoakes2" <mikeoakes2@...> wrote:

                    > Now do you feel like factorising the 98+27=125-digit integer (u[29]+1)
                    > :-)

                    Somebody has been here before, carried it up to 256 digits, and saved it all in the factordb

                    http://factorization.ath.cx/index.php?id=1100000000024656542
                    http://factorization.ath.cx/index.php?id=1100000000024656619
                    http://factorization.ath.cx/index.php?id=1100000000024656629
                    http://factorization.ath.cx/index.php?id=1100000000024361410
                    http://factorization.ath.cx/index.php?id=1100000000084404073
                    http://factorization.ath.cx/index.php?id=1100000000084404103
                    http://factorization.ath.cx/index.php?id=1100000000084404112
                    http://factorization.ath.cx/index.php?id=1100000000084404156
                    http://factorization.ath.cx/index.php?id=1100000000084404156
                    http://factorization.ath.cx/index.php?id=1100000000084405578
                    http://factorization.ath.cx/index.php?id=1100000000084405618
                    http://factorization.ath.cx/index.php?id=1100000000084405692
                    http://factorization.ath.cx/index.php?id=1100000000084405749
                    http://factorization.ath.cx/index.php?id=1100000000084405824
                    http://factorization.ath.cx/index.php?id=1100000000084405856
                    http://factorization.ath.cx/index.php?id=1100000000084406023
                    http://factorization.ath.cx/index.php?id=1100000000038159060
                    http://factorization.ath.cx/index.php?id=1100000000201891404
                    http://factorization.ath.cx/index.php?id=1100000000201895169
                    http://factorization.ath.cx/index.php?id=1100000000201898222
                    http://factorization.ath.cx/index.php?id=1100000000215895311
                  • Jens Kruse Andersen
                    ... We only need the smallest factor which is trivially found by trial factoring to be 103. The sequence of smallest prime factors is the Euclid-Mullin
                    Message 9 of 12 , Oct 1, 2011
                    • 0 Attachment
                      Mike wrote:
                      > Now do you feel like factorising the 98+27=125-digit integer (u[29]+1)

                      We only need the smallest factor which is trivially found by trial
                      factoring to be 103.
                      The sequence of smallest prime factors is the Euclid-Mullin sequence.
                      See for example http://oeis.org/A000945 and
                      http://en.wikipedia.org/wiki/Euclid%E2%80%93Mullin_sequence

                      The smallest missing prime in the 47 known terms is 31.

                      --
                      Jens Kruse Andersen
                    • djbroadhurst
                      ... It is notable that only one known factorization is incomplete: http://www.rieselprime.de/Others/EuclidMullin.htm and in that case it suffices to show that
                      Message 10 of 12 , Oct 1, 2011
                      • 0 Attachment
                        --- In primenumbers@yahoogroups.com,
                        "Jens Kruse Andersen" <jens.k.a@...> wrote:

                        > The sequence of smallest prime factors is the Euclid-Mullin sequence.
                        > See for example http://oeis.org/A000945 and
                        > http://en.wikipedia.org/wiki/Euclid%E2%80%93Mullin_sequence

                        It is notable that only one known factorization is incomplete:
                        http://www.rieselprime.de/Others/EuclidMullin.htm
                        and in that case it suffices to show that the composite
                        co-factor has no prime divisor less than 127.

                        David
                      Your message has been successfully submitted and would be delivered to recipients shortly.