# Formula for the number of pairs of odd numbers $x, x+2k \subset [a,b]$ such that $n \mid x$ or $n \mid x + 2k$? Previous solution was $k = 1$ only.

closed-formdivisibilityelementary-number-theoryinclusion-exclusionnatural numbers

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


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$$