# Thread: number sequence fiddling

1. ## number sequence fiddling

Hi,

Well the idea of bit fiddling or twiddling is pretty well established and there's a good deal of stuff out there on the web if you want to look it up.

A similar (in spirit) activity can be done with the plain everyday number sequence 0,1,2,3 etc. and I wanted to know (if I describe it properly) what other people here might call it so I can google it and see if there are any recipes out there. By the way no branching (if's or ternary's) allowed.

For example
Code:
```int N=16;
for(i=0;i<N;i++)
printf("%i ",(i/4)%2);```
will get you 0,0,0,0,1,1,1,1,0,0,0,0 , a square wave alternatiing between 0 and 1 every 4 steps.
I've been trying to get 0,1,1,1,0,-1,-1,-1,0,1 etc and have got
Code:
```int N=16;
for(i=0;i<N;i++)
printf("%i ",1-2*(i/4)%2);```
but of course I need to get the zero coming up every power of 4 times. I'm sure this has been hacked out a number of times but don't quite know how to look it up.

Suggestions welcome thank you for reading.

2. Originally Posted by stabu
... I need to get the zero coming up every power of 4 times ...
Don't you mean every multiple of 4? If so, using the not operator will help you get those zeroes.

3. Imagine taking this sequence:

Seq_A = 0,0,0,0,1,1,1,1,...

And subtracting 1 from each element. You get this:

Seq_B = -1,-1,-1,-1,0,0,0,0,...

Now add these sequences together to get:

Seq_C = Seq_A + Seq_B = -1,-1,-1,-1,1,1,1,1,...

Now, you want to knock out every fourth element, so invent another sequence:

Seq_D = 0,1,1,1,0,1,1,1,...

Multiply this with sequence C:

Seq_E = Seq_C * Seq_D = 0,-1,-1,-1,0,1,1,1,...

This is the sequence you want. No branching.

(Well, I got the signs backwards, but you get it.)

4. 0,1,1,1,0,1,1,1,0,1,1,1 is easy to do. First of all, the sequence that repeats is of length four, so the first thing we're going to have is a mod four. That'll give us a number from zero to three. Now we want to map zero to four and the rest to one.
Code:
`f = (i%4+3)/4`
Another useful sequence here is 1,1,1,1,-1,-1,-1,-1,1,1,1,1
Dividing by four and modding with two gives us zero or one depending whether we have an even or odd multiple of four. Subtracting twice that from one gives us the desired output
Code:
`g = 1-((i/4)%2)*2`
All that's left is to combine these two.

There are of course several other ways

5. Many thanks
lattica: for correcting to multiples of 4
brewbuck for the prob decomposition
iMalc for the restraint in not quite spoonfeeding me :-D

OK .. so now I can generate my matrix-travelling-by-differential-index sequence func:
Code:
```int DM=8;
int f, g;
i=0;
while (i<32) {
f = (i%DM+(DM-1))/DM;
g = 1-((i/DM)%2)*2;
printf("%2i ", f*g);
++i;
}
printf("\n");
i=0;
while (i<32) {
printf("%2i ", (1 - (i%DM)+DM-1)/DM);
++i;
}
printf("\n");```
This gets
Code:
``` 0  1  1  1  1  1  1  1  0 -1 -1 -1 -1 -1 -1 -1  0  1  1  1  1  1  1  1  0 -1 -1 -1 -1 -1 -1 -1
1  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0```
so I move sideways first, reaching the end I pop down a row and move leftwards.
The very first step is incorrect so I will jump that one. Obviously workable, but not hugely elegant.

I think to get cuter code it would seem that there may be a bit fiddling recipe for this, but it's good for now.

Many thanks you guys!

6. stabu,
I think the general term you want is "integer sequence." Wikipedia has an article that gives the names of a few dozen known examples. Try:
Wikipedia:integer sequence
Also:
The On-Line Encyclopedia of Integer Sequences
Given an integer sequence, find its name, and formula.
The On-Line Encyclopedia of Integer Sequences

In mathematics there is a huge amount of work involving rational sequences and series (the sum of a sequence of terms.)

Gil

7. Very nice, thanks gil_johnson.

I had been getting close to this, I was running searches on "number sequences" but you're clearly right I should specify integer.

Cheers!

Popular pages Recent additions