# Zeckendorf Representation of positive integer

Zeckendorf's theorem states that all positive integers can be represented uniquely as the sum of one or more distinct Fibonacci numbers in such a way that the sum does not include any two consecutive Fibonacci numbers.

So given the input 10, the Zeckendorf set would be [8,2].

This is my working code that was for Reddit's dailyprogrammer challenge:

def fib_list(max_num):
x=3     #starting at 3 because we have [1,1] in list already.
list_of_fib = [1,1]
while x < max_num:
x = list_of_fib[-1] + list_of_fib[-2]
list_of_fib.append(x)
return list_of_fib

def find_num_smaller(num, my_list):
for value in reversed(my_list):
if value <= num:
return value

def solve(num):
combo_list = []
list_to_pick_from = fib_list(num)
while num > 0:
temp_value = find_num_smaller(num,list_to_pick_from)
num -= temp_value
combo_list.append(temp_value)
print(combo_list)

solve(10)



Running it through timeit.timeit I get about 0.069 seconds with the input of 1234. Medium size input of 123456789 yields about 0.22 seconds and a large size input of 123456789123456789123456789 yields 1.3 seconds. Is there any way to speed it up? Or make it more acceptable at a "higher standard" (whatever this means, I guess some would call it 'Pythonic' but I'm not sure the correct term)? Maybe there is there some better practice I can employ here.

I have thought of turning Solve() into a generator and just getting all the combo values out, but I'm not sure if that's faster.

I know that if I were to run it multiple times, I would check if the input is within the already generated fib_list, and if it isn't I would generate a new one. But that's another question, I just want to see one input.

Let's continue from Graipher's code, sans documentation for brevity:

def fib(max_num):
n_1, n = 0, 1
while n < max_num:
yield n
n_1, n = n, n + n_1

def find_num_smaller(num, my_list):
for value in reversed(my_list):
if value <= num:
return value

def solve(num):
l = list(fib(num))
while num > 0:
temp_value = find_num_smaller(num, l)
num -= temp_value
yield temp_value


What's the slowest part here? solve consists of

l = list(fib(num))
while num > 0:
temp_value = find_num_smaller(num, l)
num -= temp_value
yield temp_value


l = list(fib(num)) is slow, but only runs once. num -= temp_value and yield temp_value are relatively quick, and run once per iteration. find_num_smaller(num, l), however, can take a long time and runs once per iteration.

This is because we're doing Shlemiel the painter's algorithm:

Shlemiel gets a job as a street painter, painting the dotted lines down the middle of the road. On the first day he takes a can of paint out to the road and finishes 300 yards of the road. "That's pretty good!" says his boss, "you're a fast worker!" and pays him a kopeck.

The next day Shlemiel only gets 150 yards done. "Well, that's not nearly as good as yesterday, but you're still a fast worker. 150 yards is respectable," and pays him a kopeck.

The next day Shlemiel paints 30 yards of the road. "Only 30!" shouts his boss. "That's unacceptable! On the first day you did ten times that much work! What's going on?"

"I can't help it," says Shlemiel. "Every day I get farther and farther away from the paint can!"

There are some quick fixes. Firstly, we can try binary search. Python has a fast implementation in the bisect library. But even better is to "move" the paint can as we go along:

while my_list[-1] > num:
my_list.pop()
return my_list[-1]


This can only do as many pops as there are elements in my_list, so all the calls added together can't be much slower than generating the list in the first place. The resulting code is much faster; for n = 10 ** 5000 it went from 2.6s to 0.026s, a 100x improvement.

There's also a bug! fib_list should be while x <= max_num; else solve(some_fibonacci_number) will include two consecutive numbers (eg. solve(5) → 3, 2 instead of 5).

There are some other minor style points:

temp_value, solve and my_list are terrible names, and fib_list and find_num_smaller are poor. Most variables are temporary, so temp_variable tells you nothing in a lot of space. solve could refer to solving any problem. my_list is silly - obviously it's "your" list and you don't even care if it's a list - you just want a sequence.

There are other improvements, too. Instead of fib giving a bounded iterator, produce an unbounded iterator and call take_while.

If find_num_smaller took a reversed iterator directly, it could be

def find_num_smaller(num, nums):
for value in nums:
if value <= num:
return value


since iterators automatically "pop" read values. You can even inline this by iterating over a filter:

def solve(num):
fibs = list(takewhile(lambda x: x <= num, gen_fibs()))
next_fibs = (x for x in reversed(fibs) if x <= num)

for next_fib in next_fibs:
num -= next_fib
yield next_fib


which then suggests inlining the loop:

def solve(num):
fibs = list(takewhile(lambda x: x <= num, gen_fibs()))

for fib in reversed(fibs):
if fib <= num:
num -= fib
yield fib


Then one might wonder if you can run fibs in reverse, and avoid generating a list. Yes, you can:

while True:
yield next
prior, next = next - prior, prior


So all you need to do is skip forward and iterate backwards:

def gen_fibs_reverse(limit):
prior, next = 0, 1

while next <= limit:
prior, next = next, next + prior

while prior:
yield prior
prior, next = next - prior, prior

def zeckendorf_decomposition(num):
fibs = gen_fibs_reverse(num)

for fib in fibs:
if fib <= num:
num -= fib
yield fib


First some general review:

1. You should use a if __name__ == "__main__": guard around the test run to allow importing of your code from another module.

2. You should add docstrings to your functions to explain what they do. Docstrings are of the format:

def f(x, y):
"""Returns the sum of x and y"""
return x + y


As you already mentioned, here is a way to use generators. This has two draw-backs compared to your code:

1. In find_num_smaller we have to iterate forwards (you cannot iterate backwards through an iterator, at least not without converting it to a list first).

2. We need to re-generate the generator every loop, because it will be partially exhausted

def fib(max_num):
"""
Yields the fibonacci sequence until the last element smaller than max_num
"""
n_1, n = 0, 1
while n < max_num:
yield n
n_1, n = n, n + n_1

def find_num_smaller(num, my_list):
"""
Iterates through an iterator until the value in the iterator is larger than num.
Returns the value before that.
"""
last_value = next(my_list)
for value in my_list:
if value > num:
return last_value
last_value = value
return last_value

def solve(num):
"""
Description here
"""
x = num
while x > 0:
temp_value = find_num_smaller(x, fib(num))
x -= temp_value
yield temp_value

if __name__ == "__main__":
print list(solve(10))


Note that your fund_num_smaller will return None if all values in my_list are smaller than num. Here I added returning the last element in that case.

However, this actually performs worse than your code (mostly because iterating reversed saves a lot of time and re-doing the fibonacci sequence wastes a lot of cycles).

As an alternative consider this code:

def find_num_smaller(num, my_list):
for value in reversed(my_list):
if value <= num:
return value

def solve(num):
l = list(fib(num))
while num > 0:
temp_value = find_num_smaller(num, l)
num -= temp_value
yield temp_value


Where I used your find_num_smaller and put the fibonacci into a list.

Here is acomparison between the three approaches for the input 123456789123456789123456789123456789123456789123456789 on my machine:

no generator     406 function calls in 0.000 seconds
only generators  10111 function calls in 0.003 seconds
mixed            407 function calls in 0.000 seconds


So using generators here will not give you a speed improvement for most inputs. For the fibonacci numbers it will, however, give you a memory improvement (which will take quite some time to matter).

For really large inputs (like 123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789) there is no improvement visible:

no generator  2947 function calls in 0.017 seconds
mixed         2948 function calls in 0.017 seconds


And for the input 123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789:

no generator  5886 function calls in 0.063 seconds
mixed         5887 function calls in 0.064 seconds


So both approaches seem to scale with the number of digits of the input.

• Generators are usually lazy evaluation so they scale way better. I'm not worry about memory because I don't expect someone to input max(int) value into it, Given that if that were to happen, Generators and your method would beat out mine by a long shot. Food for thoughts, but thanks for your feedback. Oct 7, 2016 at 15:41
• @MooingRawr No, here it doesn't, apparently. The no generator in the timings is your code. Both seem to scale with the number of digits of the input (I tried twice the length of the number in the second timing and both timings just doubled). Oct 7, 2016 at 15:47
• What helps here is that the fibonacci numbers grow really fast. Oct 7, 2016 at 15:48
• right. I forgot to factor in that It's growth is rapid, interesting... Thanks for pointing that out. Oct 7, 2016 at 15:49