PrimeGrid

Sponsored by:

Hosted at and sponsored by Rackspace.

Join PrimeGrid

Returning Participants

Community

Leader Boards

Results

Other

drummers-lowrise

Advanced search

Message boards : Prime Sierpinski Problem : About the Prime Sierpinski Problem

Author Message
Michael GoetzProject donor
Volunteer moderator
Project scientist
Avatar
Send message
Joined: 21 Jan 10
Posts: 9161
ID: 53948
Credit: 99,710,609
RAC: 7,967
321 LLR Amethyst: Earned 1,000,000 credits (1,006,834)Cullen LLR Amethyst: Earned 1,000,000 credits (1,157,331)ESP LLR Amethyst: Earned 1,000,000 credits (1,179,211)Generalized Cullen/Woodall LLR Amethyst: Earned 1,000,000 credits (1,048,769)PPS LLR Amethyst: Earned 1,000,000 credits (1,241,722)PSP LLR Ruby: Earned 2,000,000 credits (2,632,269)SoB LLR Ruby: Earned 2,000,000 credits (2,003,279)SR5 LLR Turquoise: Earned 5,000,000 credits (5,605,559)SGS LLR Amethyst: Earned 1,000,000 credits (1,457,144)TRP LLR Amethyst: Earned 1,000,000 credits (1,009,313)Woodall LLR Amethyst: Earned 1,000,000 credits (1,145,077)321 Sieve (suspended) Silver: Earned 100,000 credits (200,576)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,170,256)Generalized Cullen/Woodall Sieve Ruby: Earned 2,000,000 credits (2,085,723)PPS Sieve Jade: Earned 10,000,000 credits (18,162,350)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,035,522)TRP Sieve (suspended) Ruby: Earned 2,000,000 credits (2,051,121)AP 26/27 Turquoise: Earned 5,000,000 credits (5,877,196)GFN Sapphire: Earned 20,000,000 credits (37,214,567)PSA Turquoise: Earned 5,000,000 credits (9,426,791)
Message 9502 - Posted: 10 Jul 2008 | 17:26:42 UTC
Last modified: 26 Jan 2017 | 15:38:49 UTC

About the Prime Sierpinski Problem

Wacław Franciszek Sierpiński (14 March 1882 — 21 October 1969), a Polish mathematician, was known for outstanding contributions to set theory, number theory, theory of functions and topology. It is in number theory where we find the Sierpinski problem.

Basically, the Sierpinski problem is "What is the smallest Sierpinski number" and the prime Sierpinski problem is "What is the smallest 'prime' Sierpinski number?"

First we look at Proth numbers (named after the French mathematician François Proth). A Proth number is a number of the form k*2^n+1 where k is odd, n is a positive integer, and 2^n>k.

A Sierpinski number is an odd k such that the Proth number k*2^n+1 is not prime for all n. For example, 3 is not a Sierpinski number because n=2 produces a prime number (3*2^2+1=13). In 1962, John Selfridge proved that 78,557 is a Sierpinski number...meaning he showed that for all n, 78557*2^n+1 was not prime.

Most number theorists believe that 78,557 is the smallest Sierpinski number, but it hasn't yet been proven. In order to prove that it is the smallest Sierpinski number, it has to be shown that every single k less than 78,557 is not a Sierpinski number, and to do that, some n must be found that makes k*2^n+1 prime.

The smallest proven 'prime' Sierpinski number is 271,129. In order to prove that it is the smallest prime Sierpinski number, it has to be shown that every single 'prime' k less than 271,129 is not a Sierpinski number, and to do that, some n must be found that makes k*2^n+1 prime.

Previously, PrimeGrid was working in cooperation with Seventeen or Bust on the Sierpinski problem and working with the Prime Sierpinski Project is on the 'prime' Sierpinski problem. Although both Seventeen or Bust and the Prime Sierpinski Project have ceased operations, PrimeGrid continues the search independently to solve both conjectures.

The following k's remain for each project:

Sierpinski problem 'prime' Sierpinski problem 21181 22699* 22699 67607* 24737 79309 55459 79817 67607 152267 156511 168451 222113 225931 237019 * being tested as part of our Seventeen or Bust project

