User group for PFGW & PrimeForm programs
Yahoo Group

Riesel/Sierpinski in base 3

===============================================
Guido Smetrijns     Message 1 of 43  May 24, 2004
-----------------------------------------------
Andrew, and all others,

It seems to me like if you're looking out for Riesel/Sierpinski numbers in the base 3. [k*3^n+/-1, k even of course, odd k's are trivial R/S numbers in odd bases]. 
You mention having found at least one prime for every even k up to 2 million, in both the plus and minus case. Great job, I like it! But I think you might be in for a long journey here... 
From a different point of view I recently did some elementary searching myself . As an example the smallest Riesel number (I only looked at the minus-case) found so far was the 27-digit number 169397207256533310164792176.
Maybe I can push this limit down one or two digits relatively easy, but at present I think it will be quite hard to find an even R/S-number of less than 20 digits, say. Unless I'm overlooking something trivial of course. Furthermore I don't have the appropriate tools (yet) or the time to go for an in-depth search but maybe some other guys out there can help... Anyone ?

Kind regards,
Guido Smetrijns.
Leuven - Belgium. 
   ----- Original Message ----- 
From: andrew_j_walker 
To: primeform@yahoogroups.com 
Sent: Friday, May 21, 2004 2:58 AM
Subject: [primeform] Looping until a prime is found


In pfgw, is there a way to use an ABC file or otherwise, so that
when testing k*b^n +- 1, when a prime is found that k value is stopped
and a new one started?

I've been doing some work on and off on k*3^n +- 1 and finding
the first prime for a given k value. At the moment I'm running
a pari script to find k values with no prime up to n=1000,
outputting these to a file and then testing further with proth.exe

I'd like to do this with pfgw so that
a) It may run faster
b) Tests are deterministic rather than probable in the n<=1000 stage
c) More automated.

With part c for instance, I'd like to be able to pick an n range of
say 1001-10000 and loop over all remaining k values without
having to manually stop and start for each one!

So far my results for both the plus and minus case have found primes
for all k up to 2 million, but this needs double checking for
typos, composites being declared prime, etc. before I place the
list somewhere.

Thanks,
Andrew

=============================================
Guido Smetrijns     Message 2 of 43  May 25, 2004
-----------------------------------------------
Hi Andrew, and all others,

It seems to me like if you're looking for Riesel/Sierpinski numbers in the base 3. [k*3^n+/-1, k even of course, odd k's are trivial R/S numbers in odd bases]. 
You mention having found at least one prime for every even k up to 2 million, in both the plus and minus case. Great job, I like it! But I think you might be in for a long journey here... 
From a different point of view I recently did some elementary searching myself . As an example the smallest Riesel number (I only looked at the minus-case) found so far was the 27-digit number k=169397207256533310164792176, which is way beyond the "size" of the base-2 R/S-problem.
Maybe I can push this limit down one or two digits relatively easy, but at present I think it will be quite hard to find an even R/S-number of less than 20 digits, say. Unless I'm overlooking something trivial of course. Furthermore I don't have the appropriate tools (yet) or the time to go for an in-depth search but maybe some other guys out there can help... Anyone ?

Kind regards,
Guido Smetrijns.
Leuven - Belgium. 
   ----- Original Message ----- 
From: andrew_j_walker 
To: primeform@yahoogroups.com 
Sent: Friday, May 21, 2004 2:58 AM
Subject: [primeform] Looping until a prime is found


In pfgw, is there a way to use an ABC file or otherwise, so that
when testing k*b^n +- 1, when a prime is found that k value is stopped
and a new one started?

I've been doing some work on and off on k*3^n +- 1 and finding
the first prime for a given k value. At the moment I'm running
a pari script to find k values with no prime up to n=1000,
outputting these to a file and then testing further with proth.exe

I'd like to do this with pfgw so that
a) It may run faster
b) Tests are deterministic rather than probable in the n<=1000 stage
c) More automated.

With part c for instance, I'd like to be able to pick an n range of
say 1001-10000 and loop over all remaining k values without
having to manually stop and start for each one!

So far my results for both the plus and minus case have found primes
for all k up to 2 million, but this needs double checking for
typos, composites being declared prime, etc. before I place the
list somewhere.

Thanks,
Andrew

===============================================
Shane     Message 3 of 43  May 25, 2004
-----------------------------------------------
You should try an algorithm like the Riesel Mersenne Algorithm.
It would be generalized to use base 3, rather than base 2.

In this case the algorithm passes the number of times k is divisable 
by 3, over to the base exponent, every time a prime is found.

k*3^n-1
For instance lets start with k and n = 1 
reset algorithm by finding 
the number of times k is divisable by 3.
1*3^1-1=2 Prime!reset alg 1*3^1-1 same since k is not divisable by 3.
3*3^1-1=8
6*3^1-1=17 Prime! reset alg 2*3^2-1
3*3^2-1=26
6*3^2-1=55
9*3^2-1=80
12*3^2-1=107 Prime! reset alg 4*3^3-1
6*3^3-1=161
9*3^3-1=242
12*3^3-1=323
15*3^3-1=404
18*3^3-1=485
21*3^3-1=566
24*3^3-1=647 Prime! reset agl 8*3^4-1
... and so on.

These primes always have the largerest exponent, when classified in 
order of their size(digit length).  Compared of course to other Base 
3 Riesel/Sierpinski primes.

===============================================
andrew_j_walker     Message 4 of 43  May 25, 2004
-----------------------------------------------
Hi Guido, I started this search as a bit of fun and out of curiosity.
What I've found out is that the highly composite k values are a lot
sparser, that's why I've been able to get up to 2 million. Perhaps
someday in the future someone will be able to apply a new method
and reduce your example significantly. Have you tried any other bases?

Andrew

--- In primeform@yahoogroups.com, "Guido Smetrijns" 
<guido.smetrijns@c...> wrote:
> Andrew, and all others,
> 
> It seems to me like if you're looking out for Riesel/Sierpinski 
numbers in the base 3. [k*3^n+/-1, k even of course, odd k's are 
trivial R/S numbers in odd bases]. 
> You mention having found at least one prime for every even k up to 
2 million, in both the plus and minus case. Great job, I like it! But 
I think you might be in for a long journey here... 
> From a different point of view I recently did some elementary 
searching myself . As an example the smallest Riesel number (I only 
looked at the minus-case) found so far was the 27-digit number 
169397207256533310164792176.
> Maybe I can push this limit down one or two digits relatively easy, 
but at present I think it will be quite hard to find an even R/S-
number of less than 20 digits, say. Unless I'm overlooking something 
trivial of course. Furthermore I don't have the appropriate tools 
(yet) or the time to go for an in-depth search but maybe some other 
guys out there can help... Anyone ?
> 
> Kind regards,
> Guido Smetrijns.
> Leuven - Belgium. 
===============================================
andrew_j_walker     Message 5 of 43  May 25, 2004
-----------------------------------------------
Shane, can you please send me a reference for this algorithm?
I'm not clear as to what it is doing and how it works.

