# Getting the sequence $\{1, 0, -1, 0, 1, 0, -1, 0, \ldots\}$ without trig?

What's the simplest way to write a function that outputs the sequence:

{1, 0, -1, 0, 1, 0, -1, 0, ...}


... without using any trig functions?

I was able to come up with a very complex sequence involving -1 to some complicated formula, but I was hoping there is a more simple solution.

$n$ should start at 0 and go to infinity.

Update:

All the solutions you guys provided are great! I wasn't aware there were so many of them. I should have mentioned that I prefer a solution which doesn't use recursion; imaginary numbers; matrices; functions with if statements; or functions such as ceil, floor, or mod. I'm looking for something using basic algebra: addition/subtraction, multiplication/division, exponents, etc. However, I will accept anything since I didn't include this clause originally.

This is what I came up with:

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

Is there a less complicated way (i.e. fewer terms) to get this same sequence?

• Note that a simple recursion formula isn't possible, but $x_0=1$, $x_1=0$ and $x_{n+2}=-x_n$ works. That's kind of silly, however. – Thomas Andrews Apr 11 '12 at 19:04
• What's wrong with $1,0,-1,0,1,0,-1,0,\dots$? – Michael Joyce Apr 11 '12 at 19:37
• How is "simplest" defined in a non-subjective manner? Fewest operators? Shortest equation? Something else entirely? – zzzzBov Apr 11 '12 at 20:15
• @MichaelJoyce: I need it as a function that I can input into a calculator. – Senseful Apr 11 '12 at 21:50
• Your expression can be simplified to $$a_n=\frac{\left(-1\right)^n+1}{2}\cdot \left(-1\right)^{\frac{n(n-1)}{2}}$$ a factorisation of Mariano Suárez-Alvarez's answer – Henry Apr 12 '12 at 0:05

## 17 Answers

Let's try too : $|n \bmod 4-2|-1$

• Can you tell me what the |'s are? – user23320 Apr 11 '12 at 20:15
• @JoshuaDrake: the absolute value ( in C language it would be abs(x % 4-2)-1 ) – Raymond Manzoni Apr 11 '12 at 20:17
• @JoshuaDrake: note that the formula even works for non integer values (it gives a 'triangle wave'). – Raymond Manzoni Apr 11 '12 at 20:23
• You can see the graph of $f(x) = |x \bmod 4-2|-1$ here: wolframalpha.com/input/?i=y%3D%7C%28x+mod+4%29+-+2%7C+-+1 – Xenon Apr 11 '12 at 22:13
• @Xenon: Thanks for the graph! Let's add another possible solution : $\left(\dfrac {-4}{n+1}\right)$ using the definition of the Kronecker symbol – Raymond Manzoni Apr 12 '12 at 21:09

How about $\dfrac{i^n + (-i)^n}{2}$? (Of course, that is arguably just trigonometry in disguise).

Or as a recurrence: $a_n = -a_{n-2}$ with $(a_0,a_1)=(1,0)$.

Or $\begin{bmatrix}1 & 0\end{bmatrix}\begin{bmatrix}0&-1\\1&0\end{bmatrix}^n\begin{bmatrix}1\\0\end{bmatrix}$? (Which can be viewed as a better-disguised version of either of the two previous suggestions).

• Beat me to it ... – Mark Bennet Apr 11 '12 at 19:03
• The equivalences here are interesting. Note also that the recurrence form is a disguise for the $i^n$ form, and converted to the related homogeneous linear differential equation recreates the trig form. – Mark Bennet Apr 11 '12 at 19:21
• But what if... – anon Apr 11 '12 at 19:44
• @anon +1 That was hilarious and unexpected. That said, if I see more than one meme post a day on this site, I'm flagging 'em. – Rahul Apr 12 '12 at 0:29
• @rahul. Count yourself lucky that you don't frequent scifi.SE, where the mother of all meme sites is occasionally referenced, namely tvtropes.org. Over there, any reference to that site usually contains a SPOILER tag, since going there is essentially equivalent to falling into a black hole, time-waste-wise. – Rick Decker Jul 31 '12 at 2:10

Whether this is simplest will depend on exactly what you mean, but the following is a pretty simple description. It's certainly simpler than anything involving trig functions.

$$a_n=\begin{cases} 0 & \text{if n is odd} \\ 1 & \text{if n is divisible by 4} \\ -1 & \text{otherwise} \end{cases}$$

• This is so brutally simple I never ever were able to find it. – vakufo Apr 13 '12 at 5:31

