mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Five or Bust - The Dual Sierpinski Problem

Reply
 
Thread Tools
Old 2008-10-09, 23:04   #1
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

45F16 Posts
Default Welcome to "Five or Bust!"

The distributed computing project Seventeen or Bust is attempting to prove the following:

Conjecture: 78557 is the smallest positive odd integer ksuch that k\cdot 2^n+1 is composite for any positive integer n.

The method of inquiry is to attempt to find, for each positive odd k<78557, a positive integer value of n such that k\cdot 2^n+1 is prime. The name Seventeen or Bust was chosen because no such prime was known for exactly 17 such values of k when the project began. Currently, after the discovery of 11 large primes, there are 6 sequences which are still being tested for primes.

What happens if we allow n to take negative values? We have: k\cdot 2^{-n}+1={{k+2^n}\over{2^n}}. For k=78557, we can verify that the numerator 78557+2^n is composite for any positive integer n, and we make the following
Conjecture: 78557 is the smallest positive odd integer k such that k+2^n is composite for any positive integer n.

Again, we would like to find, for each positive odd k<78557, a positive integer n such that k+2^n is prime. Of the 39,278 such values of k, a proven prime value is known for all but 33 values. Of these 33, probable prime values of k+2^n are known for 28 of them. This leaves 5 values of k for which neither a prime nor a probable prime value of k+2^n is known. The primary purpose of this project is to search these 5 sequences for large probable primes. Hence, "Five or Bust".

There was an ongoing search on this problem in 2002, and Payam Samidoost maintained a web-site on the status entitled The dual Sierpinski problem search. I began searching the 8 unresolved sequences in August 2007, and I have discovered 3 more large probable primes. The most recent discovery, 8543+2^{1191375}, found in June, is currently listed at 358,640 decimal digits as the largest known probable prime at the website of Henri and Renaud Lifchitz, PRP Records, Probable Primes Top 10000. Numbers on this list have passed a number of tests, usually strong primality tests, that all prime numbers will pass and most composite numbers will fail. Because we do not have a factorization of N\pm 1, we cannot at present prove these numbers prime, but a theorem of Damgard, Landrock, and Pomerance implies for example that the probability that this large example is actually composite is less than 10^{-650}. This project is technically therefore not a prime search project, but rather a probable prime search project. As the current search limit on n is up to 1.4 million, any new discovery will qualify as a record probable prime, unless of course someone else finds a larger one in the meantime.

Because more k values are eliminated at smaller values of n, this "dual" Sierpinski search appears to be a little easier than the original search being pursued by Seventeen or Bust. On the other hand, because SB is searching for provable primes, they have the hope of actually producing a mathematical theorem as a result, whereas this search is only producing convincing evidence but not a proof.

The main two sub-projects are PRP testing and sieving. For now, PRP testing will be done with Prime95 version 25, and sieving can be done with Geoff's sr2sieve program. Details on how to get started are in those particular threads.

Last fiddled with by philmoore on 2011-02-17 at 00:14 Reason: replaced link to Samidoost's web-page with cached version
philmoore is offline   Reply With Quote
Old 2008-10-09, 23:25   #2
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

3×373 Posts
Default Proof that 78557 is a Sierpinski number

A Sierpinski number is an odd positive integer k such that k\cdot2^n+1 is composite for any positive integer n.

Theorem: 78557\cdot2^n+1 is composite for any positive integer n.
Proof:
If n\equiv 0 \bmod 2, 78557\cdot2^n+1 is divisible by 3.
If n\equiv 1 \bmod 4, 78557\cdot2^n+1 is divisible by 5.
If n\equiv 7 \bmod 12, 78557\cdot2^n+1 is divisible by 7.
If n\equiv 11 \bmod 12, 78557\cdot2^n+1 is divisible by 13.
If n\equiv 3 \bmod 36, 78557\cdot2^n+1 is divisible by 73.
If n\equiv 15 \bmod 36, 78557\cdot2^n+1 is divisible by 19.
If n\equiv 27 \bmod 36, 78557\cdot2^n+1 is divisible by 37.

