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

primes of the form (x+1)^p-x^p

Expand Messages
  • Maximilian Hasler
    Dear prime number fans, is there anything available about possible finiteness of primes of the form (x+1)^p-x^p ? Specifically, some curios reasons led me to
    Message 1 of 22 , Apr 5, 2009
    • 0 Attachment
      Dear prime number fans,
      is there anything available about possible finiteness of primes of the form (x+1)^p-x^p ?
      Specifically, some curios reasons led me to look at 7^p-6^p.
      It seems that 1399 and 2027 are the largest known p for which this is prime (Sloane's A062573). According to my calculations, the next such p must be larger than 17900.
      Also, 2027 is (so far) the only such p of the form n^2+2, n>1.
      Are there heuristics in favour of conjecturing finiteness of such primes?
      Thanks for any hints,
      Maximilian
    • Phil Carmody
      ... They are cyclotomic, so have the same kind of rules surrounding admissible factors as Mersennes. (Which are actually quite non-trivial, and the most
      Message 2 of 22 , Apr 5, 2009
      • 0 Attachment
        --- On Mon, 4/6/09, Maximilian Hasler <maximilian.hasler@...> wrote:
        > Dear prime number fans,
        > is there anything available about possible finiteness of
        > primes of the form (x+1)^p-x^p ?
        > Specifically, some curios reasons led me to look at
        > 7^p-6^p.
        > It seems that 1399 and 2027 are the largest known p for
        > which this is prime (Sloane's A062573). According to my
        > calculations, the next such p must be larger than 17900.
        > Also, 2027 is (so far) the only such p of the form n^2+2,
        > n>1.
        > Are there heuristics in favour of conjecturing finiteness
        > of such primes?
        > Thanks for any hints,

        They are cyclotomic, so have the same kind of rules surrounding admissible factors as Mersennes. (Which are actually quite non-trivial, and the most advanced analysis can not be considered much more than dumb application of the simplest possible rules due to having no reason to think otherwise.) They grow faster, so there's a log ratio between them, but that's just a constant factor.

        Phil
      • j_chrtn
        ... Hi Maximilian, p=1399 and 2027 are not the current records for base 7. My personal records are p=69371 and p=86689 for 7^p-6^p. And the largest PRP I have
        Message 3 of 22 , Apr 6, 2009
        • 0 Attachment
          --- In primenumbers@yahoogroups.com, "Maximilian Hasler" <maximilian.hasler@...> wrote:
          >
          > Dear prime number fans,
          > is there anything available about possible finiteness of primes of the form (x+1)^p-x^p ?
          > Specifically, some curios reasons led me to look at 7^p-6^p.
          > It seems that 1399 and 2027 are the largest known p for which this is prime (Sloane's A062573). According to my calculations, the next such p must be larger than 17900.
          > Also, 2027 is (so far) the only such p of the form n^2+2, n>1.
          >

          Hi Maximilian,

          p=1399 and 2027 are not the current records for base 7. My personal
          records are p=69371 and p=86689 for 7^p-6^p. And the largest PRP I have found of this form is currently 8^336419-7^336419.

          Take a look at Henry Lifchitz's PRP records page
          www.primenumbers.net/prptop/prptop.php for much more primes/PRP of this form.

          I believe that (1) for any integer n >= 1, there are infinitely many
          primes p such that (n+1)^p-n^p is prime and that (2) for any prime p,
          there are infinitely many integers n such that (n+1)^p-n^p is prime as
          well.
          But, unfortunately, proving (or disproving) (1) and (2) is far from being trivial I'm afraid.

          And now, just for fun, a litle challenge for you: find a prime p such that 138^p-137^p is prime or PRP.
          Good luck ;-)

          JL
        • Mike Oakes
          ... I have done quite a lot of work on this form, initially summarised in my May 2001 post to the NMBRTHRY list:
          Message 4 of 22 , Apr 6, 2009
          • 0 Attachment
            --- In primenumbers@yahoogroups.com, "j_chrtn" <j_chrtn@...> wrote:
            >
            > --- In primenumbers@yahoogroups.com, "Maximilian Hasler" <maximilian.hasler@> wrote:
            > >
            > > Dear prime number fans,
            > > is there anything available about possible finiteness of primes of the form (x+1)^p-x^p ?
            > > Specifically, some curios reasons led me to look at 7^p-6^p.
            > > It seems that 1399 and 2027 are the largest known p for which this is prime (Sloane's A062573). According to my calculations, the next such p must be larger than 17900.
            > > Also, 2027 is (so far) the only such p of the form n^2+2, n>1.
            > >
            >
            > Hi Maximilian,
            >
            > p=1399 and 2027 are not the current records for base 7. My personal
            > records are p=69371 and p=86689 for 7^p-6^p. And the largest PRP I have found of this form is currently 8^336419-7^336419.
            >
            > Take a look at Henry Lifchitz's PRP records page
            > www.primenumbers.net/prptop/prptop.php for much more primes/PRP of this form.
            >
            > I believe that (1) for any integer n >= 1, there are infinitely many
            > primes p such that (n+1)^p-n^p is prime and that (2) for any prime p,
            > there are infinitely many integers n such that (n+1)^p-n^p is prime as
            > well.
            > But, unfortunately, proving (or disproving) (1) and (2) is far from being trivial I'm afraid.
            >
            > And now, just for fun, a litle challenge for you: find a prime p such that 138^p-137^p is prime or PRP.
            > Good luck ;-)
            >
            > JL

            I have done quite a lot of work on this form, initially summarised in my May 2001 post to the NMBRTHRY list:
            http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0105&L=NMBRTHRY&P=R359&I=-3

            Since then, Jean-Louis in particular has devoted seemingly enormous numbers of cpu cycles to extending the list of known PRPs.

            My own record (and favourite PRP of all, being so "Mersenne-like") is
            3^336353-2^336353
            at 160482 digits.

            -Mike Oakes
            [PS I replied on this website about 8 hours ago, but the message seems to have vanished into the ether.]
          • Maximilian Hasler
            Thanks for all replies and useful information. Indeed I would have looked up Lifchitz database, but I cannot access it these days (or months already...). (It
            Message 5 of 22 , Apr 6, 2009
            • 0 Attachment
              Thanks for all replies and useful information.

              Indeed I would have looked up Lifchitz' database, but I cannot access it these days (or months already...).

              (It seems I'm not the only one to have this problem with primenumbers.net, but unfortunately I have the same problem with other web sites which do work for "everybody"(?) else...)

              PS: Since I can't access Henri's list, could you tell me if you have another p of the form n^2+2 apart from n=45 for x=6 ?
              (BTW, if your search is exhausive up to a certain limit, you might want to update the mentioned OEIS sequence.)

              Thanks again,
              Maximilian

              --- In primenumbers@yahoogroups.com, "Mike Oakes" wrote:
              > --- In primenumbers@yahoogroups.com, "j_chrtn" <j_chrtn@> wrote:
              > >(...)
              > > p=1399 and 2027 are not the current records for base 7. My personal
              > > records are p=69371 and p=86689 for 7^p-6^p. And the largest PRP I have found of this form is currently 8^336419-7^336419.
              > >
              > > Take a look at Henry Lifchitz's PRP records page
              > > www.primenumbers.net/prptop/prptop.php for much more primes/PRP of this form.
              > >
              > > I believe that (1) for any integer n >= 1, there are infinitely many
              > > primes p such that (n+1)^p-n^p is prime and that (2) for any prime p,
              > > there are infinitely many integers n such that (n+1)^p-n^p is prime as
              > > well.
              > > But, unfortunately, proving (or disproving) (1) and (2) is far from being trivial I'm afraid.
              > >
              > > And now, just for fun, a litle challenge for you: find a prime p such that 138^p-137^p is prime or PRP.
              > > Good luck ;-)
              > >
              > > JL
              >
              > I have done quite a lot of work on this form, initially summarised in my May 2001 post to the NMBRTHRY list:
              > http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0105&L=NMBRTHRY&P=R359&I=-3
              >
              > Since then, Jean-Louis in particular has devoted seemingly enormous numbers of cpu cycles to extending the list of known PRPs.
              (...)
            • Mark Underwood
              ... Very cool. To notch it up on the coolness factor one could express the prime exponent 336353 as 3*(2^(2^3+3^2) - 3^(3^2) + 3^(2*3)) - 1 ... On a not too
              Message 6 of 22 , Apr 7, 2009
              • 0 Attachment
                --- In primenumbers@yahoogroups.com, "Mike Oakes" <mikeoakes2@...> wrote:

                >
                > My own record (and favourite PRP of all, being so "Mersenne-like") is
                > 3^336353-2^336353
                > at 160482 digits.
                >

                Very cool. To notch it up on the coolness factor one could express
                the prime exponent 336353 as

                3*(2^(2^3+3^2) - 3^(3^2) + 3^(2*3)) - 1

                :)

                On a not too related note, here's something that may be of interest.

                Consider primes generated by 2^m + 3^n and 2^n + 3^m , with m < n.

                I've looked at n from 1 to 1000, and there is always at least
                one m < n such that 2^m + 3^n OR 2^n + 3^m is prime. But it comes
                close to failing on many occasions. (Why am I always attracted to
                this kind of exploration?)

                Here are the outcomes which came close to failing, where there were
                3 or fewer m that resulted in a prime.

                Format: (n, number of m less than n such that 2^m+3^n or 2^n+3^m is prime)

                (1,1) (2,2) (3,2) (4,3) (5,3) (6,3) (9,3) (11,3) (25,2)
                (33,3) (34,3) (54,1) (69,2) (70,3) (97,3) (103,3) (115,3)
                (117,2) (118,3) (120,3) (121,3) (122,2) (129,1) (131,2)
                (135,1) (139,3) (150,3) (157,2) (161,3) (166,3) (170,1)
                (175,1) (185,1) (190,3) (194,3) (200,2) (201,2) (206,3)
                (211,3) (213,3) (218,3) (236,2) (240,2) (242,3) (266,3)
                (274,1) (280,1) (285,3) (293,3) (294,3) (321,2) (322,3)
                (324,3) (335,1) (338,3) (348,2) (351,3) (376,2) (383,3)
                (397,3) (398,3) (405,3) (407,2) (415,2) (420,3) (422,3)
                (435,3) (445,2) (455,2) (459,2) (460,1) (473,3) (489,1)
                (493,3) (506,2) (507,3) (543,2) (547,1) (549,2) (555,3)
                (562,2) (565,3) (566,3) (567,2) (570,2) (572,3) (580,2)
                (586,3) (591,2) (603,3) (609,2) (611,1) (614,1) (627,3)
                (641,3) (651,3) (685,2) (700,3) (711,3) (717,1) (721,3)
                (729,1) (736,3) (745,3) (746,1) (747,3) (751,3) (770,3)
                (775,3) (798,2) (811,3) (813,1) (819,1) (821,1) (826,1)
                (830,3) (835,3) (845,3) (851,1) (859,3) (869,3) (879,3)
                (884,3) (887,2) (899,3) (901,3) (911,3) (913,2) (943,2)
                (951,3) (958,3) (966,1) (970,3)

                The rate of close calls seem to decrease, but slowly. But what
                surprised me initially was this: I expected that composite n would be
                more represented than they are for close calls.


                For instance let n have a factor of 3. Immediately one third of the
                m's less than n are disqualified from generating a prime, because if
                m contains a factor of 3 then both 2^n+3^m and 2^m+3^n will contain
                a factor of 2^3+3^3 = 35.

                But as it is, of the 133 n's listed above, only 45 have a factor of
                3. About what one would expect if having a factor of 3 made no
                difference. What about n with factors of 5? 33 of the 133 n's have a
                factor of 5, so the composite effect might be having some effect
                there, not sure.


                Mark
              • Maximilian Hasler
                ... Very cool. To notch it up on the coolness factor one could submit this sequence to OEIS. Modulo correcting less than to not exceeding (or specifying
                Message 7 of 22 , Apr 7, 2009
                • 0 Attachment
                  > Format: (n, number of m less than n such that 2^m+3^n or 2^n+3^m is prime)
                  >
                  > (1,1) (2,2) (3,2) (4,3) (5,3) (6,3) (9,3) (11,3) (25,2)
                  > (33,3) (34,3) (54,1) (69,2) (70,3) (97,3) (103,3) (115,3)
                  > (...)
                  > (951,3) (958,3) (966,1) (970,3)

                  Very cool. To notch it up on the coolness factor one could submit this sequence to OEIS.

                  Modulo correcting "less than" to "not exceeding" (or specifying that m may be zero, or correcting a(1)=0 and others in the above).

                  Actually there are at least 6 sequences:
                  MU = { n | MU1(n)<=3 } (or why not <= 2 or even <= 1 ?)
                  MU1(n) = # { m <= n | 2^n+3^m or 2^m+3^n is prime } (or "<" ?)
                  MU2(n) = min { m | 2^n+3^m or 2^m+3^n is prime }
                  MU3(n) = max { m <= n | 2^n+3^m or 2^m+3^n is prime } (or "<" ?)
                  MU4(n) = min { m | 2^n+3^m is prime }
                  MU5(n) = min { m | 2^m+3^n is prime }


                  I checked that they are not in OEIS except for MU5 :

                  A123359 Least m such that 3^n+2^m is prime.

                  But maybe better double-check...

                  Maximilian
                • Mark Underwood
                  ... Thank you Maximilian, The OESIS thing would only be appealing to me if the minimum m that caused 2^n+3^m or 2^m+3^n to be prime was always found to be less
                  Message 8 of 22 , Apr 9, 2009
                  • 0 Attachment
                    --- In primenumbers@yahoogroups.com, "Maximilian Hasler" <maximilian.hasler@...> wrote:
                    >
                    > > Format: (n, number of m less than n such that 2^m+3^n or 2^n+3^m is prime)
                    > >
                    > > (1,1) (2,2) (3,2) (4,3) (5,3) (6,3) (9,3) (11,3) (25,2)
                    > > (33,3) (34,3) (54,1) (69,2) (70,3) (97,3) (103,3) (115,3)
                    > > (...)
                    > > (951,3) (958,3) (966,1) (970,3)
                    >
                    > Very cool. To notch it up on the coolness factor one could submit this sequence to OEIS.
                    >
                    > Modulo correcting "less than" to "not exceeding" (or specifying that m may be zero, or correcting a(1)=0 and others in the above).
                    >
                    > Actually there are at least 6 sequences:
                    > MU = { n | MU1(n)<=3 } (or why not <= 2 or even <= 1 ?)
                    > MU1(n) = # { m <= n | 2^n+3^m or 2^m+3^n is prime } (or "<" ?)
                    > MU2(n) = min { m | 2^n+3^m or 2^m+3^n is prime }
                    > MU3(n) = max { m <= n | 2^n+3^m or 2^m+3^n is prime } (or "<" ?)
                    > MU4(n) = min { m | 2^n+3^m is prime }
                    > MU5(n) = min { m | 2^m+3^n is prime }
                    >
                    >
                    > I checked that they are not in OEIS except for MU5 :
                    >
                    > A123359 Least m such that 3^n+2^m is prime.
                    >
                    > But maybe better double-check...
                    >
                    > Maximilian
                    >

                    Thank you Maximilian,

                    The OESIS thing would only be appealing to me if the minimum m that caused

                    2^n+3^m or 2^m+3^n to be prime was always found to be less than n for all n.

                    Then I might consider adding the sequence

                    1,54,129,135,170,175,185,274,280,335,460,489,547,611, 614,...

                    These are the n such that only one m less than n makes 2^n+3^m or 2^m+3^n prime.

                    So far, so good. Up to n=1420 there is at least one m < n that that makes a prime.

                    Mark
                  • David Broadhurst
                    ... Your conjecture first fails for n = 1679. Best regards David
                    Message 9 of 22 , Apr 9, 2009
                    • 0 Attachment
                      --- In primenumbers@yahoogroups.com,
                      "Mark Underwood" <mark.underwood@...> wrote:

                      > m less than n makes 2^n+3^m or 2^m+3^n prime

                      Your conjecture first fails for n = 1679.

                      Best regards

                      David
                    • David Broadhurst
                      Mark Underwood s most interesting sequence for the OEIS might be the cases for which his conjecture fails, namely Numbers n such that there are no primes of
                      Message 10 of 22 , Apr 9, 2009
                      • 0 Attachment
                        Mark Underwood's most interesting sequence for the OEIS
                        might be the cases for which his conjecture fails, namely

                        "Numbers n such that there are no primes of the forms
                        2^m+3^n or 2^n+3^m for m < n"

                        This sequence begins with

                        n = 1679, 1743 ...

                        but Mark would need two more entries to satisfy Neil Sloane.
                        PFGW records that there are no more with n < 2500.
                        Heuristics suggest that more exist, beyond that paltry limit.

                        David
                      • Mark Underwood
                        ... Thank you David. At least I go into Good Friday with one less potential illusion. :) And that 1679,1743, .. sequence, it is not only hard computing, but
                        Message 11 of 22 , Apr 9, 2009
                        • 0 Attachment
                          --- In primenumbers@yahoogroups.com, "David Broadhurst" <d.broadhurst@...> wrote:
                          >
                          > Mark Underwood's most interesting sequence for the OEIS
                          > might be the cases for which his conjecture fails, namely
                          >
                          > "Numbers n such that there are no primes of the forms
                          > 2^m+3^n or 2^n+3^m for m < n"
                          >
                          > This sequence begins with
                          >
                          > n = 1679, 1743 ...
                          >
                          > but Mark would need two more entries to satisfy Neil Sloane.
                          > PFGW records that there are no more with n < 2500.
                          > Heuristics suggest that more exist, beyond that paltry limit.
                          >

                          Thank you David. At least I go into Good Friday with one less potential illusion. :)
                          And that 1679,1743, .. sequence, it is not only hard computing, but psychologically
                          difficult as well, to find a *lack* of primes. Actually finding primes (especially unique
                          ones) is so much more fun!

                          On that note, some 2-3 prime time fun, where a,b are 2-3 numbers and

                          both 2^a + 3^b and 3^b + 2^a are prime.


                          2^1 + 3^1
                          2^1 + 3^2 and 2^2+3^1
                          2^2 + 3^2
                          2^3 + 3^1 and 2^1 + 3^3
                          2^3 + 3^2 and 2^2 + 3^3
                          2^4 + 3^1 and 2^1 + 3^4
                          2^4 + 3^4
                          2^6 + 3^2 and 2^2 + 3^6
                          2^8 + 3^3 and 2^3 + 3^8
                          2^8 + 3^4 and 2^4 + 3^8
                          2^9 + 3^2 and 2^2 + 3^9
                          2^9 + 3^4 and 2^4 + 3^9
                          2^12 + 3^4 and 2^4 + 3^12.


                          Mark
                        • David Broadhurst
                          ... Des goûts et des couleurs, on ne discute pas. [About tastes and colours, one does not argue.] However, I remark that my sequence of blanks is *easier*
                          Message 12 of 22 , Apr 9, 2009
                          • 0 Attachment
                            --- In primenumbers@yahoogroups.com,
                            "Mark Underwood" <mark.underwood@...> wrote:

                            > that 1679,1743, .. sequence, it is not only hard computing,
                            > but psychologically difficult as well,
                            > to find a *lack* of primes.
                            > Actually finding primes (especially unique ones)
                            > is so much more fun!

                            "Des goûts et des couleurs, on ne discute pas."
                            [About tastes and colours, one does not argue.]

                            However, I remark that my sequence of blanks is *easier*
                            to generate, up to a given size of n, than is your
                            preferred sequence of unique hits, since for the former
                            we may "step to next n" after the first hit, but for the
                            latter only after the second.

                            David
                          • David Broadhurst
                            ... Other such numbers are n = 5314 and n = 6100, but PFGW is still running tests to determine whether there might be any more with n
                            Message 13 of 22 , Apr 10, 2009
                            • 0 Attachment
                              --- In primenumbers@yahoogroups.com,
                              "David Broadhurst" <d.broadhurst@...> wrote:

                              > "Numbers n such that there are no primes of the forms
                              > 2^m+3^n or 2^n+3^m for m < n"
                              >
                              > This sequence begins with
                              >
                              > n = 1679, 1743 ...

                              Other such numbers are n = 5314 and n = 6100,
                              but PFGW is still running tests to determine
                              whether there might be any more with n < 6100,
                              so the sequence is not yet ready for OEIS.

                              David
                            • David Broadhurst
                              ... These numbers include 1679, 1743, 4980, 4982, 5314, 5513, 5695, 6100, 7251, 8218 but my coverage of the range n
                              Message 14 of 22 , Apr 11, 2009
                              • 0 Attachment
                                --- In primenumbers@yahoogroups.com,
                                "David Broadhurst" <d.broadhurst@...> wrote:

                                > "Numbers n such that there are no primes of the forms
                                > 2^m+3^n or 2^n+3^m for m < n"

                                These numbers include

                                1679, 1743, 4980, 4982, 5314, 5513, 5695, 6100, 7251, 8218

                                but my coverage of the range n < 8218 is not complete,
                                so this is not yet a bona fide sequence.

                                So far, I have tested more than 7000 values of n < 8300
                                and found these 10 examples.

                                This agrees tolerably well with my prior heuristics.

                                To make a rough estimate of the density of primes of the
                                form N = 2^a + 3^b, I sieved for prime factors < 10^5,
                                with a and b running from 5000 to 5200, and found that
                                5558 values of N survived. So I estimated the
                                probability of primality to be C/log(N), with

                                C =~ exp(Euler)*log(10^5)*5558/201^2 =~ 2.82.

                                Hence I guessed that the probability of finding that
                                a number n lies in this sequence exceeds

                                exp(-C/log(2))*exp(-C/log(3)) > 1/800.

                                I say "exceeds", since 2^n+3^m starts at size
                                O(2^n) and ends at size O(3^n), as m runs from
                                1 to n-1, while 2^m+3^n stays at size O(3^n).

                                David
                              • Mark Underwood
                                ... Wow, I am surprised you could go so high, so quickly. Very nice. Some days after you presented the first two numbers, 1679 and 1743, it occurred to me that
                                Message 15 of 22 , Apr 13, 2009
                                • 0 Attachment
                                  > --- In primenumbers@yahoogroups.com,
                                  > "David Broadhurst" <d.broadhurst@> wrote:
                                  >
                                  > > "Numbers n such that there are no primes of the forms
                                  > > 2^m+3^n or 2^n+3^m for m < n"
                                  >
                                  > These numbers include
                                  >
                                  > 1679, 1743, 4980, 4982, 5314, 5513, 5695, 6100, 7251, 8218
                                  >

                                  Wow, I am surprised you could go so high, so quickly. Very nice.

                                  Some days after you presented the first two numbers, 1679 and 1743,
                                  it occurred to me that the difference between them is 64 = 2^6.
                                  Made me wonder if there might be a special "2-3" property to these
                                  numbers themselves. But with the additional numbers it seems not.
                                  Of course, if I stumble upon something I'll let you know! :)

                                  Thanks David,

                                  Mark
                                • David Broadhurst
                                  ... So far I have 1679, 1743, 4980, 4982, 5314, 5513, 5695, 6100, 6578, 7251, 7406, 7642, 8218, 8331, 9475, 9578 but this is still not a sequence, as there are
                                  Message 16 of 22 , Apr 13, 2009
                                  • 0 Attachment
                                    --- In primenumbers@yahoogroups.com, "Mark Underwood" <mark.underwood@...> wrote:

                                    > Wow, I am surprised you could go so high, so quickly. Very nice.

                                    So far I have

                                    1679, 1743, 4980, 4982, 5314, 5513, 5695, 6100, 6578, 7251, 7406, 7642, 8218, 8331, 9475, 9578

                                    but this is still not a sequence, as there are holes yet to
                                    be looked at, for n < 9578.

                                    David
                                  • David Broadhurst
                                    Submitted to OEIS: Numbers n such that 2^x + 3^y is never prime when max(x,y) = n 1679, 1743, 4980, 4982, 5314, 5513, 5695, 6100, 6578, 7251, 7406, 7642, 8218,
                                    Message 17 of 22 , Apr 17, 2009
                                    • 0 Attachment
                                      Submitted to OEIS:

                                      Numbers n such that 2^x + 3^y is never prime when max(x,y) = n

                                      1679, 1743, 4980, 4982, 5314, 5513, 5695, 6100, 6578,
                                      7251, 7406, 7642, 8218, 8331, 9475, 9578, 9749

                                      Mark Underwood found that for each non-negative integer n < 1421
                                      there is at least one prime of the form 2^m + 3^n or 2^n + 3^m
                                      with m not exceeding n.

                                      This sequence consists of numbers for which there is no such prime.

                                      David Broadhurst estimated that a fraction in excess of 1/800
                                      of the natural numbers belongs to this sequence and found
                                      17 instances with n < 10^4.

                                      For each of the remaining 9983 non-negative integers n < 10^4,
                                      a prime or probable prime of the form 2^x + 3^y was found with
                                      max(x,y) = n.

                                      Each probable prime was subjected to a combination of
                                      strong Fermat and strong Lucas tests.

                                      http://physics.open.ac.uk/~dbroadhu/cert/marktest.txt

                                      David Broadhurst, Apr 17 2009
                                    • Phil Carmody
                                      ... This form invites possibly the most bizarre, and remarkably efficient, sieve algorithm I ve yet had the misfortune of considering. Good job I m not coding
                                      Message 18 of 22 , Apr 18, 2009
                                      • 0 Attachment
                                        --- On Fri, 4/17/09, David Broadhurst <d.broadhurst@...> wrote:
                                        > Submitted to OEIS:
                                        >
                                        > Numbers n such that 2^x + 3^y is never prime when max(x,y) = n
                                        >
                                        > 1679, 1743, 4980, 4982, 5314, 5513, 5695, 6100, 6578,
                                        > 7251, 7406, 7642, 8218, 8331, 9475, 9578, 9749
                                        >
                                        > Mark Underwood found that for each non-negative integer n < 1421
                                        > there is at least one prime of the form 2^m + 3^n or 2^n + 3^m
                                        > with m not exceeding n.
                                        >
                                        > This sequence consists of numbers for which there is no
                                        > such prime.
                                        >
                                        > David Broadhurst estimated that a fraction in excess of 1/800
                                        > of the natural numbers belongs to this sequence and found
                                        > 17 instances with n < 10^4.
                                        >
                                        > For each of the remaining 9983 non-negative integers n < 10^4,
                                        > a prime or probable prime of the form 2^x + 3^y was found with
                                        > max(x,y) = n.
                                        >
                                        > Each probable prime was subjected to a combination of
                                        > strong Fermat and strong Lucas tests.
                                        >
                                        > http://physics.open.ac.uk/~dbroadhu/cert/marktest.txt

                                        This form invites possibly the most bizarre, and remarkably efficient, sieve algorithm I've yet had the misfortune of considering. Good job I'm not coding currently... I'm going to be a tortured soul for at least 2 days until I forget about it.

                                        Phil
                                      • David Broadhurst
                                        ... 1) Put this script in a file called loop.txt : SCRIPT DIM bot,1678 DIM top,1680 DIM aa DIM bb DIM nn DIMS st SET aa,bot-1 LABEL loopa SET aa,aa+1 IF aa
                                        Message 19 of 22 , Apr 18, 2009
                                        • 0 Attachment
                                          --- In primenumbers@yahoogroups.com,
                                          "Mark Underwood" <mark.underwood@> wrote:

                                          > Wow, I am surprised you could go so high, so quickly. Very nice.

                                          1) Put this script in a file called "loop.txt":

                                          SCRIPT
                                          DIM bot,1678
                                          DIM top,1680
                                          DIM aa
                                          DIM bb
                                          DIM nn
                                          DIMS st
                                          SET aa,bot-1
                                          LABEL loopa
                                          SET aa,aa+1
                                          IF aa > top THEN END
                                          SET bb,-1
                                          LABEL loopb
                                          SET bb,bb+1
                                          IF bb <= aa THEN GOTO notyet
                                          SETS st,OEIS:%d;aa
                                          PRP 2^127-1,st
                                          GOTO loopa
                                          LABEL notyet
                                          SET nn,3^aa+2^bb
                                          SETS st,3^%d+2^%d;aa;bb
                                          PRP nn,st
                                          IF ISPRIME THEN GOTO loopa
                                          SET nn,2^aa+3^bb
                                          SETS st,2^%d+3^%d;aa;bb
                                          PRP nn,st
                                          IF ISPRIME THEN GOTO loopa
                                          GOTO loopb

                                          2) In any sane environment, issue this command:

                                          nohup pfgw -f loop.txt > & /dev/null &

                                          In an insane environment, try: pfgw -f loop.txt > nul

                                          3) The output file "pfgw.log" should contain:

                                          3^1678+2^47
                                          OEIS:1679
                                          2^1680+3^67

                                          4) Now split up the job according as how many cores you
                                          have available, adjusting "bot" and "top" in each script.

                                          Thanks, Mark, for the stimulus to test the PNT heuristic.

                                          David
                                        • Mike Oakes
                                          ... I have today uploaded a file containing the results of my search for all primes of this form for 2
                                          Message 20 of 22 , May 7, 2009
                                          • 0 Attachment
                                            --- In primenumbers@yahoogroups.com, "Mike Oakes" <mikeoakes2@...> wrote:
                                            >
                                            > --- In primenumbers@yahoogroups.com, "j_chrtn" <j_chrtn@> wrote:
                                            > >
                                            > > --- In primenumbers@yahoogroups.com, "Maximilian Hasler" <maximilian.hasler@> wrote:
                                            > > >
                                            > > > Dear prime number fans,
                                            > > > is there anything available about possible finiteness of primes of the form (x+1)^p-x^p ?
                                            > > > Specifically, some curios reasons led me to look at 7^p-6^p.
                                            > > > It seems that 1399 and 2027 are the largest known p for which this is prime (Sloane's A062573). According to my calculations, the next such p must be larger than 17900.
                                            > > > Also, 2027 is (so far) the only such p of the form n^2+2, n>1.
                                            > > >
                                            > >
                                            > > Hi Maximilian,
                                            > >
                                            > > p=1399 and 2027 are not the current records for base 7. My personal
                                            > > records are p=69371 and p=86689 for 7^p-6^p. And the largest PRP I have found of this form is currently 8^336419-7^336419.
                                            > >
                                            > > Take a look at Henry Lifchitz's PRP records page
                                            > > www.primenumbers.net/prptop/prptop.php for much more primes/PRP of this form.
                                            > >
                                            > > I believe that (1) for any integer n >= 1, there are infinitely many
                                            > > primes p such that (n+1)^p-n^p is prime and that (2) for any prime p,
                                            > > there are infinitely many integers n such that (n+1)^p-n^p is prime as
                                            > > well.
                                            > > But, unfortunately, proving (or disproving) (1) and (2) is far from being trivial I'm afraid.
                                            > >
                                            > > And now, just for fun, a litle challenge for you: find a prime p such that 138^p-137^p is prime or PRP.
                                            > > Good luck ;-)
                                            > >
                                            > > JL
                                            >
                                            > I have done quite a lot of work on this form, initially summarised in my May 2001 post to the NMBRTHRY list:
                                            > http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0105&L=NMBRTHRY&P=R359&I=-3
                                            >
                                            > Since then, Jean-Louis in particular has devoted seemingly enormous numbers of cpu cycles to extending the list of known PRPs.

                                            I have today uploaded a file containing the results of my search for all primes of this form for 2<=b<=1000, 2<=p<10000, done in the years 2000-2008.

                                            It is the file "b^p-(b-1)^p.txt", within the "Prime Tables" folder in the Files area of this site.

                                            -Mike Oakes
                                          • David Broadhurst
                                            ... Here is a simple link to Mike s interesting table: http://tinyurl.com/d3nf9w David
                                            Message 21 of 22 , May 7, 2009
                                            • 0 Attachment
                                              --- In primenumbers@yahoogroups.com,
                                              "Mike Oakes" <mikeoakes2@...> wrote:

                                              > I have today uploaded a file containing the results of my search
                                              > for all primes of this form for 2<=b<=1000, 2<=p<10000, done in
                                              > the years 2000-2008.

                                              Here is a simple link to Mike's interesting table:

                                              http://tinyurl.com/d3nf9w

                                              David
                                            • Maximilian Hasler
                                              ... (Thanks, Mike !) ... Thanks, David! (Remark: These tiny urls are nice, but can be quite annoying when they point to a website that re-arranged its
                                              Message 22 of 22 , May 7, 2009
                                              • 0 Attachment
                                                --- In primenumbers@yahoogroups.com, "David Broadhurst" wrote:
                                                > --- In primenumbers@yahoogroups.com, "Mike Oakes" wrote:
                                                > > I have today uploaded a file containing the results of my search
                                                > > for all primes of this form for 2<=b<=1000, 2<=p<10000, done in
                                                > > the years 2000-2008.

                                                (Thanks, Mike !)

                                                > Here is a simple link to Mike's interesting table:
                                                > http://tinyurl.com/d3nf9w

                                                Thanks, David!
                                                (Remark: These tiny urls are nice, but can be quite annoying when they point to a website that re-arranged its directory structure - with tinyurls ultra-efficient and discreet forwarding system you sometimes can't get the slightest info about where/what you had been pointed to and try to find it "by hand"... [this happened to me a few days ago - but I forgot where & what is was about...])

                                                OTOH:

                                                p=2 : A006254 Numbers n such that 2n-1 is prime.

                                                p=3 : A002504 numbers such that 1+3x(x-1) is (a "cuban") prime.

                                                p=5 : A121617 Nexus numbers of order 5 (or A022521[n-1] = n^5 - (n-1)^5) are primes.

                                                p=7 : A121619 Nexus numbers of order 7 (A022523[n-1] = n^7 - (n-1)^7) are primes

                                                p >= 11 seems not yet there, so Mike could enter his numbers into OEIS, starting there !

                                                Maximilian, per proxy SOSR
                                                (Society for On-line Sequence Recovery)
                                              Your message has been successfully submitted and would be delivered to recipients shortly.