What's the formula of this sequence?

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.

-
do you need this formula for a computer program? (so are we allowed to use if-else-statements?) –  tampis Jun 24 '12 at 17:52

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

-
Even better than floor(), many programming languages have a built-in integer division operator that will round the result towards zero implicitly. –  Henning Makholm Jun 25 '12 at 0:55
@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. –  user17762 Jun 25 '12 at 0:59

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.

-

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<stdio.h>
#include<stdlib.h>
int main(int argc, char*argv[])
{
int i=0;
int a=atoi(argv[1]);
int n=atoi(argv[2]);

for( i = 0; i<n; i++)
{
printf("%d,%d,%d\n",i,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.

-
@glallen Are you the same person as tampis? –  user17762 Jun 25 '12 at 4:25
@Marvis: No, tampis did not generalize for any initial value or n. Both a and n increment by twos (power and division respectively) so you can use shifts for both, rather than a division, improving efficiency, and also the answer. (and you can compare our stackexchange profiles if you like - I've been on su for two years, have my github site posted, etc.) Just figured it better to improve the existing answer than to post one just slightly different by one operation. –  glallen Jun 25 '12 at 4:38
@glallen: I think n/2 is n >> 1 so fixed it in the above formula. (I hope it works now ;-) ) –  tampis Jun 26 '12 at 8:43
must have fat-fingered the &gt; &rt; when I was trying to format it, thanks. –  glallen Jun 26 '12 at 12:56

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$

-

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.

-

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 http://math.stackexchange.com/a/162540/781 :-).

-

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

-
And this is why one should never ask a programming question on math stackexchange. –  asmeurer Jun 25 '12 at 3:29
Way to make an $O(1)$ problem into $O(n)$ :| –  Thomas Jun 25 '12 at 4:22
I know there were already answers to solve the problem for programming. My answer for other readers that may wonder other solution ways. I just wanted to show the beauty of mathematics. Many different ways can found to solve a problem. Maybe It can open different doors in others mind. Thanks for understanding. –  Mathlover Jun 25 '12 at 5:55

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

-

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

-
Thank you very much. Marvis was faster, so I'll accept his answer. +1 from me anyway. –  Leri Jun 24 '12 at 18:04