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

primes such that every bit matters?

Expand Messages
  • WarrenS
    A prime P which turns into a composite if you alter any bit in its binary representation is an every bit matters prime. The examples below 10000 are 127,
    Message 1 of 14 , Apr 3, 2013
    • 0 Attachment
      A prime P which turns into a composite if you alter any bit in
      its binary representation is an "every bit matters" prime.

      The examples below 10000 are
      127, 173, 191, 223, 233, 239, 251, 257, 277, 337, 349, 373, 431, 443,
      491, 509, 557, 653, 683, 701, 733, 761, 787, 853, 877, 1019, 1193,
      1201, 1259, 1381, 1451, 1453, 1553, 1597, 1709, 1753, 1759, 1777,
      1973, 2027, 2063, 2333, 2371, 2447, 2633, 2879, 2917, 2999, 3083,
      3181, 3209, 3313, 3511, 3593, 3643, 3767, 3779, 3851, 3877, 3889,
      3967, 4013, 4177, 4283, 4441, 4451, 4561, 4597, 4603, 4679, 4813,
      4889, 4951, 5051, 5099, 5209, 5323, 5557, 5801, 5867, 6007, 6073,
      6151, 6203, 6211, 6287, 6323, 6379, 6481, 6521, 6971, 6977, 6997,
      7027, 7039, 7043, 7103, 7109, 7151, 7207, 7297, 7307, 7331, 7369,
      7507, 7573, 7583, 7841, 7883, 8017, 8087, 8111, 8171, 8231, 8243,
      8311, 8363, 8627, 8747, 8831, 8849, 8867, 8923, 9137, 9151, 9161,
      9319, 9323, 9697, 9767

      The Mersenne primes P=2^p-1 also have this "every bit matters" property when
      p = 7, 31, 127, 607, 1279, 4423
      for the p<10000.

      My current conjecture is that a fraction B of all primes are every-bit-matters primes,
      where B = exp(-2*C2 / ln2) = 0.14884878474999065378100135978
      where
      C2=0.660161815846869573927812110014...
      is the Hardy Littlewood twin prime constant described here
      http://en.wikipedia.org/wiki/Twin_prime#First_Hardy.E2.80.93Littlewood_conjecture
      [This B agrees mildly well with my computer counts for primes<10^9.
      If you count among the primes up to N I think the error in B will be of order 1/logN,
      so convergence expected to be slow. But perhaps with extrapolate-to-infinity tricks
      you could get more convincing evidence confirming or denying the conjecture.]

      It also is interesting to ask: what if the infinity of leading 0s are also considered "bits"
      susceptible to alteration?
      The following prime
      2131099 = ...0000000000001000001000010010011011 binary
      has the property that if any bit is altered, you get a composite.
      Is this the least such prime? I do not know.

      I can prove by stealing a result of Zhi-Wei Sun
      that liminfB >= 1/9761888869657922764800000000
      (and this still works even for the "leading 0s allowed" version)
      but have no proof that limsupB<1 or that limB exists.
    • Jack Brennen
      See here for something related... http://www.primepuzzles.net/problems/prob_025.htm
      Message 2 of 14 , Apr 3, 2013
      • 0 Attachment
        See here for something related...

        http://www.primepuzzles.net/problems/prob_025.htm



        On 4/3/2013 7:06 PM, WarrenS wrote:
        > A prime P which turns into a composite if you alter any bit in
        > its binary representation is an "every bit matters" prime.
        >
        > The examples below 10000 are
        > 127, 173, 191, 223, 233, 239, 251, 257, 277, 337, 349, 373, 431, 443,
        > 491, 509, 557, 653, 683, 701, 733, 761, 787, 853, 877, 1019, 1193,
        > 1201, 1259, 1381, 1451, 1453, 1553, 1597, 1709, 1753, 1759, 1777,
        > 1973, 2027, 2063, 2333, 2371, 2447, 2633, 2879, 2917, 2999, 3083,
        > 3181, 3209, 3313, 3511, 3593, 3643, 3767, 3779, 3851, 3877, 3889,
        > 3967, 4013, 4177, 4283, 4441, 4451, 4561, 4597, 4603, 4679, 4813,
        > 4889, 4951, 5051, 5099, 5209, 5323, 5557, 5801, 5867, 6007, 6073,
        > 6151, 6203, 6211, 6287, 6323, 6379, 6481, 6521, 6971, 6977, 6997,
        > 7027, 7039, 7043, 7103, 7109, 7151, 7207, 7297, 7307, 7331, 7369,
        > 7507, 7573, 7583, 7841, 7883, 8017, 8087, 8111, 8171, 8231, 8243,
        > 8311, 8363, 8627, 8747, 8831, 8849, 8867, 8923, 9137, 9151, 9161,
        > 9319, 9323, 9697, 9767
        >
        > The Mersenne primes P=2^p-1 also have this "every bit matters" property when
        > p = 7, 31, 127, 607, 1279, 4423
        > for the p<10000.
        >
        > My current conjecture is that a fraction B of all primes are every-bit-matters primes,
        > where B = exp(-2*C2 / ln2) = 0.14884878474999065378100135978
        > where
        > C2=0.660161815846869573927812110014...
        > is the Hardy Littlewood twin prime constant described here
        > http://en.wikipedia.org/wiki/Twin_prime#First_Hardy.E2.80.93Littlewood_conjecture
        > [This B agrees mildly well with my computer counts for primes<10^9.
        > If you count among the primes up to N I think the error in B will be of order 1/logN,
        > so convergence expected to be slow. But perhaps with extrapolate-to-infinity tricks
        > you could get more convincing evidence confirming or denying the conjecture.]
        >
        > It also is interesting to ask: what if the infinity of leading 0s are also considered "bits"
        > susceptible to alteration?
        > The following prime
        > 2131099 = ...0000000000001000001000010010011011 binary
        > has the property that if any bit is altered, you get a composite.
        > Is this the least such prime? I do not know.
        >
        > I can prove by stealing a result of Zhi-Wei Sun
        > that liminfB >= 1/9761888869657922764800000000
        > (and this still works even for the "leading 0s allowed" version)
        > but have no proof that limsupB<1 or that limB exists.
        >
        >
        >
        >
        > ------------------------------------
        >
        > Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
        > The Prime Pages : http://primes.utm.edu/
        >
        > Yahoo! Groups Links
        >
        >
        >
        >
        >
      • Jack Brennen
        And although Paulsen s links seem to be dead, here s a message from 10+ years ago, to this very mailing list, offering up the number 2131099:
        Message 3 of 14 , Apr 3, 2013
        • 0 Attachment
          And although Paulsen's links seem to be dead, here's a message from
          10+ years ago, to this very mailing list, offering up the number 2131099:

          http://tech.groups.yahoo.com/group/primenumbers/message/7301



          On 4/3/2013 7:20 PM, Jack Brennen wrote:
          > See here for something related...
          >
          > http://www.primepuzzles.net/problems/prob_025.htm
          >
          >
          >
          > On 4/3/2013 7:06 PM, WarrenS wrote:
          >> A prime P which turns into a composite if you alter any bit in
          >> its binary representation is an "every bit matters" prime.
          >>
          >> The examples below 10000 are
          >> 127, 173, 191, 223, 233, 239, 251, 257, 277, 337, 349, 373, 431, 443,
          >> 491, 509, 557, 653, 683, 701, 733, 761, 787, 853, 877, 1019, 1193,
          >> 1201, 1259, 1381, 1451, 1453, 1553, 1597, 1709, 1753, 1759, 1777,
          >> 1973, 2027, 2063, 2333, 2371, 2447, 2633, 2879, 2917, 2999, 3083,
          >> 3181, 3209, 3313, 3511, 3593, 3643, 3767, 3779, 3851, 3877, 3889,
          >> 3967, 4013, 4177, 4283, 4441, 4451, 4561, 4597, 4603, 4679, 4813,
          >> 4889, 4951, 5051, 5099, 5209, 5323, 5557, 5801, 5867, 6007, 6073,
          >> 6151, 6203, 6211, 6287, 6323, 6379, 6481, 6521, 6971, 6977, 6997,
          >> 7027, 7039, 7043, 7103, 7109, 7151, 7207, 7297, 7307, 7331, 7369,
          >> 7507, 7573, 7583, 7841, 7883, 8017, 8087, 8111, 8171, 8231, 8243,
          >> 8311, 8363, 8627, 8747, 8831, 8849, 8867, 8923, 9137, 9151, 9161,
          >> 9319, 9323, 9697, 9767
          >>
          >> The Mersenne primes P=2^p-1 also have this "every bit matters" property when
          >> p = 7, 31, 127, 607, 1279, 4423
          >> for the p<10000.
          >>
          >> My current conjecture is that a fraction B of all primes are every-bit-matters primes,
          >> where B = exp(-2*C2 / ln2) = 0.14884878474999065378100135978
          >> where
          >> C2=0.660161815846869573927812110014...
          >> is the Hardy Littlewood twin prime constant described here
          >> http://en.wikipedia.org/wiki/Twin_prime#First_Hardy.E2.80.93Littlewood_conjecture
          >> [This B agrees mildly well with my computer counts for primes<10^9.
          >> If you count among the primes up to N I think the error in B will be of order 1/logN,
          >> so convergence expected to be slow. But perhaps with extrapolate-to-infinity tricks
          >> you could get more convincing evidence confirming or denying the conjecture.]
          >>
          >> It also is interesting to ask: what if the infinity of leading 0s are also considered "bits"
          >> susceptible to alteration?
          >> The following prime
          >> 2131099 = ...0000000000001000001000010010011011 binary
          >> has the property that if any bit is altered, you get a composite.
          >> Is this the least such prime? I do not know.
          >>
          >> I can prove by stealing a result of Zhi-Wei Sun
          >> that liminfB >= 1/9761888869657922764800000000
          >> (and this still works even for the "leading 0s allowed" version)
          >> but have no proof that limsupB<1 or that limB exists.
          >>
          >>
          >>
          >>
          >> ------------------------------------
          >>
          >> Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
          >> The Prime Pages : http://primes.utm.edu/
          >>
          >> Yahoo! Groups Links
          >>
          >>
          >>
          >>
          >>
          >
          >
          >
          > ------------------------------------
          >
          > Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
          > The Prime Pages : http://primes.utm.edu/
          >
          > Yahoo! Groups Links
          >
          >
          >
          >
          >
        • Jens Kruse Andersen
          ... See http://oeis.org/A137985 and Terence Tao s paper (it mentions me!). The base-10 variant is called weakly prime numbers: http://oeis.org/A050249 -- Jens
          Message 4 of 14 , Apr 3, 2013
          • 0 Attachment
            WarrenS wrote:
            > A prime P which turns into a composite if you alter any bit in
            > its binary representation is an "every bit matters" prime.

            See http://oeis.org/A137985 and Terence Tao's paper (it mentions me!).
            The base-10 variant is called weakly prime numbers: http://oeis.org/A050249

            --
            Jens Kruse Andersen
          • WarrenS
            thanks everybody (I actually knew most of that, but thanks anyhow)... I had not known about William Paulsen. Paulsen apparently conjectured that 67607 is the
            Message 5 of 14 , Apr 3, 2013
            • 0 Attachment
              thanks everybody (I actually knew most of that, but thanks anyhow)...
              I had not known about William Paulsen. Paulsen apparently conjectured
              that 67607 is the least prime such that changing any bit (including leading 0s)
              always yields a composite(?). This would improve a lot versus 2131099
              (which he also knew about).

              Unfortunately for his conjecture,
              67607 + 2^16389
              is prime (says MAPLE9 -- is it right?).
              This prime shows as a side effect of proposition 2 in Paulsen's article that 67607 is not a Sierpinski number (or if it is, not one having a proof based on covering congruences)
              which I think was not previously known.

              Wm Paulsen: the prime numbers maze, Fibonacci Quart. 40 (2002) 272-279.
              http://www.fq.math.ca/Scanned/40-3/paulsen.pdf

              Paulsen also notes a candidate is 19249.
              However, 19249*2^13018586+1 is prime
              which defeats his argument although the conjecture per se is not refuted (yet).
              That is, we know 19249 is not a Sierpinski number, and hence there can be no proof
              based on covering congruences that 19249+2^k is always composite.
              Hence it is plausible there exists a prime 19249+2^k (although I do not know one).

              We can indeed kill quite a few Sierpinski candidates from the page
              http://en.wikipedia.org/wiki/Seventeen_or_Bust
              in the same way:

              * 10223 + 2^k is prime if k=19, 103, or 3619
              hence 10223 is not Sierpinski-via-covering-congruences.

              * 21181 + 2^k is prime for k=28, 196, 268, and 316
              hence 21181 is not Sierpinski-via-covering-congruences.

              * 22699 + 2^k is prime for k=26 and 1250
              hence is not Sierpinski-via-covering-congruences.

              * 24737 + 2^k is prime for k=17
              hence is not Sierpinski-via-covering-congruences.

              * 55459 + 2^k is prime for k=14, 746, and 854
              hence is not Sierpinski-via-covering-congruences.

              This in fact kills every undecided case in the "seventeen or bust" project -- none
              of them are Sierpinski-via-covering-congruences.
              It is still possible they could be Sierpinski for some other reason (i.e. luck), though.

              Paulsen also notes the prime bit-alteration graph is bipartite,
              the "parity" of a prime (number of 1s in its binary representation is even or odd?)
              governs that...
            • mikeoakes2
              ... Probably. PFGW says it is Fermat (to bases 3 & 137) and Lucas PRP, which (ducking a 16389-bit PRIMO proof) is good enough, I reckon. Mike
              Message 6 of 14 , Apr 4, 2013
              • 0 Attachment
                --- In primenumbers@yahoogroups.com, "WarrenS" <warren.wds@...> wrote:
                >
                > thanks everybody (I actually knew most of that, but thanks anyhow)...
                > I had not known about William Paulsen. Paulsen apparently conjectured
                > that 67607 is the least prime such that changing any bit (including leading 0s)
                > always yields a composite(?). This would improve a lot versus 2131099
                > (which he also knew about).
                >
                > Unfortunately for his conjecture,
                > 67607 + 2^16389
                > is prime (says MAPLE9 -- is it right?).

                Probably.
                PFGW says it is Fermat (to bases 3 & 137) and Lucas PRP, which (ducking a 16389-bit PRIMO proof) is good enough, I reckon.

                Mike
              • mikeoakes2
                ... It is surely unlikely that such an illustrious project has got it all wrong! The mistake is that all your remarks are about the so-called /dual/ Sierpinski
                Message 7 of 14 , Apr 4, 2013
                • 0 Attachment
                  --- In primenumbers@yahoogroups.com, "WarrenS" <warren.wds@...> wrote:
                  >
                  > thanks everybody (I actually knew most of that, but thanks anyhow)...
                  > I had not known about William Paulsen. Paulsen apparently conjectured
                  > that 67607 is the least prime such that changing any bit (including leading 0s)
                  > always yields a composite(?). This would improve a lot versus 2131099
                  > (which he also knew about).
                  >
                  > Unfortunately for his conjecture,
                  > 67607 + 2^16389
                  > is prime (says MAPLE9 -- is it right?).
                  > This prime shows as a side effect of proposition 2 in Paulsen's article that 67607 is not a Sierpinski number (or if it is, not one having a proof based on covering congruences)
                  > which I think was not previously known.
                  >
                  > Wm Paulsen: the prime numbers maze, Fibonacci Quart. 40 (2002) 272-279.
                  > http://www.fq.math.ca/Scanned/40-3/paulsen.pdf
                  >
                  > Paulsen also notes a candidate is 19249.
                  > However, 19249*2^13018586+1 is prime
                  > which defeats his argument although the conjecture per se is not refuted (yet).
                  > That is, we know 19249 is not a Sierpinski number, and hence there can be no proof
                  > based on covering congruences that 19249+2^k is always composite.
                  > Hence it is plausible there exists a prime 19249+2^k (although I do not know one).
                  >
                  > We can indeed kill quite a few Sierpinski candidates from the page
                  > http://en.wikipedia.org/wiki/Seventeen_or_Bust
                  > in the same way:
                  >
                  > * 10223 + 2^k is prime if k=19, 103, or 3619
                  > hence 10223 is not Sierpinski-via-covering-congruences.
                  >
                  > * 21181 + 2^k is prime for k=28, 196, 268, and 316
                  > hence 21181 is not Sierpinski-via-covering-congruences.
                  >
                  > * 22699 + 2^k is prime for k=26 and 1250
                  > hence is not Sierpinski-via-covering-congruences.
                  >
                  > * 24737 + 2^k is prime for k=17
                  > hence is not Sierpinski-via-covering-congruences.
                  >
                  > * 55459 + 2^k is prime for k=14, 746, and 854
                  > hence is not Sierpinski-via-covering-congruences.
                  >
                  > This in fact kills every undecided case in the "seventeen or bust" project -- none
                  > of them are Sierpinski-via-covering-congruences.
                  > It is still possible they could be Sierpinski for some other reason (i.e. luck), though.

                  It is surely unlikely that such an illustrious project has got it all wrong!

                  The mistake is that all your remarks are about the so-called /dual/ Sierpinski problem.

                  And in fact the Five or Bust website
                  http://www.mersenneforum.org/forumdisplay.php?f=86
                  tells us that 67607 + 2^16389 is indeed a /proven/ prime.

                  Mike
                • WarrenS
                  ... --didn t claim they were wrong. And in fact, W.Keller pointed out to me this paper #A61 here: http://www.integers-ejcnt.org/vol8.html which would seem to
                  Message 8 of 14 , Apr 4, 2013
                  • 0 Attachment
                    > It is surely unlikely that such an illustrious project has got it all wrong!

                    --didn't claim they were wrong. And in fact, W.Keller pointed out to me this paper
                    #A61 here: http://www.integers-ejcnt.org/vol8.html
                    which would seem to confirm what I said (they already knew it).
                    It's just a bit weird that I thought I had a totally original problem, and it turns out it
                    has been worked on a ton by others for years...

                    Also, this frightening number is a probable prime:
                    19249+2^551542


                    > The mistake is that all your remarks are about the so-called /dual/ Sierpinski problem.
                    --which is... what?
                  • djbroadhurst
                    ... Section 2 of the paper to which Wilfrid directed you explains the diffrence between the SierpiĀ“nski problem and its dual, as remarked upon by Mike. David
                    Message 9 of 14 , Apr 4, 2013
                    • 0 Attachment
                      --- In primenumbers@yahoogroups.com,
                      "WarrenS" <warren.wds@...> wrote:

                      > > The mistake is that all your remarks are about the so-called /dual/ Sierpinski problem.
                      > --which is... what?

                      Section 2 of the paper to which Wilfrid directed you
                      explains the diffrence between the SierpiĀ“nski problem
                      and its dual, as remarked upon by Mike.

                      David (atonally)
                    • djbroadhurst
                      ... Why might that seem weird to you, Warren? None of us should presuppose a monopoly on originality. Please see
                      Message 10 of 14 , Apr 4, 2013
                      • 0 Attachment
                        --- In primenumbers@yahoogroups.com,
                        "WarrenS" <warren.wds@...> wrote:

                        > It's just a bit weird that I thought I had a totally original
                        > problem, and it turns out it has been worked on a ton by others
                        > for years...

                        Why might that seem "weird" to you, Warren?
                        None of us should presuppose a monopoly on originality.

                        Please see
                        http://primes.utm.edu/primes/page.php?id=110402
                        > Kaiser1, Broadhurst, OpenPFGW, NewPGen, Primo
                        for a laborious ECPP proof of a prime relevant to
                        the dual Sierpi'nski problem:
                        http://oeis.org/A076336/a076336c.html
                        > 21661 61792 Broadhurst [May 20, 2002]

                        In this case, neither Peter Kaiser nor I claim originality,
                        which is indeed a scarce commodity.

                        David
                      • Maximilian Hasler
                        ... FWIW, the pages are still available at http://web.archive.org/http://www.csm.astate.edu/~wpaulsen/primemaze/pmaze.html Maximilian
                        Message 11 of 14 , Apr 4, 2013
                        • 0 Attachment
                          > And although Paulsen's links seem to be dead, here's a message from
                          > 10+ years ago, to this very mailing list, offering up the number 2131099:

                          FWIW, the pages are still available at
                          http://web.archive.org/http://www.csm.astate.edu/~wpaulsen/primemaze/pmaze.html

                          Maximilian
                        • djbroadhurst
                          ... and is dwarfed by http://www.primenumbers.net/prptop/detailprp.php?rank=1 ... David
                          Message 12 of 14 , Apr 4, 2013
                          • 0 Attachment
                            --- In primenumbers@yahoogroups.com,
                            "WarrenS" <warren.wds@...> wrote:

                            > this frightening number is a probable prime:
                            > 19249+2^551542

                            and is dwarfed by
                            http://www.primenumbers.net/prptop/detailprp.php?rank=1
                            > 2^9092392+40291

                            David
                          • Maximilian Hasler
                            ... If you paste this into OEIS (and probably google, too) you will immediately find A137985 which in the first comment links to A065092, which in turn
                            Message 13 of 14 , Apr 5, 2013
                            • 0 Attachment
                              >
                              > A prime P which turns into a composite if you alter any bit in
                              > its binary representation is an "every bit matters" prime.
                              >
                              > The examples below 10000 are
                              > 127, 173, 191, 223, 233, 239, 251, 257, 277, 337, 349, 373, 431, 443,
                              > ...

                              If you paste this into OEIS (and probably google, too)
                              you will immediately find A137985 which in the first comment links
                              to A065092, which in turn refers to Paulsen's Prime Numbers Maze.

                              Regards,
                              Maximilian
                            • Phil Carmody
                              ... There is something weird though - and that s that huge quantities of stuff I looked at a decade ago is being rediscovered by Warren. This makes my
                              Message 14 of 14 , Apr 9, 2013
                              • 0 Attachment
                                --- On Thu, 4/4/13, djbroadhurst wrote:
                                > "WarrenS" <warren.wds@...> wrote:
                                > > It's just a bit weird that I thought I had a totally original
                                > > problem, and it turns out it has been worked on a ton by others
                                > > for years...
                                >
                                > Why might that seem "weird" to you, Warren?
                                > None of us should presuppose a monopoly on originality.

                                There is something weird though - and that's that huge quantities of
                                stuff I looked at a decade ago is being rediscovered by Warren. This
                                makes my retirement from the field very hard, as he keeps posting
                                things that I've been directly interested in. However, I'm happy, as
                                a fresh mind approaching a problem can only ever increase the amount
                                that is known, never diminish it. In particular, whilst my arithmetic
                                may have been efficient, I was rarely good at the hard maths, so
                                hopefully Warren can get past the road-blocks that I had way back when.

                                Phil
                                --
                                () ASCII ribbon campaign () Hopeless ribbon campaign
                                /\ against HTML mail /\ against gratuitous bloodshed

                                [stolen with permission from Daniel B. Cristofani]
                              Your message has been successfully submitted and would be delivered to recipients shortly.