January 17, 2000
Dear Yves, Carlos, Chris and Eric,

Although I wish I had responded in due time when Carlos posted his
"Problem 29" (and sent me a very kind letter on this occasion), in
a way I am relieved that I didn't make an obviously erroneous re-
mark.  At that time I would probably have said that I believed it
would be hard, if not impossible, to get a smaller "Brier number"
than the one we knew for more than a year.

Before continuing, I would like first to express my respect and con-
gratulations to Yves for his skillful construction of those consid-
erable smaller examples.  I was very impressed and excited by that!

When I learned of the first new example (with 30 digits), I "ana-
lyzed" this number in some detail.  As a consequence, I revised my
earlier estimation to predict that an even smaller one should exist.
Before being able to communicate this to you, Yves himself had al-
ready proved that it was in fact a realistic view!

Independent of these developments, I had been intrigued by Carlos'
question, "Do you have an estimate for the least Brier number?".
So I started looking for a lower bound, knowing that it would be a
very poor one compared to the 41 digits size (now 30, 28, 27, ...?).
This amounted to look for a smallest "uncertain candidate" similar
to the known  k = 4847  for the Sierpinski problem (no prime exist-
ing for  n < 343100)  and  k = 659  for the Riesel problem (no
prime existing for  n < 141200).

I must confess that only today I noticed the related "Problem 30"
showing that, to some extent, I was duplicating Carlos' computa-
tions!  I am really sorry for the inadvertence, but as of this mo-
ment I may have gathered some additional information.  The main
statement is:

   Currently, the smallest "possible candidate" for being a
   Brier number is  k = 118373279 (9 digits).  In this case,
   both numbers  k*2^n+1  and  k*2^n-1  are composite for all
   n < 76000  (the search continuing).

For every  k' < k  I can exhibit a prime of at least one of both
forms in question.

This appears to improve Carlos' limit of  k = 16935761.  Moreover,
I can extend his table of increasing values of  k  requiring lar-
ger and larger primes, as follows:

                  k         first prime is

               16935761     k*2^22394-1  (confirmed)
              100604513     k*2^41422-1
              282681079     k*2^58783-1

Actually I have been searching up to  k < 627000000,  listing ex-
ponents of "first" primes whenever they had  n >= 2^14 = 16384.
The complete table is (the notation might be self-explanatory):

                            k          n

                         16935761    22394-
                        100604513    41422-
                        102017081    17419+
                        188001043    30554+
                        257305073    18825+
                        282681079    58783-
                        308009629    16742+
                        343689013    58314+
                        411390743    18284-
                        418452299    22648-
                        585540229    24437-
                        615516221    37854-
                        623603909    19989+

In the whole range of  k < 627000000,  only one additional "uncer-
tain candidate" was detected, which is  k = 270704167, with no
prime for  n < 76000.

If none of you would object, I would like to continue this search
in both directions: (i) raising the limit of  n < 76000  for the
two mentioned "candidates"; (ii) looking for some more possible
such candidates, that is, extending the bound of  k < 627000000
to a higher value -- but actually only up to about 10^9, because
this is the limitation on  k  prescribed by Yves' program!

In this regard, Carlos' remark, "Probably we may convince Chris
Nash to develop a special version of his poular PrimeForm..."
might give a suggestion of how the search could be pursued fur-
ther (any other idea?).

-------------

Turning now again to Yves' sensational specimen of a "Brier num-
ber" with only 27 digits, I was intrigued by the following as-
pect.  Referring to my letter of September 26, presented as an
addendum to the "Problem 29" page, I recall that every Sierpins-
ki or Riesel number must be related to some "basic" Riesel or
Sierpinski number (as I called them).  Assuming we have an ex-
tensive "catalog" of such basic numbers, for each "Brier number"
we should be able to find the associated basic Sierpinski num-
ber and similarly the associated basic Riesel number.  The Brier
number would then be expressible in terms of each of these two
basic numbers.

Now, for the most recent 27 digit Brier number

K = 878503122374924101526292469

the interrelations are in fact as follows.

K  as a Sierpinski number has

C = {3, 5, 11, 17, 31, 41, 61, 151, 331, 61681}.

This covering set has  s = 10  elements with  e = 120.

