




"""simple docstring"""




a_        =       range(2, 2_0 + 1)
a_        =       [1_0**k for k in range(ks[-1] + 1)]
a_        =       {}







def      __UpperCAmelCase     ( __UpperCamelCase	,				__UpperCamelCase	,				__UpperCamelCase	,				__UpperCamelCase	):
			__lowercase			:  Tuple								=       sum(a_i[j] for j in range(_snake_case	,				len(_snake_case	)	)	)
			__lowercase			:  Optional[Any]								=       sum(a_i[j] * base[j] for j in range(min(len(_snake_case	)	,				_snake_case	)	)	)

			__lowercase			,__lowercase			:  List[Any]								=       0, 0
			__lowercase			:  int								=       n - i

			__lowercase			:  List[Any]								=       memo.get(_snake_case	)

			if sub_memo is not None:
						__lowercase			:  Any								=       sub_memo.get(_snake_case	)

						if jumps is not None and len(_snake_case	) > 0:
									# find and make the largest jump without going over
									__lowercase			:  Union[str, Any]								=       -1
									for _k in range(len(_snake_case	) - 1	,				-1	,				-1	):
												if jumps[_k][2] <= k and jumps[_k][1] <= max_dn:
															__lowercase			:  str								=       _k
															break

									if max_jump >= 0:
												__lowercase			,__lowercase			,__lowercase			:  Union[str, Any]								=       jumps[max_jump]
												# since the difference between jumps is cached, add c
												__lowercase			:  Any								=       diff + c
												for j in range(min(_snake_case	,				len(_snake_case	)	)	):
															__lowercase			,__lowercase			:  str								=       divmod(_snake_case	,				10	)
												if new_c > 0:
															add(_snake_case	,				_snake_case	,				_snake_case	)

						else:
									__lowercase			:  Any								=       []
			else:
						__lowercase			:  Tuple								=       {c: []}
						__lowercase			:  Union[str, Any]								=       sub_memo

			if dn >= max_dn or c + diff >= base[k]:
						return diff, dn

			if k > ks[0]:
						while True:
									# keep doing smaller jumps
									__lowercase			,__lowercase			:  Dict								=       next_term(_snake_case	,				k - 1	,				i + dn	,				_snake_case	)
									diff += _diff
									dn += terms_jumped

									if dn >= max_dn or c + diff >= base[k]:
												break
			else:
						# would be too small a jump, just compute sequential terms instead
						__lowercase			,__lowercase			:  Optional[Any]								=       compute(_snake_case	,				_snake_case	,				i + dn	,				_snake_case	)
						diff += _diff
						dn += terms_jumped

			__lowercase			:  Optional[int]								=       sub_memo[c]

			# keep jumps sorted by # of terms skipped
			__lowercase			:  Tuple								=       0
			while j < len(_snake_case	):
						if jumps[j][1] > dn:
									break
						j += 1

			# cache the jump for this value digitsum(b) and c
			sub_memo[c].insert(_snake_case	,				(diff, dn, k)	)
			return (diff, dn)







def      __UpperCAmelCase     ( __UpperCamelCase	,				__UpperCamelCase	,				__UpperCamelCase	,				__UpperCamelCase	):
			if i >= n:
						return 0, i
			if k > len(_snake_case	):
						a_i.extend([0 for _ in range(k - len(_snake_case	)	)]	)

			# note: a_i -> b * 10^k + c
			# ds_b -> digitsum(b)
			# ds_c -> digitsum(c)
			__lowercase			:  Dict								=       i
			__lowercase			,__lowercase			,__lowercase			:  List[str]								=       0, 0, 0
			for j in range(len(_snake_case	)	):
						if j >= k:
									ds_b += a_i[j]
						else:
									ds_c += a_i[j]

			while i < n:
						i += 1
						__lowercase			:  Dict								=       ds_c + ds_b
						diff += addend
						__lowercase			:  str								=       0
						for j in range(_snake_case	):
									__lowercase			:  Optional[Any]								=       a_i[j] + addend
									__lowercase			,__lowercase			:  str								=       divmod(_snake_case	,				10	)

									ds_c += a_i[j]

						if addend > 0:
									break

			if addend > 0:
						add(_snake_case	,				_snake_case	,				_snake_case	)
			return diff, i - start_i







def      __UpperCAmelCase     ( __UpperCamelCase	,				__UpperCamelCase	,				__UpperCamelCase	):
			for j in range(_snake_case	,				len(_snake_case	)	):
						__lowercase			:  Optional[int]								=       digits[j] + addend
						if s >= 10:
									__lowercase			,__lowercase			:  str								=       divmod(_snake_case	,				10	)
									__lowercase			:  int								=       addend // 10 + quotient
						else:
									__lowercase			:  Optional[Any]								=       s
									__lowercase			:  Optional[Any]								=       addend // 10

						if addend == 0:
									break

			while addend > 0:
						__lowercase			,__lowercase			:  List[str]								=       divmod(_snake_case	,				10	)
						digits.append(_snake_case	)







def      __UpperCAmelCase     ( __UpperCamelCase = 10**15	):
			__lowercase			:  int								=       [1]
			__lowercase			:  Optional[Any]								=       1
			__lowercase			:  str								=       0
			while True:
						__lowercase			,__lowercase			:  Union[str, Any]								=       next_term(_snake_case	,				20	,				i + dn	,				_snake_case	)
						dn += terms_jumped
						if dn == n - i:
									break

			__lowercase			:  Optional[Any]								=       0
			for j in range(len(_snake_case	)	):
						a_n += digits[j] * 10**j
			return a_n


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








import math

import numpy as np
import qiskit
from qiskit import Aer, ClassicalRegister, QuantumCircuit, QuantumRegister, execute

def 	SCREAMING_SNAKE_CASE_							(	_snake_case	:int = 3				)  ->     qiskit.result.counts.Counts:
   if isinstance(_snake_case	,   _snake_case				):
      raise TypeError('''number of qubits must be a integer.'''				)
   if number_of_qubits <= 0:
      raise ValueError('''number of qubits must be > 0.'''				)
   if math.floor(_snake_case				) != number_of_qubits:
      raise ValueError('''number of qubits must be exact integer.'''				)
   if number_of_qubits > 10:
      raise ValueError('''number of qubits too large to simulate(>10).'''				)

   _A      =       QuantumRegister(_snake_case	,   '''qr'''				)
   _A      =       ClassicalRegister(_snake_case	,   '''cr'''				)

   _A      =       QuantumCircuit(_snake_case	,   _snake_case				)

   _A      =       number_of_qubits

   for i in range(_snake_case				):
      quantum_circuit.h(number_of_qubits - i - 1				)
      counter -= 1
      for j in range(_snake_case				):
         quantum_circuit.cp(np.pi / 2 ** (counter - j)	,   _snake_case	,   _snake_case				)

   for k in range(number_of_qubits // 2				):
      quantum_circuit.swap(_snake_case	,   number_of_qubits - k - 1				)

   # measure all the qubits
   quantum_circuit.measure(_snake_case	,   _snake_case				)
   # simulate with 10000 shots
   _A      =       Aer.get_backend('''qasm_simulator'''				)
   _A      =       execute(_snake_case	,   _snake_case	,   shots=10_000				)

   return job.result().get_counts(_snake_case				)


if __name__ == "__main__":
   print(
       f'Total count for quantum fourier transform state is: \
    {quantum_fourier_transform(3)}'
   )



