X Y
-------
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
17 3
18 5
19 7
20 9
21 11
22 13
23 15
24 17
25 19
26 21
27 23
28 25
29 27
30 29
31 31
32 1
33 3
34 5
I tried representing the pattern in form of line graph.
The pattern is like this,
if n is of the form 2^N then f(n) = 1
else f(n) = f(n-1)+2
Also, use f(1) = 1 as base condition (already covered by above logic)
>Solution :
From the recurrence formula f(n) = f(n-1) + 2 you can deduce that if n is of the form 2^k + j where j < 2^k, then: f(2^k + j) = f(2^k) + 2 * j.
And since you also know that f(2^k) = 1, you can conclude:
f(2^k + j) = 1 + 2 * j
Now if you want a formula for f(n), all you have to do is write j as a function of n. There is no particularly pretty way to write this formula, here is one:
j = n - 2^⌊log2(n)⌋
And hence:
f(n) = 1 + 2 * (n - 2^⌊log2(n)⌋)
where ⌊ ⌋ denotes the floor function and log2 denotes the binary logarithm.