For these parameters the "catalog" shows a total of 537 possible
covering sets with the following characteristics:

                 e = 120,   n = 512,   b = 48
                            n =  25,   b = 24

This means, for instance, that there are 512 covering sets with
s = 10  and  e = 120,  each of them producing 48 different basic
Sierpinski (or, equivalently, Riesel) numbers.  One of these is

k_0 = 758199439571117.

The 81th element in the generated cycle of length  e = 120

is  k_{81} = 379944331805811739.  So we can express  K  as

K = k_{81} + 2*655162023*P,  where

P = 3*5*11*17*31*41*61*151*331*61681 = 670447226147431755.

On the other hand,  K  as a Riesel number has

C = {3, 7, 13, 19, 37, 73, 97, 109, 241, 257}.

This covering set has  s = 10  elements with  e = 144.

For these parameters the "catalog" shows a total of 358 possible
covering sets with the following characteristics:

                 e = 144,   n =  54,   b = 24
                            n = 171,   b =  8
                            n = 133,   b =  4

This means that there are 133 covering sets with  s = 10  and
e = 144,  each of them producing 4 different basic Riesel numbers.
One of these is

k_0 = 37105254011687.

The 125th element in the generated cycle of length  e = 144

is  k_{125} = 3263171790421099.  So we can express  K  as

K = k_{125} + 2*47876686255*P,  where

P = 3*7*13*19*37*73*97*109*241*257 = 9174644185821387.

Note that both of the above values of  P  were also given in Yves'
note announcing his discovery.

By the way (as already mentioned in the "addendum"), I  had deter-
mined a total of 23243 possible covering sets with  s = 10,  re-
lated as follows to different values of  e :

                              e         n

                             60         2
                             72         7
                             96         2
                            120       537
                            144       358
                            160        28
                            192        45
                            216      1396
                            288     19560
                            384      1300
                            512         8

                 (subject to further verification)

My kindest greetings to all of you!

