





"""simple docstring"""
import math

def 		_SCREAMING_SNAKE_CASE			(_UpperCAmelCase					:    int			):

 if not isinstance(_UpperCAmelCase  ,     _UpperCAmelCase			):
  lowerCAmelCase    				= F'Input value of [number={number}] must be an integer'
  raise TypeError(_UpperCAmelCase			)

 if number < 1:
  lowerCAmelCase    				= F'Input value of [number={number}] must be > 0'
  raise ValueError(_UpperCAmelCase			)
 elif number == 1:
  return 3
 elif number == 2:
  return 5
 else:
  lowerCAmelCase    				= int(math.log(number // 3  ,     2			)			) + 2

  lowerCAmelCase    				= [3, 5]
  lowerCAmelCase    				= 2
  lowerCAmelCase    				= 3
  for block in range(1  ,     _UpperCAmelCase			):
   for _ in range(_UpperCAmelCase			):
    proth_list.append(2 ** (block + 1) + proth_list[proth_index - 1]			)
    proth_index += 1
   increment *= 2

 return proth_list[number - 1]


if __name__ == "__main__":
       import doctest

       doctest.testmod()

       for number in range(11):
              __UpperCamelCase     :						Optional[int]						       =  0
              try:
                     __UpperCamelCase     :						List[str]						       =  proth(number)
              except ValueError:
                     print(f'''ValueError: there is no {number}th Proth number''')
                     continue

              print(f'''The {number}th Proth number: {value}''')













'''simple docstring'''







from __future__ import annotations





def 		_UpperCAmelCase (				__A				: str    ,		__A				: str   ):
				a_		:	int									=   get_failure_array(__A   )

				# 2) Step through text searching for pattern
				a_					,      a_		:	Any									=   0, 0  # index into text, pattern
				while i < len(__A   ):
								if pattern[j] == text[i]:
												if j == (len(__A   ) - 1):
																return True
												j += 1

								# if this is a prefix in our pattern
								# just go back far enough to continue
								elif j > 0:
												a_		:	Any									=   failure[j - 1]
												continue
								i += 1
				return False





def 		_UpperCAmelCase (				__A				: str   ):
				a_		:	Optional[Any]									=   [0]
				a_		:	Any									=   0
				a_		:	int									=   1
				while j < len(__A   ):
								if pattern[i] == pattern[j]:
												i += 1
								elif i > 0:
												a_		:	List[Any]									=   failure[i - 1]
												continue
								j += 1
								failure.append(__A   )
				return failure


if __name__ == "__main__":
		# Test 1)
		__lowerCAmelCase									=   'abc1abc12'
		__lowerCAmelCase									=   'alskfjaldsabc1abc1abc12k23adsfabcabc'
		__lowerCAmelCase									=   'alskfjaldsk23adsfabcabc'
		assert kmp(pattern, texta) and not kmp(pattern, texta)

		# Test 2)
		__lowerCAmelCase									=   'ABABX'
		__lowerCAmelCase									=   'ABABZABABYABABX'
		assert kmp(pattern, text)

		# Test 3)
		__lowerCAmelCase									=   'AAAB'
		__lowerCAmelCase									=   'ABAAAAAB'
		assert kmp(pattern, text)

		# Test 4)
		__lowerCAmelCase									=   'abcdabcy'
		__lowerCAmelCase									=   'abcxabcdabxabcdabcdabcy'
		assert kmp(pattern, text)

		# Test 5)
		__lowerCAmelCase									=   'aabaabaaa'
		assert get_failure_array(pattern) == [0, 1, 0, 1, 2, 3, 4, 5, 2]