What could possibly be easier than $\Re(i^n)$, $n=0,1,\ldots$?

• totally what I wanted to suggest as well – Tobias Kienzler Apr 12 '12 at 13:26

$$\frac{1}{2} \left((-1)^{(n-1) n/2}+(-1)^{n (n+1)/2}\right)$$

• @Anixx: Because the exponents are triangular numbers!? :-) – A. Rex Apr 12 '12 at 1:39
• Any expression that uses $(−1)^x$ is trigonometry because $(−1)^x$ is another notation for $\cos(\pi x)+i\sin(\pi x)$. – Anixx Apr 12 '12 at 3:20
• @Anixx $(-1)^n = -1\cdot -1\cdot -1 \cdots (n)$ because here $n\in N$. – Eelvex Apr 12 '12 at 3:55
• @Anixx I was talking about the definition of $(-1)^n$, which is not trigonometric. – Eelvex Apr 12 '12 at 13:06
• @Anixx, your last comment is an egregius example of a non-sequitur! – Mariano Suárez-Álvarez Jul 30 '12 at 23:32

If you have a sequence and have a linear recursion formula generating the sequence, then you can easily transform it into a closed form solution using one of many methods available.

In your case let us start with the simplest recursion: $a_0=1,a_1=0,a_n=-a_{n-2},n\ge 2$. The easiest (if you have access to a computer) way to obtain a closed form solution is to use matrix theory.

First, we rewrite the recursion in matrix form: $\left(\matrix{ a_n \\ a_{n-1} }\right)=\left(\matrix{ 0 & -1 \\ 1 & 0 }\right)\left(\matrix{ a_{n-1} \\ a_{n-2} }\right)$.

From here we get: $$\left(\matrix{ a_n \\ a_{n-1} }\right)=\left(\matrix{ 0 & -1 \\ 1 & 0 }\right)^{n-1}\left(\matrix{ a_1 \\ a_0 }\right)=\left(\matrix{ 0 & -1 \\ 1 & 0 }\right)^{n-1}\left(\matrix{ 0 \\ 1 }\right)$$ A standard method to proceed at this point is to diagonalize the matrix (here the computer is your best friend, for example: use Wolfram Alpha): $$\left(\matrix{ 0 & -1 \\ 1 & 0 }\right)=\left(\matrix{ -i & i \\ 1 & 1 }\right)\left(\matrix{ -i & 0 \\ 0 & i }\right)\left(\matrix{ -i & i \\ 1 & 1 }\right)^{-1}$$ $$\left(\matrix{ a_n \\ a_{n-1} }\right)=\left(\matrix{ -i & i \\ 1 & 1 }\right)\left(\matrix{ (-i)^{n-1} & 0 \\ 0 & i^{n-1} }\right)\left(\matrix{ i/2 & 1/2 \\ -i/2 & 1/2 }\right)\left(\matrix{ 0 \\ 1 }\right)$$ and $$a_n=\frac{1}{2}(-i)^n+\frac{1}{2}i^n$$

We could start from another form of recursion: for example, $a_0=1, a_1=0, a_2=-1$ and $a_n=-(a_{n-3}+a_{n-2}+a_{n-1})$, $n\ge 3$. Then write down a 3x3 matrix representing the recursion, diagonalize it, and obtain... well, the same solution. So, it does not matter how you represent the linear recursion: in general, you are going to obtain the same closed form solution.

Another way to find a closed form solution is to use generating functions. Using generating functions is easier to do by hand (no need to diagonalize and invert matrices).

• Great answer. I hope it is not underrated. – Pedro Tamaroff Apr 11 '12 at 20:48

The specific sequence is not essential. You are asking how to construct a function with period 4. Linear combinations of shifts of one $n$-periodic function can be used to write down any other $n$-periodic function, so they are all equally good in that sense. The trouble is to get at a sequence with period 4 without basing it on another one already known to have that period, such as $i^n$.

The answer is division by 2 which, as you can see, appears in all the answers that are not built from a $\mod 4$ operation.

If you are allowed as a primitive one integer function $f(n)$ of period 2, such as $(-1)^n$, and division by 2, then any function of order $2^k$ can be constructed.

From $f(n)$ and possible divisions by 2, one can construct the parity function $p(n) = n \mod 2$. Using that and more divisions by two, one can construct for each $i$ the function that equals the $i$'th binary digit of $n$.

I don't think there is a way to avoid as ingredients in the formula at least one 2-periodic function given as a primitive, and division by 2. Except by providing a 4-periodic operation at the start, in which case linear combinations are enough.

