Welcome to "Five or Bust!"

philmoore · 2008-10-09, 23:04

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.

philmoore · 2008-10-09, 23:25

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 · 2008-10-14, 21:56

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.

gd_barnes · 2008-10-15, 23:32

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

Batalov · 2010-02-23, 01:48

Phil went retro!
...but indeed his cat was always strumming
(it is even scarier when it stares without blinking):

philmoore · 2010-02-23, 03:52

Do you notice that I don't really blink? I just close my eyes halfway... don't want to miss anything.

2008-10-09, 23:04	#1
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 3·373 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-15, 23:32	#4
gd_barnes May 2007 Kansas; USA 10100010011011₂ 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 2²·23·103 Posts	Phil went retro! ...but indeed his cat was always strumming (it is even scarier when it stares without blinking): Attached Images

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

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. 1119₁₀ 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.

2010-02-23, 03:52	#6
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 3×373 Posts	Do you notice that I don't really blink? I just close my eyes halfway... don't want to miss anything.