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

Re: [PrimeNumbers] Re: Sierpinski Problem

Expand Messages
  • Pavlos N
    This is exactly the case as you described it.If 5 didnt divide k,then we would have a finite covering set.But since 5/k then the numbers k*2^(4*m+2)+1 have an
    Message 1 of 12 , Aug 29, 2002
    • 0 Attachment
      This is exactly the case as you described it.If 5
      didnt divide k,then we would have a finite covering
      set.But since 5/k then the numbers k*2^(4*m+2)+1 have
      an algebraic factorization.
      Let k=r^4.Then:
      r^4*2^(4*m+2)+1=4*(r*2^m)^4+1
      =[2*(r*2^m)^2+2*(r*2^m)+1]*[2*(r*2^m)^2-2*(r*2^m)+1]=A*B
      I have not proven that A or B are divisible by
      infinitely many different primes as m varies ,but
      this seems very logical.
      I tried to prove it without success by assuming that
      there is a finite set of primes[p1,p2,,,pj] that
      divide A for every m>1 ,for a specific k.Then i used
      as a value for m,m=(p1-1)*(p2-1)*...*(pj-1) and tried
      to end up with something absurd.No luck.This is the
      most interesting part of my effort.The k's i found
      produce numbers k*2^n+1,some of which have factors
      belonging to a finite set and some of them have
      factors belonging to the set of primes that divide a
      polynomial.I dont know what step is next.Your valuable
      ideas are welcomed
      Pavlos
      --- jbrennen <jack@...> wrote:
      > --- In primenumbers@y..., Pavlos N <pavlos199@y...>
      > wrote:
      > > I managed to construct a Sierpinski multiplier k
      > such
      > > that k*2^n+1 is always composite for every n>1 and
      > > there is no finite set of primes that divide it.I
      > will
      > > post a more detailed email explaining exactly how
      > i
      > > worked and other details.For now on i post my
      > final
      > > result only.The k's belong to the following set of
      > > integers:
      > > k=(18446744073709551615*a+2039404931861161240)^4
      > > where a is a positive integer
      >
      > This is a really cool finding. I suspected that
      > such a multiplier
      > (or family of multipliers) was possible, but I never
      > thought of
      > using the fact that (4*x^4+1) has an algebraic
      > factorization. I
      > tried looking for k being a perfect cube or a fifth
      > power, with
      > no luck. Great work. :)
      >
      > So what we have here is:
      >
      > k*2^n+1 is of the form 4*x^4+1 if n
      > == 2 (mod 4)
      >
      > k mod 3 == 1 -> 3 | k*2^n+1 if n
      > == 1 (mod 2)
      > k mod 17 == 16 -> 17 | k*2^n+1 if n
      > == 0 (mod 8)
      > k mod 257 == 16 -> 257 | k*2^n+1 if n
      > == 4 (mod 16)
      > k mod 65537 == 16 -> 65537 | k*2^n+1 if n
      > == 12 (mod 32)
      > k mod 641 == 16 -> 641 | k*2^n+1 if n
      > == 28 (mod 64)
      > k mod 6700417 == -16 -> 6700417 | k*2^n+1 if n
      > == 60 (mod 64)
      >
      > Putting them together, k*2^n+1 is always composite.
      >
      > The requirement for k to be divisible by 5 is to
      > ensure that
      > when n == 2 (mod 4), that k*2^n+1 is not divisible
      > by 5 -- if
      > it is so divisible, then a finite covering set of
      > primes exists.
      >
      > So all that is left is to prove that for at least
      > one k in the
      > given group, no covering set S of primes exists such
      > that every
      > k*2^n+1 is divisible by a member of S. Please let
      > us in on this
      > aspect of the finding... How are you able to prove
      > the
      > non-existence of a finite covering set? Or is the
      > non-existence
      > of a finite covering set only a conjecture?
      >
      >
      >
      >


      __________________________________________________
      Do You Yahoo!?
      Yahoo! Finance - Get real-time stock quotes
      http://finance.yahoo.com
    • Phil Carmody
      ... Seconded. Pavlos, quite simply, this is a _brilliant_ discovery, and I take my hat off to you. It s definitely worth more investigation, thanks for sharing
      Message 2 of 12 , Aug 29, 2002
      • 0 Attachment
        --- jbrennen <jack@...> wrote:
        > --- In primenumbers@y..., Pavlos N <pavlos199@y...>
        > wrote:
        > > I managed to construct a Sierpinski multiplier k
        > such
        > > that k*2^n+1 is always composite for every n>1 and
        > > there is no finite set of primes that divide it.I
        > will
        > > post a more detailed email explaining exactly how
        > i
        > > worked and other details.For now on i post my
        > final
        > > result only.The k's belong to the following set of
        > > integers:
        > > k=(18446744073709551615*a+2039404931861161240)^4
        > > where a is a positive integer
        >
        > This is a really cool finding.

        Seconded.

        Pavlos, quite simply, this is a _brilliant_ discovery, and I take my hat off
        to you.

        It's definitely worth more investigation, thanks for sharing it with us.

        Phil


        =====
        "The hottest places in Hell are reserved for those who, in
        times of moral crisis, preserved their neutrality."
        -- John F. Kennedy, 24 June 1963, claiming to quote Dante,
        to whom this has been incorrectly attributed ever since.

        __________________________________________________
        Do You Yahoo!?
        Yahoo! Finance - Get real-time stock quotes
        http://finance.yahoo.com
      • Pavlos N
        I finally was able to prove that no finite covering set exists,that is,there are infinitely many primes that divide k*2^n+1 for the specific k s as n
        Message 3 of 12 , Aug 30, 2002
        • 0 Attachment
          I finally was able to prove that no finite covering
          set exists,that is,there are infinitely many primes
          that divide k*2^n+1 for the specific k's as n
          varies.The proof is available on request
          Regards
          Pavlos
          --- Pavlos N <pavlos199@...> wrote:
          > This is exactly the case as you described it.If 5
          > didnt divide k,then we would have a finite covering
          > set.But since 5/k then the numbers k*2^(4*m+2)+1
          > have
          > an algebraic factorization.
          > Let k=r^4.Then:
          > r^4*2^(4*m+2)+1=4*(r*2^m)^4+1
          >
          =[2*(r*2^m)^2+2*(r*2^m)+1]*[2*(r*2^m)^2-2*(r*2^m)+1]=A*B
          > I have not proven that A or B are divisible by
          > infinitely many different primes as m varies ,but
          > this seems very logical.
          > I tried to prove it without success by assuming that
          > there is a finite set of primes[p1,p2,,,pj] that
          > divide A for every m>1 ,for a specific k.Then i
          > used
          > as a value for m,m=(p1-1)*(p2-1)*...*(pj-1) and
          > tried
          > to end up with something absurd.No luck.This is the
          > most interesting part of my effort.The k's i found
          > produce numbers k*2^n+1,some of which have factors
          > belonging to a finite set and some of them have
          > factors belonging to the set of primes that divide a
          > polynomial.I dont know what step is next.Your
          > valuable
          > ideas are welcomed
          >
          > Pavlos
          > --- jbrennen <jack@...> wrote:
          > > --- In primenumbers@y..., Pavlos N
          > <pavlos199@y...>
          > > wrote:
          > > > I managed to construct a Sierpinski multiplier k
          > > such
          > > > that k*2^n+1 is always composite for every n>1
          > and
          > > > there is no finite set of primes that divide
          > it.I
          > > will
          > > > post a more detailed email explaining exactly
          > how
          > > i
          > > > worked and other details.For now on i post my
          > > final
          > > > result only.The k's belong to the following set
          > of
          > > > integers:
          > > > k=(18446744073709551615*a+2039404931861161240)^4
          > > > where a is a positive integer
          > >
          > > This is a really cool finding. I suspected that
          > > such a multiplier
          > > (or family of multipliers) was possible, but I
          > never
          > > thought of
          > > using the fact that (4*x^4+1) has an algebraic
          > > factorization. I
          > > tried looking for k being a perfect cube or a
          > fifth
          > > power, with
          > > no luck. Great work. :)
          > >
          > > So what we have here is:
          > >
          > > k*2^n+1 is of the form 4*x^4+1 if n
          > > == 2 (mod 4)
          > >
          > > k mod 3 == 1 -> 3 | k*2^n+1 if n
          > > == 1 (mod 2)
          > > k mod 17 == 16 -> 17 | k*2^n+1 if n
          > > == 0 (mod 8)
          > > k mod 257 == 16 -> 257 | k*2^n+1 if n
          > > == 4 (mod 16)
          > > k mod 65537 == 16 -> 65537 | k*2^n+1 if n
          > > == 12 (mod 32)
          > > k mod 641 == 16 -> 641 | k*2^n+1 if n
          > > == 28 (mod 64)
          > > k mod 6700417 == -16 -> 6700417 | k*2^n+1 if n
          > > == 60 (mod 64)
          > >
          > > Putting them together, k*2^n+1 is always
          > composite.
          > >
          > > The requirement for k to be divisible by 5 is to
          > > ensure that
          > > when n == 2 (mod 4), that k*2^n+1 is not divisible
          > > by 5 -- if
          > > it is so divisible, then a finite covering set of
          > > primes exists.
          > >
          > > So all that is left is to prove that for at least
          > > one k in the
          > > given group, no covering set S of primes exists
          > such
          > > that every
          > > k*2^n+1 is divisible by a member of S. Please let
          > > us in on this
          > > aspect of the finding... How are you able to
          > prove
          > > the
          > > non-existence of a finite covering set? Or is the
          > > non-existence
          > > of a finite covering set only a conjecture?
          > >
          > >
          > >
          > >
          >
          >
          > __________________________________________________
          > Do You Yahoo!?
          > Yahoo! Finance - Get real-time stock quotes
          > http://finance.yahoo.com
          >


          __________________________________________________
          Do You Yahoo!?
          Yahoo! Finance - Get real-time stock quotes
          http://finance.yahoo.com
        • Pavlos N
          I finally was able to prove that no finite covering set exists,that is,there are infinitely many primes that divide k*2^n+1 for the specific k s as n
          Message 4 of 12 , Aug 30, 2002
          • 0 Attachment
            I finally was able to prove that no finite covering
            set exists,that is,there are infinitely many primes
            that divide k*2^n+1 for the specific k's as n
            varies.The proof is available on request
            Regards
            Pavlos
            --- Pavlos N <pavlos199@...> wrote:
            > This is exactly the case as you described it.If 5
            > didnt divide k,then we would have a finite covering
            > set.But since 5/k then the numbers k*2^(4*m+2)+1
            > have
            > an algebraic factorization.
            > Let k=r^4.Then:
            > r^4*2^(4*m+2)+1=4*(r*2^m)^4+1
            >
            =[2*(r*2^m)^2+2*(r*2^m)+1]*[2*(r*2^m)^2-2*(r*2^m)+1]=A*B
            > I have not proven that A or B are divisible by
            > infinitely many different primes as m varies ,but
            > this seems very logical.
            > I tried to prove it without success by assuming that
            > there is a finite set of primes[p1,p2,,,pj] that
            > divide A for every m>1 ,for a specific k.Then i
            > used
            > as a value for m,m=(p1-1)*(p2-1)*...*(pj-1) and
            > tried
            > to end up with something absurd.No luck.This is the
            > most interesting part of my effort.The k's i found
            > produce numbers k*2^n+1,some of which have factors
            > belonging to a finite set and some of them have
            > factors belonging to the set of primes that divide a
            > polynomial.I dont know what step is next.Your
            > valuable
            > ideas are welcomed
            >
            > Pavlos
            > --- jbrennen <jack@...> wrote:
            > > --- In primenumbers@y..., Pavlos N
            > <pavlos199@y...>
            > > wrote:
            > > > I managed to construct a Sierpinski multiplier k
            > > such
            > > > that k*2^n+1 is always composite for every n>1
            > and
            > > > there is no finite set of primes that divide
            > it.I
            > > will
            > > > post a more detailed email explaining exactly
            > how
            > > i
            > > > worked and other details.For now on i post my
            > > final
            > > > result only.The k's belong to the following set
            > of
            > > > integers:
            > > > k=(18446744073709551615*a+2039404931861161240)^4
            > > > where a is a positive integer
            > >
            > > This is a really cool finding. I suspected that
            > > such a multiplier
            > > (or family of multipliers) was possible, but I
            > never
            > > thought of
            > > using the fact that (4*x^4+1) has an algebraic
            > > factorization. I
            > > tried looking for k being a perfect cube or a
            > fifth
            > > power, with
            > > no luck. Great work. :)
            > >
            > > So what we have here is:
            > >
            > > k*2^n+1 is of the form 4*x^4+1 if n
            > > == 2 (mod 4)
            > >
            > > k mod 3 == 1 -> 3 | k*2^n+1 if n
            > > == 1 (mod 2)
            > > k mod 17 == 16 -> 17 | k*2^n+1 if n
            > > == 0 (mod 8)
            > > k mod 257 == 16 -> 257 | k*2^n+1 if n
            > > == 4 (mod 16)
            > > k mod 65537 == 16 -> 65537 | k*2^n+1 if n
            > > == 12 (mod 32)
            > > k mod 641 == 16 -> 641 | k*2^n+1 if n
            > > == 28 (mod 64)
            > > k mod 6700417 == -16 -> 6700417 | k*2^n+1 if n
            > > == 60 (mod 64)
            > >
            > > Putting them together, k*2^n+1 is always
            > composite.
            > >
            > > The requirement for k to be divisible by 5 is to
            > > ensure that
            > > when n == 2 (mod 4), that k*2^n+1 is not divisible
            > > by 5 -- if
            > > it is so divisible, then a finite covering set of
            > > primes exists.
            > >
            > > So all that is left is to prove that for at least
            > > one k in the
            > > given group, no covering set S of primes exists
            > such
            > > that every
            > > k*2^n+1 is divisible by a member of S. Please let
            > > us in on this
            > > aspect of the finding... How are you able to
            > prove
            > > the
            > > non-existence of a finite covering set? Or is the
            > > non-existence
            > > of a finite covering set only a conjecture?
            > >
            > >
            > >
            > >
            >
            >
            > __________________________________________________
            > Do You Yahoo!?
            > Yahoo! Finance - Get real-time stock quotes
            > http://finance.yahoo.com
            >


            __________________________________________________
            Do You Yahoo!?
            Yahoo! Finance - Get real-time stock quotes
            http://finance.yahoo.com
          • Phil Carmody
            ... It seems that the proof of having a non-finite covering set for the original composite sierpinski form is mapped into either a proof of a non-finite
            Message 5 of 12 , Aug 30, 2002
            • 0 Attachment
              >
              > So all that is left is to prove that for at least one k in the
              > given group, no covering set S of primes exists such that every
              > k*2^n+1 is divisible by a member of S. Please let us in on this
              > aspect of the finding... How are you able to prove the
              > non-existence of a finite covering set? Or is the non-existence
              > of a finite covering set only a conjecture?

              It seems that the proof of having a non-finite covering set for the original
              composite sierpinski form is mapped into either a proof of a non-finite
              covering set for one of the Aurefeuillian factors or a proof of an infinite
              number of primes along either of the Aurefeuillian factors.

              Now the former just looks like it converts the original problem into a
              tricker form.

              The latter requests an infiniteness of primes along an exponentially growing
              set of values, and as far as I know no such form has been proven to yield an
              infinite number of primes, even if the heuristics indicate that's the case.
              The heuristics are more favourable than that for Mersennes, for example, but
              heuristics count for little.


              To be honest, I think the 'trickier' line of tack looks like the easier one
              - either expect something brainstorm-like in the next day or so. (I _think_
              I have something that might lead to a proof, but it's early in the morning,
              and I can't tell one end of an implication from the other present!)


              Phil


              =====
              "The hottest places in Hell are reserved for those who, in
              times of moral crisis, preserved their neutrality."
              -- John F. Kennedy, 24 June 1963, claiming to quote Dante,
              to whom this has been incorrectly attributed ever since.

              __________________________________________________
              Do You Yahoo!?
              Yahoo! Finance - Get real-time stock quotes
              http://finance.yahoo.com
            • Phil Carmody
              ... [Brough back on list] Indeed - It s Pavlos baby, and he should certainly put it on as many tables as possible. If I don t see it reach sci.math
              Message 6 of 12 , Aug 30, 2002
              • 0 Attachment
                --- Paul Leyland <pleyland@...> wrote:
                > > To be honest, I think the 'trickier' line of tack looks like
                > > the easier one
                > > - either expect something brainstorm-like in the next day or
                > > so. (I _think_
                > > I have something that might lead to a proof, but it's early
                > > in the morning,
                > > and I can't tell one end of an implication from the other present!)
                >
                > This might now be interesting to throw open to the NMBTHRY people...

                [Brough back on list]

                Indeed - It's Pavlos' baby, and he should certainly put it on as many tables
                as possible. If I don't see it reach sci.math (.research, I don't think Dave
                will have any problem accepting it) in the next day or so I shall forward it
                on there.

                Alas my battle with the infinite is lost. Two monster holes -
                No matter how many primes I shoved into a covering set I couldn't
                make an infinite one! :-I I was trying to show that for every finite
                non-covering set there existed a prime that would be a factor, and not make
                the set covering one.

                However, this logic would have be more easily applicable to the
                Sierpinski/Proth domain, and has failed there, so fails in the new domain
                too.

                These discrete-log-based sieves are a pain in the neck!

                The interesting thing about these Aurefeuillian factorisations is that the
                divisibility properties are both quadratic and discrete-log based, which
                means that you get a sieving removal ratio of either 0 or 2b/(p-1) where b
                is related to O2(p), depending on the discriminant of the quadratic.
                e.g. consider the + factor and the prime 41, it divides terms
                (n-2)/4=6,11,26,31,46,51... .
                A quadratic sieve divides (0 or 2)/(p-1) and a discrete-log sieve divides
                1/(factor of p-1), but this combines the two.

                On the infiniteness of primes front, with all these double-barreled factors,
                the density looks somewhat sparse: (n-2)/4 = 32, 53, 92, 109, 110, 137, 302,
                401, 1205, 1241... for the + factor.

                Ah well, it's nice to spin one's wheels and make doughnuts occasionally.
                Hmmm, donuts!

                Phil


                =====
                "The hottest places in Hell are reserved for those who, in
                times of moral crisis, preserved their neutrality."
                -- John F. Kennedy, 24 June 1963, claiming to quote Dante,
                to whom this has been incorrectly attributed ever since.

                __________________________________________________
                Do You Yahoo!?
                Yahoo! Finance - Get real-time stock quotes
                http://finance.yahoo.com
              • Phil Carmody
                ... Note that there are infinitely many primes that divide k*2^n+1 for the specific k s as n varies is _not_ the equivalent of there being no finite covering
                Message 7 of 12 , Aug 30, 2002
                • 0 Attachment
                  --- Pavlos N <pavlos199@...> wrote:
                  > I finally was able to prove that no finite covering
                  > set exists,that is,there are infinitely many primes
                  > that divide k*2^n+1 for the specific k's as n
                  > varies.The proof is available on request

                  Note that "there are infinitely many primes that divide k*2^n+1 for the
                  specific k's as n varies" is _not_ the equivalent of there being no finite
                  covering set. (I know the "that is" was probably informative rather than
                  definitive, but when proofs are concerned all ambiguities should be cleared
                  up.)

                  Can you please upload the proof to the yahoogroup files area, so interested
                  parties such as myself, Jack, Paul etc. can have a peek?

                  Cheers,
                  Phil


                  =====
                  "The hottest places in Hell are reserved for those who, in
                  times of moral crisis, preserved their neutrality."
                  -- John F. Kennedy, 24 June 1963, claiming to quote Dante,
                  to whom this has been incorrectly attributed ever since.

                  __________________________________________________
                  Do You Yahoo!?
                  Yahoo! Finance - Get real-time stock quotes
                  http://finance.yahoo.com
                • jbrennen
                  Note that there is a subset of Pavlos numbers which do in fact have a finite covering set, and that this subset has positive density. The following covering
                  Message 8 of 12 , Aug 30, 2002
                  • 0 Attachment
                    Note that there is a subset of Pavlos' numbers which do in fact have
                    a finite covering set, and that this subset has positive density.

                    The following covering set can be used to construct a value of
                    k=z^4 for which k*2^(4n+2)+1 is always divisible by at least one
                    member of the set:

                    13, 37, 73, 109, 241, 97, 673

                    The order of 16 modulo each of these primes is:

                    3, 9, 9, 9, 6, 12, 12

                    One such example would be where

                    z == 43765077179683 (mod 60214110539557)

                    So combining this with Pavlos' condition...

                    z == 1097007512506034898075831581637010
                    (mod 1110754286749264941174792190734555)

                    implies that k=z^4 is in Pavlos' set, yet has a finite covering set.

                    A quick check in PARI/GP:

                    m=2^64-1;
                    z=1097007512506034898075831581637010;
                    k=z^4;
                    ss=(m/5)*(13*37*73*109*241*97*673);
                    print("z mod ",m," == ",z%m);
                    for(n=0,9999,if(gcd(k*2^n+1,ss)==1,print("Failure")))
                  • djbroadhurst
                    Just looked in between trips. Skipping predictable Brown trash, I saw a really _neat_ thing by Pavlos Saridis: To make N=k*2^n+1 always composite [Saridis]: a)
                    Message 9 of 12 , Aug 31, 2002
                    • 0 Attachment
                      Just looked in between trips. Skipping predictable
                      Brown trash, I saw a really _neat_ thing by
                      Pavlos Saridis:

                      To make N=k*2^n+1 always composite [Saridis]:

                      a) take k=x^4 so that for n=4*s+2 we have an
                      algebraic factorization

                      N=(2*y^2-2*y+1)*(2*y^2+2*y+1) with y=2^s*x

                      b) find a covering set for n != 2 mod 4

                      c) if desired, make x=0 mod 5, so that p=5
                      does not cover what you did with Aurifeuille in (a)

                      Question: What is the smallest k=x^4 for which
                      this can be done, with and without the grace note (c)?

                      Back in a few weeks time...

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