Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
$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
2  
@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

5 Answers 5

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,...

share|improve this answer
    
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.

share|improve this answer
    
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.$$

share|improve this answer
    
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$.

share|improve this answer
    
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!

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.