Fortunately, the two projects (and later PrimeGrid's Extended SIerpinski Project) combined their sieving efforts into a single file. Therefore, PrimeGrid's PSP sieve supports all three projects.

Additional Information

For more information about PSP, please see:


For more information about Sierpinski, Sierpinski number, and the Sierpinsk problem, please see these resources:



Recently discovered primes:

258317*2^5450519+1 is prime! (found by Sloth@PSP on 28/7/2008)
90527*2^9162167+1 is prime! (found by Bold_Seeker@PSP on 19/6/2010)
10223*2^31172165+1 discovered as part of our Seventeen or Bust subproject, eliminating 10223 from both the Sierpinski Problem and the Prime Sierpinski Problem, by Szabolcs Péter (SyP). (official announcement)
____________
My lucky number is 75898^524288+1
Please do not PM me with support questions. They will usually go unanswered. Ask on the forums instead. Thank you!

Profile Cesium_133*
Send message
Joined: 23 Jan 09
Posts: 1
ID: 34574
Credit: 38,341
RAC: 0
PPS Sieve Bronze: Earned 10,000 credits (10,113)
Message 13896 - Posted: 26 Feb 2009 | 9:25:25 UTC - in response to Message 9502.

This is flippin' neat, this number theory stuff. It allows me to participate in advanced mathematics without knowing anything about it! :D

Now my question, directed at this thread:

Is there a substantive, actual, real use for Prime Sierpinski numbers, or is this an exercise in computing power? I know nothing of this advanced math, nothing at all; I know what primes are, and I know (2^n)-1 is prime when n is a prime #. Beyond that, I know of no actual uses for prime numbers, although I hear they are used in cryptography in some form or fashion.

Basically, what will be advanced by learning what the smallest PS # is? Is it cryptography, probability, physics, something else, none of the above? I am curious... again, I have no math knowledge above Algebra II, so I'm learning here... :) John...
____________

TroubledBunnyProject donor
Volunteer tester
Avatar
Send message
Joined: 4 Jun 07
Posts: 605
ID: 8931
Credit: 384,513,338
RAC: 1,355
321 LLR Gold: Earned 500,000 credits (590,247)Cullen LLR Amethyst: Earned 1,000,000 credits (1,019,085)ESP LLR Amethyst: Earned 1,000,000 credits (1,006,207)Generalized Cullen/Woodall LLR Silver: Earned 100,000 credits (300,592)PPS LLR Ruby: Earned 2,000,000 credits (3,839,000)PSP LLR Amethyst: Earned 1,000,000 credits (1,147,411)SoB LLR Gold: Earned 500,000 credits (521,611)SR5 LLR Amethyst: Earned 1,000,000 credits (1,036,817)SGS LLR Amethyst: Earned 1,000,000 credits (1,068,652)TRP LLR Amethyst: Earned 1,000,000 credits (1,004,422)Woodall LLR Gold: Earned 500,000 credits (531,350)321 Sieve (suspended) Silver: Earned 100,000 credits (223,275)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (2,655,968)Generalized Cullen/Woodall Sieve Amethyst: Earned 1,000,000 credits (1,006,509)PPS Sieve Double Silver: Earned 200,000,000 credits (343,952,410)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,014,690)TRP Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,141,121)AP 26/27 Amethyst: Earned 1,000,000 credits (1,422,266)GFN Ruby: Earned 2,000,000 credits (4,753,065)PSA Jade: Earned 10,000,000 credits (16,276,495)
Message 13898 - Posted: 26 Feb 2009 | 11:56:12 UTC

I know (2^n)-1 is prime when n is a prime


Umm...

For n = 23, (2^23)-1 = 8388607 which has a factor 47 so isn't prime.

If (2^n)-1 is prime when n is a prime then the project would be redundant...
____________

35 x 2^3587843+1 is prime!

