




'''simple docstring'''


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






def 		_lowerCAmelCase							(   lowercase							: str					,  lowercase							: Tuple					,  lowercase							: Optional[int]					,  lowercase							: List[str]    )			->List[str]:
   """simple docstring"""




   lowercase__       							=							sum(a_i[j] for j in range(_lowerCAmelCase					,  len(_lowerCAmelCase    )    )    )
   lowercase__       							=							sum(a_i[j] * base[j] for j in range(min(len(_lowerCAmelCase    )					,  _lowerCAmelCase    )    )    )

   lowercase__       							=							0, 0
   lowercase__       							=							n - i

   lowercase__       							=							memo.get(_lowerCAmelCase    )

   if sub_memo is not None:
      lowercase__       							=							sub_memo.get(_lowerCAmelCase    )

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

         if max_jump >= 0:
            lowercase__       							=							jumps[max_jump]
            # since the difference between jumps is cached, add c
            lowercase__       							=							diff + c
            for j in range(min(_lowerCAmelCase					,  len(_lowerCAmelCase    )    )    ):
               lowercase__       							=							divmod(_lowerCAmelCase					,  1_0    )
            if new_c > 0:
               add(_lowerCAmelCase					,  _lowerCAmelCase					,  _lowerCAmelCase    )

      else:
         lowercase__       							=							[]
   else:
      lowercase__       							=							{c: []}
      lowercase__       							=							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__       							=							next_term(_lowerCAmelCase					,  k - 1					,  i + dn					,  _lowerCAmelCase    )
         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__       							=							compute(_lowerCAmelCase					,  _lowerCAmelCase					,  i + dn					,  _lowerCAmelCase    )
      diff += _diff
      dn += terms_jumped

   lowercase__       							=							sub_memo[c]

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

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






def 		_lowerCAmelCase							(   lowercase							: str					,  lowercase							: str					,  lowercase							: Tuple					,  lowercase							: List[Any]    )			->List[Any]:
   """simple docstring"""




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

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

   while i < n:
      i += 1
      lowercase__       							=							ds_c + ds_b
      diff += addend
      lowercase__       							=							0
      for j in range(_lowerCAmelCase    ):
         lowercase__       							=							a_i[j] + addend
         lowercase__       							=							divmod(_lowerCAmelCase					,  1_0    )

         ds_c += a_i[j]

      if addend > 0:
         break

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






def 		_lowerCAmelCase							(   lowercase							: Tuple					,  lowercase							: Optional[int]					,  lowercase							: List[Any]    )			->List[str]:
   """simple docstring"""




   for j in range(_lowerCAmelCase					,  len(_lowerCAmelCase    )    ):
      lowercase__       							=							digits[j] + addend
      if s >= 1_0:
         lowercase__       							=							divmod(_lowerCAmelCase					,  1_0    )
         lowercase__       							=							addend // 1_0 + quotient
      else:
         lowercase__       							=							s
         lowercase__       							=							addend // 1_0

      if addend == 0:
         break

   while addend > 0:
      lowercase__       							=							divmod(_lowerCAmelCase					,  1_0    )
      digits.append(_lowerCAmelCase    )






def 		_lowerCAmelCase							(   lowercase							: str = 1_0**1_5    )			->int:
   """simple docstring"""




   lowercase__       							=							[1]
   lowercase__       							=							1
   lowercase__       							=							0
   while True:
      lowercase__       							=							next_term(_lowerCAmelCase					,  2_0					,  i + dn					,  _lowerCAmelCase    )
      dn += terms_jumped
      if dn == n - i:
         break

   lowercase__       							=							0
   for j in range(len(_lowerCAmelCase    )    ):
      a_n += digits[j] * 1_0**j
   return a_n


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











import numpy as np
import qiskit



def 						A_							(	_lowerCAmelCase = 8				,  _lowerCAmelCase = None	)		->					str:
 UpperCamelCase      :   Tuple			      =  np.random.default_rng(seed=_lowerCAmelCase	)

 # Roughly 25% of the qubits will contribute to the key.
 # So we take more than we need.
 UpperCamelCase      :   List[str]			      =  6 * key_len
 # Measurement basis for Alice's qubits.
 UpperCamelCase      :   List[Any]			      =  rng.integers(2				,  size=_lowerCAmelCase	)
 # The set of states Alice will prepare.
 UpperCamelCase      :   List[Any]			      =  rng.integers(2				,  size=_lowerCAmelCase	)
 # Measurement basis for Bob's qubits.
 UpperCamelCase      :   Optional[int]			      =  rng.integers(2				,  size=_lowerCAmelCase	)

 # Quantum Circuit to simulate BB84
 UpperCamelCase      :   List[Any]			      =  qiskit.QuantumCircuit(_lowerCAmelCase				,  name="BB84"	)

 # Alice prepares her qubits according to rules above.
 for index, _ in enumerate(_lowerCAmelCase	):
  if alice_state[index] == 1:
   bbaa_circ.x(_lowerCAmelCase	)
  if alice_basis[index] == 1:
   bbaa_circ.h(_lowerCAmelCase	)
 bbaa_circ.barrier()

 # Bob measures the received qubits according to rules above.
 for index, _ in enumerate(_lowerCAmelCase	):
  if bob_basis[index] == 1:
   bbaa_circ.h(_lowerCAmelCase	)

 bbaa_circ.barrier()
 bbaa_circ.measure_all()

 # Simulate the quantum circuit.
 UpperCamelCase      :   Union[str, Any]			      =  qiskit.Aer.get_backend("aer_simulator"	)
 # We only need to run one shot because the key is unique.
 # Multiple shots will produce the same key.
 UpperCamelCase      :   Tuple			      =  qiskit.execute(_lowerCAmelCase				,  _lowerCAmelCase				,  shots=1				,  seed_simulator=_lowerCAmelCase	)
 # Returns the result of measurement.
 UpperCamelCase      :   Optional[Any]			      =  job.result().get_counts(_lowerCAmelCase	).most_frequent()

 # Extracting the generated key from the simulation results.
 # Only keep measurement results where Alice and Bob chose the same basis.
 UpperCamelCase      :   Tuple			      =  "".join(
     [
         result_bit
         for alice_basis_bit, bob_basis_bit, result_bit in zip(
             _lowerCAmelCase				,  _lowerCAmelCase				,  _lowerCAmelCase	)
         if alice_basis_bit == bob_basis_bit
     ]	)

 # Get final key. Pad with 0 if too short, otherwise truncate.
 UpperCamelCase      :   Tuple			      =  gen_key[:key_len] if len(_lowerCAmelCase	) >= key_len else gen_key.ljust(_lowerCAmelCase				,  "0"	)
 return key


if __name__ == "__main__":
    print(f"""The generated key is : {bbaa(8, seed=0)}""")
    from doctest import testmod

    testmod()
