Calculate number of integers less than n fitting the form 6n±1

Question

Of course the approximation is n/3, but I am looking for a way to get the number of integers, not an approximation.

Answer 1

A good approximation is $\lfloor\frac{n+1}{3}\rfloor$. It is correct except if $n\equiv 5\pmod6$, in which case it overestimates by $1$.

This overestimate can be corrected in a couple of ways.

If you accept the mod function, sometimes denoted $\%$ where $a\% b$ is the (least nonnegative) remainder in dividing $a$ by $b$, then we can get a correct count of your function by $\lfloor\frac{n+1}{3}\rfloor-\lfloor \frac{n\%6}{5}\rfloor$.

If you don't like the mod ($\%$) operator, you could try $\lfloor\frac{n+1}{3}\rfloor-\lfloor \frac{1+\cos\left(\pi\left( \frac{n+1}{3}\right) \right)}{2}\rfloor$, which I think works.

Answer 2

There are several sequences that count the amount of $6k\pm1$ less than or equal to $n$.

---

Here is a specific sequence:

$$A_n=2\cdot\left\lfloor\frac{n+1}{6}\right\rfloor-\frac{(n\bmod6)^4}{24}+\frac{5(n\bmod6)^3}{12}-\frac{35(n\bmod6)^2}{24}+\frac{25(n\bmod6)}{12}$$

---

Here is the general solution:

1. Divide by $3$ and write-down the error next to it:

   • $\frac{ 0}{3},+\frac{0}{3}$
   • $\frac{ 1}{3},+\frac{2}{3}$
   • $\frac{ 2}{3},+\frac{1}{3}$
   • $\frac{ 3}{3},+\frac{0}{3}$
   • $\frac{ 4}{3},-\frac{1}{3}$
   • $\frac{ 5}{3},+\frac{1}{3}$

2. Rewrite the error as a function of $n\bmod6$:

   • $f(0)=+\frac{0}{3}$
   • $f(1)=+\frac{2}{3}$
   • $f(2)=+\frac{1}{3}$
   • $f(3)=+\frac{0}{3}$
   • $f(4)=-\frac{1}{3}$
   • $f(5)=+\frac{1}{3}$

3. Compute the interpolating function and add $\frac{n}{3}$ to the result:

$$A_n=\frac{(n\bmod6)^5}{60}-\frac{5(n\bmod6)^4}{24}+(n\bmod6)^3-\frac{55(n\bmod6)^2}{24}+\frac{43(n\bmod6)}{20}+\frac{n}{3}$$