Proof by another user of the formula for $k = 1$, that is the total number of pairs $(x, x + 2k)$ of odd numbers in in interval $[a,b]$ such that $n \mid x$ or $n \mid x + 2k$.
So I'm wondering where the general formula for any $k \in \Bbb{N}$ differs.
I think the first part should be the same, i.e. we have $h(a,b,n,k) = 2(\lfloor\dfrac{b}{n}\rfloor – \lfloor \dfrac{b}{2n}\rfloor – \lfloor \dfrac{a-1}{n}\rfloor + \lfloor\dfrac{a-1}{2n} \rfloor) + g(a,b,n,k)$.
However, I'm having trouble with finding the actual formula.
Attempt:
$$
A = A(a,b,n,k) := \{ i = 0..\dfrac{b – 2k -a}{2} : a + 2i = nx, x \in \Bbb{Z}\} \\
B = B(a,b,n,k) := \{ i=0..\dfrac{b – 2k-a}{2} : a + 2i + 2k = nx, x \in \Bbb{Z}\} \\
\text{ Then, the quantity I seek is simply inclusion-exclusion:} \\
h(a,b,n,k) = \#A + \#B – \# (A \cap B)
$$
The inclusion-exclusion was not required in the $k=1$ case, because $A \cap B$ always would be $\varnothing$ since $n$ an odd can't divide both $a + 2i$ and $a + 2i + 2k$ for any $i$.
However, I am not sure how to take the sizes of $A,B$ nor how to perform their intersection.
More work:
Under $a + 2i = nx$ we have the following chain of $\iff$'s:
$$
0 \leq i \leq \dfrac{b – 2k – a}{2} \\
\iff \\
a \leq a + 2i \leq b – 2k \\
\iff \\
a \leq nx \leq b – 2k \\
\iff \\
\lceil \dfrac{a}{n} \rceil \leq x \leq \lfloor\dfrac{b – 2k}{n}\rfloor \\
\implies
\#A = \lfloor\dfrac{b – 2k}{n} \rfloor – \lceil\dfrac{a}{n} \rceil + 1
$$
Similarly, for $\# B$ we have the inequality (under $a + 2i + 2k = nx$):
$$
0 \leq i \leq \dfrac{ b – 2k – a}{2} \\
\iff \\
a + 2k \leq a + 2i + 2k \leq b – 2k + 2k \\
\iff \\
a + 2k \leq n x \leq b \\
\iff \\
\lceil \dfrac{a + 2k}{n}\rceil \leq x \leq \lfloor \dfrac{b}{n} \rfloor \\
\implies \# B = \lfloor \dfrac{b}{n} \rfloor – \lceil \dfrac{a + 2k}{n} \rceil + 1
$$
But I'm still wondering about the intersection $A \cap B$!
from math import floor, sqrt, ceil
def hole_actual_count(a, b, n, k):
count = 0
for x in range(a, b-1):
if x % 2 == 1:
if x % n == 0 or (x + 2*k) % n == 0:
count += 1
return count
def rough_hole_estimate(a, b, n, k):
A = floor((b - 2*k)/n) - ceil(a/n)
B = floor(b/n) - ceil((a + 2*k)/n)
C = floor((b - 2*k)/n) - ceil((a + 2*k)/n)
return A + B - C + 1
def error_in_estimate(a, b, n, k):
return hole_actual_count(a, b, n, k) - rough_hole_estimate(a, b, n, k)
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
for k in range(1, (b - a)//2):
En = error_in_estimate(a, b, n, k)
print(f"E({a}, {b}, {n}, {k}) = {En}")
Currently, my thinking is:
$$
z \in A \cap B \iff a + 2i = nx, a + 2j + 2k = ny
$$
for some $0 \leq i,j \leq \dfrac{b – 2k – a}{2}, x,y \in \Bbb{N}$.
When that happens, we have that $2(i – j – k) = n(x – y)$
However, the above code tests that idea, and shows the following erorr values:
E(1, 5, 3, 1) = 0
E(1, 7, 3, 1) = -1
E(1, 7, 3, 2) = -1
E(1, 9, 3, 1) = -1
E(1, 9, 3, 2) = -2
E(1, 9, 3, 3) = -4
E(1, 11, 3, 1) = 0
E(1, 11, 3, 2) = -1
E(1, 11, 3, 3) = -3
E(1, 11, 3, 4) = 0
E(1, 13, 3, 1) = -1
E(1, 13, 3, 2) = -1
E(1, 13, 3, 3) = -4
E(1, 13, 3, 4) = -1
E(1, 13, 3, 5) = -1
E(1, 15, 3, 1) = -1
E(1, 15, 3, 2) = -2
E(1, 15, 3, 3) = -5
E(1, 15, 3, 4) = -1
E(1, 15, 3, 5) = -2
E(1, 15, 3, 6) = -5
E(1, 17, 3, 1) = 0
E(1, 17, 3, 2) = -1
Best Answer
Let $A$ be the number of odd numbers $p$ such that $a\le p\le b-2k$ and $n\mid p$.
Let $B$ be the number of odd numbers $q$ such that $a+2k\le q\le b$ and $n\mid q$.
Let $C$ be the number of odd numbers $r$ such that $a\le r\le b-2k,n\mid r$ and $n\mid r+2k$.
Then, one has $$h(a,b,n,k)=A+B-C$$ where $$A=\left\lfloor\frac{b-2k}{n}\right\rfloor-\left\lfloor\frac{b-2k}{2n}\right\rfloor-\bigg(\left\lfloor\frac{a-1}{n}\right\rfloor-\left\lfloor\frac{a-1}{2n}\right\rfloor\bigg)$$ and $$B=\left\lfloor\frac{b}{n}\right\rfloor-\left\lfloor\frac{b}{2n}\right\rfloor-\bigg(\left\lfloor\frac{a+2k-1}{n}\right\rfloor-\left\lfloor\frac{a+2k-1}{2n}\right\rfloor\bigg)$$
For $C$, note that $r\equiv r+2k\equiv 0\pmod n\iff r\equiv 2k\equiv 0\pmod n$.
If $2k\not\equiv 0\pmod n$, then $C=0$.
If $2k\equiv 0\pmod n$, then $C=A$.
Therefore, one gets $$h(a,b,n,k)=\begin{cases}A+B&\text{if $2k\not\equiv 0\pmod n$} \\\\A+B-A&\text{if $2k\equiv 0\pmod n$}\end{cases}$$
which can be summarized as
$$\color{red}{h(a,b,n,k)=A+B-\bigg(1-\left\lceil\frac{2k}{n}\right\rceil+\left\lfloor\frac{2k}{n}\right\rfloor\bigg)A}$$ where $$A=\left\lfloor\frac{b-2k}{n}\right\rfloor-\left\lfloor\frac{b-2k}{2n}\right\rfloor-\left\lfloor\frac{a-1}{n}\right\rfloor+\left\lfloor\frac{a-1}{2n}\right\rfloor$$ and $$B=\left\lfloor\frac{b}{n}\right\rfloor-\left\lfloor\frac{b}{2n}\right\rfloor-\left\lfloor\frac{a+2k-1}{n}\right\rfloor+\left\lfloor\frac{a+2k-1}{2n}\right\rfloor$$