After Seventeen or Bust

[OberonBob]

I know it is way too early to be thinking about this now, but at some point we are going to finish this challenge, and when we do, it would be cool to move on to the dual and mixed Sierpinski problems.

The best way to do this, IMHO, is to go ahead and build this into the client, and just not activate it until our last 12 primes are found. I am not Math guy, but the tests for the other projects have to be simular. The mixed problem only has one number left to check, and the dual only has eight.

If you want to keep people in the fold to do the other tests, then you are going to have to be ready for it, when the time comes.

just something to think about.

[wblipp]

The Sierpinski Problem is sometimes stated as the two numbers found by Selfridge in 1962 are the two smallest Sierpinski numbers. (78,557 and 271,129). For example, this page says "The Sierpinski problem is to show that these indeed are the first two Sierpinski numbers"
http://www.csm.astate.edu/~wpaulsen/.../mazeisol.html

So continuing the project to confirm the second smallest Sierpinski number would be a natural extension.

Sierpinski's work was probably inspired by Riesel's work that proved the same thing as Sierpinski with the "+" changed to "-". The smallest Riesel number is thought to be 509,203. The Proth.exe program can check primality in these numbers, too, so it would be a similar project to check whether this is the smallest Riesel number.

Bier numbers are numbers that are simultaneously Riesel and Sierpinski numbers. The smallest known Brier number I've seen, found in Jan 2000, is
878503122374924101526292469
http://www.glasgowg43.freeserve.co.uk/brier2.htm

Confirming that would probably keep the project going into the era of Petahertz processore.

[tqft]

I would vote for Brier numbers they seem just too wacky to not to be of use in the 50 years or so is is going to take to start understanding them.

I am trying to get my head around the concept of seirpinski numbers and why they have the property they do.

So far I understand their is covering set that if one number is prime somehow guarantees the rest of the properties. Not far along I know.

[smh]

So continuing the project to confirm the second smallest Sierpinski number would be a natural extension.

See http://www.glasgowg43.freeserve.co.uk/siersurv.htm for the status of all K's below 1.000.000

I don't know how you see a search for brier numbers. Thats something completely different compared to what we are doing now.

Testing for smaller Riesel numbers is almost the same as we are doing now, only for different numbers.

But don't worry, we've got plenty of time to think what to do after SoB

[wblipp]

Originally posted by tqft
I am trying to get my head around the concept of seirpinski numbers and why they have the property they do.

I can't find it now, but I saw a proof that 78,557 is a Sierpinski number. I thought it was a pop up window from the SoB site. This example helped me understand the "covering set" concept. One half of all values of n are divisible by 3, and one-twelfth are divisible by 73 (or something like this), and when you put it all together, ALL values of n are divisible by something.

All known Sierpinski numbers can be constructed this way. But that doesn't prove that all Sierpinki numbers can be constructed this way. Worse yet, it is possible that a very large set of very large primes could create a covering set for remaining unsettled numbers. The only way known to prove a number is not a Sierpinski number is to find a prime in the sequence.

Originally posted by smh
I don't know how you see a search for brier numbers. Thats something completely different compared to what we are doing now.

Testing for smaller Riesel numbers is almost the same as we are doing now, only for different numbers.

To prove a number is not a Brier number, you either prove it is not a Riesel number or you prove it is not a Sierpinski number. We have a mechanism for proving things are not Sierpinski numbers, and you agree it would be similar to create a mechanism for proving numbers are not Riesel numbers. From those two mechanisms, it's simple to create a mechanism that throws out candidates that flunk one of the tests.

[Joe O]

Try this page.

[MAD-ness]

Thanks Joe.

Both for the linkage and for helping montrd put that together.

[wblipp]

Originally posted by Joe O
Try this page.

Thanks - that's the page! This example makes it clear how you would show that a number is a Sierpinski number or a Reisel number.

The other key component of this search is the proth primality test for checking whether a proth number is prime. The iinternet seems to be inconsistent about what this theorem states. UTM's statement has includes mention of a Jacobi symbol that isn't in Wolfram's statement.
UTM link, with "Jacobi Symbol"
Wolfram link, without "Jacobi Symbol"

Has anyone put together an explanation of the Proth Primality test that is as easy to follow as Prime Rib's proof for 78557?

[MAD-ness]

