Comparing counts of relatively prime integers within a finite set

Question

I am working on an approach to Legendre's Conjecture that depends on the following result being true (where $p$ is any prime, $n$ is any integer where $p \nmid n$):

$$c_p(p,x) \ge c_p(n,x)$$

I am not sure that it is always true but I am unable to find a counter example. I am starting with the case where $p=3$ and $n=5$.

Let:

• $f(x) = \prod\limits_{p\text{ prime & }p | x}p$
• $p_n$ be the $n$th prime
• $p\#$ be the primorial of $p$
• $v(x) = \dfrac{(x+1)\#}{f(x^2+x)}$
• gcd$(a,b)$ be the greatest common divisor of $a$ and $b$.
• $c_p(n,x) = $ the count of integers $0\le t$ such that $pt+n < x$ and gcd$(x^2+x,pt+n)=1$

Here's my question:

Given:

• $x \ge 7$
• $x \equiv 1 \pmod 3$
• $15 | v(x)$

Does it always follow that:

$$c_3(3,x) \ge c_3(5,x)$$

Here are some examples:

• $x=7$

• $v(7) = \dfrac{8\#}{f(56)} = \dfrac{7\#}{14} = 15$
• $c_3(3,7) = 1$ which consists of $\{3\}$
• $c_3(5,7) = 1$ which consists of $\{5\}$

• $x=13$

• $v(13) = \dfrac{14\#}{f(182)} = \dfrac{13\#}{182} = 165$
• $c_3(3,13) = c_3(3,7)+1$ which consists of $\{3,9\}$
• $c_3(5,13) = c_3(5,7)+1$ which consists of $\{5,11\}$

• $x=16$

• $v(16) = \dfrac{17\#}{f(272)} = \dfrac{17\#}{34} = 15,015$
• $c_3(3,16) = c_3(3,13)+1$ which consists of $\{3,9,15\}$
• $c_3(5,16) = c_5(3,13)$ which consists of $\{5,11\}$

Does it always follow that $c_3(3,x) \ge c_3(5,x)$? Can someone find a counter example?

Answer 1

I wrote some code in Julia to search for cases where the condition $c_3(3, x) \geq c_3(5, x)$ is false (essentially a brute-force approach). I'm posting this as an answer because I think some of the optimizations I made to the problem while writing this code might be useful in tackling similar problems. Here's a snippet of the code I've written that defines the relevant functions:

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])

These functions are defined in a fairly straightforward way, almost exactly as described in the question (the primesieve(x) method is an implementation of the Sieve of Eratosthenes that generates the list of primes less than x). I initially attempted to search for counter-examples using the following code:

for x = 7:3:10000
    if v(x) % 15 == 0
        if cₚ(3, 3, x) < cₚ(3, 5, x)
            println(x)
        end
    end
end

Although this code correctly implemented all the necessary constraints, it did not run because the value of v(x) was out of the bounds of the Int64 type for some of the larger values of x (this is not surprising, since the primorial function grows rapidly). This called for an alternative way to check the condition $15 \vert v(x)$ (or equivalently, $v(x) \equiv 0 \pmod{15}$).

The number $v(x)$ is a ratio of two other numbers: $\#(x+1)$ - the product of all the primes less than $x+1$, and $f(x^2 + x) = f(x\cdot (x+1))$ - the radical (largest square-free factor) of $x\cdot (x+1)$. The numerator of this fraction is always divisible by $15 = 3\cdot 5$, since it is required that $x \geq 7$. Checking $15 \vert v(x)$ therefore becomes equivalent to asking whether $15$ does not divide the number $f(x\cdot (x+1))$.

Although this simplification alone is enough to avoid the integer overflow, one can optimize the code even further - the condition $15 \nmid f(y)$ is equivalent to $3 \nmid f(y) \land 5 \nmid f(y)$. Further, $p \nmid f(y)$ is equivalent to $p \nmid y$, for any prime $p$. For $y = x^2 + x$, the conditions become $3 \nmid (x\cdot (x + 1))$ and $5 \nmid (x\cdot (x + 1))$. Since $x$ is required to be of the form $x \equiv 1 \pmod{3}$, the first condition is already satisfied. It suffices to check only the second condition $5 \nmid (x\cdot (x + 1))$, which is true for $x \equiv 1, 2, 3 \pmod{5}$.

The code can be modified to:

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

This is a lot more efficient computationally and does not require any function other than $c_p(n, x)$ to be defined.

Edit: Some of the counter-examples found by this program are $76, 208, 322, 391, 406, 412, 436, 493, \text{ and } 496$.