Profile ~~~(,__,)^'>Project donor
Volunteer tester
Avatar
Send message
Joined: 30 Jan 08
Posts: 3731
ID: 18322
Credit: 49,385,163
RAC: 0
321 LLR Gold: Earned 500,000 credits (550,585)Cullen LLR Gold: Earned 500,000 credits (668,541)ESP LLR Silver: Earned 100,000 credits (193,409)PPS LLR Ruby: Earned 2,000,000 credits (3,796,320)PSP LLR Gold: Earned 500,000 credits (521,137)SoB LLR Gold: Earned 500,000 credits (534,235)SR5 LLR Gold: Earned 500,000 credits (741,726)SGS LLR Amethyst: Earned 1,000,000 credits (1,044,407)TRP LLR Silver: Earned 100,000 credits (270,664)Woodall LLR Silver: Earned 100,000 credits (162,233)321 Sieve (suspended) Bronze: Earned 10,000 credits (32,623)Cullen/Woodall Sieve (suspended) Jade: Earned 10,000,000 credits (10,307,669)PPS Sieve Sapphire: Earned 20,000,000 credits (22,766,584)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Gold: Earned 500,000 credits (620,950)TRP Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,002,904)AP 26/27 Silver: Earned 100,000 credits (171,036)GFN Turquoise: Earned 5,000,000 credits (5,319,121)PSA Gold: Earned 500,000 credits (675,622)
Message 14981 - Posted: 21 Apr 2009 | 11:02:50 UTC - in response to Message 9502.

I'm sorry if this is a very naive question.

A Serpinkski number is defined as odd k where k*2^n+1 is not prime for any postive, odd integer n and 2^n>k see message 9502.

I can see that one can prove that a number is not a Serpinski number by finding a prime but surely to prove a number is a Serpinski number requires one to prove a negative. One can perhaps demonstrate that 78557*2^googolplex+1 +1 is not prime but that does not show that even larger numbers are composite. Or does it?

Be gentle with me on the maths and indeed errors of logic.

Cheers!

T

thommy3
Send message
Joined: 7 Jan 08
Posts: 42
ID: 17265
Credit: 268,651
RAC: 0
PSP LLR Bronze: Earned 10,000 credits (11,240)TRP LLR Bronze: Earned 10,000 credits (10,735)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Bronze: Earned 10,000 credits (88,757)TRP Sieve (suspended) Bronze: Earned 10,000 credits (36,174)AP 26/27 Bronze: Earned 10,000 credits (16,749)PSA Bronze: Earned 10,000 credits (98,594)
Message 14982 - Posted: 21 Apr 2009 | 12:20:23 UTC - in response to Message 14981.

One can proof there is a pattern of factors repeating every 36 values on n. So all possible n are covered.
See http://www.teamprimerib.com/sob/78557.php for example.

Profile ~~~(,__,)^'>Project donor
Volunteer tester
Avatar
Send message
Joined: 30 Jan 08
Posts: 3731
ID: 18322
Credit: 49,385,163
RAC: 0
321 LLR Gold: Earned 500,000 credits (550,585)Cullen LLR Gold: Earned 500,000 credits (668,541)ESP LLR Silver: Earned 100,000 credits (193,409)PPS LLR Ruby: Earned 2,000,000 credits (3,796,320)PSP LLR Gold: Earned 500,000 credits (521,137)SoB LLR Gold: Earned 500,000 credits (534,235)SR5 LLR Gold: Earned 500,000 credits (741,726)SGS LLR Amethyst: Earned 1,000,000 credits (1,044,407)TRP LLR Silver: Earned 100,000 credits (270,664)Woodall LLR Silver: Earned 100,000 credits (162,233)321 Sieve (suspended) Bronze: Earned 10,000 credits (32,623)Cullen/Woodall Sieve (suspended) Jade: Earned 10,000,000 credits (10,307,669)PPS Sieve Sapphire: Earned 20,000,000 credits (22,766,584)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Gold: Earned 500,000 credits (620,950)TRP Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,002,904)AP 26/27 Silver: Earned 100,000 credits (171,036)GFN Turquoise: Earned 5,000,000 credits (5,319,121)PSA Gold: Earned 500,000 credits (675,622)
Message 14985 - Posted: 21 Apr 2009 | 12:52:37 UTC - in response to Message 14982.

