7
$\begingroup$

I am working on some project that needs to calculate what $a_n$ element of the set of numbers $1, 1, 2, 2, 4, 4, 8, 8, 16, 16 \ldots$ will be.

$n$ can be quite big number so for performance issues I have to calculate formula for this set of numbers (Note: first element may be different). What I've done so far is that I managed to find out how to calculate next element using element before. My formula for this is:

$a_n = a_{n-1}\cdot 2^{\frac{1 + (-1)^{n-1}}2}$

Now from this I want to calculate $a_n$ element using $a_1$ element. with this I am stuck.

  • 0
    do you need this formula for a computer program? (so are we allowed to use if-else-statements?)2012-06-24

9 Answers 9

26

$a_n$ is termed as a "sequence" and not a series. Getting back to the question, $a_n = 2^{\lfloor n/2 \rfloor}$ should do the job, where $\lfloor x \rfloor$ is the greatest integer $\leq x$, where $n$ goes from $0$. Usually the function to do this, is available through the command floor() in most languages. If your first element is $a$ and not $1$, your $a_n = a \times 2^{\lfloor n/2 \rfloor}$

  • 1
    @HenningMakholm True. I wrote this keeping in mind MATLAB. As an aside and not related to the question, I was recently wondering what is a better way to get floor in MATLAB other than using the command `floor()`. Since `floor((64)^(1/3))` in MATLAB returns an answer $3$ due to the truncation of $1/3$ in the exponent.2012-06-25
12

You are I assume thinking of $a_1,a_1,2a_1,2a_1,4a_1,4a_1, \dots$. Then the following will work: $a_n=a_1\times 2^{\lfloor \frac{n-1}{2} \rfloor}.$ Here $\lfloor x\rfloor$ is the "floor" function, where $\lfloor x\rfloor$ is the greatest integer that is $\le x$.

You seem to be labelling your sequence as $a_1,a_2,a_3,\dots$. Many mathematicians prefer to let the first index be $0$. In that case, you will have $a_n=a_0\times 2^{\lfloor \frac{n}{2} \rfloor}$.

  • 0
    Thank you v$e$ry much. Marvis was faster, so I'll accept his answer. +1 from me anyway.2012-06-24
9

Apart from Greatest Integer function, this sequence will also generate the required series. $ \huge 2^{ \frac 1 2 \left ( n + \frac{1 + (-1)^{n+1}}{2} \right )} $ Check it out in Wolframalpha.

8

a code example in c++ (with the formula $a_n = 2^{\lfloor n/2 \rfloor}$ already given by Marvis):

a_n = a << (n >> 1) 

The shift operator << will give you a fast implementation of calculating $2^m$. The operator >> will give a fast implementation of calculating $\lfloor n/2 \rfloor$.

This could be implemented very efficiently in C/assembly language. Bitshifts themselves are already x86 instructions, and since both operations are by powers of two, you can use the following:

 #include #include int main(int argc, char*argv[]) {         int i=0;         int a=atoi(argv[1]);         int n=atoi(argv[2]);          for( i = 0; i>1,a<<(i>>1));         }         return 0; } 

Running gcc -O2 -S seq.c to inspect the generated code in assembly, the 'math' is completed in two cpu-instructions: sarl %ecx and sall %cl, %r8d. It cannot get any faster than this.

  • 0
    must have fat-fingered the `> &rt;` when I was trying to format it, thanks.2012-06-26
4

When you have an unknown sequence, the best thing to try is to query the Online Encyclopedia of Integer Sequences (OEIS). This one is A016116. That page gives several forumlas for this, including the $2^{\lfloor n/2 \rfloor}$ answer given above.

2

$\large a_n=\frac{2^{\sin{\frac{(2n-1)\pi}{2}}\sum \limits_{k=1}^n k \sin{\frac{(2k-1)\pi}{2}} }}{2}$

or

$\large a_n=\frac{2^{(-1)^{(n+1)}\sum \limits_{k=1}^n k (-1)^{(k+1)} }}{2}=\frac{2^{\sum \limits_{k=1}^n k (-1)^{(k+n)} }}{2}$

Maybe it is longer way for programming. It is just for fun.

  • 0
    "Beauty"? I am not sure this shows any beauty.2015-07-23
2

In addition to the other more correct answers, it is interesting to note that this sequence can be generated with only two bit shifts:

${\tt{}a_n=1 << (n >> 1)}$

Note that ${\tt{}n}\in[0,\infty]$, not ${\tt{}n}\in[1,\infty]$. Also, if you allow $\tt{}1$ to vary (for example, choose $\tt{}a_{n,\alpha}=\alpha << (n >> \alpha)$), you get sequences like this:

$\alpha=1: \quad 1, 1, 2, 2, 4, 4, 8, 8, 16, 16, \cdots$
$\alpha=2: \quad 2, 2, 2, 2, 4, 4, 4, 4, 8, 8, \cdots$
$\alpha=2: \quad 3, 3, 3, 3, 3, 3, 3, 3, 6, 6, \cdots$

0

$\forall n\geqslant1,\qquad a_{2n}=a_{2n-1}=2^{n-1}$

0

If you are using a programming language that supports it, you could do 1 << ((n + 1)/2), where << is a bitshift, and / is integer division (you could also use floor((n + 1)/2) if you don't have integer division). The + 1 is needed because you are starting indexing at 1 instead of 0 (otherwise, it would just be 1 << (n/2).

This will be the most efficient way to do it. Be aware that once n reaches a large enough number (64 or 128, depending on your architecture), you will get numbers that are too large to fit into a word, unless you are using a language that implicitly supports arbitrary large integers, like Python. The result in that case is usually undefined.

By the way, stackoverflow is a better place to ask these kinds of questions (unless you really are interested in answers like https://math.stackexchange.com/a/162540/781 :-).