Problems & Puzzles: Problems

Problem 29.- Brier Numbers

A Sierpinski Number is an integer k such that k.2ⁿ+1 is composite for any integer value of n. In 1962, John Selfridge discovered the Sierpinski number k = 78557, which is now believed to be in fact the smallest such number.

A Riesel Number is an integer k such that k.2ⁿ-1 is composite for any integer value of n. In 1956 Riesel showed that k = 509203 has this property.

Two months ago I asked myself if it could exists an integer k such that at the same time k.2ⁿ+1 and k.2ⁿ-1 are composite for any value of n.

Quickly faced with the crude fact that I had not any idea about how to answer my own question J … then in a very stylish manner I simply switched to ask to my friend Wilfrid Keller the same question.

His answer arrived almost immediately: that kind of numbers not only should exist but very recently (?) Eric Brier produced the first one known. Let me call this kind of numbers “Brier Numbers”.

Since 28/9/98 and up today, 16/19/99, the  smallest know Brier Number is 29364695660123543278115025405114452910889, that I will call it “The smallest known Brier number” or simply SKB(28/9/98)

SKB(28/9/98, E. Brier) = 29364695660123543278115025405114452910889 (41 digits)

Questions:

1. Can you produce a smaller Brier Number than SKB(28/9/98)?
2. Can you estimate the magnitude order of the smallest Brier Number (that I will call The Alpha-Brier Number or simply B_a?

Hints: After the Keller’s kind communication I got in touch with Eric Brier asking him for the method employed by him to produce this kind of numbers.  I offered him also my pages for publishing his method and for exposing all the other open questions that should arise around the Brier Numbers.

Please click here to download the document that Eric produced and that must help you to organize your own search. This document also poses several other open questions that “arise quite naturally” and two complements.

I have added other two complements:

a)       A letter from Wilfrid Keller to Chris Nash, Eric Brier & Yves Gallot, dated the 26/9/98 that in the middle of many other things suggests how to get a smaller Brier number than the existing at that time.

b)       The announcement from Eric Brier about his discovery of SKB(28/9/98)

Yves Gallot has discovered (15/01/2000) a smaller Brier number. This one is 30 digits large against the previous record 41 digits large obtained by Eric Brier the 28/9/98. This is the Gallot's announcement:

"I searched a set which generates a Riesel number by excluding 5, 17, 257, 65537, 641, 6700417 because it is known that { 3, 5, 17, 257, 65537, 641, 6700417 } generates a Sierpinski number (and 3 can be used in both sets). The idea is to:

1 - find a "small" set of prime that generates a Riesel number.
2 - search a set of prime that doesn't include the set of primes previously found, except 3, and generates a Sierpinski number.

Of course, the union of the two sets generates a Brier number. The idea is just Eric's method, but I automatized this process and the first run of the program (still under construction and today semi-automatic) was successful. I used no special rules but a brute-force algorithm that generates all cases for e=24 to .... Eric found a solution with e1=96 and e2=288. My program found that e1=64 and e2=144 are enough. It also re-discovered Eric's solution.

I hope to finish my program next week and maybe a smallest solution will be found. If it can check all solutions for e1=24 to 516 and for e2=24 to 516, we have a good chance to find the smallest "cyclic" Brier number in it..."

***

Comment: The before record remained one year and 3 months unbeaten. I wonder how long this new record will remain...and if the conjecture of Chris Nash (See Problem 30) about a possible Brier number of 10-11 digits will be confirmed by the method used by Brier and Gallot...

***

"Wilfrid, Carlos and Eric, I just found a new smaller Brier number:
3872639446526560168555701047 (28 digits)

The sets are:{ 3, 7, 73, 13, 19, 241, 37, 109, 97, 673 } with e1 = 144 = 2^4 * 3^2 and { 3, 5, 31, 17, 11, 151, 41, 331, 61681, 61 } with e2 = 120 = 2^3 * 3 * 5 then for the complete set e = 720 = 2^4 * 3^2 * 5. I evaluated k with Chinese Remainder Theorem for 2*2880*1152 permutations to find the smallest solution. I continue the search...Yves"

SKB(16/1/2000, Y. Gallot) = 3872639446526560168555701047 (28 digits)

I guess that it's a good idea to stop any kind of forecasting about remaining time of records for the moment...:-)

***

Yeaph!...it was a good idea. The morning after I had the third and smaller Brier number by Yves Gallot in my inbox. This is his email:

"Last night, my computer found a smaller Brier number:878503122374924101526292469 (27 digits)