Thanks thommy3. I think that just about covers it. Mind you I might well come back with some more darn fool questions once I've sat done and worked through it but it looks like it will be a mighty fine start.

Again my sincere thanks.

T

Profile [AF>EDLS] frederic abussan
Avatar
Send message
Joined: 27 Aug 06
Posts: 15
ID: 3334
Credit: 61,146,696
RAC: 0
321 LLR Silver: Earned 100,000 credits (130,639)PSP LLR Silver: Earned 100,000 credits (490,045)SGS LLR Ruby: Earned 2,000,000 credits (2,035,573)Woodall LLR Silver: Earned 100,000 credits (174,737)321 Sieve (suspended) Bronze: Earned 10,000 credits (92,206)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,016,798)PPS Sieve Emerald: Earned 50,000,000 credits (51,125,810)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Ruby: Earned 2,000,000 credits (2,005,212)AP 26/27 Amethyst: Earned 1,000,000 credits (1,049,301)
Message 15356 - Posted: 3 May 2009 | 18:20:16 UTC

Hello

The challenge I have finished 4 of my 10 pc not working on PrimGrid but its strange I still got sometimes wu psp sending on that 4 computers with BOINC 6.4.7 and 6.6.20 I can not understand wat it happening ?
____________

Profile John M. Johnson "Novex"Project donor
Volunteer tester
Avatar
Send message
Joined: 16 Aug 07
Posts: 625
ID: 10876
Credit: 1,066,951
RAC: 0
321 LLR Bronze: Earned 10,000 credits (50,802)Cullen LLR Silver: Earned 100,000 credits (111,106)PPS LLR Silver: Earned 100,000 credits (101,350)PSP LLR Bronze: Earned 10,000 credits (15,210)SGS LLR Bronze: Earned 10,000 credits (27,055)TPS LLR (retired) Bronze: Earned 10,000 credits (67,826)Woodall LLR Bronze: Earned 10,000 credits (10,609)321 Sieve (suspended) Bronze: Earned 10,000 credits (70,873)Cullen/Woodall Sieve (suspended) Bronze: Earned 10,000 credits (20,185)PPS Sieve Bronze: Earned 10,000 credits (20,034)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Bronze: Earned 10,000 credits (24,551)TRP Sieve (suspended) Bronze: Earned 10,000 credits (40,040)AP 26/27 Silver: Earned 100,000 credits (159,148)PSA Silver: Earned 100,000 credits (344,961)
Message 20504 - Posted: 23 Jan 2010 | 14:32:39 UTC - in response to Message 15356.
Last modified: 23 Jan 2010 | 14:33:41 UTC

Hello

The challenge I have finished 4 of my 10 pc not working on PrimGrid but its strange I still got sometimes wu psp sending on that 4 computers with BOINC 6.4.7 and 6.6.20 I can not understand wat it happening ?



Just a guess, but maybe you have different versions of boinc on your different computers??


Edit: Question, is it 100% certain that there will be a prime found? and if so could there be more then 1?
____________


John M. Johnson "Novex"

thommy3
Send message
Joined: 7 Jan 08
Posts: 42
ID: 17265
Credit: 268,651
RAC: 0
PSP LLR Bronze: Earned 10,000 credits (11,240)TRP LLR Bronze: Earned 10,000 credits (10,735)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Bronze: Earned 10,000 credits (88,757)TRP Sieve (suspended) Bronze: Earned 10,000 credits (36,174)AP 26/27 Bronze: Earned 10,000 credits (16,749)PSA Bronze: Earned 10,000 credits (98,594)
Message 20534 - Posted: 25 Jan 2010 | 7:47:17 UTC - in response to Message 20504.


Edit: Question, is it 100% certain that there will be a prime found? and if so could there be more then 1?


No, it's not 100% certain.
And there could be more than 1 (infinitely many) primes for each k. But only the first is of interest here.

