7
$\begingroup$

Consider the following statement:

for any $a < b \in \mathbb{N}$, one of the following holds:

  1. $\gcd(a,b) = 1$.
  2. there is a $a < x < b$ such that $\gcd(a,x) = \gcd(x,b) = 1$.
  3. there are $a < x < y < b$ such that $\gcd(a,x) = \gcd(x,y) = \gcd(y,b) = 1$.

Is this statement true?


Motivation:

I found a variant of this problem in one of the recent algorithms competitions.

Consider the following problem:

Input: two integers $a$ and $b$ where $a \lt b$.

Output: smallest number $l$ such that there are integers $a = x_0 < x_1 < x_2 < \ldots < x_l < x_{l+1} = b$ such that all consecutive integers in the list are co-prime: $\gcd(x_i, x_{i+1}) = 1$ for $i=0,\ldots, l$.

Examples:

  1. $a = 7, b = 13$: $\gcd(a,b) = 1$, therefore $l = 0$.

  2. $a = 10, b = 12$: $\gcd(a,b) = 2 \neq 1$, therefore $l \geq 1$. Let the sequence be $10, 11, 12$. $\gcd(10, 11) = 1, \gcd(11, 12) = 1$.

  3. $a = 2184, b = 2200$: There is no $a< x < b$ such that $\gcd(a,x)=\gcd(x,b)=1$. However, we can find $2$ integers that satisfy this problem.

There is a reference algorithm that algorithms are evaluated against. That algorithm assumes that

  1. There is always an $l$ that satisfies the condition.

  2. $l\leq 2$.

I don't see why they are true.

I have a polynomial time algorithm that does not assume either of them. I am not losing out on the asymptotic performance compared to the reference algorithm, but I could get the performance constants much lower if I can understand and prove the validity of the assumptions.

$\endgroup$
  • 5
    $\begingroup$ That it is always solvable can be seen by considering all integers between $A$ and $B$ ( $N_1=A+1$, $N_2=A+2$,..). This shows $L \leq B-A-1$. $\endgroup$ – polkjh May 1 '13 at 16:21
  • $\begingroup$ polkjh: that seems to work, given that GCD( n, n+1 ) = 1 (which is true). $\endgroup$ – DarthShader May 1 '13 at 16:42
  • $\begingroup$ Please use the latex support available on this site. $\endgroup$ – Aryabhata May 2 '13 at 15:28
  • 2
    $\begingroup$ Related: en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Woods_number $\endgroup$ – Aryabhata May 2 '13 at 16:56
  • 2
    $\begingroup$ I think you may have more luck on Mathematics. $\endgroup$ – Kaveh Jan 3 '16 at 9:45
1
$\begingroup$

The conjecture $\ell \leq 2$ seems to be open. It is stated as Conjecture 3 in a paper of Dowe. Dowe does show that the Goldbach conjecture implies that $\ell \leq 3$, and mentions that Alan Woods showed in his PhD thesis that $\ell$ is bounded. Perhaps the recent proof of the odd Goldbach conjecture also implies a definite and small bound.

If $\ell > 1$ then $b-a$ is an Erdős-Woods number. In particular, if $\ell > 2$ then both $b-a$ and $b-a-1$ have to be Erdős-Woods numbers. A059756 lists the first few Erdős-Woods numbers. While all numbers on that list are even, there are also odd Erdős-Woods numbers, some of which are listed in A111042. The smallest values of $a$ corresponding to given differences are listed in A059757. While this list is not increasing, it does seem as if the numbers are growing pretty fast. Any counterexample to $\ell \leq 2$ would to be such that both $b-a$ and $b-a-1$ are Erdős-Woods numbers, and in particular $b-a > 430$ (per A059756). This suggests (but does not prove) that any such counterexample will be huge, and so for all practical purposes we can assume that $\ell \leq 2$.

$\endgroup$

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.