O comprimento da menor cadeia co-prime entre dois inteiros

Considere a seguinte declaração:

para qualquer $a < b \in \mathbb{N}$, um dos seguintes itens é válido:

1. $\gcd(a,b) = 1$.
2. existe um tal que .$a < x < b$$\gcd(a,x) = \gcd(x,b) = 1$
3. há tal que .$a < x < y < b$$\gcd(a,x) = \gcd(x,y) = \gcd(y,b) = 1$

Esta afirmação é verdadeira?

Motivação:

Eu encontrei uma variante desse problema em uma das competições recentes de algoritmos.

Considere o seguinte problema:

Entrada: dois inteiros e , onde .$a$$b$$a \lt b$

Saída: menor número modo que haja números inteiros modo que todos os números inteiros consecutivos na lista sejam co-primos: para .$l$$a = x_0 < x_1 < x_2 < \ldots < x_l < x_{l+1} = b$$\gcd(x_i, x_{i+1}) = 1$$i=0,\ldots, l$

Exemplos:

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

2. $a = 10, b = 12$ : , portanto . Seja a sequência . .$\gcd(a,b) = 2 \neq 1$$l \geq 1$$10, 11, 12$$\gcd(10, 11) = 1, \gcd(11, 12) = 1$

3. $a = 2184, b = 2200$ : Não existe tal que . No entanto, podemos encontrar números inteiros que satisfazem esse problema.$a< x < b$$\gcd(a,x)=\gcd(x,b)=1$$2$

Existe um algoritmo de referência no qual os algoritmos são avaliados. Esse algoritmo assume que

1. Sempre existe um que satisfaz a condição.$l$

2. $l\leq 2$ .

Não vejo por que eles são verdadeiros.

Eu tenho um algoritmo de tempo polinomial que não assume nenhum deles. Não estou perdendo o desempenho assintótico comparado ao algoritmo de referência, mas poderia obter as constantes de desempenho muito mais baixas se eu pudesse entender e provar a validade das suposições.

A conjectura parece estar aberta. É declarado como Conjectura 3 em um artigo da Dowe . Dowe mostra que a conjectura de Goldbach implica esse e menciona que Alan Woods mostrou em sua tese de doutorado que é limitado. Talvez a prova recente da conjectura ímpar de Goldbach também implique um limite definido e pequeno.$\ell \leq 2$$\ell \leq 3$$\ell$

Se então é um número de Erdős-Woods. Em particular, se então e devem ser números Erdős-Woods. A059756 lista os primeiros números de Erdős-Woods. Embora todos os números dessa lista sejam pares, também existem números ímpares de Erdős-Woods, alguns dos quais estão listados em A111042 . Os menores valores de correspondente a determinadas diferenças estão listados em A059757 . Embora essa lista não esteja aumentando, parece que os números estão crescendo muito rapidamente. Qualquer contraexemplo para seria tal que e$\ell > 1$$b-a$$\ell > 2$$b-a$$b-a-1$$a$$\ell \leq 2$$b-a$$b-a-1$são números de Erdős-Woods e, em particular, (por A059756). Isso sugere (mas não prova) que esse contra-exemplo será enorme e, para todos os efeitos práticos, podemos assumir que .$b-a > 430$$\ell \leq 2$