Seventeen or Bust

Last updated

Seventeen or Bust is a volunteer computing project started in March 2002 to solve the last seventeen cases in the Sierpinski problem. The project solved eleven cases before a server loss in April 2016 forced it to cease operations. Work on the Sierpinski problem moved to PrimeGrid, which solved a twelfth case in October 2016. [1] Five cases remain unsolved as of June 2024. [2]

Contents

Goals

Seventeen or Bust old client Sob client1.gif
Seventeen or Bust old client

The goal of the project is to prove that 78557 is the smallest Sierpinski number, that is, the least odd k such that k·2n+1 is composite (i.e. not prime) for all n > 0. When the project began, there were only seventeen values of k < 78557 for which the corresponding sequence was not known to contain a prime.

For each of those seventeen values of k, the project searches for a prime number in the sequence

k·21+1, k·22+1, …, k·2n+1, …

testing candidate values n using Proth's theorem. If one is found, it proves that k is not a Sierpinski number. If this is done for all seventeen values, the conjectured answer 78557 to the Sierpinski problem will be proven true.

There is also the possibility that some of the sequences contain no prime numbers. In that case, the search will continue forever, searching for prime numbers where none can be found. However, there is empirical evidence suggesting the conjecture is true. [3]

Every known Sierpinski number k has a small covering set , a finite set of primes with at least one dividing k·2n+1 for each n>0 (or else k has algebraic factorizations for some n values and a finite prime set that works only for the remaining n). [4] For example, for the smallest known Sierpinski number, 78557, the covering set is {3,5,7,13,19,37,73}. By considering the possible values of n modulo 36, it can be shown that one of these primes is always a factor. For another known Sierpinski number, 271129, the covering set is {3,5,7,13,17,241}. Each of the remaining sequences has been tested and none has a small covering set, so it is suspected that each of them contains primes.

The second generation of the client was based on Prime95, which is used in the Great Internet Mersenne Prime Search. In January 2010, the Seventeen or Bust project started collaboration with PrimeGrid which uses the software LLR for its tests related to the Sierpinski problem. [2]

The Seventeen or Bust server went down during April 2016, when the server and backups were lost for reasons that were not revealed to the public. The independent project is no longer active, but work on the problem continues at PrimeGrid under the same name. [5] [6]

Twelve prime numbers have been found to date, eleven by the original Seventeen or Bust, and a twelfth by PrimeGrid's SoB project: [2]

knDigits of k·2n+1Date of discoveryFound by
46,157 698,207 210,18626 Nov 2002Stephen Gibson
65,567 1,013,803 305,19003 Dec 2002James Burt
44,131 995,972 299,82306 Dec 2002deviced (nickname)
69,109 1,157,446 348,43107 Dec 2002Sean DiMichele
54,767 1,337,287 402,56922 Dec 2002Peter Coels
5,359 5,054,502 1,521,56106 Dec 2003Randy Sundquist
28,433 7,830,457 2,357,20730 Dec 2004Anonymous
27,653 9,167,433 2,759,67708 Jun 2005Derek Gordon
4,847 3,321,063 999,74415 Oct 2005Richard Hassler
19,249 13,018,586 3,918,99026 Mar 2007Konstantin Agafonov
33,661 7,031,232 2,116,61713 Oct 2007Sturle Sunde
10,223 31,172,165 9,383,76131 Oct 2016 [7] [1] Péter Szabolcs
21,181≳ 41,600,00012,538,309(Search in progress)
22,699≳ 41,800,00012,605,752(Search in progress)
24,737≳ 41,600,00012,523,328(Search in progress)
55,459≳ 41,600,00012,524,236(Search in progress)
67,607≳ 41,700,00012,581,713(Search in progress)

The largest of these primes, 10223·231172165+1, held the record as the largest known prime number that is not a Mersenne prime from October 2016 until May 2023. [8] The primes on this list over one million digits in length are the six known "Colbert numbers" whimsically named after Stephen Colbert. These are defined as primes which eliminate a remaining Sierpinski number candidate. [9] [10]

Each of these numbers has enough digits to fill up a medium-sized novel, at least. The project was dividing numbers among its active users, in hope of finding a prime number in each of the five remaining sequences:

k·2n+1, for k = 21181, 22699, 24737, 55459, 67607.

In March 2017, n had exceeded 31,000,000 for the last five k values. At that time, PrimeGrid decided to suspend testing to do a double check of all those smaller n values for which the Proth test residue had been lost, or for which the result had not been successfully verified by two independent computations on different computers. [11] Testing resumed after the double check was finally completed on October 10, 2019, taking about two and a half years. [12]

The current status for the remaining multipliers can be seen at PrimeGrid's website. [13]

Modular restrictions

Every multiplier has modular restrictions for the exponent n, assuming the latter exists. For example, for k = 21,181, it is sufficient to check only values of n congruent to 20 (mod 24); the covering set for all other terms is {3, 5, 7, 13, 17}. Similarly, for k = 22,699, only terms with n congruent to 46 (mod 72) are candidates, as the set of all other terms have covering set {3, 5, 7, 13, 17, 19, 73}.[ citation needed ]

See also

Related Research Articles

In mathematics, a Mersenne prime is a prime number that is one less than a power of two. That is, it is a prime number of the form Mn = 2n − 1 for some integer n. They are named after Marin Mersenne, a French Minim friar, who studied them in the early 17th century. If n is a composite number then so is 2n − 1. Therefore, an equivalent definition of the Mersenne primes is that they are the prime numbers of the form Mp = 2p − 1 for some prime p.

<span class="mw-page-title-main">Prime number</span> Number divisible only by 1 or itself

