






def     a__  (	UpperCAmelCase							:    int    )						->		int:
  if not isinstance(UpperCAmelCase       ,				UpperCAmelCase    ):
    raise TypeError('''recursive_lucas_number accepts only integer arguments.'''    )
  if n_th_number == 0:
    return 2
  if n_th_number == 1:
    return 1

  return recursive_lucas_number(n_th_number - 1    ) + recursive_lucas_number(
      n_th_number - 2    )

def     a__  (	UpperCAmelCase							:    int    )						->		int:
  if not isinstance(UpperCAmelCase       ,				UpperCAmelCase    ):
    raise TypeError('''dynamic_lucas_number accepts only integer arguments.'''    )
  UpperCAmelCase :							List[str]								=				2, 1
  for _ in range(UpperCAmelCase    ):
    UpperCAmelCase :							Dict								=				b, a + b
  return a


if __name__ == "__main__":
     from doctest import testmod

     testmod()
     _lowerCamelCase       :     Any           =							int(input("Enter the number of terms in lucas series:\n").strip())
     print("Using recursive function to calculate lucas series:")
     print(" ".join(str(recursive_lucas_number(i)) for i in range(n)))
     print("\nUsing dynamic function to calculate lucas series:")
     print(" ".join(str(dynamic_lucas_number(i)) for i in range(n)))








from functools import lru_cache

@lru_cache
def     a__  (	UpperCAmelCase							:    int    )						->		int:
  if not isinstance(UpperCAmelCase       ,				UpperCAmelCase    ):
    raise TypeError('''k must be an integer.'''    )
  if k < 0:
    raise ValueError('''k integer must be greater or equal to zero.'''    )
  if k == 0:
    return 0
  elif k == 1:
    return 1
  else:
    return fibonacci(k - 1    ) + fibonacci(k - 2    )

def     a__  (	UpperCAmelCase							:    list       ,				UpperCAmelCase							:    int    )						->		int:
  UpperCAmelCase :							List[str]								=				len(UpperCAmelCase    )
  # Find m such that F_m >= n where F_i is the i_th fibonacci number.
  UpperCAmelCase :							Any								=				0
  while True:
    if fibonacci(UpperCAmelCase    ) >= len_list:
      UpperCAmelCase :							Optional[Any]								=				i
      break
    i += 1
  UpperCAmelCase :							List[Any]								=				0
  while fibb_k > 0:
    UpperCAmelCase :							List[str]								=				min(
        offset + fibonacci(fibb_k - 1    )       ,				len_list - 1    )  # Prevent out of range
    UpperCAmelCase :							Optional[Any]								=				arr[index_k]
    if item_k_1 == val:
      return index_k
    elif val < item_k_1:
      fibb_k -= 1
    elif val > item_k_1:
      offset += fibonacci(fibb_k - 1    )
      fibb_k -= 2
  else:
    return -1


if __name__ == "__main__":
     import doctest

     doctest.testmod()





