mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Conjectures 'R Us

Closed Thread
 
Thread Tools
Old 2007-01-06, 02:13   #12
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

5×701 Posts
Default

Quote:
Originally Posted by geoff View Post
A prime is needed for 92*17^n+1.
Oops.
jasong is offline  
Old 2007-01-06, 03:56   #13
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

24×7×17 Posts
Default

Quote:
Originally Posted by jasong View Post
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
robert44444uk is offline  
Old 2007-01-06, 04:07   #14
masser
 
masser's Avatar
 
Jul 2003
wear a mask

13×113 Posts
Default

Quote:
Originally Posted by jasong View Post

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.

Last fiddled with by masser on 2007-01-06 at 04:42
masser is offline  
Old 2007-01-06, 05:26   #15
Citrix
 
Citrix's Avatar
 
Jun 2003

32×52×7 Posts
Default

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))

Last fiddled with by Citrix on 2007-01-06 at 06:23
Citrix is offline  
Old 2007-01-06, 05:28   #16
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

24·7·17 Posts
Default

Quote:
Originally Posted by Citrix View Post
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 is offline  
Old 2007-01-06, 06:36   #17
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

24×7×17 Posts
Default How it is done

Quote:
Originally Posted by rogue View Post
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 is offline  
Old 2007-01-06, 06:42   #18
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

77016 Posts
Default Base 16 error

Quote:
Originally Posted by Citrix View Post

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 is offline  
Old 2007-01-06, 07:36   #19
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

24×7×17 Posts
Default Base 16 corrected

Quote:
Originally Posted by robert44444uk View Post
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
robert44444uk is offline  
Old 2007-01-06, 07:36   #20
Citrix
 
Citrix's Avatar
 
Jun 2003

62716 Posts
Default Base 16

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
Citrix is offline  
Old 2007-01-06, 07:41   #21
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

77016 Posts
Default Base 8 reconfirmed

Quote:
Originally Posted by Citrix View Post
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]

Quote:
Originally Posted by Citrix View Post
Jasong seems to be correct, it seems like base 6 riesel number.
???

Regards

Robert Smith
robert44444uk is offline  
Old 2007-01-06, 07:48   #22
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

24·7·17 Posts
Default Square trivials

Quote:
Originally Posted by Citrix View Post
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
robert44444uk is offline  
Closed Thread

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
Riesel/Sierp #'s for bases 3, 7, and 15 Siemelink Conjectures 'R Us 105 2009-09-04 06:40
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 04:54.

Fri Nov 27 04:54:40 UTC 2020 up 78 days, 2:05, 4 users, load averages: 1.19, 1.26, 1.19

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.