Andrew

===============================================
Shane     Message 6 of 43  May 25, 2004
-----------------------------------------------
There no other know references, as far as I know.
Here is what I have found about the algorithm in base two:

A Mersenne prime would be generally considered a 
Riesel prime of the form:  (k*2^n-1) with n prime, and a fixed k = 1.

Definition:
If you take all the Riesel primes (k<2^n), and list them in order of 
their size,(digit length)
R=3  7  11 23 31 47 79 127 191 223 239 383 479 607 863 1087 1151 
1279...
n=2  3  2  3  5  4  4  7   6   5   4   7   5   5   5   6    7    
8 ...
you will see that Mersenne primes by default nature,  always have 
the largest exponent n, 
up that particular point.  Hence the natural question, "what about 
the other largest n?"   
Is there a distinguishing property?  The answer is yes!

Algorithm:
This general sequence of primes includes all Mersenne primes, within 
it.
The algorithm can be started from any known prime of the sequence, 
ie Mp.  
For instance starting with M7, the algorithm searches for the first 
prime, 
produced by an odd m:  (k*2^n-1) + (m*2^n)  = prime
127=(1*2^7-1)
(1*2^7-1) + (1*2^7) = 255 composite
(1*2^7-1) + (3*2^7) = 511 composite
(1*2^7-1) + (5*2^7) =767 composite
(1*2^7-1) + (7*2^7) =1023 composite
(1*2^7-1) + (9*2^7)=1279 is prime
next
1279= (5*2*8-1)
(5*2^8-1) + (1*2^8) = 1535 composite
(5*2^8-1) + (3*2^8) = 2047 composite 
(5*2^8-1) + (5*2^8) = 2559 composite
(5*2^8-1) + (7*2^8) = 3071 composite
(5*2^8-1) + (9*2^8) = 3583 is prime
next
3583 = (7*2^9-1)
repeat etc..

Mersenne numbers, and primes, that have already been double checked 
by (G.I.M.P.S.) 
need'nt be tested.  The maximum bound of m is some unknown but, 
multiples of n are 
used as an initial searching field.  If a prime is not found within 
the first multiple/s of n,  
then the next multiple is searched, etc.  
Though if you plan to continue to test for the next prime 
afterwards, 
multiple fields of n are your best option.  As soon as the first 
prime is found, 
the algorithm is reset  with the new exponent.  Technically n, is 
how many times two, 
appears as a factor of k, for each prime found during the 
algorithm.  
Those factors of two, are passed over to their proper, exponent 
index.  
For instance, if we take the expression of odd m above, and replace 
it with an even k.
(This is the algorithm)
k & n =  prime
4  0 = 3
2  2 = 7
4  3 =  31
4  5 = 127
10  7 = 1279
14  8 = 3583
10  9 = 5119
6  10 = 6143
4   11 = 8191   two is a factor of k, 13 times.
The exponents of two, from k on the left, are added to n on the 
right,  
p = 2+1+2+2+1+1+1+1+2 = 13 
This is true of any candidate's exponent, gM or Mn for that matter.

Distinguishing property: 
Regular Riesel primes, such as 11,23,47,79,191,223,239,383,... 
cannot nessesarily be used 
as starting points, to find the largest exponent n.  For instance 
from 191, 
the next prime found using it's k, and exponent, is 383.  Although, 
they are still in an increasing order, and eventually merge back 
into the general sequence, 
if you start from them.  The algorithm also works similarly with 
Proth primes of the form k*2^n+1. 
So one could also call this program RMPFA, or Riesel Mersenne Proth 
Fermat Algorithm. 
This will be investigated later as a Robinson project k*2^n+/-1, 
when enough data surrounding Mersenne primes is gathered. 
Regular Riesel's are much like tree branches, that merge into the 
stem, or master sequence.

Expected approximations:
Both k&n stay relatively the same size.  However n, is about twice 
as large, 
as the number of general Mersenne primes found, although there 
should be some 
logarithmic explanation involving  e^gamma.   This directly implies 
that Mersenne primes, 
can be used to estimate the next general Mersenne.
Mp = 2^p-1___gM = (p+2)*2^(p+2)-1  For example:  
2^20996011-1___(20996013)*2^(20996013)-1 
The variable is usually fairly small(though at it's largest after 
Mp), 
since it has to follow with (p+2).  Any gM can be used to 
approximate the next one, 
using this method.  This has been verified so far, up to M31.  
The first woodall prime, that is also a general Mersenne prime is, 
751*2^751-1

Factoring properties, of the algorithm's candidates:
M19 PRIME 
1048575 == 3 * 5 * 5 * 11 * 31 * 41__
2097151 == 7 * 7 * 127 * 337         
3145727 == 13 * 241979               
4194303 == 3 * 23 * 89 * 683_______
5242879 == 19 * 275941              
6291455 == 5 * 1258291              
7340031 == 3 * 3 * 3 * 271853______Every 3rd candidate is divisable 
by 3.
8388607 == 47 * 178481                
9437183 == 7 * 37 * 83 * 439         
10485759 == 3 * 3495253_________
11534335 == 5 * 2306867              
12582911 == 11 * 11 * 103991         
13631487 == 3 * 61 * 74489_______
14680063 gM 7 21 PRIME	            

In that same example,

M19 PRIME 
1048575 == 3 * 5 * 5 * 11 * 31 * 41__
2097151 == 7 * 7 * 127 * 337         
3145727 == 13 * 241979                
4194303 == 3 * 23 * 89 * 683        
5242879 == 19 * 275941               
6291455 == 5 * 1258291___________Every 5th candidate is divisable by 
5.
7340031 == 3 * 3 * 3 * 271853        
8388607 == 47 * 178481               
9437183 == 7 * 37 * 83 * 439        
10485759 == 3 * 3495253              
11534335 == 5 * 2306867__________
12582911 == 11 * 11 * 103991         
13631487 == 3 * 61 * 74489           
14680063 gM 7 21 PRIME             
This is true of any factor found, from it's first appearence 
onwards.  
Once a prime is found, the remainder of the sieved newpgen file, 
can be used to help sieve the next gM, since the algorithm overlaps 
some of it's candidates.  
(See "Salvaging old Newpgen files" below)

Estimation:
With k<2^n, the probability, that (k*2^n-1) is prime should be about 
1/log(k*2^n-1).

From a visual standpoint, Mersenne primes, tend to be on the lower 
side of the logarithmic wave, 
like steps.  We see that after every Mersenne, there is a tendency 
to have a very large gap, 
between it and the next gM.

Visuals of Mersenne steps:
1 2  M1
1 3  M2
1 5  M3
1 7  M4
5 8  

1 13 M5  
5 14 

1 17 M6  
1 19 M7
7 21 

1 31 M8  
5 32

1 61 M9   
3 64   

1 89 M10  
3 94   

1 107  M11 
9 109 

1 127  M12
95 128  

1 521  M13
681 522

