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

Sierpinski covering sets

Expand Messages
  • mikeoakes2
    I have established the following result:- For each of the 6 currently remaining candidates for the smallest Sierpinski number, no covering set of primes, with
    Message 1 of 6 , Dec 10, 2009
    • 0 Attachment
      I have established the following result:-

      For each of the 6 currently remaining candidates for the smallest Sierpinski number,
      no covering set of primes, with arbitrary many elements, each of magnitude <= 4*10^9, exists.

      This adds enormous confidence to the working assumption that none of them are indeed Sierpinski numbers.

      Here is the pari-gp script:-

      /*
      A Sierpinski number is such that, for fixed k, (k*2^n+1) is composite for all n >= 1.
      As of December 2009, there are only six candidates:
      k = 10223, 21181, 22699, 24737, 55459, and 67607
      which have not been eliminated as possible Sierpinski numbers.
      */
      {
      p_max=4000000000; \\approx. max supported by pari
      default(primelimit,p_max)
      n_max=1000; \\alter as nec.
      print("searching for Sierpinski covering sets for k in {10223,21181,22699,24737,55459,67607} with n_max="n_max" p_max="p_max);
      forstep (k=10223,67607,[21181-10223,22699-21181,24737-22699,55459-24737,67607-55459],
      print("k="k);
      pow_n=1;
      cover_found=1; \\default
      for (n=1,n_max,
      pow_n=pow_n*2;
      u=k*pow_n+1;
      divisor_found=0;
      forprime(p=2,p_max,
      if(u%p==0,
      divisor_found=1;
      break;
      ); \\end if
      ); \\end forprime p
      if (!divisor_found,
      print("k="k": no divisor found for n="n);
      cover_found=0;
      break;
      ); \\ end if
      ); \\end for n
      if (cover_found,
      print("k="k": covering set found");
      ); \\end if
      ); \\end forstep k
      t=gettime;
      print(" took "t" ms");
      }

      =>

      searching for Sierpinski cover sets for k in {10223,21181,22699,24737,55459,67607} with n_max=1000 p_max=4000000000
      k=10223: no divisor found for n=101
      k=21181: no divisor found for n=620
      k=22699: no divisor found for n=190
      k=24737: no divisor found for n=607
      k=55459: no divisor found for n=706
      k=67607: no divisor found for n=531
      took 905422 ms
      Goodbye!

      I wonder: is this an improvement on existing "no covering set" results for the Sierpinski problem?

      -Mike Oakes
    • Jack Brennen
      Isn t this (for example) a much easier way to show that 10223 has no such covering set: 10223*2^137+1 == 1904660910466121 * 935125926286211318869570932217
      Message 2 of 6 , Dec 10, 2009
      • 0 Attachment
        Isn't this (for example) a much easier way to show that 10223
        has no such covering set:

        10223*2^137+1 ==
        1904660910466121 * 935125926286211318869570932217

        Implying of course that any covering set for 10223 includes
        one of those two primes...

        mikeoakes2 wrote:
        > I have established the following result:-
        >
        > For each of the 6 currently remaining candidates for the smallest Sierpinski number,
        > no covering set of primes, with arbitrary many elements, each of magnitude <= 4*10^9, exists.
        >
        > This adds enormous confidence to the working assumption that none of them are indeed Sierpinski numbers.
        >
        > Here is the pari-gp script:-
        >
        > /*
        > A Sierpinski number is such that, for fixed k, (k*2^n+1) is composite for all n >= 1.
        > As of December 2009, there are only six candidates:
        > k = 10223, 21181, 22699, 24737, 55459, and 67607
        > which have not been eliminated as possible Sierpinski numbers.
        > */
        > {
        > p_max=4000000000; \\approx. max supported by pari
        > default(primelimit,p_max)
        > n_max=1000; \\alter as nec.
        > print("searching for Sierpinski covering sets for k in {10223,21181,22699,24737,55459,67607} with n_max="n_max" p_max="p_max);
        > forstep (k=10223,67607,[21181-10223,22699-21181,24737-22699,55459-24737,67607-55459],
        > print("k="k);
        > pow_n=1;
        > cover_found=1; \\default
        > for (n=1,n_max,
        > pow_n=pow_n*2;
        > u=k*pow_n+1;
        > divisor_found=0;
        > forprime(p=2,p_max,
        > if(u%p==0,
        > divisor_found=1;
        > break;
        > ); \\end if
        > ); \\end forprime p
        > if (!divisor_found,
        > print("k="k": no divisor found for n="n);
        > cover_found=0;
        > break;
        > ); \\ end if
        > ); \\end for n
        > if (cover_found,
        > print("k="k": covering set found");
        > ); \\end if
        > ); \\end forstep k
        > t=gettime;
        > print(" took "t" ms");
        > }
        >
        > =>
        >
        > searching for Sierpinski cover sets for k in {10223,21181,22699,24737,55459,67607} with n_max=1000 p_max=4000000000
        > k=10223: no divisor found for n=101
        > k=21181: no divisor found for n=620
        > k=22699: no divisor found for n=190
        > k=24737: no divisor found for n=607
        > k=55459: no divisor found for n=706
        > k=67607: no divisor found for n=531
        > took 905422 ms
        > Goodbye!
        >
        > I wonder: is this an improvement on existing "no covering set" results for the Sierpinski problem?
        >
        > -Mike Oakes
        >
        >
        >
        >
        >
        > ------------------------------------
        >
        > Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
        > The Prime Pages : http://www.primepages.org/
        >
        > Yahoo! Groups Links
        >
        >
        >
        >
        >
      • mikeoakes2
        ... Yes, Jack, you are of course quite right. Thanks for pointing that out so neatly. Stepping back from the code, I realized quite soon after posting that all
        Message 3 of 6 , Dec 10, 2009
        • 0 Attachment
          --- In primenumbers@yahoogroups.com, Jack Brennen <jfb@...> wrote:
          >
          > Isn't this (for example) a much easier way to show that 10223
          > has no such covering set:
          >
          > 10223*2^137+1 ==
          > 1904660910466121 * 935125926286211318869570932217
          >
          > Implying of course that any covering set for 10223 includes
          > one of those two primes...
          >

          Yes, Jack, you are of course quite right. Thanks for pointing that out so neatly.

          Stepping back from the code, I realized quite soon after posting that all it did was find, for each k, any n value that gave a large smallest factor, and that is achievable with lots of off-the-shelf sieving and factorizing programs.

          Mike
        • Jens Kruse Andersen
          ... A Google search of 1904660910466121 finds http://www.math.sc.edu/~filaseta/papers/SierpinskiEtCoPapNew.pdf They reached the same factorization as Jack and
          Message 4 of 6 , Dec 10, 2009
          • 0 Attachment
            Jack Brennen wrote:
            > 10223*2^137+1 ==
            > 1904660910466121 * 935125926286211318869570932217

            A Google search of 1904660910466121 finds
            http://www.math.sc.edu/~filaseta/papers/SierpinskiEtCoPapNew.pdf
            They reached the same factorization as Jack and listed:

            n, smallest prime factor of 10223*2^n+1
            77 619033
            101 45677096693
            137 1904660910466121

            The next n with no factor below 10^9 is 509.
            What is the smallest factor of 10223*2^509+1?
            It is probably above 10^30.

            --
            Jens Kruse Andersen
          • mikeoakes2
            ... In defence of my code, it solved all 6 cases in 15 mins, without my having to depend on referring to web pages of known factorisations, which are the
            Message 5 of 6 , Dec 10, 2009
            • 0 Attachment
              --- In primenumbers@yahoogroups.com, Jack Brennen <jfb@...> wrote:
              >
              > Isn't this (for example) a much easier way to show that 10223
              > has no such covering set:
              >
              > 10223*2^137+1 ==
              > 1904660910466121 * 935125926286211318869570932217
              >
              > Implying of course that any covering set for 10223 includes
              > one of those two primes...
              >

              In defence of my code, it solved all 6 cases in 15 mins, without my having to depend on referring to web pages of known factorisations, which are the result of significant computational effort, and which you perhaps used to find that n=137 index among the the prima facie hundreds to choose from?

              Mike
            • Jack Brennen
              No significant computational effort needed for this case. PARI code:
              Message 6 of 6 , Dec 10, 2009
              • 0 Attachment
                No significant computational effort needed for this case. PARI code:

                k=10223;for(i=1,200,f=factorint(k*2^i+1,15);if(length(f[,1])==1,print([k,i,factorint(k*2^i+1)])))

                Runs with elapsed time about 2 seconds. Output:

                [10223, 77, [619033, 1; 2495595681878097381929, 1]]
                [10223, 101, [45677096693, 1; 325387086953, 1; 1743849966293, 1]]
                [10223, 137, [1904660910466121, 1; 935125926286211318869570932217, 1]]

                It's also quick to find one for 22699 which has no small factors:

                [22699, 190, [84884846681, 1;
                419638892754915061028443044698201980071935256023017, 1]]


                Unfortunately, the other 4 candidates don't present such
                low-hanging fruit; their k*2^n+1 numbers either have small
                factors, or they are too big to factor quickly.



                mikeoakes2 wrote:
                >
                >
                > --- In primenumbers@yahoogroups.com, Jack Brennen <jfb@...> wrote:
                >> Isn't this (for example) a much easier way to show that 10223
                >> has no such covering set:
                >>
                >> 10223*2^137+1 ==
                >> 1904660910466121 * 935125926286211318869570932217
                >>
                >> Implying of course that any covering set for 10223 includes
                >> one of those two primes...
                >>
                >
                > In defence of my code, it solved all 6 cases in 15 mins, without my having to depend on referring to web pages of known factorisations, which are the result of significant computational effort, and which you perhaps used to find that n=137 index among the the prima facie hundreds to choose from?
                >
                > Mike
                >
                >
                >
                > ------------------------------------
                >
                > Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
                > The Prime Pages : http://www.primepages.org/
                >
                > Yahoo! Groups Links
                >
                >
                >
                >
                >
              Your message has been successfully submitted and would be delivered to recipients shortly.