Profile John M. Johnson "Novex"Project donor
Volunteer tester
Avatar
Send message
Joined: 16 Aug 07
Posts: 625
ID: 10876
Credit: 1,066,951
RAC: 0
321 LLR Bronze: Earned 10,000 credits (50,802)Cullen LLR Silver: Earned 100,000 credits (111,106)PPS LLR Silver: Earned 100,000 credits (101,350)PSP LLR Bronze: Earned 10,000 credits (15,210)SGS LLR Bronze: Earned 10,000 credits (27,055)TPS LLR (retired) Bronze: Earned 10,000 credits (67,826)Woodall LLR Bronze: Earned 10,000 credits (10,609)321 Sieve (suspended) Bronze: Earned 10,000 credits (70,873)Cullen/Woodall Sieve (suspended) Bronze: Earned 10,000 credits (20,185)PPS Sieve Bronze: Earned 10,000 credits (20,034)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Bronze: Earned 10,000 credits (24,551)TRP Sieve (suspended) Bronze: Earned 10,000 credits (40,040)AP 26/27 Silver: Earned 100,000 credits (159,148)PSA Silver: Earned 100,000 credits (344,961)
Message 20537 - Posted: 25 Jan 2010 | 13:24:50 UTC - in response to Message 20534.


Edit: Question, is it 100% certain that there will be a prime found? and if so could there be more then 1?


No, it's not 100% certain.
And there could be more than 1 (infinitely many) primes for each k. But only the first is of interest here.



Above when it says "some n must be found that makes k*2^n+1 prime." Doesn't that indicate that there is a 100% chance of a prime within the search numbers: ?

Sierpinski problem 'prime' Sierpinski problem 10223 10223* 21181 22699* 22699 67607* 24737 79309 55459 79817 67607 90527 152267 156511 168451 222113 225931 237019 ==?
____________


John M. Johnson "Novex"

JohnProject donor
Honorary cruncher
Avatar
Send message
Joined: 21 Feb 06
Posts: 2876
ID: 2449
Credit: 2,681,934
RAC: 0
321 LLR Bronze: Earned 10,000 credits (11,773)Cullen LLR Bronze: Earned 10,000 credits (14,945)ESP LLR Bronze: Earned 10,000 credits (26,855)PPS LLR Bronze: Earned 10,000 credits (84,876)PSP LLR Bronze: Earned 10,000 credits (15,311)SoB LLR Bronze: Earned 10,000 credits (21,440)SR5 LLR Bronze: Earned 10,000 credits (29,270)SGS LLR Bronze: Earned 10,000 credits (26,616)TPS LLR (retired) Bronze: Earned 10,000 credits (36,288)TRP LLR Bronze: Earned 10,000 credits (41,655)Woodall LLR Bronze: Earned 10,000 credits (15,807)321 Sieve (suspended) Bronze: Earned 10,000 credits (20,014)Cullen/Woodall Sieve (suspended) Bronze: Earned 10,000 credits (23,405)PPS Sieve Bronze: Earned 10,000 credits (36,192)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Bronze: Earned 10,000 credits (20,306)TRP Sieve (suspended) Bronze: Earned 10,000 credits (21,738)GFN Bronze: Earned 10,000 credits (86,217)PSA Ruby: Earned 2,000,000 credits (2,143,756)
Message 20541 - Posted: 25 Jan 2010 | 14:40:13 UTC - in response to Message 20537.

Above when it says "some n must be found that makes k*2^n+1 prime." Doesn't that indicate that there is a 100% chance of a prime within the search numbers: ?

You left off the beginning of the quote which explains it all. In order to prove the conjecture, a prime must be found. This does not indicate that there's a 100% chance of finding a prime.

Most number theorists believe that 78,557 is the smallest Sierpinski number, but it hasn't yet been proven. In order to prove it, it has to be shown that every single k less than 78,557 is not a Sierpinski number, and to do that, some n must be found that makes k*2^n+1 prime.

____________

Message boards : Prime Sierpinski Problem : About the Prime Sierpinski Problem

[Return to PrimeGrid main page]
Copyright © 2005 - 2017 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 0.74, 0.95, 1.10
Generated 20 Jul 2017 | 21:22:10 UTC