import math
from difflib import SequenceMatcher

# === User Adjustable Variables ===
MIN_N = 72523715257       # Minimum value of n to search
SEARCH_RANGE = 100000     # The range of offsets around each approximation to search
PRECISION_SCALE = 1e15    # Scale factor for capturing decimal precision in base-36
MAX_TERMS = 200           # Number of terms in the continued fraction expansion
SIMILARITY_THRESHOLD = 0.8  # Minimum similarity (0-1) to report a near miss
# =================================

# Function to convert a number to a base-36 string
def to_base36(num):
    chars = "0123456789abcdefghijklmnopqrstuvwxyz"
    if num < 0:
        return "-" + to_base36(-num)
    if num == 0:
        return "0"
    base36 = []
    while num > 0:
        base36.append(chars[num % 36])
        num //= 36
    return "".join(reversed(base36))

# Function to compute the continued fraction expansion of a number
def continued_fraction_expansion(x, max_terms):
    terms = []
    for _ in range(max_terms):
        int_part = int(x)
        terms.append(int_part)
        frac_part = x - int_part
        if frac_part == 0:
            break
        x = 1 / frac_part
    return terms

# Function to compute rational approximations from continued fraction terms
def rational_approximations(cf_terms):
    approximations = []
    p0, p1 = 1, cf_terms[0]
    q0, q1 = 0, 1
    approximations.append((p1, q1))
    
    for term in cf_terms[1:]:
        p2 = term * p1 + p0
        q2 = term * q1 + q0
        approximations.append((p2, q2))
        p0, p1 = p1, p2
        q0, q1 = q1, q2
    
    return approximations

# Base-36 target string
target_prefix = "merry.christmas"

# Convert target base-36 string to decimal value
def base36_to_decimal(base36_str):
    chars = "0123456789abcdefghijklmnopqrstuvwxyz"
    int_part, _, frac_part = base36_str.partition(".")
    
    # Integer part conversion
    int_value = sum(chars.index(c) * (36 ** i) for i, c in enumerate(reversed(int_part)))
    
    # Fractional part conversion
    frac_value = sum(chars.index(c) * (36 ** -(i + 1)) for i, c in enumerate(frac_part))
    
    return int_value + frac_value

# Decimal value of "merry.christmas"
base36_value = base36_to_decimal(target_prefix)

# Compute continued fraction expansion and rational approximations
cf_terms = continued_fraction_expansion(base36_value, max_terms=MAX_TERMS)
rational_approximations_list = rational_approximations(cf_terms)

# Function to compute similarity between two strings
def similarity(a, b):
    return SequenceMatcher(None, a, b).ratio()

# Function to check if the base-36 representation of tan(n) starts with target prefix
def check_prefix_of_tan(n, target_prefix):
    try:
        tan_value = math.tan(n)
        base36_tan = to_base36(int(abs(tan_value) * PRECISION_SCALE))  # Scale for precision
        exact_match = base36_tan.startswith(target_prefix.replace(".", ""))
        return exact_match, base36_tan
    except ValueError:
        return False, None

# Extended search for a solution
found_n = None
near_misses = []  # Store near misses for analysis
for p, q in rational_approximations_list:
    # Compute n from arctan(p/q)
    angle_radians = math.atan(p / q)
    angle_degrees = math.degrees(angle_radians)  # Convert to degrees
    n = round(angle_degrees)  # Round to nearest integer

    # Adjust for large minimum n
    n = max(n, MIN_N)

    # Test a range of values around n for periodicity
    for offset in range(-SEARCH_RANGE, SEARCH_RANGE + 1):  # Search within range
        test_n = n + offset
        is_match, base36_tan = check_prefix_of_tan(test_n, target_prefix)
        if is_match:
            found_n = test_n
            break
        elif base36_tan:  # Check for near misses
            sim_score = similarity(base36_tan, target_prefix.replace(".", ""))
            if sim_score >= SIMILARITY_THRESHOLD:
                near_misses.append((test_n, base36_tan, sim_score))
    if found_n:
        break

# Output results
if found_n:
    print("Found n:", found_n)
else:
    print("No exact match found.")
    print("Near misses:")
    for miss in sorted(near_misses, key=lambda x: -x[2]):  # Sort by similarity score
        print(f"n={miss[0]}, base-36={miss[1]}, similarity={miss[2]:.2f}")