$H(n)=\lfloor\dfrac{b}{n}\rfloor- \lfloor \dfrac{a}{n} \rfloor=$ (roughly) # odd pairs $o, o+2 \in [a,b]$ such that $n \mid o$ or $n \mid o+2$

Question

I came up with the following formula and deleted that question so that I don't have two questions on the same formula.

Conjecture. Let $a, b, n \in 2\Bbb{N} + 1$ be odd natural numbers. Then the formula:

$$ H(a, b, n) = \left \lfloor \dfrac{b}{n} \right \rfloor -\left \lfloor\dfrac{a}{n}\right\rfloor + C(n) $$

for some function $C: (\Bbb{2\Bbb{N} + 1}) \to \{-1, 0, 1\}$, counts exactly the number of holes punched into the set $P = \{(o, o+2) : o, o+2 \in [a, b]\}$, where by "punches a hole" we mean either $n \mid o$ or $n \mid (o+2)$.

Question. It seems to be true computationally, so what is a formula for computing $C(n)$ that is similar to the formula so far (can use floor, mod, +, -, /, *)?

I tried experimenting with the code to come up with the formula, but that failed, so I'm only posting the code so that you can see apparently $C(n) \in \{-1, 0, 1\}$, but not to "experiment with and find $C(n)$". What we need to do is a formal analysis based on divisibilty / modular arithmetic, possibly breaking up into modulo cases.

The code:

from math import floor, sqrt

N = 50

def actual_count(a, b, n):
    count = 0
        
    for x in range(a, b-1):
        if x % 2 == 1:
            if x % n == 0 or (x+2) % n == 0:
                count += 1
    return count

m = 0
m1 = 0

for a in range(0, N): 
    a = 2*a + 1
    for b in range(0, N):                    
        b = 2*b + 1
        if b >= a + 4:            
            for n in range(1, N):
                n = 2*n + 1
                if n <= sqrt(b):              
                    Hn = floor(b/n) - floor(a/n)
        
                    Cn = actual_count(a,b,n)
                    
                    if Hn - Cn < m1:
                        m1 = Hn - Cn
                    
                    if Hn - Cn > m:
                        m = Hn - Cn
                        
                    print(a, b, n, Hn - Cn)
                    
print (m1, m)

seems to always print a min/max of $-1, 1$ at the end of the program, regardless of how high you set $N$ to be. Hence the conjecture.

---

Motivation.

This is related to twin prime counting formulas, so I've tagged with that. Essentially once you have $H(n) = H(a,b,n)$ you apply the inclusion-exclusion principle so that:

$$ \pi_2(a,b) = \dfrac{b - a}{2} - \sum_{3 \leq q \leq \sqrt{b}} H(q) - \sum_{3 \leq q \lt q' \leq \sqrt{b}} H(qq') + \dots $$

where the $i$th summation is over all distinct odd prime $i$-tuples with each prime $\leq \sqrt{b}$. That is easy to see for me since I've been messing around with primes for a while. I just wanted to mention what this applies to. So, $\pi_2(a,b)$ counts exactly the number of twin prime pairs lying in the interval $[a, b]$.

The next step would be comparing $\pi_2(a, b^2)$ with $\pi_2(a, b^2 + 2b)$ since then the summations in each formula are over the exact same ranges! So essentially all terms involving $a$ will cancel. And what you get is an expression related to the inclusion-exclusion formula for $\pi(b^2) - \pi(b) + 1$ which can be found at Algorithms for evaluating $\pi(x)$.

What should happen is that if the twin primes were finite, then there exists a natural number $N$ such that for all $b \gt a \gt N$ we have an equation involving $\pi(x)$ that will just seem absurd with respect to the prime number theorem's result.

---

By experimenting with the Python code. The result (for $a = 0$) seems to be:

$$ H(0, b,n) := \lfloor \dfrac{b + n - 2}{n} \rfloor + D(b,n) $$

where $D(b,n) \in \{0, 1\}$. This is a lot closer, but still not exact.

---

Attempt. Assuming the solution $C(n)$ takes (and we want it to take) the form $C(n) = \lfloor\dfrac{nX + bY + aZ + W}{n} \rfloor$, we have that the computer can't find coefficients that do the job:

from math import floor, sqrt

def hole_actual_count(a, b, n):
    count = 0
    
    for x in range(a, b-2):
        if x % 2 == 1:
            if x % n == 0 or (x + 2) % n == 0:
                count += 1
        
    return count

