Problems & Puzzles: Problems

Problem 36. The Liskovets-Gallot numbers

Valery Liskovets, while studying the "List of primes  k.2n + 1  for  k < 300, compiled by Ray Ballinger and Wilfrid Keller" made the following penetrating observation:

"(there is) a sharp irregularity in the distribution of ODD and EVEN exponents n for some values of k (such that 3 divides k)"

As a matter of fact, counting in that list the quantity of odd or even n values for each of the k values pointed out by Valery, such that for these n values k*2^n+1 is prime, it happens that:

  • Examples of k values with primes k*2^n+1 having dominating  odd n values:
    k=51 (37 odd n values/44 total n values), 231(51/61) & 261(61/75)
  • Examples of k values with primes k*2^n+1 having dominating  even n values:
    K=87 (37 even n values/39 total n values), 93(41/42), 177(46/54), 213(16/17) & 267(37/42)

From this very elemental data Liskovets switched to the following intrepid conjecture:

"...Sierpinski-like conjectures look plausible: Conjectures (+odd/+even): There exist k, 3|k, such that primes k*2^n+1 do exist but only with odd n /only with even n.

In a more Sierpinski-like shape I would say that the Liskovets conjectures that:
There are some k values such that k*2^n+1 is composite for all n values of certain fixed parity.

All this was communicated by e-mail by Liskovets to Yves Gallot the Thursday 24 of May, not without extending his conjectural thinking to the k*2^n-1 numbers:

"The same question can be considered in the negative case (i.e. for
primes k*2^n-1). Here, remarkably, by trivial reasons, k = 9*r^2
give rise to primes only for odd n. So, the corresponding -odd
conjecture holds and k_o^- := min{such k} = 9. But what about primes
with even n solely (or at least with strongly prevailing even values
of n, such as for k = 117)?

The same day a few hours later Yves wrote: "...(I have) applied some classical methods used to find some solutions to the Sierpinski, Riesel, Brier problem. See my note for details. I modified a little bit my programs and obtained some solutions."

These solutions (and the  very first Liskovets-Gallot numbers ever produced) are:

k*2^n+1=composite for all n=even: k=66741
k*2^n+1=composite for all n=odd: k=95283
k*2^n-1=composite for all n=even: k=39939
k*2^n-1=composite for all n=odd: k=172677

As a matter of fact Yves says that "I conjecture that 66741, 95283, 39939, ... and 172677 are the smallest solutions for the forms - having no algebraic factorization (such as 4*2^n-1 or 9*2^-1) - but I can't prove it."

All this was communicated then by Gallot via email the same day 24 to Ray Ballinger, Wilfrid Keller and me.

In my case I decided to make the current problem presentation for the Saturday 26 issue of my site.


1. Can you confirm/verify the Gallot's first solutions

2.- Are the Yves k solutions the minimal provable ones for every case (+even, +odd, -even, -odd)

3. Find 5 more solutions for every case

4.- Are there solutions for the combined conditions +/- even or +/- odd? (this could emulate the Brier numbers). If not, can you explain why?



Today (1/6/01) Valery Liskovets wrote the following about the existence of these k values biased to even or odd n values such that k*2^n+1 is prime:

"can anybody explain these distribution biases quantitatively (I think this should be an easy task)?"

He also makes another question:

"In fact I was initially interested in Cunningham pairs with a given k. No such pair is known for 51*2^n+1, etc. I believe, however, that this is an "arti-fact" and there exist consecutive values of n giving rise to (Cunningham) primes. Is this hope true?"

So, we have two more questions - other than the first four - and none answer. So this is getting great! (isn't it?) 


Jean-Claude Rosa made a simple demonstration that 666741*2^n+1 is always composite for n even:

"... A=66741*2^n+1 with n=2*p. If p is odd then A=0 mod 5. So only A=66741*2^n with n=4*q must be analysed. We have: -- 2^8=1 mod 17; 66741= -1 mod 17 so A=0 mod 17 if n=8*d (8;16;24;....)

-- 2^12=1 mod 13; 66741= -1 mod 13 so A=0 mod 13 if n=12*d (12;24;36;...)

-- 2^4=2 mod 7; 66741=3 mod 7 so A=0 mod 7 if n=3*d+1,(4;16;28;...)

-- 2^20= -15 mod 241; 66741= -16 mod 241 so A=0 mod 241 if n=4*(6*d+5) ;(20;44;68;...);(2^24=1 mod 241)

So I proved that A is always composite..."

Rosa also sent later a similar proof than the previous one for the numbers 399939*2^n-1, n= even, but after knowing from Yves the complete set of primes that divides the numbers. He did the same for 95283*2^n+1, n=odd.


Rosa also wrote (11/06/01) the following:

"A possible answer of question 3 of Problem 36 is:

k*2^n+1 for all n=even ; k=66741+3*5*7*13*17*241*d

k*2^n+1 for all n=odd ; k=95283+3*5*7*11*13*19*73*109*d

k*2^n-1 for all n=even ; k=39939+3*5*7*11*13*19*73*109*d

If you have the complete set of primes that divides the number 172677*2^n-1 with n odd, you can write the same answer."

He is rigorously right, but these are not "primitive" solutions, as I should demand in my question 3.


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


Records   |  Conjectures  |  Problems  |  Puzzles