It is instructive to compare this to the proof for the dual sequence:

Theorem: 78557+2^n is composite for any positive integer n.
Proof:
If n\equiv 0 \bmod 2, 78557+2^n is divisible by 3.
If n\equiv 3 \bmod 4, 78557+2^n is divisible by 5.
If n\equiv 5 \bmod 12, 78557+2^n is divisible by 7.
If n\equiv 1 \bmod 12, 78557+2^n is divisible by 13.
If n\equiv 33 \bmod 36, 78557+2^n is divisible by 73.
If n\equiv 21 \bmod 36, 78557+2^n is divisible by 19.
If n\equiv 9 \bmod 36, 78557+2^n is divisible by 37.
philmoore is offline   Reply With Quote
Old 2008-10-14, 21:56   #3
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

3·373 Posts
Default

I see that my probable prime record at
http://www.primenumbers.net/prptop/prptop.php
has just been displaced to #2, but I have no doubt that this project will find a new record. I would guess that we will find our first new probable prime in the range of n < 3 million.
philmoore is offline   Reply With Quote
Old 2008-10-15, 23:32   #4
gd_barnes
 
gd_barnes's Avatar
 
May 2007
Kansas; USA

25·17·19 Posts
Default

This is an EXCELLENT project idea, Phil!

I was curious about a similar-type effort on the Riesel side quite sometime back. I did a little searching here and there on it.

One of the things that I recall struck me as odd is that the lowest remaining k to not have a prime on the RieselSieve project, k=2293, also did not have a prime or PRP up to n=~100K for 2^n-2293. The k is so much smaller than any other remaining k that it is very surprising that it doesn't have a prime or PRP yet on either of the 'dual' sides.

One thing that makes such an effort unusual for Riesels is that you get into the case of negative numbers. In other words, do we consider -3, -5, -7, -11, etc. to be prime? I would think that most people would say no but others might debate otherwise.

I also did some PRP testing a while back for all k<20 up to n=~150K for 2^n-k and 2^n+k. A majority of it had already been done, as was evidenced by PRP's reported on the site that you mentioned, but I did find several PRP's for the larger k's in the group as well as a missing PRP for k=3 on one side so it was nice to know that double-checking does pay off from time to time.

My machines are pretty well tied up through the end of the year but I'll look to contribute here in early 2009.

Good luck with the project!


Gary


P.S. edit: I just now noticed that Phil's cat here is strumming one of its paws and its eyes blink. Pretty cool! lol

Last fiddled with by gd_barnes on 2008-10-15 at 23:36
gd_barnes is offline   Reply With Quote
Old 2010-02-23, 01:48   #5
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

24A916 Posts
Default

Phil went retro!
...but indeed his cat was always strumming
(it is even scarier when it stares without blinking):
Attached Images
 
Batalov is offline   Reply With Quote
Old 2010-02-23, 03:52   #6
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

21378 Posts
Default

Do you notice that I don't really blink? I just close my eyes halfway... don't want to miss anything.
philmoore is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
GQQ: a "deterministic" "primality" test in O(ln n)^2 Chair Zhuang Miscellaneous Math 21 2018-03-26 22:33
Stockfish game: "Move 8 poll", not "move 3.14159 discussion" MooMoo2 Other Chess Games 5 2016-10-22 01:55
Aouessare-El Haddouchi-Essaaidi "test": "if Mp has no factor, it is prime!" wildrabbitt Miscellaneous Math 11 2015-03-06 08:17
Would Minimizing "iterations between results file" may reveal "is not prime" earlier? nitai1999 Software 7 2004-08-26 18:12

All times are UTC. The time now is 11:36.

Sat Apr 10 11:36:17 UTC 2021 up 2 days, 6:17, 1 user, load averages: 2.61, 2.32, 1.93

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.