The sets are:{ 3, 7, 73, 13, 257, 19, 241, 37, 109, 97 } with e1 = 144 = 2^4 * 3^2 and{ 3, 5, 31, 17, 11, 151, 41, 331, 61681, 61 } with e2 = 120 = 2^3 * 3 * 5 then for the complete set e = 720 = 2^4 * 3^2 * 5.

k was evaluated with Chinese Remainder Theorem for 2*2880*1152 combinations. The product of the primes of the two sets is:9174644185821387 * 670447226147431755 / 3 = 2050371581757870446479551733981395. This 34 digit number is probably the smallest possible one. But I still have some candidates that are a bit larger and may generate a smaller k, but we should be closed to the minimal for k."

***

So the new smaller known Brier numbers is:

SKB(17/1/2000, Y. Gallot) = 878503122374924101526292469 (27 digits)

***

This Monday (17) I received two more letters highly stimulated by the Gallot's results. The first one came from Wilfrid Keller and the second one from Chris Nash. I  believe the both letters should be known completely, specially if you are interested in producing smaller and smaller Brier numbers. Both of the letters provide interesting clues to organize the future search by the method currently employed by Brier & Gallot. In particular the Keller's letter provides some new results to the search approach suggested in the Problem 30 for finding the Brier-alpha number ...

I have merged the two letters in one -txt document. Click here to download it.

***

Yves Gallot has wrote in his own site a note about his search for Brier numbers that maybe will be of interest to Brier numbers hunters.

***

Ten Years later (May 2010), Emmanuel Vantieghem wrote:

The number k = 47867742232066880047611079 is a Brier number of 26 digits.  According to the text of problem 29, I guess it is the smallest known at present.

A covering set for the sequence  ( k 2^n-1 )  is  S1 = {3,7,11,19,31,37,41,61,73,109,151,331} and a covering set for the sequence  ( k 2^n+1 )  is S2 = {3,5,13,17,97,241,257}. I was brought to this in attempting to prove the assertion in problem 52.  Indeed, for every  n, at least one of the primes of  S1  divides  k-2^n  and at least one of the primes of  S2  divides  k+2^n, as can easily be checked.  Considering not only positive values for  n  but also negative ones lead me to my result.

The evidence of my claim lies in the covering sets  S1  and  S2.  Anyone can check that for any value of  n,  the number  k 2^n - 1  is divisible by at least one element of the set  S1.  It suffices to verify this for  n = 1, 2, ..., 180, since the appearance of a prime in the sequence  ( k 2^n - 1 )  is periodic.  The periods of the set  S1  are indeed {2,3,10,18,5,36,20,60,9,36,15,30} with LCM 180.
The same holds for  k 2^n + 1  and S2. The periods for the primes of  S2  are  {2,4,12,8,48,24,16}  with LCM 48.

So, SKB(26/5/2010, E. Vantieghem) = 47867742232066880047611079 (26 digits)

***

On 28/05/2010, I sent an email to Mr. Wilfrid Keller, Yves Gallot & Eric Brier, in order to let them know the Emmanuel's result.

Immediately Yves responded:

***

So, the ball is rolling on... and, SKB(2007, Filaseta et al) = 143665583045350793098657 (24 digits)

***

See also:

http://mathworld.wolfram.com/BrierNumber.html

Sloane, N. J. A. Sequence A076335 in "The On-Line Encyclopedia of Integer Sequences."

In particular the following line:

"There are no Brier numbers below 10^9. [From Arkadiusz Wesolowski (math(AT)wesolowski.ids.pl), Aug 03 2009]"

This means that the smallest Brier numbers is somewhere in bewteen 10^9 and 143665583045350793098657.

Does somebody has the A. Wesolowski proof of his assertion?

***

***

Regarding my question "Does somebody has the A. Wesolowski proof of his assertion?" posed above last week I received two answer, in this order:

a) W. Keller wrote ():

 ...I had also been aware of the paper by Filaseta, Finch and Kozek. But I didn't think about relating
it to your "Problem 29". Your readers might be interested in knowing where this paper
has finally been published:

  Journal of Number Theory, vol. 128 (2008), pp. 1916-1940;
  electronic: April 2008.

I also wanted to make some remarks concerning your note about
Arkadiusz Wesolowski's verification that "There are no Brier
numbers below 10^9".

We seem to know considerably more than that. Looking at the
table on your page on "Problem 49. Sierpinski-like numbers",
we see that k=2152690373 is given as the "smallest uncertain
candidate" for being a Brier number (but actually
2152690373*2^22461+1 is a prime, so this k really isn't such
a "candidate" anymore).