tqft: I replied to your thread asking questions about SoB, specifically the definition of 'cEMs' with a link to this thread:

http://www.free-dc.org/forum/showthr...&threadid=2361

That thread also has information about the Sierpinski problem with some links and explanations that aren't found elsewhere (to the best of my knowledge).

Hope that helps.

[jwolfe]

Originally posted by Joe O
Try this page.

Shouldn't the table have an entry for 0?

[Joe O]

You're right

78557.2n+1
n (mod 36) Case is a multiple of
0 n= 36.b+0 = 2.(18.b+0) 0 (mod 2) A 3

[philmoore]

Here's a condensed version of the proof that 78557 is a Sierpinski number. n = a mod b means that (n-a) is divisible by b, or that dividing n by b leaves a remainder of a.

If n = 0 mod 2, 78557*2^n+1 is divisible by 3.
If n = 1 mod 4, 78557*2^n+1 is divisible by 5.
If n = 7 mod 12, 78557*2^n+1 is divisible by 7.
If n = 11 mod 12, 78557*2^n+1 is divisible by 13.
If n = 3 mod 36, 78557*2^n+1 is divisible by 73.
If n = 15 mod 36, 78557*2^n+1 is divisible by 19.
If n = 27 mod 36, 78557*2^n+1 is divisible by 37.

This exhausts all possibilities for n, so therefore 78557*2^n+1 is never prime.

[philmoore]

I forgot to give you your homework assignment: Prove that 271,129 is also a Sierpinski number.

[Lagardo]

