import numpy as np
import matplotlib.pyplot as plt
from scipy.interpolate import splev, splrep
from decimal import Decimal

sequence = [
1, 3, 7, 8, 21, 49, 76, 224, 467, 514, 1155, 2683, 5216, 10544, 26867, 51510, 95823, 198669, 357535, 863317, 1811764, 3007503, 5598802, 14428676, 33185509, 54538862, 111949941, 227634408, 400708894, 1033162084, 2102388551, 3093472814, 7137437912, 14133072157, 20112871792, 42387769980, 100251560595, 146971536592, 323724968937, 1003651412950, 1458252205147, 2895374552463, 7409811047825, 15404761757071, 19996463086597, 51408670348612, 119666659114170, 191206974700443, 409118905032525, 611140496167764, 2058769515153876, 4216495639600700, 6763683971478124, 9974455244496707, 30045390491869460, 44218742292676575, 138245758910846492, 199976667976342049, 525070384258266191, 1135041350219496382, 1425787542618654982, 3908372542507822062, 8993229949524469768, 17799667357578236628
]

x_values_known = np.arange(len(sequence))
sequence_decimal = [Decimal(value) for value in sequence]
spline_rep = splrep(x_values_known, sequence_decimal, k=2)
extended_x_values = np.arange(len(sequence) + 1)
predicted_next_number = splev(extended_x_values[-1], spline_rep)
predicted_next_number_hex = hex(int(predicted_next_number))
plt.plot(x_values_known, sequence_decimal, label='sequence')
plt.plot(
    extended_x_values,
    splev(extended_x_values, spline_rep),
    label='Recreated Sequence',
    linestyle='dashed'
)
plt.scatter(
    extended_x_values[-1],
    float(predicted_next_number),
    color='red',
    marker='o',
    label='Predicted Next Number'
)
plt.legend()
plt.xlabel('Index')
plt.ylabel('Value')
plt.title('Original vs. Recreated sequence with Prediction')
plt.show()
print(f"Next key: {predicted_next_number}")
print(f"Hexadecimal: {predicted_next_number_hex}")