mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2006-10-05, 22:41   #1
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

DB116 Posts
Default Question about Riesel and Sierpinski conjecture.

For those of you who don't know, there are two math projects trying to prove a conjecture. For Riesel Sieve, they're trying to prove that 509203 is the smallest Riesel number. A Riesel number is a number k, such that k*2^n-1 is composite for all n. Seventeen or Bust is trying to prove the PLUS 1 version of the problem(I don't know what the conjectured Sierpenski number is.

Anyway, there are 9-10 k-values left for the Sierpenski conjective, and 69-70 values left for the Riesel conjecture.

Now, here's where I let my ignorance show:

The Riesel conjecture has gone from 254602 values to prove prime down to about 70, and the Sierpenski conjecture, which I believe started at a little under 40,000 values(I think), is now down to 9-10 values. My question is:

Now that the number of values is so much lower, couldn't someone apply the same techniques used to find the Riesel and Sierpenski numbers, and use those techniques to study the numbers left over? Maybe finding something that the computers involved in the problem couldn't?

As I said, I'm ignorant of these things. I'm thinking maybe the sieving programs have already implemented what I'm talking about, but I'm not sure. My knowledge of modular arithmetic is very limited, although I hope to learn at some point.
jasong is offline   Reply With Quote
Old 2006-10-06, 06:17   #2
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

22×32×5×13 Posts
Default

Quote:
Originally Posted by jasong View Post
Now that the number of values is so much lower, couldn't someone apply the same techniques used to find the Riesel and Sierpenski numbers, and use those techniques to study the numbers left over?
The Riesel and Sierpenski numbers were found by creating covering sets, and then finding out what numbers matched the covering set. For example, we know that if 3 divides any number in the sequence of increasing exponents, then it divides every second number. Similary, if 7 divides any number it divides every 3rd number, and 31 divides every 5th. It's easy to find these multiples, and it's not too hard to find combinations that would cover every number. From this covering, it's pretty easy to use the Chinese Remainder Theorem to find the Sierpinski and Riesel numbers that correspond to such a covering. The suspected smallest numbers are the smallest that were found from extensive searches of this type.

This original method doesn't start with candidate Riesel and Sierpinski numbers, so having a small number of candidates doesn't help.

Now you might think about taking the remaining candidates and attempting to compose a covering set that was missed in the original process. To try this, you would start with the factorization of the smallish exponents and attempt to pick a covering set starting with these factors. If you try this, you will soon find that some of the exponents have smallest factors with dozens of digits, and any covering set will require a period that is much too long to figure out.

Having figured that out, you might next think "surely it's not natural to have to go such large exponents - isn't that a hint that at least of some these might be unrecognized Riesel and Sierpinski numbers." You would be wrong, though. Many of the remaining candidates have pretty large partial covering sets. For example, the Sierpinski candidate 67607 has 712 out every 720 exponents divisible by a small prime. This scarcity of potential exponents means the candidates for primes grow rapidly. Combined with the increasing scarcity of primes as the numbers get larger, you expect to need to go very far to find a prime. I worked out a detailed estimate for Seventeen or Bust a few years ago, and they have actually been finding primes slightly faster than that estimate. So if there is any surprise about the number of remaining candidates, it has to be that the number is so small - no hint of unrecognized Riesel and Sierpinski numbers.

So there doesn't seem to be anything to do but keep plugging away with the present methods.
wblipp is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Very Prime Riesel and Sierpinski k robert44444uk Open Projects 587 2016-11-13 15:26
Sierpinski/ Riesel bases 6 to 18 robert44444uk Conjectures 'R Us 139 2007-12-17 05:17
Sierpinski/Riesel Base 10 rogue Conjectures 'R Us 11 2007-12-17 05:08
Sierpinski / Riesel - Base 23 michaf Conjectures 'R Us 2 2007-12-17 05:04
Sierpinski / Riesel - Base 22 michaf Conjectures 'R Us 49 2007-12-17 05:03

All times are UTC. The time now is 14:46.

Tue Oct 20 14:46:59 UTC 2020 up 40 days, 11:57, 1 user, load averages: 2.72, 2.60, 2.50

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.