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

Re: 2^p+3

Expand Messages
  • jim_fougeron
    ... For an infinity of easy to show counter examples, look at this form: k#+p If p is a fixed prime 3, then the expression will be +-1 mod(6), however, the
    Message 1 of 22 , May 1, 2002
    • 0 Attachment
      --- In primenumbers@y..., "jbrennen" <jack@b...> wrote:
      >--- In primenumbers@y..., "rlberry2002" <rlberry2002@y...> wrote:
      >> Paul,
      >>
      >> I obviously misunderstood your equation; I read it as (2^p) + 3
      >> where p=2,result 7; p=3, result 11, and so on.
      >
      >No, you got it right :-)
      >
      >> I stand by my earlier statements (let's term it as Robert's
      >> Conjecture) though: A one variable equation which, (a) does not
      >> reduce and (b) contains infinitely many 1 Mod 6 and/or 5 Mod 6
      >> numbers, will contain infinitely many prime numbers.
      >
      > See Sierpinski numbers for a well-known counterexample:
      > 78557*2^n+1 contains an infinite number of elements which are
      > (5 mod 6), but has no prime numbers for any integer n.

      For an infinity of easy to show counter examples, look at this form:

      k#+p

      If p is a "fixed" prime > 3, then the expression will be +-1 mod(6),
      however, the expression (for a variable k and fixed p) will produce
      ONLY a finite (if any) amount of primes. Primes can only be generated
      by the above form while k < p. Once k reaches the size of p, then
      p will always be a factor of the expression.

      Take for example k#+13.
      This is prime for k=3, 5, 7 and NO others, since 2#+13=3*5,
      11#+13= 23*101 and when k>=13 then k#+13 is always has a factor of 13.
      However k#+13 == 1mod(6) (except for 2#+13==3mod(6)).

      Jim.
    • mikeoakes2@aol.com
      AFAIK the largest PRP of form 2^n+3 is still the one found by me in July 2001:- 2^122550+3 It is the 19th largest known PRP, according to Henri Lifchitz s
      Message 2 of 22 , May 1, 2002
      • 0 Attachment
        AFAIK the largest PRP of form 2^n+3 is still the one found by me in July
        2001:-
        2^122550+3

        It is the 19th largest known PRP, according to Henri Lifchitz's database at
        http://ourworld.compuserve.com/homepages/hlifchitz/

        The sequence for lower values is Sloane's A057732. I had searched up to
        n=127677, and proved primality for n <=2370 using Titanix, finishing this
        project on 15 Aug 2001.

        (See also my post to the primenumbers group dated 8 Jul 2002.)

        Mike Oakes


        In a message dated 01/05/02 14:41:02 GMT Daylight Time,
        Paul.Jobling@... writes:

        > Hi,
        >
        > I was just wondering what the state of play was with looking for a
        > (pseudo-)prime of the form 2^p+3 - what search limits have been reached,
        > and
        > have any PRP's been found? I recall that there was some searching being
        > done a
        > couple of years ago (I think), but I do not know what (if any) results were
        > found?
        >
        > Regards,
        >
        > Paul.
        >




        [Non-text portions of this message have been removed]
      • rlberry2002
        Please pardon my ignorance; I am here to learn to grow in my knowledge of number theory. However, I will try to be more careful in responding to posts before
        Message 3 of 22 , May 1, 2002
        • 0 Attachment
          Please pardon my ignorance; I am here to learn to grow in my
          knowledge of number theory. However, I will try to be more careful
          in responding to posts before I have fully thought out my response -
          you could extend me the same courtesy.

          Your example of N=2^p + 12213 violates one of the two qualifications
          that I laid down - "the equation cannot be reducible". I typically
          would use this tenet for an equation like 4n + 1 (which does have
          infinitely many primes in it)where n is odd. The tenet holds for
          numbers of the form 2^p + n also, it just is usually harder to find
          the pattern that this type of equation reduces to. In your example,
          you provide the pattern which violates my first condition: that is
          for 2, 3, 1 Mod 12, 5 Mod 12, 7 Mod 12, & 11 Mod 12; there a fixed
          set of possible outcomes each of which will have fixed factors
          depending upon which of the outcomes it fall under.

          For instance, the equation 30Y + 35 = N generates infinitely many 5
          Mod 6 numbers none of which are prime. This equation is easy since it
          reduces to 5*(6Y + 7) = N; numbers of the form 2^p + N require a
          deeper analysis as long as N itself does not have a factor of 2^p.

          Just a few thoughts

          Robert

          --- In primenumbers@y..., "jbrennen" <jack@b...> wrote:
          > --- In primenumbers@y..., "rlberry2002" <rlberry2002@y...> wrote:
          > > Paul,
          > >
          > > I obviously misunderstood your equation; I read it as (2^p) + 3
          > > where p=2,result 7; p=3, result 11, and so on.
          >
          > No, you got it right :-)
          >
          > > I stand by my earlier statements (let's term it as Robert's
          > > Conjecture) though: A one variable equation which, (a) does not
          > > reduce and (b) contains infinitely many 1 Mod 6 and/or 5 Mod 6
          > > numbers, will contain infinitely many prime numbers.
          >
          > See Sierpinski numbers for a well-known counterexample:
          > 78557*2^n+1 contains an infinite number of elements which are
          > (5 mod 6), but has no prime numbers for any integer n.
          >
          > Back to the original question... There are easily found concrete
          > examples of the form 2^p+n which do not have an infinite number of
          > prime values (with p prime) despite having an infinite number of
          > (1 mod 6) and (5 mod 6) numbers:
          >
          > N=2^p+12213 (with p prime) has no prime values whatsoever.
          >
          > This is because:
          >
          > If p == 2, N is divisible by 19
          > If p == 3, N is divisible by 11
          > If p == 1 (mod 12), N is divisible by 5
          > If p == 5 (mod 12), N is divisible by 5
          > If p == 7 (mod 12), N is divisible by 7
          > If p == 11 (mod 12), N is divisible by 13
          >
          > Every prime p meets one of the six cases above, so N is never
          > prime when p is prime.
        • Phil Carmody
          ... I would trust that such courtesy is demonstrated on the list. (Yeah, flame me off list, you won t be the first... (or the second) ... Strictly, it is
          Message 4 of 22 , May 1, 2002
          • 0 Attachment
            --- rlberry2002 <rlberry2002@...> wrote:
            > Please pardon my ignorance; I am here to learn to grow in my
            > knowledge of number theory. However, I will try to be more careful
            > in responding to posts before I have fully thought out my response
            > - you could extend me the same courtesy.

            I would trust that such courtesy is demonstrated on the list.
            (Yeah, flame me off list, you won't be the first... (or the second)
            :-) )

            > Your example of N=2^p + 12213 violates one of the two
            > qualifications
            > that I laid down - "the equation cannot be reducible".

            Strictly, it is irreducible. The letter of the law is obeyed.

            > I typically
            > would use this tenet for an equation like 4n + 1 (which does have
            > infinitely many primes in it)where n is odd. The tenet holds for
            > numbers of the form 2^p + n also, it just is usually harder to find
            >
            > the pattern that this type of equation reduces to. In your
            > example,
            > you provide the pattern which violates my first condition: that is
            >
            > for 2, 3, 1 Mod 12, 5 Mod 12, 7 Mod 12, & 11 Mod 12; there a fixed
            > set of possible outcomes each of which will have fixed factors
            > depending upon which of the outcomes it fall under.

            Sure, but that's not redicibility. What Jack has highlighted is an
            intrinsically interesting property about that sequence of numbers.
            This property will ba shared by an infinite number of other
            sequences, not just the ...+12213. The property isn't reducibility,
            and that term was used, it's a very precisely defined term, so Jack
            and others can't be faulted for taking the term at face falue.
            Perhaps the term "with no intrinsic predicatble factorisations" or
            similar could be used to cover such concepts.

            Such forms are certainly vastly interesting, the Sierpinski/Riesel
            problems (that Jack mentioned, IIRC) are all about whether there are
            primes with forms that have no intricsic predictable factorisations.

            (hmmm, reminder to self or others - is there a link waiting to be
            added to the yahoogroup regarding the Sierpinski/Riesel problems?)

            Phil

            __________________________________________________
            Do You Yahoo!?
            Yahoo! Health - your guide to health and wellness
            http://health.yahoo.com
          • rlberry2002
            Phil, As always, your comments and insights are welcome. I had to do a little refresher myself on Sierpinski numbers: a positive, odd integer k for which
            Message 5 of 22 , May 1, 2002
            • 0 Attachment
              Phil,

              As always, your comments and insights are welcome. I had to do a
              little refresher myself on Sierpinski numbers: a positive, odd
              integer k for which integers of the form k*2^p + 1 are all composite.
              I would suggest that there is little here which serves as an adequate
              counter example to the conjecture that I previously made.

              First, for all k less than 78557, at least 1 prime has been found to
              be generated by k*2^p + 1 with only 19 exceptions (and I feel it is
              just that the first prime solution for these 19 k's has not yet been
              found). It is only conjectured that k=78557 is a Sierpinski number.
              It is likely that the smallest Sierpinski number (if indeed one does
              exist) is so large that direct factorization, indirect factorization,
              etc. will not be feasible. One final point concerning k=78557 will
              show the difficulty in analyzing these numbers: For k=78557, p=300
              you get a 95-digit result. In other words, the 300th example for
              k=78557 is already a number of such magnitude that only 1 number in
              300 will be prime. Guess what the odds look like for the next 300
              values of p.

              Indeed, any series of numbers of the form k*N^p +/- c are very
              difficult to analysis except with indirect methods.

              Regards,

              Robert

              --- In primenumbers@y..., Phil Carmody <thefatphil@y...> wrote:
              > --- rlberry2002 <rlberry2002@y...> wrote:
              > > Please pardon my ignorance; I am here to learn to grow in my
              > > knowledge of number theory. However, I will try to be more
              careful
              > > in responding to posts before I have fully thought out my response
              > > - you could extend me the same courtesy.
              >
              > I would trust that such courtesy is demonstrated on the list.
              > (Yeah, flame me off list, you won't be the first... (or the second)
              > :-) )
              >
              > > Your example of N=2^p + 12213 violates one of the two
              > > qualifications
              > > that I laid down - "the equation cannot be reducible".
              >
              > Strictly, it is irreducible. The letter of the law is obeyed.
              >
              > > I typically
              > > would use this tenet for an equation like 4n + 1 (which does have
              > > infinitely many primes in it)where n is odd. The tenet holds for
              > > numbers of the form 2^p + n also, it just is usually harder to
              find
              > >
              > > the pattern that this type of equation reduces to. In your
              > > example,
              > > you provide the pattern which violates my first condition: that
              is
              > >
              > > for 2, 3, 1 Mod 12, 5 Mod 12, 7 Mod 12, & 11 Mod 12; there a
              fixed
              > > set of possible outcomes each of which will have fixed factors
              > > depending upon which of the outcomes it fall under.
              >
              > Sure, but that's not redicibility. What Jack has highlighted is an
              > intrinsically interesting property about that sequence of numbers.
              > This property will ba shared by an infinite number of other
              > sequences, not just the ...+12213. The property isn't reducibility,
              > and that term was used, it's a very precisely defined term, so Jack
              > and others can't be faulted for taking the term at face falue.
              > Perhaps the term "with no intrinsic predicatble factorisations" or
              > similar could be used to cover such concepts.
              >
              > Such forms are certainly vastly interesting, the Sierpinski/Riesel
              > problems (that Jack mentioned, IIRC) are all about whether there are
              > primes with forms that have no intricsic predictable factorisations.
              >
              > (hmmm, reminder to self or others - is there a link waiting to be
              > added to the yahoogroup regarding the Sierpinski/Riesel problems?)
              >
              > Phil
              >
              > __________________________________________________
              > Do You Yahoo!?
              > Yahoo! Health - your guide to health and wellness
              > http://health.yahoo.com
            • Jack Brennen
              ... We re glad you did a little research on Sierpinski numbers. However, you must have missed something. It is PROVEN, and can be shown using nothing more
              Message 6 of 22 , May 1, 2002
              • 0 Attachment
                rlberry2002 wrote:
                > As always, your comments and insights are welcome. I had to do a
                > little refresher myself on Sierpinski numbers: a positive, odd
                > integer k for which integers of the form k*2^p + 1 are all composite.
                > I would suggest that there is little here which serves as an adequate
                > counter example to the conjecture that I previously made.
                >
                > First, for all k less than 78557, at least 1 prime has been found to
                > be generated by k*2^p + 1 with only 19 exceptions (and I feel it is
                > just that the first prime solution for these 19 k's has not yet been
                > found). It is only conjectured that k=78557 is a Sierpinski number.

                We're glad you did a little research on Sierpinski numbers.

                However, you must have missed something. It is PROVEN, and can be shown
                using nothing more than very simple arithmetic, that k=78557 is
                a Sierpinski number. The proof, in condensed form:

                If n == 0 (mod 2), 78557*2^n+1 is divisible by 3
                If n == 1 (mod 4), 78557*2^n+1 is divisible by 5
                If n == 3 (mod 36), 78557*2^n+1 is divisible by 73
                If n == 15 (mod 36), 78557*2^n+1 is divisible by 19
                If n == 27 (mod 36), 78557*2^n+1 is divisible by 37
                If n == 7 (mod 12), 78557*2^n+1 is divisible by 7
                If n == 11 (mod 12), 78557*2^n+1 is divisible by 13

                Every integer n satisfies one of these seven congruences.

                The unproven conjecture is that k=78557 is the
                *smallest* Sierpinski number.
              • Gary Chaffey
                Does the idea of 2^p+3 extend to 2^p-3? I have found that 2^233-3 is PRP now p is of the form 60k-7. Is this just a coincedence or is there some sort of
                Message 7 of 22 , May 3, 2002
                • 0 Attachment
                  Does the idea of 2^p+3 extend to 2^p-3? I have found
                  that 2^233-3 is PRP now p is of the form 60k-7. Is
                  this just a coincedence or is there some sort of
                  pattern.
                  I haven't checked
                  2^233= a mod 233
                  2^(2^233)= 2^n mod a
                  Like Norman did for 2^p+3 with p=7 and 67
                  Gary

                  __________________________________________________
                  Do You Yahoo!?
                  Yahoo! Health - your guide to health and wellness
                  http://health.yahoo.com
                • Phil Carmody
                  ... This can be checked as follows. If 5 | 2^x-3 then 2^x==3 (5) then x==3 (4) If 7 | 2^x-3 then 2^x==3 (7) no solution If 11 | 2^x-3 then 2^x==3 (11) then
                  Message 8 of 22 , May 3, 2002
                  • 0 Attachment
                    --- Gary Chaffey <garychaffey@...> wrote:
                    > Does the idea of 2^p+3 extend to 2^p-3? I have found
                    > that 2^233-3 is PRP now p is of the form 60k-7. Is
                    > this just a coincedence or is there some sort of
                    > pattern.

                    This can be checked as follows.

                    If 5 | 2^x-3 then 2^x==3 (5) then x==3 (4)
                    If 7 | 2^x-3 then 2^x==3 (7) no solution
                    If 11 | 2^x-3 then 2^x==3 (11) then x==8 (10)
                    If 13 | 2^x-3 then 2^x==3 (13) then x==4 (12)
                    ...

                    These remove
                    3,7,11,15,19,23,27,31,35,39,43,47,51,55,59 (mod 60)
                    8 18 28 38 48 58 (mod 60)
                    4 16 28 40 52 (mod 60)
                    ...

                    There are other primes that add to this mod 60 period, obviously.

                    Not every residue is removed, which leads me to suspect that 53 isn't
                    the only residue primes will be found along.

                    Phil

                    =====
                    --
                    "One cannot delete the Web browser from KDE without
                    losing the ability to manage files on the user's own
                    hard disk." - Prof. Stuart E Madnick, MIT.
                    So called "expert" witness for Microsoft. 2002/04/02

                    __________________________________________________
                    Do You Yahoo!?
                    Yahoo! Health - your guide to health and wellness
                    http://health.yahoo.com
                  • djbroadhurst
                    A little reminder: if you find a PRP of the form 2^n-3 or 2^n+3 (for any n, not just a prime) you may have prospects of a BLS (which failing a KP) proof by
                    Message 9 of 22 , May 3, 2002
                    • 0 Attachment
                      A little reminder: if you find a PRP of the form
                      2^n-3 or 2^n+3 (for any n, not just a prime) you may
                      have prospects of a BLS (which failing a KP) proof
                      by looking at work on factorization of Phi(2,k),
                      since, in *either* case, *both* N-1 and N+1 are
                      algebraically factorizable into these intensively
                      studied base-2 cyclotomic numbers:
                      http://www.cerias.purdue.edu/homes/ssw/cun/index.html
                      Apologies to those for whom this is blindingly obvious.
                      David Broadhurst
                    Your message has been successfully submitted and would be delivered to recipients shortly.