Revising our earlier correspondence, I found the following
additional information. On February 14, 2000 I copied to you:

 

I have a new lower bound for the smallest Brier number: it must
be > 10^9 !

[...]

Here is the complete list of "smallest" primes having  n >= 2^14,
for  k < 10^9 :

     16935761    22394-
    100604513    41422-
    102017081    17419+
    118373279    82587+
    188001043    30554+
    257305073    18825+
    270704167    85461-
    282681079    58783-
    308009629    16742+
    343689013    58314+
    411390743    18284-
    418452299    22648-
    585540229    24437-
    615516221    37854-
    623603909    19989+
    630511667    16587+
    637741513    78920+
    753118759    18529-
    807512089    27626+
    820235483    17004-
    835116281    20311+
    840923429    16473+
    870834563    38990-
    920892347    22452-
    927795317    17135+
 

This list might be seen as an indication of a "proof of his
assertion."

In March 2001 I told you that I was about to completing the
search for all k < 2^31 = 2147483648, finally reaching the
above-mentioned limit of k = 2152690373.

In the meantime you had been organizing a coordinated search
for k > 2^31 at

      http://www.primepuzzles.net/private/index.htm .

On April 24, 2002 I wrote to you, summarizing the results of
our joint efforts at that time:

 

Esta vez tengo noticias acerca del coeficente  k=1355477231
relacionado con el problema numero 30:  acabo de enviar el
numero primo  1355477231*2^356981 + 1 (107472 digitos)  a la
lista de Chris Caldwell!  Ademas he probado que los corres-
pondientes numeros  1355477231*2^n - 1  son compuestos para
todo  n < 393000.

A traves de este resultado ahora sabemos que no existe nin-
gun "numero de Brier" menor que  k=2294020991,  el "candi-
dato" identificado por usted.
 

About this coefficient  k  your "Status of the search for
k=2294020991 the 24/04/2004" said that the range n=790000-800000
was still "Working". But now, to my great surprise, I see on Chris
Caldwell's database the prime 2294020991*2^800493+1, submitted on
December 17, 2004!

According to your "Ranges proposed & status of search", wouldn't
this imply that there is no Brier number below k=2362690377, at
least?

Next: What about the two "survivors" (only two?) in the interval
2362690377 <= k <= 2572690377 with no primes for n <= 90000 ?
Which are these, and have they been searched further?

Aren't we possibly "done" up to k = 3622690387, altogether?

I think it would be really interesting to continue this search
until a really "hard" candidate might be identified.

In any case, on the page on "Problem 30" you could probably add
the prime 2294020991*2^800493+1 as the next step of the
"stepladder".

Finally, I wanted to give you a (quite belated) update to your
"Problem 31": In 2004, Maxim Vsemirnov has slightly improved
John Nicol's record (near the end of your page), please see the
attached paper

b) A. Wesolowski wrote:

Through a computer search I noted that the number is greater than 10^9.

My strategy was simple:

find k such that k.2^n + 1 and k.2^n - 1 are both composite for all n up to 1000.

* The point is that the trial division method is helpful only if n > 1000.

5 days from k = 10^7 to k = 10^9 is amazing!

I generated a list of k's. Next, I did change one thing (*).

After the tests were done, there was a proof.

 

The computing continues as the rules I presented above,

k = 2335574321, exponent = 10799+

***

But the most surprising thing was that A. Wesolowski reported that the SKB(26/5/2010, E. Vantieghem) = 47867742232066880047611079 (26 digits) was already known and calculated as part of another search in 1975!!!:

This number was found out in 1975.

http://www.jstor.org/pss/2005463

From this article I take out this image:

***

BTW, this number was also the core of our Problem 52 and the declared origin of the search of Mr. Emmanuel Vantieghem, as he stated in his email (I was brought to this in attempting to prove the assertion in problem 52). So, accordingly and is my interpretation, that Mr. Vantieghem took this number from the Problem 52 and noticed that it was also a solution for the Problem 29, a smaller not reported solution. Am I right, Mr. Vantieghem? (Your interpretation is perfectly correct ! Sincere greetings !, June 2010)

On his turn the Problem 52 was taken by me from one entry of the pages "Prime Curios!" from my friend G. L. Honaker, Jr.

So the circle is happily closed now, reporting very surprising news:

1) Problem 29 & Problem 52 are two sides of a unique problem: every solution of P29 is a solution of P52 and viceversa.

