title: 2 Recurrence equations - Finding index
body: <p>I have some trouble figuring out a relationship between the 2 recurrence relations given below.  </p>
  
  <pre><code>f(0) = 1  
  f(1) = 1  
  f(2) = 2  
  f(2n) = f(n) + f(n + 1) + n          (for n &gt; 1)  
  f(2n + 1) = f(n - 1) + f(n) + 1      (for n &gt;= 1)
  </code></pre>
  
  <p>So the series is like:(Index: 0,1,2,3...n)<br>
  1,1,2,3,7,4,13,6,15,11,22,12,25,18,28,20,34...  </p>
  
  <p>The goal is find the index of the occurrence of any given number which is in the series.<br>
  Example:<br>
  Given: 7<br>
  Output: 4  i.e f(4) = 7  </p>
  
  <p>Also, since a number <em>may</em> occur more than once in the given sequence, return the <em>last time</em> that number occurs.<br>
  Example:<br>
  Given: 22<br>
  here, f(10) = 22  and f(17) = 22<br>
  so, Output: 17</p>
  
  <p>From the python code - I have observed that a number occurs utmost twice (not 100% sure though..).</p>
  
  <p>My code to find the nth number in the series:</p>
  
  <pre><code>memo = {}
  def rep(k):
      if k&lt;=1:
          return 1
      if k == 2:
          return 2
      if not k in memo:
          if k%2==0:
              memo[k] = (k/2) + rep((k/2)+1) + rep(k/2)
          else:
              memo[k] = 1 + rep(((k-1)/2)-1) + rep((k-1)/2)
      value_key[memo[k]] = k
      return memo[k]
  </code></pre>
  
  <p>I have used <code>memo</code> to hash the values that I have already generated, but using this approach to generate and trying out number from 0 till I get a value that is equal to the given number (simple brute force)  takes forever and causes MemoryErrors for larger digits(Input will vary from 1 to 20 digits).</p>
  
  <p>So, is there any relation between the given equations that I am missing?<br>
  If I could find a relation between <code>f(n)</code> (given input) and <code>n</code> - I think it can be easily implemented in code, but I am not able to simplify it mathematically - I've tried substituting one in another (the given recurrence relations) but so far I couldn't figure out anything.</p>