Problems & Puzzles:
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
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
Contributions came from Farideh Firoozbakht,
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
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
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
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.