2) If this is so, the first Brier number produced was not the 41 digits SKB(28/9/98, E. Brier)  but the 26 digits SKB(26/5/2010, E. Vantieghem) that was really discovered by Fred Cohen & J. L. Selfridge in 1975. 23 years before.

3) The current smallest known solution up today (Jun 2010) to both Problems 29 & 52 is the 24 digits SKB(2007, Filaseta et al).

***

Accordingly this is the current history & status:

***

On June 20, Eric Brier wrote:

It is a strange feeling to discover that such numbers were known in 1975!

Thank you for the information anyway.

 

I have been very surprised to read the construction of Izotov to build Sierpinski numbers without covering sets.

It confirms that it is a domain where most probably many things are still to be discovered.

***

On June 21, 2010 A. Wesolowski wrote:

***

On Jan 3, 2014 I received an email from Christope Clavier announcing that he has gotten 14 smaller Eric Brier numbers

Please find attached a list of fourteen Brier numbers that are all smaller than the current record established by Filaseta et al. in 2007 according to your page.

Below each number I give the two covering sets related to k.2^n+1 and k.2^n-1 respectively.
I found all these numbers on the last day of 2013.

The smallest of them is the following 22-digit Brier number : 3316923598096294713661

I will send an email to inform several people that I think may be interested.
Nevertheless, do not hesitate to communicate by yourself to other people if you wish.

43262598580503239091589 (22.6361)
{3, 5, 17, 257, 241, 97, 673}
{61, 41, 11, 31, 151, 331, 37, 13, 73, 19, 7, 3}

107711321583468432196343 (23.0323)
55465536577115049124007 (22.744)
{3, 5, 17, 13, 241, 97, 673}
{61, 41, 11, 31, 151, 331, 37, 109, 73, 19, 7, 3}

105404490005793363299729 (23.0229)
{61, 41, 11, 31, 151, 331, 37, 109, 73, 19, 7, 3}
{3, 5, 17, 13, 241, 97, 673}

3316923598096294713661 (21.5207)
{3, 5, 17, 13, 241, 97, 673}
{1321, 41, 11, 31, 151, 331, 37, 109, 73, 19, 7, 3}

32099522445515872473461 (22.5065)
92348240410439475192041 (22.9654)
50500982247079839441193 (22.7033)
28960674973436106391349 (22.4618)
{61, 41, 11, 31, 151, 331, 37, 109, 73, 19, 7, 3}
{3, 5, 17, 13, 241, 97, 257}

88595984169672153528691 (22.9474)
12607110588854501953787 (22.1006)
10439679896374780276373 (22.0187)
76719416286801468925067 (22.8849)
21444598169181578466233 (22.3313)
{3, 5, 17, 13, 241, 97, 257}
{61, 41, 11, 31, 151, 331, 37, 109, 73, 19, 7, 3}


Smallest Brier number of this file: 3316923598096294713661 (21.5207)

One day later I received the following note from Wilfrid Keller

Dear Christophe Clavier,

I am very pleased to congratulate you on the discovery
(or rather: construction) of a new smallest known "Brier
number".

It's a particularly happy event, as the 23-digit value

   10439679896374780276373 (22.0187)

included in your list had just been presented in a paper
by Dan Ismailescu and Peter Seho Park
( https://cs.uwaterloo.ca/journals/JIS/VOL16/Ismailescu/ismailescu3.pdf ,
submitted in June 2013, published as recently as
December 5, 2013).

So your 22-digit example remains unaffected as the current
"record" - a remarkable achievement!

Thank you for letting me know your results as quickly.

Best regards and a Happy New Year!

Wilfrid Keller

Clavier gave me permission to announce his results to OEIS site and you may see these here A076335.

Pending to receive from Christope a small note explaining his approach in order to get his remarkable results (all these numbers on the last day of 2013)... Here is his explanation...

