Sierpinski/ Riesel bases 6 to 18

[jasong]

Originally Posted by geoff

A prime is needed for 92*17^n+1.

Oops.

[robert44444uk]

Originally Posted by jasong

It seems very likely like 14*8^n-1 is composite for all n. NewPgen says it's composite for all n up to 50,000,000.

I would have to agree, 14 provides composites, and therefore is the Riesel number. I went back to my excel spreadsheet and I had it noted there as the Riesel. What is more, it is proved as the Riesel.

Regards

Robert Smith

[masser]

Originally Posted by jasong

Edit2: NewPGen allows increasing n, but not k, so I'm I don't think it's possible to implement masser's idea without programming knowledge. Would be happy to be proven wrong.

jasong,

IIRC, NewPGen allows increasing k, too. But in the menu for "sieve until" it only says n. If you pick the fixed k sieves, and then select updating n under that menu heading, NewPGen actually updates the k values. I think this confusion is mentioned in the README file that comes with NewPGen. I'll check this out and get back to you...

have fun,

masser

Edit: I just checked the latest Windows version of NewPGen and it seems to work for only base 2. Sorry, jasong - that's a dead end for finding Riesel/Sierpinski numbers....I would follow Rogue's suggestion above and use srsieve or psieve, located here:

http://pages.prodigy.net/chris_nash/psieve.html

along with instructions on using it.

[Citrix]

Could someone find the covering set for base 8 k=14 on the riesel side. Jasong seems to be correct, it seems like base 6 riesel number.

For base=9 on the riesel side a perfect square can never provide a prime. For example 36*9^n-1 can be factorized trivially into 6*3^n+1 and 6*3^n-1. I think this proves 74 as the smallest riesel for base 9.

same goes for base=16 and k=9 on the riesel side.

edit: reserving base=16 k=1to 10000 on sierpinski side. 114 numbers left at n=128. not using trivial solutions like 4,8 etc.. or numbers such that k=2 (mod 3) or k=4 (mod 5). Also removing 4*a^2 as this leads to gaussian factorization.

edit4: 120 does not appear to be a riesel number for base 16. I really think there might be something wrong with the calculations. (120*16^7-1 is 3-PRP! (0.0030s+0.0004s))

[robert44444uk]

Originally Posted by Citrix

Robert, since you are posting the stuff for all bases, could you post the stuff for base 3 and well as base 4. I have been working on base 4 sierpinski with some 4 candidates left, I don't know about base 4 Riesel.

OK, I think a very low possible Riesel number base 4 is 56169, which has the covering set [5,7,17,13,241] which covers every 12n. This is the lowest non trivial for this covering set. Another set which might give rise to a low Riesel which needs to be checked is [5,7,17,13,97,673], however the chances of it beng less than 56169 are remote but not impossible.

Regards

Robert Smith

[robert44444uk]

Originally Posted by rogue

The point is that you only want to do a a thousand or more k at a time. Sieve to 1e5 (or whatever limit you want). If nothing pops out as a Riesel or Sierpinski number, then do the next 1000. Iterate until one is found.

The problem is that, for some values, there is no mooted covering set less than 10^16, therefore the suggested method is inefficient for these bases. Tacking 3 and 15 needs another approach, but I am at a loss to think how to do efficiently.

The method I use, which needs programming to run efficiently, (I am doing all of the caculations in Excel or even manually in some instances), involves (for the Sierpinski case)