def rough_hole_estimate(a, b, n):
    return floor((b + n - 2)/n)

def error_in_estimate(a, b, n):
    return hole_actual_count(a, b, n) - rough_hole_estimate(a, b, n)

def error_function_desired_form(X, Y, Z, W, a, b, n):
    return floor((X*a + Y*b + Z*n + W) / n)

N = 20
a = 1

min_soln = (N, N, N, N)
min_solns = []

for X in range(-N, N):
    for Y in range(-N, N):
        for Z in range(-N, N):
            for W in range(-N, N):
                for b in range(0, N):
                    b = 2*b + 1
                    for n in range(1, int(floor(sqrt(b)) / 2) + 1):
                        n = 2*n + 1
                        En = error_in_estimate(a, b, n)
                        
                        if error_function_desired_form(X, Y, Z, W, a, b, n) != En:
                            break
                    else:
                        continue
                    break
                else:
                    soln = (X,Y,Z,W)
                    Xm,Ym,Zm,Wm = min_soln
                    if abs(X*Y*Z*W) < abs(Xm*Ym*Zm*Wm):
                        min_soln = soln
                        min_solns.append(soln)
                        
print(min_solns)
                

prints [] since there are no apparent solutions at least with low coefficients.

Answer 1

You have that $\lfloor\frac{b}{n}\rfloor$ counts how many numbers less or equal to b are multiple of $n$. From these you have to subtract those multiple of $2n$ to have only the odd ones, getting $\lfloor\frac{b}{n}\rfloor-\lfloor\frac{b}{2n}\rfloor$. Now if you want only those in $[a,b]$ you have to subtract the count for $a−1$ to get: $\lfloor\frac{b}{n}\rfloor-\lfloor\frac{b}{2n}\rfloor-\lfloor\frac{a-1}{n}\rfloor+\lfloor\frac{a-1}{2n}\rfloor$. After this, everything must be multiplied by $2$ because most of those numbers belong to $2$ couples, but we need to subtract the contribution of $a$ and $b$ if these are multiples of $n$: this can be accomplished with $\lfloor\frac{b}{n}\rfloor-\lfloor\frac{b-1}{n}\rfloor$ and $\lfloor\frac{a}{n}\rfloor-\lfloor\frac{a-1}{n}\rfloor$. So we finally get:

$$\begin{aligned} H(a,b,n) &= 2\left(\lfloor\frac{b}{n}\rfloor-\lfloor\frac{b}{2n}\rfloor-\lfloor\frac{a-1}{n}\rfloor+\lfloor\frac{a-1}{2n}\rfloor\right)-\lfloor\frac{b}{n}\rfloor+\lfloor\frac{b-1}{n}\rfloor-\lfloor\frac{a}{n}\rfloor+\lfloor\frac{a-1}{n}\rfloor \\&= \lfloor\frac{b}{n}\rfloor-2\lfloor\frac{b}{2n}\rfloor-\lfloor\frac{a-1}{n}\rfloor+2\lfloor\frac{a-1}{2n}\rfloor+\lfloor\frac{b-1}{n}\rfloor-\lfloor\frac{a}{n}\rfloor \end{aligned}$$

Answer 2

Let $n\ge 3$.

Let $M$ be the number of odd numbers $m$ such that $$a\le mn\le b-2$$ Also, $K$ be the number of odd numbers $k$ such that $$a+2\le kn\le b$$

Then, one has $H(a,b,n)=M+K$.

Now, note that $$a\le mn\le b-2\iff\left\lceil\frac{a}{n}\right\rceil\le m\le \left\lfloor\frac{b-2}{n}\right\rfloor$$ and $$a+2\le kn\le b\iff\left\lceil\frac{a+2}{n}\right\rceil\le k\le\left\lfloor\frac{b}{n}\right\rfloor$$

• If $\left\lceil\frac{a}{n}\right\rceil$ is odd and $\left\lfloor\frac{b-2}{n}\right\rfloor$ is odd, then $M=\frac{\left\lfloor\frac{b-2}{n}\right\rfloor-\left\lceil\frac{a}{n}\right\rceil+2}{2}$

• If $\left\lceil\frac{a}{n}\right\rceil$ is odd and $\left\lfloor\frac{b-2}{n}\right\rfloor$ is even, then $M=\frac{\left\lfloor\frac{b-2}{n}\right\rfloor-\left\lceil\frac{a}{n}\right\rceil+1}{2}$