Before writing about the way I found the 14 Brier numbers smaller than the 24-digit record from Filatesa et al. I must say that Wilfrid Keller informed me on Junuary 3, 2014 about a recent result from Dan Ismailescu and Peter Seho Parkthat that I was unaware of. They wrote a paper (https://cs.uwaterloo.ca/journals/JIS/VOL16/Ismailescu/ismailescu3.pdf) that has been published in the Journal of Integer Sequences on December 5, 2013 where they provide a new smallest known Brier number: 10439679896374780276373 (23 digits).
This number is present in my list and is only beated by the smallest of the list: 3316923598096294713661 (22 digits).
So this means I beated the current record only once and not fourteen times as I thought!
Note also that 10439679896374780276373 is prime while 3316923598096294713661 is not so that Dan Ismailescu and Peter Seho Parkthat still hold the smallest known *prime* Brier number.

Regarding the way I found my numbers, there is no much to say. I merely tried to find (in a careful but non systematic way) a good pair of covering sets. I would define what I mean by a good pair of covering sets by the following efficiency metric:  \mu = \pi / N  where \pi is the product of the primes belonging to the two sets divided by 3 (because the prime 3 appears twice and must be counted once) and where N is the number of odd Brier numbers produced by the CRT modulo \pi. The rational behind this metric is that if we modelize the distribution of these N odd integers as being uniform in the interval [0,\pi-1], then we must expect that the smallest one is about as small as \pi / N. The magnitude of the smallest Brier number produced by some pair of covering sets is thus influenced by \pi and N which are both related to the pair of sets, as well as by an independant luck/unluck factor. As I will expose shortly, the 22-digit Brier number I found is mainly due to luck!

Four pairs of covering sets are involved in my list of 14 Brier numbers:

(note: the size (log in base 10) of each Brier number is given beside it into parenthesis)

pair 1: {3, 5, 17, 257, 241, 97, 673} and {61, 41, 11, 31, 151, 331, 37, 13, 73, 19, 7, 3} or vice-versa which produced one number:
- 43262598580503239091589 (22.6361)

pair 2: {3, 5, 17, 13, 241, 97, 673} and {61, 41, 11, 31, 151, 331, 37, 109, 73, 19, 7, 3} or vice-versa which produced three numbers:
- 107711321583468432196343 (23.0323)
- 55465536577115049124007 (22.744)
- 105404490005793363299729 (23.0229)

pair 3: {3, 5, 17, 13, 241, 97, 673} and {1321, 41, 11, 31, 151, 331, 37, 109, 73, 19, 7, 3} or vice-versa which produced only the record number:
- 3316923598096294713661 (21.5207)

pair 4: {3, 5, 17, 13, 241, 97, 257} and {61, 41, 11, 31, 151, 331, 37, 109, 73, 19, 7, 3} or vice-versa which produced as much as nine numbers:
- 32099522445515872473461 (22.5065)
- 92348240410439475192041 (22.9654)
- 50500982247079839441193 (22.7033)
- 28960674973436106391349 (22.4618)
- 88595984169672153528691 (22.9474)
- 12607110588854501953787 (22.1006)
- 10439679896374780276373 (22.0187)
- 76719416286801468925067 (22.8849)
- 21444598169181578466233 (22.3313)

Note that for each of these pairs of covering sets N is equal to 3,317,760 so that the efficiency figures for each pair are respectively:

pair 1 => \mu = 22.7914
pair 2 => \mu = 22.4189
pair 3 => \mu = 23.7545
pair 4 => \mu = 22.0008

One can notice that the last pair have the better efficiency figure which is reflected by the fact that it produced as much as nine small Brier numbers. Also note that its smallest number has a size (22.0187) which is quite close to the expected one (22.0008). On the contrary it is curious that the record number was produced by the third pair which was a priori the less promising one (because of the seemingly bad ideas of having replaced 257 by 673 and 61 by 1321) . One can define a kind of (un)luck index \delta as the discrepancy between the expected and the actual sizes of the smallest number produced by a pair: \delta = \mu - log_10(smallest number). The more \delta is, the more luck we had, and conversely.
With this notion in hand we can list the luck index of the smallest number of each pair:

pair 1 => \delta = 22.7914 - 22.6361 = +0.1553  (slightly lucky)
pair 2 => \delta = 22.4189 - 22.744  = -0.3251  (somewhat unlucky)
pair 3 => \delta = 23.7545 - 21.5207 = +2.2338  (exceptionnaly lucky)
pair 4 => \delta = 22.0008 - 22.0187 = -0.0179  (near as expected) 

As one can see, finding this precise record number in this precise pair of covering set was a quite lucky event. It seems to me that for large \delta values one can see 1/10^{\delta} as an approximation of the probability that the pair of covering sets would produce such a small number. In that particular case this gives a probability close to 1 over 170.

One can ask whether a smaller Brier number constructed from covering sets may exist. Though the answer is uncertain, the analysis above tend to inspire pessimism. Indeed it is probable that the most promising pairs have already been considered either by previous small Brier numbers seekers or by myself. Thus a winning pair would probaly have its \mu value greater than 23.7545 and consequently should give occurence to a luck index probably much greater than +2.2338 which seems improbable. Of course this reasonning is definitely not a proof of the non existence of smaller Brier numbers.

***

***