Problems & Puzzles: Puzzles

Puzzle 937. A non-composite sequence? Emmanuel Vantieghem sent the following nice puzzle: For any  n > 0  let  B = p(1) * p(2) * ... * p(n)   be the product of the first  n  primes. Let  X  be the smallest number, bigger than  B/p(n+1)  and coprime to  B.   (for instance, when  n = 4, B = 210, B/11 = 19,09..  thus, X = 23  and  m(4) = 23*11 - 210 = 43) Define the number  m(n)  as  X*p(n+1) - B.  Obviously, m(n) > 0. The first values of  m(n)  are :      1, 19, 19, 43, 17, 43, 1, 31, 41, 43, 137, 199, 103, 59, 79, ... These look to be always either  1  or prime. Q. Can you prove this or can you find a counterexample ?

---

Contributions came from Dmitry Kamenetsy, Pedrag Terzic and Ken Wilke.

***

Dmitry wrote on Dec 30, 2018:

Unless I missed something simple, this sequence is quite extraordinary! I checked the first 150000 terms and they are all 1 or prime. Only four 1's occur in this range for n=1, 7, 232 and 430. I am attaching the sequence.

...

Some more interesting facts:

- Whenever the term in this sequence is not 1, it is greater than the corresponding n-th prime. So if we can find an efficient way to find the "smallest X co-prime to B" then this sequence could be useful in generating primes. Either way it is significant enough to be added to this page: https://en.wikipedia.org/wiki/Formula_for_primes

- In the first 150000 terms, this sequence generates 142977 unique primes.

- In the first 150000 terms, the biggest difference between two consecutive terms is 266065002.

- In the first 150000 terms, there is only a single pair of consecutive terms that are twin primes: 41 and 43.
 

- In the first 150000 terms, the following primes (less than 100) are never generated: 2,3,5,7,11,13,23,29,37,47,53,61,71,73,83,89,97.

_***

Pedrag Terzic wrote on Jan 1, 2019

Not a solution but an observation. It seems that it is also possible to formulate a slightly different puzzle:
 

For any  n > 0  let  B = p(1) * p(2) * ... * p(n)   be the product of the first  n  primes.
 

Let  X  be the greatest number, lesser than  B/p(n+1)  and coprime to  B.
 

Define the number  m(n)  as  B - X*p(n+1) , then m(n) is either  1  or prime.
 

The first values of  m(n)  are :

 5, 1, 23, 1, 61, 59, 37, 61, 191, 577, 233, 47, 241, 223, 239, ...

I have verified it for n up to 25000. Here is a txt file with all these terms.

_***

Ken wrote on Jan 4, 2019:

For any n > 0 let B = p(1) * p(2) * ... * p(n) be the product of the first n primes.

Let X be the smallest number, bigger than B/p(n+1) and coprime to B.

 (for instance, when n = 4, B = 210, B/11 = 19,09.. thus, X = 23 and m(4) = 23*11 - 210 = 43)

Define the number m(n) as X*p(n+1) - B. Obviously, m(n) > 0.

The first values of m(n) are :

1, 19, 19, 43, 17, 43, 1, 31, 41, 43, 137, 199, 103, 59, 79, ...

These look to be always either 1 or prime.

Let p(*) be a prime that divides m(n). Then p(*) must not be n or less because then p(*) would divide both B and X contradicting the choice of X. Furthermore p(*) cannot divide p(n+1) because then p(*) would divide both (p(n+1) and B contradicting the choice of B. Hence p(*) must be greater than or equal to p(n+2). This means that for m(n) < p(n+2)2 , m(n) equals 1 or a prime. If m(n) is composite, then all prime factors of m(n) are greater than or equal to p(n+2).

This problem reminds me of Problem 246 published in Crux Mathematicorum in January, 1978, dealing with Tallman’s Formula. See https://cms.math.ca/crux/backfile/Crux_v4n01_Jan.pdf

P.22-23  Problem 246

***

 

---