• If $\left\lceil\frac{a}{n}\right\rceil$ is even and $\left\lfloor\frac{b-2}{n}\right\rfloor$ is odd, then $M=\frac{\left\lfloor\frac{b-2}{n}\right\rfloor-\left\lceil\frac{a}{n}\right\rceil+1}{2}$

• If $\left\lceil\frac{a}{n}\right\rceil$ is even and $\left\lfloor\frac{b-2}{n}\right\rfloor$ is even, then $M=\frac{\left\lfloor\frac{b-2}{n}\right\rfloor-\left\lceil\frac{a}{n}\right\rceil}{2}$

Therefore, one can write $$M=\frac{\left\lfloor\frac{b-2}{n}\right\rfloor-\left\lceil\frac{a}{n}\right\rceil+\frac{1-(-1)^{\left\lfloor\frac{b-2}{n}\right\rfloor}}{2}+\frac{1-(-1)^{\left\lceil\frac{a}{n}\right\rceil}}{2}}{2}$$ i.e. $$M=\frac{2\left\lfloor\frac{b-2}{n}\right\rfloor-2\left\lceil\frac{a}{n}\right\rceil-(-1)^{\left\lfloor\frac{b-2}{n}\right\rfloor}-(-1)^{\left\lceil\frac{a}{n}\right\rceil}+2}{4}$$

Therefore, one has $$H(a,b,n)=M+K=\frac{2\left\lfloor\frac{b-2}{n}\right\rfloor-2\left\lceil\frac{a}{n}\right\rceil-(-1)^{\left\lfloor\frac{b-2}{n}\right\rfloor}-(-1)^{\left\lceil\frac{a}{n}\right\rceil}+2}{4}+\frac{2\left\lfloor\frac{b}{n}\right\rfloor-2\left\lceil\frac{a+2}{n}\right\rceil-(-1)^{\left\lfloor\frac{b}{n}\right\rfloor}-(-1)^{\left\lceil\frac{a+2}{n}\right\rceil}+2}{4}$$

Answer 3

@mathlove The code is now working and has verified your formula (the error is zero!).

from math import floor, sqrt, ceil

def hole_actual_count(a, b, n):
    count = 0

    for x in range(a, b-1):
        if x % 2 == 1:
            if x % n == 0 or (x + 2) % n == 0:
                count += 1

    return count

def rough_hole_estimate(a, b, n):
    return M(a,b,n) + K(a,b,n)

def M(a,b,n):
    """
    Thanks @mathlove:
       https://math.stackexchange.com/a/4280856/26327    
    """
    a = ceil(a/n)
    b = floor((b-2)/n)
    return (2*b - 2*a - (-1)**b -(-1)**a +2) / 4

def K(a,b,n):
    return M(a+2, b+2, n)


def error_in_estimate(a, b, n):
    return hole_actual_count(a, b, n) - rough_hole_estimate(a, b, n)

N = 100


for a in range(0, N):
    a = 2*a + 1
    for b in range(0, N):
        if b > a:
            b = 2*b + 1
            for n in range(1, int(floor(sqrt(b)) / 2) + 1):
                n = 2*n + 1
                En = error_in_estimate(a, b, n)            

                print(f"E({a}, {b}, {n}) = {En}")



  

Answer 4

BillyJoe's technique:

---

from math import floor, sqrt, ceil

def hole_actual_count(a, b, n):
    count = 0
    
    for x in range(a, b-1):
        if x % 2 == 1:
            if x % n == 0 or (x + 2) % n == 0:
                count += 1
        
    return count

def rough_hole_estimate(a, b, n):
    return M(b,n) - K(a,n) + floor((b-1)/n) - floor(a/n)

def M(b,n):
    """
    Thanks @BillyJoe in an MSE comment.
    """
    return floor(b/n) - 2 * floor(b/(2*n))
    
def K(a,n):
    return M(a-1,n)
    

def error_in_estimate(a, b, n):
    return hole_actual_count(a, b, n) - rough_hole_estimate(a, b, n)

N = 1000


for a in range(0, N):
    a = 2*a + 1
    for b in range(0, N):
        if b > a:
            b = 2*b + 1
            for n in range(1, int(floor(sqrt(b)) / 2) + 1):
                n = 2*n + 1
                En = error_in_estimate(a, b, n)            
                
                print(f"E({a}, {b}, {n}) = {En}")

    
                            
                    

Code outputs zero as the error value now, which means exact formula!