To respond to the title of the thread (don't ask me for a mathematical proof ) : If I understand the tidbit about the density of prime numbers correctly, SoB will be around a long, long time. And I mean long. 5 primes are good, number 6 and 7 should be coming up within the next couple years, I doubt #8 will be found by this project in its current form and the remaining ones would require some serious computational firepower or some entirely different approach...

[jwolfe]

Originally posted by Lagardo
To respond to the title of the thread (don't ask me for a mathematical proof )

I think the closest thing to a "proof" is here. It estimates the number of values of n expected to be remaining at a given search level. It was written almost two years ago, but the numbers seem to be holding up.

Based on its estimates, I wouldn't be surprised if SB found another prime right away and one more after that within the next year. The project is actually a little behind the "expected" progress (12 vs. 10.9 at n=2 million).

Finding all the primes probably won't happen any time soon. The article indicates that there's about a 5% chance of finding all the primes in the Sierpinski problem by the time n reaches about 1 billion. SB has so far managed to raise the lower bound from about 500,000 to about 2 million, and the upper bound from about 2 million to about 3 million. That's quite an accomplishment, but there's still a lot of work to be done. Even with continued software speed improvements, a growing user base, and Moore's Law taken into account, SB is still years away from completion.

- Jeff

[tqft]

Thanks for the great info.

As I now understanding more about the size of the problem, I think worrying about what is next are fairly academic.

But please correct me if I am wrong on this point:
we are not testing a covering set per se - ie generating numbers and testing for primeness, but testing numbers and trying to build a covering set (which we do not expect we can do).

[wblipp]

Originally posted by philmoore
I forgot to give you your homework assignment: Prove that 271,129 is also a Sierpinski number.

I assume the homework is open book.
Start here:

Searching For Large Sierpinski Numbers

We learn that the covering set is 3, 5, 7, 13, 17, 241, and the modulus is 24.

Most of these numbers were also in the covering set for 78,557, so we can probably adapt a lot of this proof from that proof.

Coverage by Prime 3
271129 mod 3 = 1.
Also 2^2 mod 3 = 1.

This is different from 78557 because
78,557 mod 3 = 2. But we can adapt to that difference.
271129 * 2 * (2^2n) + 1 mod 3 is (1) * (2) * (1)^n + 1 = 3 = 0 mod 3. Hence

if n=1 mod 2, 271129*2^n+1 is divisible by 3

Coverage by Prime 5
271129 mod 5 = 4
2^4 mod 5 = 1

271129 * (2^4n) + 1 mod 5 = (4) * (1)^n + (1) = 5 = 0 mod 5

Hence if n=0 mod 4 then 271129*2^n+1 is divisible by 5


Coverage by Prime 7
271129 mod 7 = 5
2^2 mod 7 = 4
2^3 mod 7 = 1

271129 * (2^2) * (2^3n) + 1 mod 7 = (5) * (4) * (1)^n + 1 = 21 = 0 mod 7

If n=2 mod 3 then 271129*2^n+1 is divisible by 7

Coverage by Prime 13
271129 mod 13 = 1
2^6 mod 13 = 12
2^12 mod 13 = (2^6)^2=12^2=1 mod 13

271129 * (2^6) * (2^12n) + 1 = (1) * (12) * (1)^n + 1 = 13 = 0 mod 13

Hence if n=6 mod 12 then 271129*2^n+1 is divisible by 13


Coverage for Prime 17
271129 mod 17 = 13
2^6 mod 17 = 13
2^8 mod 17 = 1

271129 * (2^6) * (2^8) + 1 =(13) * (13) * (1)^n + 1 = 170 = 0 mod 17

Iif n=6 mod 8, then 271129*2^n+1 is divisible by 17


[B]Coverage for Prime 241[B[
271129 mod 241 = 4
2^10 mod 241 = 60
2^24 mod 241 = 1

271129 * (2^10) * (2^24) + 1 = (4) * (60) * (1)^n + 1 = 241 = 0 mod 241

If n=10 mod 24 then 271127*2^n is divisible by 241

OK - let's see if we have all values of n mod 24 covered

0 = 0 mod 4, divisiible by 5
1 = 1 mod 2, divisible by 3
2 = 2 mod 3, divisible by 7
3 = 1 mod 2. divisible by 3
4 = 0 mod 4, divisible by 5
5 = 1 mod 2, divisible by 3 (also 7)
6 = 6 mod 12, divisible by 16 (also 17)
7 = 1 mod 2, divisible by 3
8 = 0 mod 4, divisible by 5 (also 7)
9 = 1 mod 2. divisible by 3
10 = 10 mod 24, divisible by 241
11 = 1 mod 2, divisible by 3 (also 7)
12 = 0 mod 4, divisible by 5
13 = 1 mod 2, divisible by 3
14 = 2 mod 3, divisible by 7 (also 17)
15 = 1 mod 2, divisible by 3
16 = 0 mod 4, divisible by 5
17 = 1 mod 2, divisible by 3 (also 7)
18 = 6 mod 12, divisible by 13
19 = 1 mod 2, divisible by 3
20 = 0 mod 4, divisible by 5
21 = 1 mod 2, divisible by 3 (also 7)
22 = 6 mod 8, divisible by 17
23 = 1 mod 2, divisible by 3

[eatmadustch]

one thing we're going to have to start worrying about earlier is the size of a test. Already it's 120 blocks, and an old computer has 1 hour for 1 block. That means, an old computer needs like weeks to finish just one test, especially if it's not on 24/7. When n rises the test is going to be unbearably long. Isn't it possible to just report the test after say 1 million iterations and let someone else continue from there? In future I think something like that will be needed!

[Mystwalker]

Theoretically it's possible, but the PC continuing the range needs the "cache" file of the prior one. At n = 2.5M is was roundabout 300 KByte IIRC - but the size increases AFAIK. So a lot of bandwidth is needed. Once a test is completed, there's only residue and result left.

The question is:
What's the problem with big tests?
The only disadvantages I see are:

- Ppl only testing this DC project for a day or two do not contribute any work - well, I guees the main work comes from the ppl who stay at this project, so it's not that big a loss; when a PC is only used for a short period of time, the cache file can be transferred to another PC

- big loss of work in case of a failure (disk crash etc.) - I hope there are not that many tests getting lost through those failures; although it's very displeasing when the server doesn't accept a block and hands out a new test...

[Lagardo]

Originally posted by Mystwalker
At n = 2.5M is was roundabout 300 KByte IIRC - but the size increases AFAIK. So a lot of bandwidth is needed.

Dunno - that's about the size of a seti WU and I've never seen/heard/read someone complain about the bandwidth of those.

Except Berkeley themselves, of course...

[MAD-ness]

That is exactly the point Lagardo.

Returning the cache would bump the project from the "uses an incredibly small amount of bandwidth, even with a ton of users" level to the "saturates an OC-12 in a heartbeat" level.

Even if that type of bandwidth usage was allowable or possible, it hardly seems worth the cost.

BTW, the OC-12 comment wasn't meant literally, it might be a bit of an embellishment.