(i) factoring b^n-1 for n (=A) which are small or highly composite (especially 6,8,12,16,20,24,30,32,36,40,48,60,64...).
(ii) calculating the multiplicative order base b of all of the prime factors
(iii) summing the reciprocals of the multiplicative orders for all non trivial prime factors of a given A
(iv) if the sum in (iii) is greater than 1, then there is probably a covering set of a combination of the prime factors of that b^A-1
(v) discover possible combinations of those prime factors for a given A that give rise to covering sets
(vi) construct a table with values 1..A and P(1), P(2)..P(x) where P's are the prime factors of b^A-1, and discover all combinations of P's which cover all values 1..A (this is not easy to do, unless you are good mathematician or programmer) - I tend to use a greedy algorithm to discover the sets and their positions
(vii) mark the first instance of value 1..A where the prime factor occurs in the table
(viii) for a particular P(x) calculate a K value which divides K.b^n+1, n from 1 to P(x), express as KmodP(x)
(ix) use the Chinese Remainder Theorem, using K(1)..K(x)modP(1)..P(x) to discover the k, for all combinations in (vi)
(x) discard all k which are also trivial (k*b^n-1 is divisible by any of the factors of b-1)
(xi) the lowest k discovered by CRM is a low Sierpinski number for that covering set.
(xii) repeat for other covering sets, although the likely smallest case is the simplest covering set

For example, in the Sierpinski 13 case:

(i) 13^4-1 = 28560=2^4*3*5*7*17
(ii) 2,3 multiplicative order =1 (trivial), 7 = M(2), 5 and 17 are M(4)
(iii) 1/2+1/4+1/4=1
(iv) therefore possible covering set
(v) only one possible set of factors as sum of reciprocals is =1
(vi) covering sets given by (a) 7 in positions 1 and 3, 5 in 2 and 17 in 4, (b) 7 in 1 and 3, 5in 4 and 17 in 2 (c) 7 in positions 2,4, 5 in 1, and 17 in 3, (d) 7 in 2,4, 5 in 3 and 17 in 1.
(vii) (a) 7,1..5,2..17,4 etc
(viii) (a) 1mod7, 1mod5, 16mod17 (b)....
(ix) (a) 526, (b) 239, (c) 293 (d) 132
(x) and (xi) trivial k are provided by 1mod2 and 1mod3 , and 132 is neither
(xii) it is quicker to test for primes of k.b^n+1, with k<132 than to look at other covering sets in this instance. First primes are generally low values of n and in this instance, only k=48 and 120 created a problem, however 120*13^1552+1 is prime, as is 48*13^6267+1.

Anyone up to program?

Regards

Robert Smith

[robert44444uk]

Originally Posted by Citrix

edit4: 120 does not appear to be a riesel number for base 16. I really think there might be something wrong with the calculations. (120*16^7-1 is 3-PRP! (0.0030s+0.0004s))

Aiaia, I have totally screwed up base 16, did not have a covering set after all. I will try again from scratch.

Regards

Robert Smith

[robert44444uk]

Originally Posted by robert44444uk

Aiaia, I have totally screwed up base 16, did not have a covering set after all. I will try again from scratch.

Regards

Robert Smith

OK, here are values for the covering set [17,7,13,241] repeating every 6n.

Sierpinski 66741
Riesel 33965

Still possible lower values from the covering set [7,13,19,37,73] repeating every 9n.

Regards


Robert Smith

[Citrix]

16 numbers left under 10,000 tested to n=4000 (or 16,000 in base 2). Stopping now.

186*16^n+1
2158*16^n+1
2857*16^n+1
2908*16^n+1
3061*16^n+1
4885*16^n+1
5886*16^n+1
6348*16^n+1
6663*16^n+1
6712*16^n+1
7212*16^n+1
7258*16^n+1
7615*16^n+1
7651*16^n+1
7773*16^n+1
8025*16^n+1

[robert44444uk]

Originally Posted by Citrix

Could someone find the covering set for base 8 k=14 on the riesel side.

Covering set for base 8 k=14 is [3,5,13]

Originally Posted by Citrix

Jasong seems to be correct, it seems like base 6 riesel number.

???

Regards

Robert Smith

[robert44444uk]

Originally Posted by Citrix

For base=9 on the riesel side a perfect square can never provide a prime. For example 36*9^n-1 can be factorized trivially into 6*3^n+1 and 6*3^n-1. I think this proves 74 as the smallest riesel for base 9.

same goes for base=16 and k=9 on the riesel side.

Mmmm, this is an extra complexity for non base 2 riesel numbers. Will have to define trivial riesel solutions in the base = square scenarios to include k which is also square.

Are there other trivial solutions we should look out for? Aurifeullians?

Regards

Robert Smith