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:

***