# Solution to sequence of integers not divisible by 3

I think I have a solution so this sequence in:

$a_n = \lfloor \frac{n-1}{2}\rfloor + n$.

I have been plugging numbers in and so far it works. However, there must be a better way to check if this indeed a solution.

My questions are:

1) Is this a solution, and

2) What is the best method for checking answers like this?

• Are you trying to show that $a_n$ is never divisible by 3? – Sam Weatherhog Oct 8 '15 at 3:05
• Yes. Sorry if that was not clear. – MKreegs Oct 8 '15 at 3:06
• Indeed your sequence avoids all multiples of $3$. Moreover, it hits every non-multiple of $3$. – André Nicolas Oct 8 '15 at 3:25

## 2 Answers

There are at least two ways to do this. Firstly, because you are looking at divisibility, you can generally split the proof into cases. The second option you have is to use induction since it seems you are trying to prove this for $n\ge 1$ (or some other integer).

The first way is more general in that you can show that $a_n$ is not divisible by $3$ for any integer $n$. We will split into the two cases $n$ even or $n$ odd. If $n$ is odd then $n=2k+1$ for some $k\in \mathbb{Z}$ so:

$$\left\lfloor \frac{n-1}{2} \right\rfloor +n=\left\lfloor \frac{2k+1-1}{2} \right\rfloor+2k+1=\left\lfloor k \right\rfloor+2k+1=3k+1$$ and $3k+1$ is not divisible by $3$ so the result works for all odd integers. If $n$ is even then $n=2k$ for some $k\in \mathbb{Z}$ and:

$$\left\lfloor \frac{n-1}{2} \right\rfloor +n=\left\lfloor \frac{2k-1}{2} \right\rfloor+2k=\left\lfloor k-\frac{1}{2} \right\rfloor+2k=k-1+2k=3k-1$$ and $3k-1$ is not divisible by $3$ so the result holds for all even integers too.

• Sam Weatherhog's answer has all you need. A remark: As $k$ is an arbitrary positive integer, and a number not a multiple of $3$ has to be $\pm1\pmod3$ this shows your sequence enumerates all numbers that are not multiples of 3. – P Vanchinathan Oct 8 '15 at 3:26
• @PVanchinathan nice! Only comment is that $k$ is an arbitrary integer (not necessarily positive). – Sam Weatherhog Oct 8 '15 at 3:35

Well, $n$ is either even or odd.

If $n$ is even, $n=2k$ and $$\lfloor\frac {n-1}2\rfloor=\lfloor k-\frac 12 \rfloor=k-1$$ So $$a_{2k}=k-1+2k=3k-1$$

If $n$ is odd, $n=2k+1$ and $$\lfloor\frac {n-1}2\rfloor=\lfloor k \rfloor=k$$ So $$a_{2k+1}=k+2k+1=3k+1$$

Either way $a_n$ can't be divisible by $3$.