Secuencia de enteros consecutivos con un número relativamente primer número.

Question

Hay publicado un resultado que dice lo siguiente?

Deje $p$ ser un número primo. Entonces para todo entero $n>p$ hay al menos un número en la secuencia consecutiva $2n,2n+1,2n+2,\ldots,2n+2p-1$ que es relativamente primos para todos los números primos menores o iguales a $p$.

Por ejemplo, si $p=5$$n=17$, la secuencia de $34,35,36,37,38,39,40,41,42,43$ dispone de varios números no divisibles por $2,3,5$. Ahora esta solo necesita ser verdadero para cualquier $n>p$ y cualquier prime $p$.

Ya he pedido a mi colega que recibió su Ph D. en la Teoría de números. Él me sugirió que pose a un público más amplio, y por eso estoy aquí. Cualquier sugerencia en los resultados, sería muy apreciado.

Answer 1

La conjetura es falsa.

Deje $p_1, p_2, p_3, \dots$ ser el de los números primos. Definir el primorial Jacobsthal función de $h(k)$ a ser el más pequeño que la longitud de la $\ell$ de manera tal que cada secuencia consecutiva de números enteros de la longitud de la $\ell$ contiene un número relativamente primer a $p_1, \dots p_k$. Su conjetura es equivalente a la afirmación de que $h(k) \le 2 p_k$.

(La condición es invariante al añadir o restar múltiplos de $P = \prod_{i=1}^k p_i$, por lo que la condición de que $n > p$ es irrelevante, y para fijo $p$ la conjetura puede ser verificado por un cálculo finito; basta examinar secuencias consecutivas de números enteros entre el $0$ $P - 1$ incluido.)

De acuerdo a la tabla de valores de $h(k)$ en el trabajo se han vinculado

$$p_{14} = 43, h(14) = 90 > 86$$

so there is a consecutive sequence of $89$ integers none of which is relatively prime to the primes up to $43$. This is the smallest counterexample.

You can show that $h(k) \ge 2p_{k-1}$ by constructing a consecutive sequence of integers of length $2p_{k-1} - 1$ none of which is relatively prime to $p_1, \dots p_k$. This can be done by considering the integers $n - a n - a + 1, \dots n + 1, n + a$ where $n$ is a solution to the system of congruences

$$n \equiv 0 \bmod p_1 \dots p_{k-2}$$ $$n-1 \equiv 0 \bmod p_{k-1}$$ $$n+1 \equiv 0 \bmod p_k$$

and $a = p_{k-1} - 1$. This construction is actually best possible for $p_k \le el 19$; for example when $p_k = 19$ it produces the sequence $60044, \puntos 60076$. It first stops being best possible when $p_k = 23$, where this construction gives a sequence of length $37$ but the longest sequence has length $39$ (namely $20332472, \puntos 20332510$).

For completeness' sake here is the (very sloppy, I'm sure) Python script I used to test the conjecture; it allowed me to compute enough values of $h(k)$ that I could look it up on the OEIS, and looking at the longest sequences led me to the construction above. Note that it computes $h(k) - 1$, the length of the longest sequence of integers not relatively prime to $p_1, \dots p_k$.

from sympy import sieve
from math import gcd
from operator import mul
import functools as ft

def longest(p):
    primes = list(sieve.primerange(1, p+1))
    product = ft.reduce(mul, primes, 1)

    biglist = list(range(0, primordial(p)))

    def isrelprime(n):
        answer = True
        for p in primes:
            if gcd(n,p) != 1:
                answer = False
        return answer

    best = 0
    bestlen = 0
    curlen = 0
    for i in biglist:
        if not isrelprime(i):
            curlen += 1
        else:
            curlen = 0
        if curlen > bestlen:
            best = i
            bestlen = curlen

    print("\nPrime : " + str(p))
    print("Best : " + str(best))
    print("Length : " + str(bestlen))

    for i in range(0, bestlen):
        print(str(best - i) + " has gcd " + str(gcd(best - i, product)))

primes = list(sieve.primerange(1, 20))
for p in primes:
    longest(p)

Y aquí un poco de código adicional para calcular el mcd de una determinada secuencia de enteros consecutivos con el producto de los números primos hasta algunos de los mejores.

def check(n, p, len):
    primes = list(sieve.primerange(1, p+1))
    product = ft.reduce(mul, primes, 1)
    for i in range(0, len):
        print(str(n - i) + " has gcd " + str(gcd(n - i, product)))

check(60076, 19, 33)
check(20332510, 23, 39)