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

Re: A question

Expand Messages
  • 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 1 of 12 , Oct 1, 2011
      --- 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 2 of 12 , Oct 1, 2011
        --- 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 3 of 12 , Oct 1, 2011
          --- 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 4 of 12 , Oct 1, 2011
            >
            > 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 5 of 12 , Oct 1, 2011
              --- 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 6 of 12 , Oct 1, 2011
                --- 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 7 of 12 , Oct 1, 2011
                  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 8 of 12 , Oct 1, 2011
                    --- 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.