mersenneforum.org Welcome to "Five or Bust!"
 Register FAQ Search Today's Posts Mark Forums Read

 2008-10-09, 23:04 #1 philmoore     "Phil" Sep 2002 Tracktown, U.S.A. 45F16 Posts 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 $k$such 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
 2008-10-09, 23:25 #2 philmoore     "Phil" Sep 2002 Tracktown, U.S.A. 3×373 Posts 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.
 2008-10-14, 21:56 #3 philmoore     "Phil" Sep 2002 Tracktown, U.S.A. 3·373 Posts 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.
 2008-10-15, 23:32 #4 gd_barnes     May 2007 Kansas; USA 25·17·19 Posts 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
 2010-02-23, 01:48 #5 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 24A916 Posts Phil went retro! ...but indeed his cat was always strumming (it is even scarier when it stares without blinking): Attached Images
 2010-02-23, 03:52 #6 philmoore     "Phil" Sep 2002 Tracktown, U.S.A. 21378 Posts Do you notice that I don't really blink? I just close my eyes halfway... don't want to miss anything.

 Similar Threads Thread Thread Starter Forum Replies Last Post Chair Zhuang Miscellaneous Math 21 2018-03-26 22:33 MooMoo2 Other Chess Games 5 2016-10-22 01:55 wildrabbitt Miscellaneous Math 11 2015-03-06 08:17 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