1 607  M14
113 608 

1 1279  M15
1127 1280  

1 2203  M16
3113 2204

1 2281  M17
143 2284

1 3217  M18
55 3221

1 4253  M19
741 4254

1 4423  M20
153 4426

1 9689  M21
1053 9690

1 9941  M22
103 9943

1 11213  M23
91 11217

1 19937  M24
769 19939 

1 21701  M25
669 21705

1 23209  M26
7841 23210

1 44497  M27
6615 44499

1 86243  M28
1541 86246

1 110503  M29
25415 110504

1 132049  M30
86071 132051
25341 132053
85025 132054 

1 216091  M31
62431 216093 
97065 216095

Program to find these primes in base two found here, RMA.RAR
http://15k.org/rma/

Group here:
http://mersenneforum.org/forumdisplay.php?f=16
===============================================
andrew_j_walker     Message 7 of 43  Jun 2, 2004
-----------------------------------------------
Unfortuneately a few computer/power outages have slowed my run
down but hopefully in the next few days I'll be able to complete it.
For fun I extracted a list of the first 10000 prps found to
see how pfgw would go at proving them prime. Using -f -tp 
pfgw-prime.log had 9921 entries and pfgw.log had none. Checking the
log file I found some entries of the following type:

Primality testing 1588*3^13-1 [N-1/N+1, Brillhart-Lehmer-Selfridge]
factors: 2531784923

However, testing without -f could prove this prime. Is this related
to the bug Jim previously mentioned? There were several more examples
of this, the next for 1808*3^13-1

Andrew
===============================================
jim_fougeron     Message 8 of 43  Jun 3, 2004
-----------------------------------------------
--- In primeform@yahoogroups.com, "andrew_j_walker" <ajw01@u...> 
wrote:
> 
> Unfortuneately a few computer/power outages have slowed my run
> down but hopefully in the next few days I'll be able to complete it.
> For fun I extracted a list of the first 10000 prps found to
> see how pfgw would go at proving them prime. Using -f -tp 
> pfgw-prime.log had 9921 entries and pfgw.log had none. Checking the
> log file I found some entries of the following type:
> 
> Primality testing 1588*3^13-1 [N-1/N+1, Brillhart-Lehmer-Selfridge]
> factors: 2531784923
> 
> However, testing without -f could prove this prime. Is this related
> to the bug Jim previously mentioned? There were several more 
examples
> of this, the next for 1808*3^13-1

This is a "similar" but different bug.   I will add that to the
to get fixed.

 > Andrew 
===============================================
jim_fougeron     Message 9 of 43  Jun 3, 2004
-----------------------------------------------
This bug (and others) have been fixed, and a updated development
version of PFGW has been placed into the OpenPFGW yahoo groups' 
file folder.   I will not place the Win32 EXE files into this
group (primeform), until this build has time for some people to
use it.  However, if I hear of no complaints, I will put that 
version into the primeform file folder in a few weeks.

Jim.

--- In primeform@yahoogroups.com, "andrew_j_walker" <ajw01@u...> 
wrote:
> 
> Unfortuneately a few computer/power outages have slowed my run
> down but hopefully in the next few days I'll be able to complete it.
> For fun I extracted a list of the first 10000 prps found to
> see how pfgw would go at proving them prime. Using -f -tp 
> pfgw-prime.log had 9921 entries and pfgw.log had none. Checking the
> log file I found some entries of the following type:
> 
> Primality testing 1588*3^13-1 [N-1/N+1, Brillhart-Lehmer-Selfridge]
> factors: 2531784923
> 
> However, testing without -f could prove this prime. Is this related
> to the bug Jim previously mentioned? There were several more 
examples
 > of this, the next for 1808*3^13-1
> 
> Andrew 
===============================================
andrew_j_walker     Message 10 of 43  Jun 8, 2004
-----------------------------------------------
Thanks for the updates Jim. I've now also finished the k*3^n+1
run up to n=10 million and k=8191. The only difference this time is
I added a few more fermat test bases and factoring to 1000 if it
passes these tests (not before!!). This adds a little to the testing 
time, but should significantly decrease the number of composites 
getting through. I'm now running the composite file (3.33 million 
entries!) through the newest winpfgw using -f -tp. I'll report
any it has problems with here.

Andrew

===============================================
andrew_j_walker     Message 11 of 43  Jun 16, 2004
-----------------------------------------------
Jim and all,

I finally managed to get the winpfgw run completed which I mentioned 
below. The good news is that with the extra bases used and the trial 
factoring no pseudo-primes slipped through. The bad news is that I
found 23 numbers that were missing from pfgw-prime.log , i.e.
pfgw -f -tp returned as composite. I checked these with
Dario Alpern's factoring applet and they all were found to be true 
primes. Note that the powers are all clustered together (except for
two with n=7) so it may be an FFT length problem. However they are
all declared as PRPs so maybe not. I also noticed for the first few
that checking without the -f will prove them prime.

The machine that produced this problem was a P4. I checked on an 
older machine (3) and it didn't have this problem. Here's an example
where the proving doesn't work:

C:\ajw\base3>pfgw -f -i -tp -q208496*3^39-1
PFGW Version 20040608.Win_Dev (Beta 'caveat utilitor') [FFT v23 w/P4]

***** Using functions from the static linked GMP library

CPU Information (From Woltman v22 library code)
Intel(R) Pentium(R) 4 CPU 1.50GHz
CPU speed: 1513.57 MHz
CPU features: RDTSC, CMOV, PREFETCH, MMX, SSE, SSE2
L1 cache size: 8 KB
L2 cache size: 256 KB
L1 cache line size: 64 bytes
L2 cache line size: 64 bytes
TLBS: 64

Primality testing 208496*3^39-1 [N+1, Brillhart-Lehmer-Selfridge]
trial factoring to 65536
Running N+1 test using discriminant 29, base 1+sqrt(29)
Running N+1 test using discriminant 29, base 2+sqrt(29)
208496*3^39-1 is composite (0.0216s+0.0017s)

Andrew

208496*3^39-1
1711312*3^40-1
2039008*3^42-1
2234744*3^33-1
2235880*3^39-1
3677336*3^35-1
4738784*3^33-1
5281352*3^36-1
5564912*3^32-1
6372964*3^7-1
6648752*3^40-1
6797008*3^34-1
7160248*3^30-1
7552672*3^28-1
8435168*3^34-1
8454136*3^35-1
8911112*3^36-1
8921680*3^34-1
8967794*3^7-1
9217396*3^31-1
9497560*3^38-1
9510824*3^33-1
9521204*3^33-1


