title: Greedy algorithm for finding a negafibonacci representation of a number?
body: <p>According to <a href="https://en.wikipedia.org/wiki/Zeckendorf&#39;s_theorem" rel="noreferrer">Zeckendorf's theorem</a>, every positive integer can be written in a unique way as the sum of non-consecutive distinct Fibonacci numbers. Such a decomposition can be found easily with a greedy algorithm consisting essentially in subtracting the largest Fibonacci number that fits and iterating, for example:</p>
  
  <p><code>20 = 13 + 7 = 13 + 5 + 2</code></p>
  
  <p>However, the theorem also implies that any integer (also &lt;= 0) has a unique decomposition as a sum of distinct, non-consecutive negaFibonacci numbers, that is the sequence</p>
  
  <p>0, 1, -1, 2, -3, 5, -8, ...</p>
  
  <p>or F_(-n) = (-1)^(n+1) F_n. Some examples:</p>
  
  <p><code>-4 = - 3 - 1</code></p>
  
  <p><code>4 = 5 + 1</code></p>
  
  <p><code>11 = 13 - 3 + 1</code></p>
  
  <p>Is there a known easy algorithm for decomposing a given integer in this way?</p>