How did they prove that Riesel/Sierpinski numbers.

Exist?


Or did they even do that? I'm assuming they did, because you don't just look for something you don't even know exists... So how did they first prove tht a k exists?


And then after they did that, how did they find a k? Like I'm not looking for the smallest, merely how they acn find any. Thanks a bunch.

[wblipp]

Originally Posted by Unregistered

Exist?

Covering Sets.

It's easy to show that if 3 divides k*2ⁿ+1, then 3 divides k*2ⁿ⁺²+1, and every second value of n for ever. Likewise if 7 ever divides a value, then it divides every third "n" from there. Every prime has a repeating cycle. A covering set is a set of primes such that their repeat cycles cover every value of n.

Originally Posted by Unregistered

I'm assuming they did, because you don't just look for something you don't even know exists...

Nobody knows if odd perfect numbers exist, but mathematicians have searched for them for thousands of years. Some mathematicians, such as our famous curmudgeon in residence, Bob Silverman, are thoroughly convinced they do not exist. Others, such as the famous Richard Brent, say they have doubts but would not be particularly surprised if one was found. OddPerfect.org is an information sharing and collaboration coordination site for mathematicians working on this question.

[Mini-Geek]

Adding to what wblipp said:
http://www.mersenneforum.org/showthr...993#post144993 shows the covering set of 78557, the smallest known Sierpinski number. You can make a list of 0-35 (as in, n=0 to 35 mod 36) and see that every n has a factor in the covering set.

Two questions do still remain, though:
1. who first thought that there might be k's with no primes, and why? I'd guess that Riesel and Sierpinski were some of the first, for k*2^n-1 and k*2^n+1 respectively.
2. And, how did people discover that certain numbers were Riesel or Sierpinski numbers? When were the first of these discoveries made, and how?

By the way, is it known if there are any Riesel or Sierpinski numbers that have an infinite covering set? i.e. there are no primes, but no finite covering set of numbers that shows that every n a factor.
And to add to 2, are any efforts still continuing to find more Riesel and Sierpinski numbers? Has effort been put forth to find a covering set (even a large one) for the remaining k's in the Seventeen or Bust project (and similar projects)?

[wblipp]

Originally Posted by Mini-Geek

By the way, is it known if there are any Riesel or Sierpinski numbers that have an infinite covering set?

When k is a perfect square there are sometimes Aurifeuillian factorizations that remove some powers of n, with the others being removed by a partial covering set. This at least creates he possibility of no finite covering set - I don't know if any cases with no finite covering have actually been proven.

Originally Posted by Mini-Geek

Has effort been put forth to find a covering set (even a large one) for the remaining k's in the Seventeen or Bust project (and similar projects)?

It's too early to seriously worry about that. A few years ago I did a heuristic analysis of when the nth prime would be found. They are ahead of schedule so far, and the expected value for the last one is far beyond the present level, so there isn't any reason to expect a Sierpinski number among the remaining set.

You can get a feel for the size that would be necessary by considering the primes found by the Dual Sierpinski problem. Any covering set for a Sierpinski number is also a covering set for the Dual Sierpinski number. It's possible, though, for one of the primes in the covering set to exactly equal one of the values, making a prime even though there is a covering set. So any covering set for the remaining k's must include all Dual Sierpinski primes for that k. I've looked at a few of these and decided it makes sense to wait a lot longer before investing any effort in searching for a previously missed covering set.

[Mini-Geek]

How hard is it to look for a covering set? What does it involve? Can it be automated by a computer? Has an automated covering set searcher been programmed, as far as anyone knows?

Originally Posted by wblipp

When k is a perfect square there are sometimes Aurifeuillian factorizations that remove some powers of n, with the others being removed by a partial covering set. This at least creates he possibility of no finite covering set - I don't know if any cases with no finite covering have actually been proven.

Hm...interesting. Thanks.

Originally Posted by wblipp