===============================================
jim_fougeron     Message 12 of 43  Jun 16, 2004
-----------------------------------------------
--- In primeform@yahoogroups.com, "andrew_j_walker" <ajw01@u...> 
wrote:
> 
> Jim and all,
> 
> I finally managed to get the winpfgw run completed which I 
mentioned 
> below. The good news is that with the extra bases used and the 
trial 
> factoring no pseudo-primes slipped through. The bad news is that I
> found 23 numbers that were missing from pfgw-prime.log , i.e.
> pfgw -f -tp returned as composite. I checked these with
> Dario Alpern's factoring applet and they all were found to be true 
> primes. Note that the powers are all clustered together (except for
> two with n=7) so it may be an FFT length problem. However they are
> all declared as PRPs so maybe not. I also noticed for the first few
> that checking without the -f will prove them prime.
> 
> The machine that produced this problem was a P4. I checked on an 
> older machine (3) and it didn't have this problem. Here's an 
example
> where the proving doesn't work:
> 
> C:\ajw\base3>pfgw -f -i -tp -q208496*3^39-1
> PFGW Version 20040608.Win_Dev (Beta 'caveat utilitor') [FFT v23 
w/P4]

I see the same for this number on the 20040608 version also.  The 
20040205 version does correctly list this as prime. 

When I run it with the "broken" PFGW using verbose=true in the 
pfgw.ini, I get this:

Primality testing 208496*3^39-1 [N+1, Brillhart-Lehmer-Selfridge]
trial factoring to 65536
Running N+1 test using discriminant 29, base 1+sqrt(29)
Adjusting authentication level by 1 for PRIMALITY PROOF
non-SSE2 FFT: 176 bit request FFT size=(40,6) - [from (40,23)]
Using 'Generic' modular reduction code
Running N+1 test using discriminant 29, base 2+sqrt(29)
Adjusting authentication level by 1 for PRIMALITY PROOF
SSE2 FFT: 176 bit request FFT size=(64,4) - [from (64,23)]
Using 'Generic' modular reduction code
208496*3^39-1 is composite (0.0066s+0.0002s)

a 64 limb FFT with 4 bit limbs.  Something is VERY VERY wrong there.
In the working (v 20040205), this is the FFT's chosen

Primality testing 208496*3^39-1 [N+1, Brillhart-Lehmer-Selfridge]
trial factoring to 65536
Running N+1 test using discriminant 29, base 1+sqrt(29)
Using non-SSE2 FFT
Adjusting authentication level by 1 for PRIMALITY PROOF
Reduced from FFT(40,23) to FFT(40,22)
Reduced from FFT(40,22) to FFT(40,21)
Reduced from FFT(40,21) to FFT(40,20)
Reduced from FFT(40,20) to FFT(40,19)
Reduced from FFT(40,19) to FFT(40,18)
Reduced from FFT(40,18) to FFT(40,17)
Reduced from FFT(40,17) to FFT(40,16)
176 bit request FFT size=(40,16)
Running N+1 test using discriminant 29, base 2+sqrt(29)

I am not sure what went wrong, but I can easily find out why
it chose such an obviously wrong FFT size.

Jim.

===============================================
jim_fougeron     Message 13 of 43  Jun 17, 2004
-----------------------------------------------
There is a new build (dev build) of PFGW contained within the OpenPFGW
Yahoo group's file folder.  This version fixes the bug listed here,
and it also should now again be buildable under Linux. Greg is working
on making sure that is so, and building a "static" linked pfgw for
Linux.

Thanks Andrew for reporting this.

Jim.

===============================================
Ulrich Thiel     Message 14 of 43  Jun 18, 2004
-----------------------------------------------
Hi!

The newest release works fine! Great work!
The problem with the configure scripts was Gentoo Linux specific. I've 
found a message describing the solution in the archive: You have to 
unset the CC and CXX global variables. Perhaps you can add

#gentoo specific
unset CC
unset CXX

to the beginning of the main configure script!? After this the script 
works fine.

Ulrich Thiel

===============================================
masserto     Message 15 of 43  Sep 3, 2004
-----------------------------------------------
Dear Guido,

I recently found that 2*k*3^n-1 is always composite if

k=739171331147778631

The "covering set" for this Riesel number is:

{5,7,13,17,19,37,73,97,577,757,769}

Has anyone found a smaller k so that 2*k*3^n-1 is always composite?

Best regards,
Tom Masser

===============================================
Guido Smetrijns     Message 16 of 43  Sep 4, 2004
-----------------------------------------------
Dear Tom,

My congratulations and applause for your 18-digit Riesel number in base 3,
quite an improvement on my initial 27-digit finding! I guess it must have
kept you busy for some time! However, I think there is a possibility that
your current record might be broken again.
After your announcement I had another look at the problem and discovered a
covering set with only 10 elements, compared to the 11-element covering set
of yours. This set is {5,7,13,19,37,73,109,433,757,8209} and the
corresponding product is 6848415653309939345, which is about half of the
product of {5,7,13,17,19,37,73,97,577,757,769} = 12933267788230776805.
This means that, statistically, the solutions to a system of linear
congruences (via CRT) will also be smaller.
With this in mind, I "manually" solved as a test-case one such system (10
congruences) and came up with a 19-digit solution k=2595760713702375057.
Since the number of possible systems of linear congruences can be quite
high, I suppose we still haven't hit the bottom line here
In order to work this thing further out, however, I would need two things:
First, a way to generate all possible systems of linear congruences for a
given covering set, and secondly, a "tool" or "CRT-applet" for easily
solving such a system with large integer coefficients. So far I haven't
found anything on the internet yet...
And maybe still smaller covering sets are just waiting to be discovered...
Any help is welcome!

Kind regards,
Guido Smetrijns
Leuven - Belgium.

===============================================
Mikael Klasson     Message 17 of 43  Sep 4, 2004
-----------------------------------------------
Hi,

here's a smaller 14-digit k with 9 elements in the covering set:
k=17630689120601, covering set {5,7,13,17,19,37,41,193,757}

It's shamelessly based off of Tom's solution, and can probably be optimized
further.

Cheers,
Mikael

===============================================
Guido Smetrijns     Message 18 of 43  Sep 4, 2004
-----------------------------------------------
Hi Mikael,

Congrats to you too!
But, as you suspected already yourself, still not optimal : 15618563306548
is the one to beat now (same covering set).
Who's next? Let's aim for a 13-digit one!
Can the covering set still be improved? Hmmm, I doubt it...

Greetz,
Guido.

===============================================
Mikael Klasson     Message 19 of 43  Sep 5, 2004
-----------------------------------------------
Hi Guido,

here's an 11-digit k for you!

k=31532322469, same covering set.

Cheers,
Mikael

===============================================
andrew_j_walker     Message 20 of 43  Sep 5, 2004
-----------------------------------------------
--- In primeform@yahoogroups.com, "masserto" <masserto@y...> wrote:
> 
> Dear Guido,
> 
> I recently found that 2*k*3^n-1 is always composite if
> 
> k=739171331147778631
> 
> The "covering set" for this Riesel number is:
> 
> {5,7,13,17,19,37,73,97,577,757,769}
> 
> Has anyone found a smaller k so that 2*k*3^n-1 is always composite?
> 
> Best regards,
> Tom Masser
> 