A prime number is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways of writing it as a product, 1 × 5 or 5 × 1, involve 5 itself. However, 4 is composite because it is a product (2 × 2) in which both numbers are smaller than 4. Primes are central in number theory because of the fundamental theorem of arithmetic: every natural number greater than 1 is either a prime itself or can be factorized as a product of primes that is unique up to their order.

In mathematics, a Fermat number, named after Pierre de Fermat, the first known to have studied them, is a positive integer of the form: where n is a non-negative integer. The first few Fermat numbers are: 3, 5, 17, 257, 65537, 4294967297, 18446744073709551617, ....

In number theory, a Sierpiński number is an odd natural number k such that is composite for all natural numbers n. In 1960, Wacław Sierpiński proved that there are infinitely many odd integers k which have this property.

In mathematics, a Cullen number is a member of the integer sequence . Cullen numbers were first studied by James Cullen in 1905. The numbers are special cases of Proth numbers.

In mathematics, a Riesel number is an odd natural number k for which is composite for all natural numbers n. In other words, when k is a Riesel number, all members of the following set are composite:

73 (seventy-three) is the natural number following 72 and preceding 74. In English, it is the smallest natural number with twelve letters in its spelled out name.

600 is the natural number following 599 and preceding 601.

2000 is a natural number following 1999 and preceding 2001.

In number theory, a nontotient is a positive integer n which is not a totient number: it is not in the range of Euler's totient function φ, that is, the equation φ(x) = n has no solution x. In other words, n is a nontotient if there is no integer x that has exactly n coprimes below it. All odd numbers are nontotients, except 1, since it has the solutions x = 1 and x = 2. The first few even nontotients are this sequence:

John Lewis Selfridge, was an American mathematician who contributed to the fields of analytic number theory, computational number theory, and combinatorics.

In mathematics, a covering set for a sequence of integers refers to a set of prime numbers such that every term in the sequence is divisible by at least one member of the set. The term "covering set" is used only in conjunction with sequences possessing exponential growth.

In number theory, Proth's theorem is a primality test for Proth numbers.

<span class="mw-page-title-main">PrimeGrid</span> BOINC based volunteer computing project researching prime numbers

PrimeGrid is a volunteer computing project that searches for very large prime numbers whilst also aiming to solve long-standing mathematical conjectures. It uses the Berkeley Open Infrastructure for Network Computing (BOINC) platform. PrimeGrid offers a number of subprojects for prime-number sieving and discovery. Some of these are available through the BOINC client, others through the PRPNet client. Some of the work is manual, i.e. it requires manually starting work units and uploading results. Different subprojects may run on different operating systems, and may have executables for CPUs, GPUs, or both; while running the Lucas–Lehmer–Riesel test, CPUs with Advanced Vector Extensions and Fused Multiply-Add instruction sets will yield the fastest results for non-GPU accelerated workloads.

Riesel Sieve was a volunteer computing project, running in part on the BOINC platform. Its aim was to prove that 509,203 is the smallest Riesel number, by finding a prime of the form k × 2n − 1 for all odd k smaller than 509,203.

20,000 is the natural number that comes after 19,999 and before 20,001.

60,000 is the natural number that comes after 59,999 and before 60,001. It is a round number. It is the value of (75025).

In mathematics, the Lucas–Lehmer–Riesel test is a primality test for numbers of the form N = k ⋅ 2n − 1 with odd k < 2n. The test was developed by Hans Riesel and it is based on the Lucas–Lehmer primality test. It is the fastest deterministic algorithm known for numbers of that form. For numbers of the form N = k ⋅ 2n + 1, either application of Proth's theorem or one of the deterministic proofs described in Brillhart–Lehmer–Selfridge 1975 are used.

A Proth number is a natural number N of the form where k and n are positive integers, k is odd and . A Proth prime is a Proth number that is prime. They are named after the French mathematician François Proth. The first few Proth primes are

References

  1. 1 2 "PrimeGrid's Seventeen or Bust Subproject, Official Announcement" (PDF). 2016. Archived (PDF) from the original on 2016-11-12. Retrieved 2020-04-27.
  2. 1 2 3 Michael Goetz. "Seventeen or Bust and the Sierpinski Problem (PrimeGrid Forum)". Archived from the original on 2020-04-26. Retrieved 2020-04-27.
  3. Chris Caldwell. "Sierpinski number". Archived from the original on 2017-11-13. Retrieved 2008-02-27.
  4. "Does every Sierpinski number have a finite congruence covering?". Stack Exchange . March 4, 2016.
  5. Michael Goetz. "Re: Server down?". Archived from the original on 28 June 2016.
  6. Michael Goetz. "Re: Update on seventeenorbust.com". Archived from the original on 2020-08-05. Retrieved 2020-04-27.
  7. "PrimeGrid Forum thread". Archived from the original on 2020-08-09. Retrieved 2020-04-27.
  8. "The Top Twenty Largest Known Primes". The Prime Pages . Archived from the original on 16 July 2012. Retrieved 7 November 2016.
  9. Colbert Number - from Wolfram MathWorld Archived 2010-03-26 at the Wayback Machine . Mathworld.wolfram.com (2009-04-05). Retrieved on 2014-05-11.
  10. The Prime Glossary: Colbert number Archived 2013-12-15 at the Wayback Machine . Primes.utm.edu. Retrieved on 2014-05-11.
  11. Michael Goetz (20 Mar 2017). "The SoB Double Check has begun". PrimeGrid Forum. Archived from the original on 4 April 2020. Retrieved 27 April 2020.
  12. Michael Goetz (10 Oct 2019). "The SoB Double Check is DONE!!!". PrimeGrid Forum. Archived from the original on 2 July 2017. Retrieved 27 April 2020.
  13. "Seventeen or Bust statistics". PrimeGrid. Archived from the original on 2020-04-06. Retrieved 2020-04-06.