It's too early to seriously worry about that. A few years ago I did a heuristic analysis of when the nth prime would be found. They are ahead of schedule so far, and the expected value for the last one is far beyond the present level, so there isn't any reason to expect a Sierpinski number among the remaining set.

Sure, but no harm in looking. Imagine all the work that could be saved if one or more of the k's is really a Sierpinski number. Just consider for a moment how many CPU years have been spent sieving and searching these numbers, vs how much CPU time might be spent looking for a covering set, which would eliminate the need to do this.

Originally Posted by wblipp

You can get a feel for the size that would be necessary by considering the primes found by the Dual Sierpinski problem. Any covering set for a Sierpinski number is also a covering set for the Dual Sierpinski number. It's possible, though, for one of the primes in the covering set to exactly equal one of the values, making a prime even though there is a covering set. So any covering set for the remaining k's must include all Dual Sierpinski primes for that k. I've looked at a few of these and decided it makes sense to wait a lot longer before investing any effort in searching for a previously missed covering set.

I was wondering about the relation between the covering sets of Sierpinski and Dual Sierpinski numbers. Now I see why the searches being separate isn't redundant. Thanks.

Originally Posted by Unregistered

How did they prove that Riesel/Sierpinski numbers exist?

I don't know, but Riesel and Sierpinski proved that there are an infinite number of Riesel and Sierpinski numbers in 1956 and 1960 respectively. In '62, John Selfridge showed that 78557 was a Sierpinski number, and we're still trying to prove it's the smallest.

Thanks for the answers!

What I'm looking for though, is how they were able to find such a k, doesn't really have to be the smallest.

Because I wanted to try to apply it to 3^n-2.

[wblipp]

Originally Posted by Unregistered

What I'm looking for though, is how they were able to find such a k, doesn't really have to be the smallest.

Because I wanted to try to apply it to 3^n-2.

I'm guessing you want to find odd k's such that k*3ⁿ-2 is always composite.

One process is to find a covering arrangement and then find the k values that match that covering arrangement. For example, if 13 ever divides k*3ⁿ-2. it will divide every 3rd value of n, and if 7 ever divides k*3ⁿ-2, it will divide every 6th value of n. Continue like this until you have enough primes to cover everything. Arrange them in an assumed sequence (13 divides when n = 1,4,7..., 7 divides when n=2,8,14..., etc). Then find the k value that matches that covering arrangement. Note that every covering set will correspond to multiple covering arrangements.

I believe this is the process that was used to find the smallest known Riesel and Sierpinski numbers. Proving they are really the smallest then requires finding a prime for all the smaller k values.

If your interest lasts long enough, you will soon find yourself interested in knowing factors of 3^n-1 for values of n that are smooth. This is the path I followed with Riesel and Sierpinski numbers that resulted on the project ElevenSmooth, which is looking for factors of 2^n-1 where n is 11-smooth. Doing this with the base 3 will not intersect with as many other mathematical interests; Richard Brent collects and publishes factors of 3^n-1 for n<10,000 - I don't know of a standard repository for higher exponents. In comparison, Will Edgington collects factors of 2^n-1 for all values of n.

William

[henryzz]

Originally Posted by wblipp

I'm guessing you want to find odd k's such that k*3ⁿ-2 is always composite.

try covering.exe from post #60 http://www.mersenneforum.org/showthread.php?t=10316
260880774563 is the best i have found so far
you can rediscover it with the line:
144 3 -2 100000 260880774564

the way lower numbers have been appearing with different parameters i expect it isnt the lowest
i will try more tommorrow

BTW it hasnt been tested much(if at all) with anything but +1 or -1 conjectures but it seems to be producing reasonably correct results for -2

wow, thanks so much!

I love you guys :D Only on a math forum will you find people who are civilized enough to actually help people most of the time, and not spam spam spam everywhere.

[henryzz]

i cant find anything better currently

[10metreh]

Originally Posted by Unregistered

wow, thanks so much!

I love you guys :D Only on a math forum will you find people who are civilized enough to actually help people most of the time, and not spam spam spam everywhere.

There is spam, but posts get moderated first.