Nice work, that's smaller than any I remember seeing. Have you looked
at the plus case?

Andrew
===============================================
andrew_j_walker     Message 21 of 43  Sep 5, 2004
-----------------------------------------------
--- In primeform@yahoogroups.com, Mikael Klasson <mikkl605@s...> 
wrote:
> Hi Guido,
> 
> here's an 11-digit k for you!
> 
> k=31532322469, same covering set.
> 
> Cheers,
> Mikael
> 

Brilliant! Now we're getting to the range where testing all lower k 
might be possible. I've been testing plus and minus up to 10 million,
however going up to 10^9 would be reasonable, or even higher
if the range of n is limited to start with.

Andrew
===============================================
Payam Samidoost     Message 22 of 43  Sep 5, 2004
-----------------------------------------------
> > here's an 11-digit k for you!
> > k=31532322469, same covering set.
> 
> Brilliant! Now we're getting to the range where testing all lower k 
> might be possible. I've been testing plus and minus up to 10 million,
> however going up to 10^9 would be reasonable, or even higher
> if the range of n is limited to start with.
> 

Do NOT forget the dual approach, as it can sieve out MANY candidates.

Payam
===============================================
andrew_j_walker     Message 23 of 43  Sep 5, 2004
-----------------------------------------------
--- In primeform@yahoogroups.com, "Payam Samidoost" <sami@a...> wrote:
> 
> > > here's an 11-digit k for you!
> > > k=31532322469, same covering set.
> > 
> > Brilliant! Now we're getting to the range where testing all lower 
k 
> > might be possible. I've been testing plus and minus up to 10 
million,
> > however going up to 10^9 would be reasonable, or even higher
> > if the range of n is limited to start with.
> > 
> 
> Do NOT forget the dual approach, as it can sieve out MANY 
candidates.
> 
> Payam

Thanks for the reminder about these, if I go much higher I will
use this however up to 10 million I'll try to get as many primes as
possible in the k*3^n+-1 form. I'll have to modify the script I was
using to output the dual primes found as well. Unfortuneately
the duals are more limited as you have to use a general prime test
on them rather than a proth-like test.

Andrew
===============================================
Payam Samidoost     Message 24 of 43  Sep 5, 2004
-----------------------------------------------
Hi Andrew

> Thanks for the reminder about these, if I go much higher I will
> use this however up to 10 million I'll try to get as many primes as
> possible in the k*3^n+-1 form. I'll have to modify the script I was
> using to output the dual primes found as well. Unfortuneately
> the duals are more limited as you have to use a general prime test
> on them rather than a proth-like test.

Small exponent duals (which can easily be *proved* prime) can sieve out MANY
of the candidates (up to %80). I strongly recommend testing them just from
the begining.

Even large exponent duals which remain *probable* primes, still can narraw
the search FAR faster than the positive side.

I recall that we are doing some practical work here, to find the smallest k.
Considering the duals may be a great practical improvement.

Yours,
Payam
===============================================
andrew_j_walker     Message 25 of 43  Sep 5, 2004
-----------------------------------------------
--- In primeform@yahoogroups.com, "Payam Samidoost" <sami@a...> wrote:
> Hi Andrew
> 
> > Thanks for the reminder about these, if I go much higher I will
> > use this however up to 10 million I'll try to get as many primes 
as
> > possible in the k*3^n+-1 form. I'll have to modify the script I 
was
> > using to output the dual primes found as well. Unfortuneately
> > the duals are more limited as you have to use a general prime test
> > on them rather than a proth-like test.
> 
> Small exponent duals (which can easily be *proved* prime) can sieve 
out MANY
> of the candidates (up to %80). I strongly recommend testing them 
just from
> the begining.
> 
> Even large exponent duals which remain *probable* primes, still can 
narraw
> the search FAR faster than the positive side.
> 
> I recall that we are doing some practical work here, to find the 
smallest k.
> Considering the duals may be a great practical improvement.
> 

I intend to do the duals as well, what I plan is:

a) Search both without duals up to k=10^7, what I'm doing now
b) Search both with duals up to a higher k.
I initially did this a year or so ago up to around 1 million, however
using the faster pfgw with scripting it should be possible to go a lot
further (maybe 10^9 or more).

Andrew
===============================================
Mikael Klasson     Message 26 of 43  Sep 6, 2004
-----------------------------------------------
Hi,

here's an 11-digit candidate for the 2*k*3^n+1 case:

k=62525488043, covering set {5,7,13,17,19,37,41,193,757}

Does anyone have a smaller k?

Mikael
===============================================
Guido Smetrijns     Message 27 of 43  Sep 6, 2004
-----------------------------------------------
First of all my congratulations and standing ovation for Mikael Klasson !!!
Very "klassy", Mikael!

I never expected such a low k-value was possible!
Meanwhile my poor old PC has been able to proof overnight that k=31532322469
is indeed the minimal value for the covering set
{5,7,13,17,19,37,41,193,757}. If this k is still to be improved, it will
thus require an even more appropriate covering set !!

Secondly, we might indeed start to think about trying the other way, from
the bottom up.
If I understand well, Andrew Walker has already searched all k values less
then 10 million, both in the plus and the minus case.
I hereby assume that all k-values < 10,000,000 did not produce a possible
Riesel/Sierpinski number, and furthermore I assume that the "tested"
expression was k*3^n+-1 in stead of 2k*3^n+-1, so all tested k-values were
actually already even to start with. Andrew, can you confirm this?.

The reason for pointing this out is the fact that I did some testing myself
above 10 million in the minus case. The first possible Riesel candidate I
discovered was k=10,789,522. More accurately, the expression 10789522*3^n-1
is composite for all n<620000.  It will thus require a "new record base-3
Proth prime" to demolish the current Riesel character of this number, if at
all possible.
I personally gave up exploring this value any further, but if someone else
wants to give it a try, I would be glad to pass him/her my previous results
and my sieving files (sieved to a depth of 25*10^9).

Kind regards,
Guido.

===============================================
andrew_j_walker     Message 28 of 43  Sep 6, 2004
-----------------------------------------------
--- In primeform@yahoogroups.com, "Guido Smetrijns" <guido@s...> 
wrote:
> First of all my congratulations and standing ovation for Mikael 
Klasson !!!
> Very "klassy", Mikael!
> 
> I never expected such a low k-value was possible!
> Meanwhile my poor old PC has been able to proof overnight that 
k=31532322469
> is indeed the minimal value for the covering set
> {5,7,13,17,19,37,41,193,757}. If this k is still to be improved, it 
will
> thus require an even more appropriate covering set !!
> 
> Secondly, we might indeed start to think about trying the other 
way, from
> the bottom up.
> If I understand well, Andrew Walker has already searched all k 
values less
> then 10 million, both in the plus and the minus case.

Only up to about k=40,000 or so, more for k<10^6

> I hereby assume that all k-values < 10,000,000 did not produce a 
possible
> Riesel/Sierpinski number, and furthermore I assume that the "tested"
> expression was k*3^n+-1 in stead of 2k*3^n+-1, so all tested k-
values were
> actually already even to start with. Andrew, can you confirm this?.

