10
$\begingroup$

Can you provide a counterexample for a claim given below?

Inspired by Puzzle 937 I have formulated the following claim:

For any $n > 0$ let $B = p_1 \cdot p_2 \cdot .... \cdot p_n$ be the product of the first $n$ primes. Let $X$ be the smallest number, bigger than $B^k/p_{n+1}$ and coprime to $B^k$, where $k$ is a fixed positive integer. Define the number $m_n$ as $X \cdot p_{n+1}-B^k$ , then $m_n$ is either $1$ or prime.

Try it for yourself!

I was searching for counterexample using the following PARI/GP code:

CE(lb,ub,k)={
for(n=lb,ub,
B=prod(i=1,n,prime(i));
X=ceil((B^k)/prime(n+1));
while(gcd(X,B^k)!=1,
X++);
m=X*prime(n+1)-B^k;
if(!(ispseudoprime(m) || m==1),print(m)))
}
$\endgroup$
  • $\begingroup$ @babanaCats, for $B^1=30$, aren't both $p_{n+1}$ and $X$ equal? $\endgroup$ – Collag3n Mar 7 at 9:30
  • $\begingroup$ I found no counterexamples for $1\le n\le 1000$, $1\le k\le 30$. $\endgroup$ – rogerl Mar 12 at 22:50
  • $\begingroup$ @rogerl Thank you for your investigation. $\endgroup$ – Peđa Terzić Mar 13 at 12:16
0
$\begingroup$

After sieving $p_n$, numbers coprime to the primoral $p_n\#$ are prime at least up to $p_{n+1}^2$ ($1$ and square excluded of course)

e.g. $p_n=5$, numbers coprime to $p_n\#=30=B$ (also coprime to $B^k$) are $\{1,7,11,13,17,19,23,29,31,37,41,43,47,49,...\}$ and are prime up to $49$.

These numbers are generally expressed in this form: $p_n\#\cdot i+\{1,p_{n+1},...\}$

e.g. for $p_n=3$ they are expressed as $$6i+\{1,5\}$$ e.g. for $p_n=5$ they are expressed as $$30i+\{1,7,11,13,17,19,23,29\}$$

Obviously, $X$ is coprime to $B^k$ (it was picked in the coprime list) and so is $p_{n+1}$ which means $X\cdot p_{n+1}$ is also coprime to $B^k$(=$30i$ in our example) and since $X\cdot p_{n+1}=B^k+m_n$, we know $m_n$ is in that coprime list.

$m_n=p_{n+1}\cdot x$ where $x=X-\frac{B^k}{p_{n+1}}$ is smaller than the maximum gap between coprimes in the list (since we pick the first smaller coprime greater than $\frac{B^k}{p_{n+1}}$). If this maximum gap is smaller than $p_{n+1}$, then $m_n<p_{n+1}^2$ and is therefore prime or $1$.

I think it was shown that the maximum gap between numbers coprime to $p_n$ is smaller than $p_{n+1}$, but I'll have a look when I have a bit more time.

edit: well....it was not http://oeis.org/A048670

$\endgroup$
  • $\begingroup$ undelete of a quick try. Too quick in fact, but a failure that might...perhaps....give some ideas. I won't have enought time to dig more. $\endgroup$ – Collag3n Mar 13 at 19:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.