# Need help deriving a formula

1. Oct 25, 2004

### rishid

Need to analyze the pattern and create a formula if possible out of the data below. Inputting the first column and outputting the second.
1 1
2 1
3 3
4 1
5 3
6 5
7 7
8 1
9 3
10 5
11 7
12 9
13 11
14 13
15 15
16 1

Only thing I got that is on powers of 2, it should be 1.

If you got any ideas, throw them at me.

Thanks,

RishiD

2. Oct 25, 2004

### chroot

Staff Emeritus
Looks like it's just going through the odd integers, resetting to one on powers of two.

- Warren

3. Oct 25, 2004

### matt grime

Try writing out i rows, starting a new row each time you come across 1. the 'answer' should jump out at you (i'm not sure yo'ure even looking for an answer, to be honest, and what "should be 1").

4. Feb 27, 2010

### richJ

Hello Rishid,
I have the solution to your problem you posted on Oct. 25, 2004.

The formula is: x = 2 i + 1 - (2 ^ (int(log2(i)) + 1)

where i is the integer and x is the result,
log2(n) is the log (base 2) of n,
and int(n) is the integer value of n.

The table illustrates the calcs. (I used periods to line up the values because the message formatting automatically removes extraneous spaces. Also I was forced to use variables to represent each step for the same formatting reason). Specifically,

a = 2i + 1
b= int(log2(i))
c= int(log2(i)) + 1
d = 2^(int(log2(i))+1)
and finally the result you're trying to generate: x = a - d

i.....a.....b....c.....d.....x

1.....3.....0.....1.....2.....1
2.....5.....1.....2.....4.....1
3.....7.....1.....2.....4.....3
4.....9.....2.....3.....8.....1
5.....11....2....3.....8.....3
6.....13....2....3.....8.....5
7.....15....2....3.....8.....7
...
16...33....4.....5.....32...1

I hope this helps.
RichJ