My favourite is $(-1)^{\frac{n-1}{2}}(n \text{ mod } 2 )$. Seems quite tidy compared to other possible expressions.

This may be silly, but ${(-1)^{\lceil n/2\rceil+1} }\cdot{(-1)^{n+1}+1\over 2}$, where $\lceil m\rceil$ is the smallest integer greater than or equal to $m$.

If you like the programming language C, you could write

2*!(n % 4) - !(n % 2)


which works for n from 0 up to the point where n overflows your integer size.

• If n is an unsigned it'll keep on working past integer overflow, too. – fluffy Apr 12 '12 at 22:56

I think that |n mod 4−2|−1 is a great solution. Here is some that not require absolute value:

(1 - (n mod 4))((n+1) mod 2)

The logic behind it is: n mod 2 gives 0, 1, 0, 1.. because we want all odd numbers to be 0 we use n+1 mod 2. Than we use (1 - (n mod 4)) to make 0 input to output 1 and 2 input to output -1. n mod 4 is just to limit the numbers between 0 and 3.

Cheers.

• This can be made more symmetrical as $(1 - n\bmod 4)(1 - n \bmod 2)$ – Peter Taylor Apr 16 '12 at 10:10

If you wish to avoid imaginary numbers, you need to ensure that $-1$ takes an integer power: so your answer seems pretty efficient in that respect.

If we relax the condition of avoiding imaginary numbers, then we no longer require integer powers, because we can allow $i = (-1)^{\frac{1}{2}}$ as in several other answers.

Alternatively, if we allow clock arithmetic/modular arithmetic, or rounding with ceiling or floor, it becomes much more straightforward to engineer a discrete, repeating pattern.

Otherwise, I can simplify your answer just a little (require fewer operations):

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

• Any expression that uses $(-1)^x$ is trigonometry because $(-1)^x$ is another notation for $\cos(\pi x)+ i \sin (\pi x)$ – Anixx Apr 11 '12 at 23:41
• @Anixx he needs to be able to enter it into a calculator, presumably without trigonometric functions. Most calculators can evaluate exponents, this should be fine. – itdoesntwork Apr 12 '12 at 13:35

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

But, technically that's using imaginary because it is really doing $$a_n=\frac{(-1)^n+1}{2}i^{(-1)^n-1}$$

With binary operators (not the prettiest solution but probably the fastest):

((n&1)^1) - ((n&2) & ~((n&1)<<1))

• Probably not the fastest, because there is (((x+3)>>1)&1) - ((x>>1)&1). – sam hocevar Apr 15 '12 at 9:30
• I love stuff like this – Almo Apr 24 '12 at 20:25

Let $a_n$ be defined like the coefficients of the series expansion at $x=0$ for $$\frac1{1-x^2}=1-x^2+x^4-x^6\cdots=\sum\limits_{n=0}^\infty a_n x^n .$$ You'll get your sequence by calculating: $\displaystyle \;\;\;\left[\frac1{n!}\frac{d^n}{dx^n}\frac1{1-x^2}\right]_{x=0}$.

• Rodrigues-ish. You could also say $a_n=[x^{n}]$ – Pedro Tamaroff Jul 30 '12 at 21:31
• @PeterTamaroff Sorry don't get it. Who's Rodrigues? – draks ... Jul 30 '12 at 21:45
• See this – Pedro Tamaroff Jul 30 '12 at 21:51
• @PeterTamaroff ahh, yeah I like(use) this kind. But what do you mean with $[x^n]$? – draks ... Jul 30 '12 at 21:57

I like

function GetNumInSquence(int num)
{
assert(num >= 0);

int m_lookup = { 1, 0, -1, 0 };
int numInSquence = m_lookup[num % 4];
return numInSequence;
}


No ifs or trig or anything; just a simple lookup. It's also easy to read the code. Someone else's 2*!(n % 4) - !(n % 2) is really cool, but it requires explanation to know what it's doing.

Here is a solution using only 5 bitwise or arithmetic operations:

2 - (((x + 1) | (x + x)) & 3)

• Your solution is too complicated. The simplest solution no one has yet posted is mathematical expression n%2. Please see my answer for an explanation how it works. math.stackexchange.com/a/134935/20207 – bodacydo Apr 21 '12 at 19:43
• @bodacydo - your solution is not a solution; it never outputs -1. – sam hocevar Apr 21 '12 at 21:12

## protected by anonApr 12 '12 at 19:36

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?