1

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

jhpratt
  • 137
  • Easiest is a "cases" formula, that treats the numbers $n$ of the form $6k$, $6k+1$, $6k+2$, $6k+3$, $6k+4$, and $6k+5$ separately. (The cases $6k+2$, $6k+3$, $6k+4$ are essentially identical.) If you want formulas, use the "floor" function $\lfloor x\rfloor$. – André Nicolas Sep 13 '14 at 21:24
  • I realise I can do that (in conjunction with summation), but I was looking for a formula. The floor function does not necessarily work: 15 gives 4 (5,7,11,13), but flooring only gives 3. – jhpratt Sep 13 '14 at 21:30
  • For numbers of the form $6k+1,6k+2,6k+3, 6k+4$ the number is $2\lfloor n/6\rfloor +1$. There are $5$, you missed the number $1$ in your list. – André Nicolas Sep 13 '14 at 22:05

2 Answers2

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.

paw88789
  • 40,402
0

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

barak manos
  • 43,109