Problems & Puzzles: Puzzles

Puzzle 504. F(n) & G(n) Emmanuel Vantieghem sent the following puzzle: Let P(n) be the product of the first n odd primes. Thus, P(1) = 3, P(2) = 15, P(3) = 105, ... Let A(n) be the highest power of 2, smaller than P(n). Thus, A(1) = 2, A(2) = 8, A(3) = 64, ... Let F(n) be the difference P(n) - A(n). Thus, F(1) = 1, F(2) = 7, F(3) = 41, ... Q1 : Is F(n) increasing with n ? Q2 : What is the limit of F(n) when n goes to infinity ? Does it exists ?   2) Let B(n) be the smallest power of 2 bigger than P(n). Thus, B(1) = 4, B(2) = 16, B(3) = 128, ... Let G(n) be the difference B(n) - P(n). Thus, G(1) = 1, G(2) = 1, G(3) = 23, ... Q3 : Is G(n) increasing with n ? Q4 : What is the limit of G(n) when n goes to infinity ? Does it exists ?

---

Contributions came from Farideh Firoozbakht,

***

Farideh wrote:

Answer to Q1 : No it isn't increasing with n, for n = 2212 we have F(n) > F(n+1).
In fact 1.5 F(2213) < F(2212) < 1.6 F(2213) ; F(2212) has 8391 digits, F(2213)
has 8390 digits and F(2212) - F(2213) has 8390 digits.

Answer to Q3 : No it isn't increasing with n, for n = 21331 we have G(n) > G(n+1).
In fact 1.05 G(21332) < G(21331) < 1.06 G(21332);
Number of digits of G(21331) = Number of digits of G(21332) = 104538 and
Number of digits of G(21331) - G(21332) is 104537.

***

Emmanuel Vantieghem wrote:

As to the first question, it's answer is negative.  With a PC one may find out that the smallest  n  such that  F(n) < F(n-1)  is  2213.  I there is a next such an  n, it must be greater than 50000. 
As to the second question, it is easy to see that, when  F(n)  is not equal to  1,  F(n)  must be strictly bigger than the  n-th odd prime.  So, it suffices to examine when  F(n)  can have the value  1.  Well, n > 1  and  F(n) = 1  implies : 2^k + 1  divisible by  15, where  2^k = A(n).  But  2^k + 1  divisible by  3  means  k  odd, say  k = 2u + 1.  In that case, we have  modulo 5 :  2^(2u+1) = 2*(4^u) = either -2  or  +2.  Thus, 2^k + 1  cannot be divisible by  15  when  n  is bigger than  2.  From this, it follows that the limit of  F(n)  is infinity.
The first question for  G(n)  also has a negative answer.  The smallest  n  such that  G(n) < G(n-1)  is  21332  and there is no other such  n  smaller than  50000.
As to question  4, we also have that, when  G(n)  is not equal to  1,  G(n)  must be strictly bigger than the  n-th odd prime.  So, it suffices to examine the possibilities for  G(n)  to be equal to  1.  Obviously, this happens for  n = 1  and for  n = 2.  Take  n > 2.  We then must look at some  k  such that  2^k - 1  is divisible by  3*5*7 = 105.  It is easy to compute the multiplicative order of  2  modulo  105 (i.e : the smallest  u  such that  2^u  is congruent to  1  mod 105) : it is  12.  This means that, for  2^k -1  to be divisible by  105,  k  must be of the form  12v.  But, modulo  9, we have : 2^(12v) = (2^12)^v = (4096)^v = 1.  This means that, when  2^k - 1  is divisible by  105, it is also divisible by  9.  Since  P(n)  is never divisible by  9,  2^k - 1  cannot be equal to  P(n)  when  n  > 2.  Thus, the limit of  G(n)  is also infinity.

Combining the answers to questions 2 and 4, we can conclude that, if  d(n)  is the distance of the primorial  p(n)#  to the nearest power of  2, we have  d(n) >= 2 p(n+1)  for  n > 3.

***