I only used even k, up to moderate limits. When I start a new search
I'll go deeper than I previously did for the dual case.

> The reason for pointing this out is the fact that I did some 
testing myself
> above 10 million in the minus case. The first possible Riesel 
candidate I
> discovered was k=10,789,522. More accurately, the expression 
10789522*3^n-1
> is composite for all n<620000.  It will thus require a "new record 
base-3
> Proth prime" to demolish the current Riesel character of this 
number, if at
> all possible.
> I personally gave up exploring this value any further, but if 
someone else
> wants to give it a try, I would be glad to pass him/her my previous 
results
> and my sieving files (sieved to a depth of 25*10^9).
> 
> Kind regards,
> Guido.
> 
Guido, that matches with the lowest k I found as well, I tested up
to about n=200,000. However I didn't go very far with the dual
of abs(k-3^n). Does anyone know what to do if this dual turns out to
be 1,3,5 or 7 ??

Andrew
===============================================
andrew_j_walker     Message 29 of 43  Sep 6, 2004
-----------------------------------------------
> Guido, that matches with the lowest k I found as well, I tested up
> to about n=200,000. However I didn't go very far with the dual
> of abs(k-3^n). Does anyone know what to do if this dual turns out to
> be 1,3,5 or 7 ??
> 
> Andrew

Actually a post has just come through to the number theory mailing 
list from Eric Brier stating:

"If a number n is such that n*2^k + 1 is composite for all k due to a 
covering set of primes, this set of primes ensures also that 2^k + n 
is composite for all k, maybe with very special case of 2^k + n = one 
of the covering primes"

So how can we be sure in the dual case we don't eliminate one of
the special cases by mistake?

Andrew
===============================================
Mikael Klasson     Message 30 of 43  Sep 7, 2004
-----------------------------------------------
Thank you, Guido.

For the curious, I've searched through all k less than 31532322469, checking
if any of them has a covering set under the following conditions:

1. each prime p in the set is smaller than 10^6
2. each prime p in the set has order(3,p)<=200
3. k != 0 (mod 3)

No match was found until 31532322469.
In retrospect the order bound of 200 was probably a bit low. Nevertheless,
the chance of a smaller k seems very slim to me.

Cheers,
Mikael

===============================================
andrew_j_walker     Message 31 of 43  Sep 8, 2004
-----------------------------------------------
Below is the scriptify script based on bits from other people
and myself I was going to use to investigate this further. 
Unfortuneately it seems a bit too slow to use up to large k, can 
anyone offer suggestions for speeding it up? Note that the n=300 I 
chose to split between using the isPRP() function and pfgws PRP()
test is arbitary. For the vast majority of k a pseudoprime
will be found for n<300. From a similar script I was using checking
the non-dual case, pfgw is by far faster than something like pari
for larger n, but maybe pari is faster for smaller n?

At present isPRP() uses only a base 5 test, as the comment suggests
I also have tried this using a number of bases, reducing the number of
bases had little change on the speed. Using the 5 bases followed by
factoring up to 10000 should eliminate all but the stubbornest 
composites!

Andrew

int isPRP(int val) {
int prp5;
int prp101;
int prp137;
int prp11;
int prp67;

factorize(val,2,100);

if(FACTORFOUND>1) {
if (FACTORFOUND==val) {
return 1;
}
return 0;
}

prp5=powmod(5,val-1,val); /* check for PRP-5 */
if(prp5==1) {

factorize(val,2,10000); 

if(FACTORFOUND>1) {
if (FACTORFOUND==val) {
return 1;
}
return 0;
}

return 1; /* number is PRP-5,PRP-137,PRP-101,PRP-11 and 
PRP-67 */



}

return 0;
}

file log1000;
file logmissing;
file logmissing2;
log1000 = fopen("duals.txt", "a");
logmissing = fopen("no_dual_plus.txt", "a");
logmissing2 = fopen("no_dual_minus.txt", "a");
int k = 2;
int nextoutput = k+1000;
int n;
int tmp1;
int tmp2;
int tmp3;
int tmp4;
int tmp5;
int missing=0;
int found;
for (; k <= 10000000; k = k + 2) {
if (k % 3) {
found=0;
for (n = 1; n < 8192; n = n + 1) {
tmp1 = k*3^n+1;
tmp2 = k+3^n;
if (n<300) { 
tmp3 = isPRP(tmp1);
tmp4 = isPRP(tmp2);
}
if (n>=300) {
tmp3 = PRP(tmp1);
tmp4 = PRP(tmp2);
}
if (tmp3 == 1) {
found=1;
if (n >= 1000) {
fprintf(log1000, "%d*3^%d+1", k, n);
}
n=1000000; /* to get out of the loop */
}
if (tmp4 == 1) {
if (found == 0) { 
found=1;
if (n >= 1000) {
fprintf(log1000, "%d+3^%d", k, n);
}
}
n=1000000; /* to get out of the loop */     
}
}
if (found == 0) {
missing = missing + 1;
fprintf(logmissing, "%d", k);
}
found=0;
for (n = 1; n < 8192; n = n + 1) {
tmp1 = k*3^n-1;
tmp2 = 3^n-k;
if (tmp2<0) {
tmp2= -tmp2;
}
if (n<300) { 
tmp3 = isPRP(tmp1);
tmp4 = isPRP(tmp2);
}
if (n>=300) {
tmp3 = PRP(tmp1);
tmp4 = PRP(tmp2);
}
if (tmp3 == 1) {
found=1;
if (n >= 1000) {
fprintf(log1000, "%d*3^%d-1", k, n);
}
n=1000000; /* to get out of the loop */
}
if (tmp4 == 1) {
if (found == 0) {
found=1;
if (n >= 1000) {
fprintf(log1000, "abs(%d-3^%d)", k, n);
}
}
n=1000000; /* to get out of the loop */
}     
}
if (found == 0) {
missing = missing + 1;
fprintf(logmissing2, "%d", k);
}

if (k > nextoutput) {
nextoutput += 1000;
printf ("Finished k=%d (%d not found)\n", k, missing);
}
}
}
===============================================
jim_fougeron     Message 32 of 43  Sep 9, 2004
-----------------------------------------------
The biggest speedup is to not use PFGW, but to use a custom C program
with GMP.  With C (or C++), you can do true sieving, and thus not
speed up by an order of magnitude.

