# The sequence of integers which are not divisible by 3 [closed]

Is there a known formula to generate the sequence of all integers which are not divisible by 3? Additionally, is there a formula to generate the sequence of all integers that are not divisible by 3 nor by 2?

-

## closed as off-topic by Najib Idrissi, Claude Leibovici, A.D, graydad, Jonas MeyerJul 15 at 2:47

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Najib Idrissi, Claude Leibovici, A.D, graydad
If this question can be reworded to fit the rules in the help center, please edit the question.

$a_n=3n+1$ ${}{}{}{}$ –  Amr Jan 19 '13 at 12:03
He probably means all integers not divisible by 3. –  Git Gud Jan 19 '13 at 12:05
@Git Gud I think this is easy to do as well. I just want to know a precise definition of a formula –  Amr Jan 19 '13 at 12:07

The non-multiples of $3$ are given by the formula $$a_n = \frac{3}{4} + \frac{3n}{2} + \frac{(-1)^n}{4},$$ where $n \in \mathbb{Z}.$

Similarly, the non-multiples of both $3$ and $2$ can be given by $$b_n = \frac{-3}{2} + 3n + \frac{(-1)^n}{2} = 2a_n - 3.$$

-
it works, and recurence formula is is a(n) = 3n - a(n-1) –  user58874 Jan 19 '13 at 12:39
Second part of my question is still open –  user58874 Jan 19 '13 at 12:40
a(n) = 3n - a(n-1) , a(0)=1 –  user58874 Jan 19 '13 at 12:52
@user58874 I don't see why - is there a problem with the sequence $(b_n)_n$? –  Cocopuffs Jan 19 '13 at 13:51

$f(n) = \lfloor \frac {3}{2} n - \frac {1}{2} \rfloor$ will generate all the non-multiples of 3 in order.

-
sorry but is not correct –  user58874 Jan 19 '13 at 12:43
@user58874: Looks right to me. You know $\lfloor x \rfloor$ is the floor function, right? –  Hurkyl Jan 19 '13 at 12:45

Mysteriously, {1,1+4,1+4+2, 1+4+2+4, 1+4+2+4+2, ...} does what you ask.

a_1=1

a_odd,n = a_n-1 + 2

a_even,n = a_n-1 + 4.

{1, 5, 7, 11, 13, 17, 19, 23, 25, 29, ...}

-

The formula $a(n)$ := the $n$-th number not divisible by $3$ (with $a(0) = 1$) would often be useful.

The two formulas $b(n) = 3n+1$ and $c(n) = 3n+2$ together enumerate them as two doubly-infinite sequences. The idea is to pick an equivalence class and iterate over it.

The single formula $d(n) = \frac{3}{2}n + (-1)^n \frac{1}{2}$. The idea hre is that every two steps you need to increase by $3$, thus $\frac{3}{2}n$, then $(-1)^n$ to alternate between adding and subtracting something. (Depending on what we were enumerating, we might need to add in a constant as well)

This formula enumerates all of them as a singly infinite sequence: $$e(n) = d\left( \frac{1}{2} n - \left(1 - (-1)^n \right) \left( \frac{n}{2} + \frac{1}{4} \right) \right)$$ The first few terms are $e(0) = d(0)$, $e(1) = d(-1)$, $e(2) = d(1)$, $e(3) = d(-2)$, $e(4) = d(2)$, ....

A recursive formula works: $f(0) = 1$, $f(1) = 2$, $f(n) = 3 + f(n-2)$.

By cases,

$$g(n) = \begin{cases} 3\frac{n}{2}+1 & n \text{ even} \\ 3 \frac{n-1}{2} + 2 & n \text{ odd} \end{cases}$$

Similar tricks apply to the case of not being divisible by 2 or by 3. This might be more simply described as being $1$ or $-1$ modulo $6$.

-
A recursive formula works: a(n) = 3n - a(n-1) –  user58874 Jan 19 '13 at 12:46

I have something that I created for some Math projects in Java. I created this formula since I didn't find anything for that. Maybe it can help you. Here's a translation for formal Math, and Java code in the end. Enjoy

A generic formula to generate the sequence of non divisible numbers for any base:

First, some definitions:

• $b$: base
• $n$: Nth number in the sequence of non divisible numbers of base b.
• $\bmod$: modulus operator. (% operator in C++, Java and many others).

