Escribí un código en Julia para buscar casos en los que la condición $c_3(3, x) \geq c_3(5, x)$ es falso (esencialmente un enfoque de fuerza bruta). Estoy publicando esto como una respuesta porque creo que algunas de las optimizaciones que hice al problema mientras escribía este código podrían ser útiles para abordar problemas similares. Aquí hay un fragmento del código que he escrito que define las funciones relevantes:
f(x::Int64)::Int64 = prod([p for p in primesieve(x) if mod(x, p) == 0])
primorial(x::Int64)::Int64 = prod(primesieve(x))
v(x::Int64)::Int64 = primorial(x + 1) / f(x^2 + x)
cₚ(p::Int64, n::Int64, x::Int64)::Int64 =
length([t for t = 0:floor(Int64, (x - n)/p) if gcd(x^2 + x, p*t + n) == 1])
Estas funciones se definen de forma bastante sencilla, casi exactamente como se describe en la pregunta (el primesieve(x) es una implementación del método Tamiz de Eratóstenes que genera la lista de primos menores que x ). Inicialmente intenté buscar contraejemplos utilizando el siguiente código:
for x = 7:3:10000
if v(x) % 15 == 0
if cₚ(3, 3, x) < cₚ(3, 5, x)
println(x)
end
end
end
Aunque este código implementó correctamente todas las restricciones necesarias, no se ejecutó porque el valor de v(x) estaba fuera de los límites de la Int64 para algunos de los valores más grandes de x (esto no es sorprendente, ya que el primorial crece rápidamente). Esto exigía una forma alternativa de comprobar la condición $15 \vert v(x)$ (o, de forma equivalente, $v(x) \equiv 0 \pmod{15}$ ).
El número $v(x)$ es un cociente de otros dos números: $\#(x+1)$ - el producto de todos los primos menores que $x+1$ y $f(x^2 + x) = f(x\cdot (x+1))$ - la radical (mayor factor libre de cuadrados) de $x\cdot (x+1)$ . El numerador de esta fracción es siempre divisible por $15 = 3\cdot 5$ ya que se requiere que $x \geq 7$ . Comprobación de $15 \vert v(x)$ equivale, por tanto, a preguntarse si $15$ no dividir el número $f(x\cdot (x+1))$ .
Aunque esta simplificación es suficiente para evitar el desbordamiento de enteros, se puede optimizar el código aún más: la condición $15 \nmid f(y)$ equivale a $3 \nmid f(y) \land 5 \nmid f(y)$ . Además, $p \nmid f(y)$ equivale a $p \nmid y$ para cualquier primo $p$ . Para $y = x^2 + x$ las condiciones se convierten en $3 \nmid (x\cdot (x + 1))$ y $5 \nmid (x\cdot (x + 1))$ . Desde $x$ debe ser de la forma $x \equiv 1 \pmod{3}$ la primera condición ya se cumple. Basta con comprobar sólo la segunda condición $5 \nmid (x\cdot (x + 1))$ lo cual es cierto para $x \equiv 1, 2, 3 \pmod{5}$ .
El código puede ser modificado para:
for x = 7:3:1000
if !(x % 5 in [0, 4])
if cₚ(3, 3, x) < cₚ(3, 5, x)
println(x)
end
end
end
Esto es mucho más eficiente desde el punto de vista computacional y no requiere ninguna función más que $c_p(n, x)$ a definir.
Editar: Algunos de los contraejemplos encontrados por este programa son $76, 208, 322, 391, 406, 412, 436, 493, \text{ and } 496$ .
