-1
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.

Line Graph for the input output pairs

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)

Anubhav Sharma
  • 159
  • 1
  • 12
  • 1
    I’m voting to close this question because it belongs to [Math SO](https://math.stackexchange.com/) – Justinas Jun 17 '23 at 19:28
  • In what language? You can always write that function yourself – Justinas Jun 17 '23 at 19:29
  • 1
    *"if n is of the form 2^n then f(n) = 1"* <<<< Nonononononono. Big no. I strongly, very strongly advise you not to use the same variable name for two different numbers. You could say "if x is of the form 2^n, then f(x) = 1" or "if n is of the form 2^k, then f(n) = 1" but DO NOT say "if n is of the form 2^n, then f(n) = 1" otherwise it's going to be impossible to reason about this. You're going to have to write n = 2^n and nothing is going to make sense. – Stef Jun 17 '23 at 19:36
  • 3
    This looks like a [Josephus permutation](https://en.wikipedia.org/wiki/Josephus_problem). – Corvus Jun 17 '23 at 19:38
  • @Stef Updated. Thanks for pointing it out. – Anubhav Sharma Jun 17 '23 at 19:38
  • 2
    If I'm not mistaken, it's "clear the most significant bit, multiply by 2, and add 1". https://stackoverflow.com/questions/7790233/how-to-clear-the-most-significant-bit could give you a start with the first step. It's simpler if your language has a function like "count leading zeros" or other integer log base 2. – Nate Eldredge Jun 17 '23 at 19:40

1 Answers1

1

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.

Stef
  • 13,242
  • 2
  • 17
  • 28