Rosetta Code

Zeckendorf number representation

Represent integers as sums of non-consecutive Fibonacci numbers using Zeckendorf's theorem.

Edit the source, then Run. Checks start after your first Run. Ctrl/⌘ + Enter runs; Tab indents. Preview services use sample data and never contact a real service.

Sourcerosettacode/popular/zeckendorf_number_representation.vibe
def fibonacci_up_to(limit: int) -> array<int>
  fibs = [1, 2]
  while fibs.fetch(fibs.length - 1) < limit
    next_fib = fibs.fetch(fibs.length - 1) + fibs.fetch(fibs.length - 2)
    fibs.push(next_fib)
  end
  fibs
end

def zeckendorf(n: int) -> array<int>
  if n == 0
    return [0]
  end

  fibs = fibonacci_up_to(n)
  remaining = n
  parts: array<int> = []

  i = fibs.length - 1
  while i >= 0
    if fibs.fetch(i) <= remaining
      parts.push(fibs.fetch(i))
      remaining = remaining - fibs.fetch(i)
    end
    i = i - 1
  end

  parts
end

def run -> array<{ n: int, zeckendorf: string }>
  results: array<{ n: int, zeckendorf: string }> = []
  n = 1
  while n <= 20
    parts = zeckendorf(n)
    label = ""
    j = 0
    while j < parts.length
      if j > 0
        label = label + " + "
      end
      label = label + parts.fetch(j).to_s
      j = j + 1
    end
    results.push({ n: n, zeckendorf: label })
    n = n + 1
  end
  results
end

Output

Click Run example to see the result.

Code checks

Run once to load the checker. Your code stays in this browser.