





import functools
from math import sqrt
from time import time





def    _lowercase    (  _UpperCAmelCase	,					*_UpperCAmelCase	,					**_UpperCAmelCase )  ->     str:
				lowerCamelCase		       =time()
				lowerCamelCase		       =func(*_UpperCAmelCase	,					**_UpperCAmelCase )
				lowerCamelCase		       =time()
				if int(end - start ) > 0:
								print(F"""{func.__name__} runtime: {(end - start):0.4f} s""" )
				else:
								print(F"""{func.__name__} runtime: {(end - start) * 10_00:0.4f} ms""" )
				return output





def    _lowercase    (  _UpperCAmelCase )  ->     list[int]:
				if n < 0:
								raise Exception("""n is negative""" )
				if n == 0:
								return [0]
				lowerCamelCase		       =[0, 1]
				for _ in range(n - 1 ):
								fib.append(fib[-1] + fib[-2] )
				return fib





def    _lowercase    (  _UpperCAmelCase )  ->     list[int]:

				def fib_recursive_term(_UpperCAmelCase ) -> int:
								if i < 0:
												raise Exception("""n is negative""" )
								if i < 2:
												return i
								return fib_recursive_term(i - 1 ) + fib_recursive_term(i - 2 )

				if n < 0:
								raise Exception("""n is negative""" )
				return [fib_recursive_term(_UpperCAmelCase ) for i in range(n + 1 )]





def    _lowercase    (  _UpperCAmelCase )  ->     list[int]:

				@functools.cache
				def fib_recursive_term(_UpperCAmelCase ) -> int:
								if i < 0:
												raise Exception("""n is negative""" )
								if i < 2:
												return i
								return fib_recursive_term(i - 1 ) + fib_recursive_term(i - 2 )

				if n < 0:
								raise Exception("""n is negative""" )
				return [fib_recursive_term(_UpperCAmelCase ) for i in range(n + 1 )]





def    _lowercase    (  _UpperCAmelCase )  ->     list[int]:
				if n < 0:
								raise Exception("""n is negative""" )
				# Cache must be outside recursuive function
				# other it will reset every time it calls itself.
				lowerCamelCase		       ={0: 0, 1: 1, 2: 1}  # Prefilled cache

				def rec_fn_memoized(_UpperCAmelCase ) -> int:
								if num in cache:
												return cache[num]

								lowerCamelCase		       =rec_fn_memoized(num - 1 ) + rec_fn_memoized(num - 2 )
								lowerCamelCase		       =value
								return value

				return [rec_fn_memoized(_UpperCAmelCase ) for i in range(n + 1 )]





def    _lowercase    (  _UpperCAmelCase )  ->     list[int]:
				if n < 0:
								raise Exception("""n is negative""" )
				if n >= 14_75:
								raise Exception("""n is too large""" )
				lowerCamelCase		       =sqrt(5 )
				lowerCamelCase		       =(1 + sqrt_a) / 2
				return [round(phi**i / sqrt_a ) for i in range(n + 1 )]


if __name__ == "__main__":
							UpperCAmelCase__  :	Any     =30
							time_func(fib_iterative, num)
							time_func(fib_recursive, num)  # Around 3s runtime
							time_func(fib_recursive_cached, num)  # Around 0ms runtime
							time_func(fib_memoization, num)
							time_func(fib_binet, num)












def    _lowercase    (  _UpperCAmelCase = 99_80_01 )  ->     int:

				# fetches the next number
				for number in range(n - 1	,					99_99	,					-1 ):
								lowerCamelCase		       =str(_UpperCAmelCase )

								# checks whether 'str_number' is a palindrome.
								if str_number == str_number[::-1]:
												lowerCamelCase		       =9_99

												# if 'number' is a product of two 3-digit numbers
												# then number is the answer otherwise fetch next number.
												while divisor != 99:
																if (number % divisor == 0) and (len(str(number // divisor ) ) == 3.0):
																				return number
																divisor -= 1
				raise ValueError("""That number is larger than our acceptable range.""" )


if __name__ == "__main__":
							print(F"{solution() = }")