The generic function for non divisible sequence of base $b$: $\mathrm f(b,n)$

$$\mathrm f(b,n) = b \cdot \left\lfloor \frac{n}{b-1} \right\rfloor + 1 + \bigl( n \bmod (b-1) \bigr)$$

** Note, the notation for floor function is:

$$\lfloor 1.5 \rfloor = 1$$ $$\lfloor 3.3 \rfloor = 3$$

Before reduce the function, let's extend it, using a function for the modulus operator ($\bmod$).

The modulus function:

$$y \bmod d = f(y,d)$$

$$\mathrm f(y,d) = y - \left( \left\lfloor \frac y d \right\rfloor \cdot d \right)$$

Now let's replace the modulus operator ($\bmod$) in the main formula, where $n$ will the $y$, and $(b-1)$ will be the $d$, in the formula above:

$$\mathrm f(b,n) = b \cdot \biggl\lfloor \frac{n}{b-1} \biggr\rfloor + 1 + \Biggl( n - \biggl( \biggl\lfloor \frac{n}{b-1} \biggr\rfloor \cdot (b-1) \biggr) \Biggr)$$

With the extended formula we can do this reduction steps:

• step 1: reorganize to clarify next steps. $$\mathrm f(b,n) = \bigg( \bigg\lfloor \frac{n}{(b-1)} \bigg\rfloor \cdot b \bigg) - \bigg( \bigg\lfloor \frac{n}{(b-1)} \bigg\rfloor \cdot (b-1) \bigg) + n + 1$$

• step 2: convert $\big( \lfloor n/(b-1) \rfloor \cdot b \big)$ to $\big( \lfloor n/(b-1) \rfloor \cdot (b-1) \big) + \lfloor n/(b-1) \rfloor$ $$\mathrm f(b,n) = \bigg( \bigg\lfloor \frac{n}{(b-1)} \bigg\rfloor \cdot (b-1) \bigg) + \bigg\lfloor \frac{n}{(b-1)} \bigg\rfloor - \bigg( \bigg\lfloor \frac{n}{(b-1)} \bigg\rfloor \cdot (b-1) \bigg) + n + 1$$

• step 3: cut oposite groups. The final formula: $$\mathrm f(b,n) = \bigg\lfloor \frac{n}{(b-1)} \bigg\rfloor + n + 1$$

Now we have a much simplier function, without the modulus operator ($mod$).

Here's some Java code of the initial formula:

// Initial formula in Java:

// Note that Math.floor() don't need to be used, since n is an int and
// (b-1) is also an int, returning an int value:

static public int functionNonDiv(int b, int n) {
return b*(n/Math.floor(b-1)) + 1 + (n % (b-1)) ;
}

// Real function in Java, without Math.floor():

static public int functionNonDiv(int b, int n) {
return b*(n/(b-1)) + 1 + (n % (b-1)) ;
}



The simplified formula:


// Function for sequence of non divisible numbers of base b:

static public int functionNonDiv(int b, int n) {
return Math.floor(n / (b-1)) + n + 1 ;
}

// Real function in Java, without Math.floor():

static public int functionNonDiv(int b, int n) {
return (n / (b-1)) + n + 1 ;
}



Now, some examples of output of the formula from the java code:

Base: 2
0> 1
1> 3
2> 5
3> 7
4> 9
5> 11
6> 13
7> 15
8> 17
9> 19

Base: 3
0> 1
1> 2
2> 4
3> 5
4> 7
5> 8
6> 10
7> 11
8> 13
9> 14

Base: 5
0> 1
1> 2
2> 3
3> 4
4> 6
5> 7
6> 8
7> 9
8> 11
9> 12



I hope that this can help. Note that my main language is not english and I'm not a mathematician.

Note: Fixed some reduction steps.

Enjoy!

-
If you want to start the sequence for numbers larger than base:  static public int functionNonDiv(int b, int n) { return (n / (b-1)) + n + 1 + b ; }  –  GMP Oct 17 '13 at 3:36

All positive integers not divisible by 3 are generated by 3k +1 and 3k +2 for k = 0,1,2,3,4,... All positive integers not divisible by 2 nor by 3 are generated by 6k +1 and 6k +5 for k = 0,1,2,3,4,...

-
I mean a formula to generate the sequence of all integers in ascending order like 2k +1 is generating all odd numbers in strict ascending order. –  user58874 Jan 19 '13 at 12:24