I would recommend GMP to test up to like n=300.  Any k's which are
"missing" from that, can be run through a script like seen below.
That script would read from a file, vs a for loop.  Very few k's
would live past 300.  I could probably pump out a program based upon
what I see below (and using the GMP dll's in our file folders), in 
a very short time (an hour or so).

Jim.

===============================================
jim_fougeron     Message 33 of 43  Sep 9, 2004
-----------------------------------------------
I have written a very quick C program, that does this:

1st it builds a bit array of all primes from 3 to 2^31-1.

It then loops over k's, looping over n's.  

It tests k+3^n until that value is over 2^31, or a prime is found.
If no prime is found, it then tests k*3^n+1 up to where k*3^n+1 
exceeds 2^31 or a prime is found.  If no prime found, then it outputs
this to a log file.

Then it does the same for 3^n-k (abs of course), and k*3^n-1.  
Stopping if the results exceeds 3^31 or if a prime is found.

The program takes about 30 seconds to fill the prime bitmap.  It
then takes about .5s to compute k's from 2 to 1000000.   There were
3200 values (1676 of the +'s and 1524 of -'s) which no small prime
was found.  Those are all of the values left, and these could 
be "fed" back into a PFGW script, or an "extension" of my program.

NOTE that as k gets larger, then only checking the expressions that
are under 2^31 is not adequate, however, it does still cut down
a run of 100,000,000 into only 1657756 candidates. I am sure that
if I did some real quick testing using GMP (up to say n=50), there
would be only a few hundred left.  

Jim.

===============================================
andrew_j_walker     Message 34 of 43  Sep 9, 2004
-----------------------------------------------
Thanks Jim, I wouldn't mind getting a copy of your siever to try
running on some larger k ranges. Since my last post I remembered
that I wrote a simple gmp program last year which just did prp
tests up to n=1023 without any trail division (although
mpz_probab_prime_p() does internally trial divide to some small 
limit). I'll put a copy at the bottom if anyone wants to do 
comparisons.

I only ever ran this for the minus case, the output looks like
3606326
5539472
10789522
15719414
16184054
.
.
.
960068014
962539444
962798786
964544428
(598 entries).

Before this I did a search for both up to n=500 and k=100 million.
(using pari).
I did a lot of work on the k.3^n+-1 values finding primes for nearly 
all of them, but almost no work on k+3^n or abs (k-3^n).

 --- In primeform@yahoogroups.com, "jim_fougeron" <jfoug@c...> wrote:
> I have written a very quick C program, that does this:
> 
> 1st it builds a bit array of all primes from 3 to 2^31-1.
> 
> It then loops over k's, looping over n's.  
> 
> It tests k+3^n until that value is over 2^31, or a prime is found.
> If no prime is found, it then tests k*3^n+1 up to where k*3^n+1 
> exceeds 2^31 or a prime is found.  If no prime found, then it 
outputs
> this to a log file.
> 
> Then it does the same for 3^n-k (abs of course), and k*3^n-1.  
> Stopping if the results exceeds 3^31 or if a prime is found.
> 
> The program takes about 30 seconds to fill the prime bitmap.  It
> then takes about .5s to compute k's from 2 to 1000000.   There were
> 3200 values (1676 of the +'s and 1524 of -'s) which no small prime
> was found.  Those are all of the values left, and these could 
> be "fed" back into a PFGW script, or an "extension" of my program.
> 
> NOTE that as k gets larger, then only checking the expressions that
> are under 2^31 is not adequate, however, it does still cut down
> a run of 100,000,000 into only 1657756 candidates. I am sure that
> if I did some real quick testing using GMP (up to say n=50), there
> would be only a few hundred left.  
> 
> Jim.
> 

#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>

main (int argc, char **argv)
{
long n,fc,done;
mpz_t k,x,y;

FILE * NumStream;

mpz_init(k);
mpz_init(x);
mpz_init(y);

mpz_init_set_ui(k,2);

while(1)
{
done=0;
mpz_set_ui(y,1);
for(n=1;n<=1023;n++)
{
mpz_mul_ui(y,y,3); /* y=3^n */
mpz_mul(x,y,k);
mpz_sub_ui(x,x,1); /* x=k*3^n-1 */
if( (mpz_probab_prime_p(x,10)>0) )
{
done=1;
n=1023;
}
if(done==0)
{
mpz_sub(x,k,y); /* x=k-y=k-3^n */
mpz_abs(x,x);   /* x=abs(k-3^n) */
if( (mpz_probab_prime_p(x,10)>0) )
{
done=1;
n=1023;
}
}
}
if(done==0)
{
gmp_printf("%Zd\n",k);
NumStream = fopen("dualminus.txt","a");
gmp_fprintf(NumStream,"%Zd\n",k);
fclose(NumStream);
}
mpz_add_ui(k,k,2);
if( mpz_divisible_ui_p(k,3) )
mpz_add_ui(k,k,2);
}

mpz_clear(k);
mpz_clear(x);
mpz_clear(y);
return(0);
} 
===============================================
jim_fougeron     Message 35 of 43  Sep 9, 2004
-----------------------------------------------
Here are all of the 3^n + and 3^n - that are left over. They are
"clean" up to n=10000.  All k's up to 100 million were tested.
The pfgw input file will stop processing a k, when a PRP is found
for it (Of course you will need to make sure the prp is prime later).
It is setup to test from n=10000 to n=20000.   After you get to 20k,
then remove any "k" values found (the a: param), adjust the n value
to a higher range (the b: value), and re-run.   

If you want, I can push from the k range 10^8 up to 10^9 pretty
easily.  I will not test "as" deeply (probably cutoff at n=2000,
but there should not be more than 100 at that level.

ABC2 $a+3^$b | $a*3^$b+1 // {number_primes,$a,1}
a: in { 2621746 11013584 48886226 59054564}
b: from 10000 to 20000

ABC2 3^$b-$a | $a*3^$b-1 // {number_primes,$a,1}
a: in { 10789522 23375192 29140796 36730222}
b: from 5000 to 10000

NOTE there are 4 candidates in the + side, and 4 in the - side

So far no k under 10^8 (which I have tested) appear to have a 
covering set of factors, but the above 8 candidates are VERY sparse.

Jim.

PS:
One nice thing out of this "test" was that your script found a bug
in the new dev version of PFGW (which was not in the "older" stable
version).  In the new version, I have de-coupled the expression 
parser from the rest of the program (am still working on that), and
have created an "easy_eval" set of functions.  Well there was some
behavior missing (calling the easy_eval_GetInteger() with a literal
number, and not a "symbol" number was failing).


===============================================
andrew_j_walker     Message 36 of 43  Sep 9, 2004
-----------------------------------------------
Below the numbers I've put some data on which of these k values I 
found primes for. There could of course be a smaller n prime for the
dual form.
 --- In primeform@yahoogroups.com, "jim_fougeron" <jfoug@c...> wrote:
> Here are all of the 3^n + and 3^n - that are left over. They are
> "clean" up to n=10000.  All k's up to 100 million were tested.
> The pfgw input file will stop processing a k, when a PRP is found
> for it (Of course you will need to make sure the prp is prime 
later).
> It is setup to test from n=10000 to n=20000.   After you get to 20k,
> then remove any "k" values found (the a: param), adjust the n value
> to a higher range (the b: value), and re-run.   
> 
> If you want, I can push from the k range 10^8 up to 10^9 pretty
> easily.  I will not test "as" deeply (probably cutoff at n=2000,
> but there should not be more than 100 at that level.
> 
> ABC2 $a+3^$b | $a*3^$b+1 // {number_primes,$a,1}
> a: in { 2621746 11013584 48886226 59054564}
> b: from 10000 to 20000

2621746*3^119335+1 is prime (dual tested to 10000)
11013584*3^100378+1 is prime(dual tested to 10000)
48886226*3^51212+1 is prime (dual tested to 10000)
59054564*3^64030 is prime   (dual tested to 10000

> ABC2 3^$b-$a | $a*3^$b-1 // {number_primes,$a,1}
> a: in { 10789522 23375192 29140796 36730222}
> b: from 5000 to 10000
> 

10789522*3^n-1 no prime up to n=200000
23375192*3^n-1 no prime up to n=150062
29140796*3^n-1 no prime up to n=150062
36730222*3^15624-1 is prime

> NOTE there are 4 candidates in the + side, and 4 in the - side
> 
> So far no k under 10^8 (which I have tested) appear to have a 
> covering set of factors, but the above 8 candidates are VERY sparse.
> 
> Jim.
> 
> PS:
> One nice thing out of this "test" was that your script found a bug
> in the new dev version of PFGW (which was not in the "older" stable
> version).  In the new version, I have de-coupled the expression 
> parser from the rest of the program (am still working on that), and
> have created an "easy_eval" set of functions.  Well there was some
> behavior missing (calling the easy_eval_GetInteger() with a literal
> number, and not a "symbol" number was failing).
> 
> 
===============================================
andrew_j_walker     Message 37 of 43  Sep 9, 2004
-----------------------------------------------
--- In primeform@yahoogroups.com, "andrew_j_walker" <ajw01@u...> > 
> 10789522*3^n-1 no prime up to n=200000
> 23375192*3^n-1 no prime up to n=150062
below was wrong before.
29140796*3^n-1 no prime up to n=200000

 > 36730222*3^15624-1 is prime
> 
> 
===============================================
Robert     Message 38 of 43  Oct 1, 2006
-----------------------------------------------
--- In primeform@yahoogroups.com, "andrew_j_walker" <ajw01@...> wrote:
>
> --- In primeform@yahoogroups.com, "masserto" <masserto@y...> wrote:
> > 
> > Dear Guido,
> > 
> > I recently found that 2*k*3^n-1 is always composite if
> > 
> > k=739171331147778631
> > 
> > The "covering set" for this Riesel number is:
> > 
> > {5,7,13,17,19,37,73,97,577,757,769}
> > 
> > Has anyone found a smaller k so that 2*k*3^n-1 is always composite?
> > 
> > Best regards,
> > Tom Masser
> > 
> 
> Nice work, that's smaller than any I remember seeing. Have you looked
> at the plus case?
> 
> Andrew

There has been a delay since this was posted. 

Regarding the Sierpinski case:

One such covering set is  [13,5,7,41,73,17,193,6481,97,577] which have
multiplicative order base 3 of 3,4,6,8,12,16,16,24,48,48, all of which
are factors of 48. Using CRM provides the following k which provides
composite 2*k*3^n+1 for all n:

36785490291994693 

I am by no means convinced this is the smallest k but it might be as
it is 20 times smaller than the lowest known Riesel. It will be a very
hard problem to prove this is the lowest 2*k never prime. 

The corresponding Riesel associated with this covering set provides a
larger value of k than the Tom's Riesel value.

A nice series for OEIS would be 78557,36785490291994693,66741,159986....

Mooted Sierpinski numbers base a=2,3,4,5..., where to be the k value
the Sierpinski must be multiplied by all primes which have
multiplicative order base a of 1 (to elimiate trivial results). Anyone
up to extend this series as a challenge? 

Regards

Robert Smith
===============================================
David Broadhurst     Message 39 of 43  Oct 1, 2006
-----------------------------------------------
--- In primeform@yahoogroups.com, "Robert" <rw.smith@...> wrote:

> A nice series for OEIS would be 
> 78557,36785490291994693,66741,159986....
> Mooted Sierpinski numbers base a=2,3,4,5...

Please send it to Neil, with "mooted" ==> conjectured.

Nice work with a=3, thanks, Robert.

David
===============================================
Robert     Message 40 of 43  Oct 2, 2006
-----------------------------------------------
--- In primeform@yahoogroups.com, "David Broadhurst"
<d.broadhurst@...> wrote:
>
> --- In primeform@yahoogroups.com, "Robert" <rw.smith@> wrote:
> 
> > A nice series for OEIS would be 
> > 78557,36785490291994693,66741,159986....
> > Mooted Sierpinski numbers base a=2,3,4,5...
> 
> Please send it to Neil, with "mooted" ==> conjectured.

Done and dusted, although I am no expert on finding suitable references

Regards

Robert Smith
===============================================
David Broadhurst     Message 41 of 43  Oct 2, 2006
-----------------------------------------------
--- In primeform@yahoogroups.com, "Robert" <rw.smith@...> wrote:

> > 78557,36785490291994693,66741,159986....
> Done and dusted

Did you remember to multiply 36785490291994693 by 2 ?

David
===============================================
Robert     Message 42 of 43  Oct 2, 2006
-----------------------------------------------
--- In primeform@yahoogroups.com, "David Broadhurst"
<d.broadhurst@...> wrote:
>
> --- In primeform@yahoogroups.com, "Robert" <rw.smith@> wrote:
> 
> > > 78557,36785490291994693,66741,159986....
> > Done and dusted
> 
> Did you remember to multiply 36785490291994693 by 2 ?
> 
> David
>

Defined it in a different way, so that each of the numbers in the
series must be multiplied by all primes with multiplicative order base
b of 1 to get to a k.

Regards

Robert
===============================================
Robert     Message 43 of 43  Jan 7, 2007
-----------------------------------------------
--- In primeform@yahoogroups.com, "Robert" <rw.smith@...> wrote:
>

> 
> Regarding the Sierpinski case:
> 
> One such covering set is  [13,5,7,41,73,17,193,6481,97,577] which have
> multiplicative order base 3 of 3,4,6,8,12,16,16,24,48,48, all of which
> are factors of 48. Using CRM provides the following k which provides
> composite 2*k*3^n+1 for all n:
> 
> 36785490291994693 
> 
> I am by no means convinced this is the smallest k but it might be as
> it is 20 times smaller than the lowest known Riesel. 
>

Aiaiai, doing further research on this shows that, in the primenumbers
group the following got posted, 20 times smaller than my value:

The minimal k with covering set of size 48 is:

k=3574321403229074
The modulus M is 2*5*7*13*17*41*73*97*193*769*6481

Source: Jack Brennen May 17, 2002, Yahoo Primenumbers

Sorry about that, but it is good to know that the problem is 20 times
easier to solve.

Regards

Robert Smith
===============================================
Cached by Georg Fischer at Nov 14 2019 12:47 with clean_yahoo.pl V1.4