(end of the Wilfrid's letter)

--------------------------------------------------------------------

Dear Wilfrid, Yves, Carlos and Eric (Jan 17, 2000)


>When I learned of the first new example (with 30
>digits), I "analyzed" this number in some detail.  As
>a consequence, I revised my earlier estimation to
>predict that an even smaller one should exist.

I proceeded similarly, noting that Yves uses the "virtual prime of order 16" {65537,641,6700417} in his 30-digit construction in the same way as Sierpinski originally did. I remember also that Eric's original methods sought a smaller Brier number by replacing these large primes with a smaller "virtual prime of order 16" - Yves latest covering set looks very familiar.

However I am still of the opinion that a Brier number of less than 10 digits (and hence within the Proth limit) could very possibly exist, although as we may expect with k=4847 in the Sierpinski problem, it may not necessarily be provable with finite covering sets.

I congratulate Yves on his skill at using the "exclusion method" to find the two independent covering sets. The exclusion does simplify the construction considerably, but I believe Brier numbers are possible whose Sierpinski and Riesel coverings have more "common prime factors" than just {3}, and such a construction would be considerably smaller. For instance, in the coverings generated, 19 appears in one but not the other, yet 19 often appears as the smallest prime factor in both sets. If such a prime could be shared, it appears it could be used as part of the second covering 'at no cost' to the smallest Chinese remainder theorem solution.

I have been looking at an iterative process that tries to 'share' primes in this way, using Eric Brier's 'virtual primes' to grow (partial) coverings of very long period and with very many permutations - however I feel a full evaluation may be beyond my computational limits.

Such a sharing was suggested to me by the analogous problem to Brier numbers suggested on Carlos' pages, to find a Fibonacci sequence u(1)=a, u(2)=b and it's permuted sequence u'(2)=b, u'(1)=a, always composite. (Again we rely solely on the order of primes, this time in the Fibonacci, not Mersenne sequence). The sharing is more noticeable here since u(3)=u'(3), so u(3) can be chosen as divisible by primes with coprime 'cycle lengths', these shared primes cover both sequences as efficiently as possible.

As a small example, I notice that {3,7,31,127,23} have cycle lengths of 2,3,5,7,11 in the k.2^n+-1 case. We may construct a k value such that

k.2^0+1 is divisible by all of these primes.
k.2^1155-1 is divisible by all of these primes.

k is determined mod (2*3*7*31*127*23) and of course the Keller iteration k->2k+P may be applied.

which suggests a good start point for two simultaneous coverings of e=2310. Both sequences have all but 240 of their values of n mod 2310 covered by this small set of primes. 2310 is sufficiently composite to suggest many other small primes are available to be used in this covering, for instance, 89 is also of order 11 and may be used in the covering set of one sequence, perhaps even both? (Covering an additional 24 values in each). Other factors, of order dividing 2310, need to be distributed between the two sequences, and perhaps primes such as 19 may again appear in both coverings.

Another suggested large composite value of e is 5040 (the exponent used in APRT-CL to ensure N^5040-1 has many prime factors), however I am not so convinced this is efficient (11 is not a divisor, and there are two primes of order 11. Similarly there is no prime of order 6 in either case).

>Currently, the smallest "possible candidate" for being
>a Brier number is  k = 118373279 (9 digits)
>In the whole range of  k < 627000000,  only one
>additional "uncertain candidate" was detected, which
>is  k = 270704167, with no prime for  n < 76000.

I think a completion up to 10^9 (the limit of Proth) then further searching of these and any other "uncertain" values would be most worthwhile.
 
> In this regard, Carlos' remark, "Probably we may
>convince Chris Nash to develop a special version of
>his poular PrimeForm..." might give a suggestion of
>how the search could be pursued further (any other
>idea?).

I see this being possible in two ways - the easiest of course is to allow testing beyond 10^9, with an expression such as (10^9+k).2^n+1 - currently k and n are restricted to the same limits as Proth merely as a coding convenience, although the test algorithm could be highly optimized for this case (rather than applying the general algorithms PrimeForm uses).

The other possibility is to modify the code to enable both k.2^n-1, k.2^n+1 to be tested (looping on n first!) and automatically moving to the next k value if ever a prime is found.

>Referring to my letter of September 26, presented as an
>addendum to the "Problem 29" page, I recall that every
>Sierpinski or Riesel number must be related to >some "basic" Riesel or  Sierpinski number (as I called
>them).

The "Keller cycles" k->2k+P mod 2P, and the 'inversion' k->2P-k (switching Riesel and Sierpinski numbers) has been studied quite extensively by a friend of mine, Mr Joseph McLean. He has in fact attempted the Brier number problem as well, his approach being to seek a "self-inverse" Keller cycle, where k->2P-k is another member of the cycle. Such a Brier number would have the same covering set in both sequences, he has not been able to establish if such a number exists although he has considerable conditions on the factors of P.

Incidentally, did Yves try the congruences switching the roles of the coverings, Sierpinski<->Riesel?

When looking at Eric Brier's "virtual primes", I noticed several other symmetries that can be applied. For instance, if three primes of order (dividing) 3n combine to make a "virtual prime" of order n, there are in fact TWO distinct virtual primes - order is important, up to cyclic permutations which are dealt with by the Keller cycle. These two distinct cycles use the same covering set, but in a different permutation, somehow relating distinct "basic" Sierpinski and Riesel numbers.

Perhaps interestingly, I notice that a Brier number with covering set products P and P' corresponds to a given value k=x mod 2P and k=y mod 2P'. The Keller cycle can be applied to both of these simultaneously

(x,y) -> (2x+P mod 2P,2y+P' mod 2P')

or without the stipulation that x and y are odd

(x,y) -> (2x mod P, 2y mod P').

The Brier number created is on a cycle of Brier numbers with length which is "the order of 2" in the group Z/PZ x Z/P'Z (in fact it is the smallest power of 2 for which the additive order of (x,y) divides 2^n-1).

It is in fact not necessary to solve all possible congruences of Sierpinski and Riesel number to examine every possible combination of Sierpinski and Riesel number in Z/PZ x Z/P'Z. 

It is merely necessary to find one Sierpinski number, solve the congruences for each Riesel number on the cycle, then use the simpler iteration

x->2x+lcm(P,P') mod 2lcm(P,P')

to find the smallest Brier number on that cycle. The "Brier cycles" for distinct Riesel numbers are not necessarily distinct and so the search ends as soon as a previously-discovered pair (x,y) is encountered.

My best wishes to you all, I will think about this some more...

Chris Nash
Lexington KY
UNITED STATES


