Find fibonachicken number

fibonachicken.py

# Copyright (c) 2014, Younggun Kim
#
# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
#
# The above copyright notice and this permission notice shall be included in
# all copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
# THE SOFTWARE.

# Find fibonachicken number which is ideal # of chicken box for N people.
# Ref. : https://www.facebook.com/560898400668463/posts/737548943003407
# Web  : http://fibonachicken.herokuapp.com/
# Author: [email protected]

import math
from functools import lru_cache

IMPLEMENTATION_LIMIT = 1346269

def is_perfect_sqrt(n):
    s = int(math.sqrt(n))
    return s*s == n

# Gessel formula
@lru_cache(maxsize=IMPLEMENTATION_LIMIT)
def is_fibonacci(n):
    return is_perfect_sqrt(5*n*n + 4) or is_perfect_sqrt(5*n*n - 4)

PHI = 1.618032786885246 # 987/610 Approximation
# it returns f(n+1)
def next_fibonacci(fib):
    # http://en.wikipedia.org/wiki/Golden_ratio#Relationship_to_Fibonacci_sequence
    if not is_fibonacci(fib): raise ValueError("{} is not a fibonacci number.".format(fib))

    if fib > 1: return round(fib*PHI)
    else: return 1 #raise ValueError("It works only if fib > 1")

# NOTE: This would not work for all 'fib' number.
# Only work if fib is less than 1346269.
# But this value is high enough for fibonachicken(), I'll go with this.
# If someone knows better solution with O(1) complexity,
# please let me know your solution. It would be really appreciated. :)
def prev_fibonacci(fib):
    if fib >= IMPLEMENTATION_LIMIT: raise NotImplementedError("Too high! fib < 1346269")
    if not is_fibonacci(fib): raise ValueError("{} is not a fibonacci number.".format(fib))

    if fib > 2: return round(fib/PHI)
    else: return 1 #raise ValueError("It works only if fib > 2")

def closest_fibonacci(n):
    for i in range(n-1, 0, -1):
        if is_fibonacci(i):
            return i

# find fibonachicken!
@lru_cache(maxsize=IMPLEMENTATION_LIMIT)
def fibonachicken(n):
    chickens = 0
    while(n > 0):
        try:
            chickens += prev_fibonacci(n)
            n -= n
        except ValueError:
            # Oops! non-fibonacci like people out there!
            # Use Zeckendorf's theorem.
            # http://en.wikipedia.org/wiki/Zeckendorf%27s_theorem
            cfib = closest_fibonacci(n)
            chickens += prev_fibonacci(cfib)
            n -= cfib
        except NotImplementedError:
            chickens += fibonachicken(IMPLEMENTATION_LIMIT-1)
            n -= IMPLEMENTATION_LIMIT-1

    return chickens

## Test prev_fibonacci()
#for fib in range(10000000, 0, -1):
#    if is_fibonacci(fib):
#        try: assert is_fibonacci(prev_fibonacci(fib))
#        except: print(fib, prev_fibonacci(fib))
#

# it could be represented by 13+2.
# So sum up each fibonachicken(13), fibonachicken(2) would be 9.