The sequence of integers which are not divisible by 3

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

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

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

$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

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

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