fork download
copy 
  1. import math
  2. from itertools import combinations
  3. Phi = (5 ** 0.5 + 1) / 2
  4. phi = 1 / Phi
  5.  
  6. def get_next_lowest_fib(n, i=2):
  7.     while i <= n:
  8.         yield round((Phi ** i - ((-1 * phi) ** i)) / (5 ** 0.5))
  9.         i += 1
  10.  
  11. def zeckendorf(n):
  12.     fib_index = round((math.log(n) + math.log(5) / 2) / (math.log(Phi)))
  13.     fibs = [i for i in get_next_lowest_fib(fib_index)]
  14.     possibles = []
  15.     for i in range(1, len(fibs) + 1):
  16.         for combo in combinations(fibs, i):
  17.             if sum(combo) == n:
  18.                 possibles.append(combo)
  19.  
  20.     for pcombo in possibles:
  21.         for num in pcombo:
  22.             num_index = fibs.index(num)
  23.             if num_index + 1 < len(fibs):
  24.                 next_num = fibs[num_index + 1]
  25.                 if next_num in pcombo:
  26.                     break
  27.         else:
  28.             return set(pcombo)
  29.  
  30. print([(i, zeckendorf(i)) for i in [120, 34, 88, 90, 320]])
Success #stdin #stdout 0.01s 9992KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
[(120, {8, 89, 2, 21}), (34, {34}), (88, {8, 1, 3, 21, 55}), (90, {1, 89}), (320, {8, 233, 3, 21, 55})]
https://ideone.com/d0RTO9
language:
Python 3 (python  3.12)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!