Chapter 030 — Number Patterns

# --- Visualization: Fibonacci spiral, Pascal, and sequence families ---
import numpy as np
import matplotlib.pyplot as plt
plt.style.use('seaborn-v0_8-whitegrid')

def fibonacci(n):
    a, b = 0, 1
    result = []
    for _ in range(n):
        result.append(a)
        a, b = b, a + b
    return result

fig, axes = plt.subplots(1, 2, figsize=(13, 5))

# Plot 1: Fibonacci spiral approximation
ax = axes[0]
fibs = fibonacci(12)
x, y = 0, 0
angle = 0
for i, f in enumerate(fibs[1:]):
    t = np.linspace(angle * np.pi/2, (angle + 1) * np.pi/2, 100)
    r = f
    cx = x + r * np.cos(angle * np.pi/2 + np.pi)
    cy = y + r * np.sin(angle * np.pi/2 + np.pi)
    ax.plot(cx + r * np.cos(t), cy + r * np.sin(t), color=plt.cm.viridis(i/12), linewidth=2)
    angle = (angle + 1) % 4
ax.set_aspect('equal')
ax.set_title('Fibonacci Spiral (Approximate)')
ax.set_xlabel('x')
ax.set_ylabel('y')

# Plot 2: Convergence of Fibonacci ratios to golden ratio
ax = axes[1]
fibs_arr = fibonacci(25)
ratios = [fibs_arr[i+1]/fibs_arr[i] for i in range(1, len(fibs_arr)-1)]
phi = (1 + np.sqrt(5)) / 2
ax.plot(range(1, len(ratios)+1), ratios, 'o-', label='F(n+1)/F(n)', color='steelblue')
ax.axhline(phi, color='crimson', linestyle='--', label=f'φ = {phi:.6f}')
ax.set_xlabel('n')
ax.set_ylabel('Ratio')
ax.set_title('Fibonacci Ratios Converge to φ')
ax.legend()

plt.tight_layout()
plt.show()

print(f"First 15 Fibonacci: {fibonacci(15)}")
print(f"Golden ratio φ = {phi:.10f}")

# --- Implementation: Sequence generators and pattern detection ---
import numpy as np

def fibonacci_gen():
    """Infinite Fibonacci generator."""
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

def figurate(s, n):
    """nth s-gonal number. s=3: triangular, s=4: square, s=5: pentagonal."""
    return n * ((s - 2) * n - (s - 4)) // 2

def catalan(n):
    """nth Catalan number: C(n) = C(2n,n)/(n+1). Counts many combinatorial structures."""
    from math import comb
    return comb(2 * n, n) // (n + 1)

def differences(seq):
    """Compute successive differences of a sequence until constant."""
    diffs = [list(seq)]
    while len(set(diffs[-1])) > 1:
        d = diffs[-1]
        diffs.append([d[i+1] - d[i] for i in range(len(d)-1)])
        if len(diffs[-1]) < 2:
            break
    return diffs

# Triangular numbers: differences should become constant
tri = [figurate(3, n) for n in range(1, 10)]
print("Triangular numbers:", tri)
diffs = differences(tri)
print("Differences:")
for i, d in enumerate(diffs):
    print(f"  Level {i}: {d}")

# Catalan numbers
cats = [catalan(n) for n in range(10)]
print(f"\nCatalan numbers: {cats}")

# Binet's formula for Fibonacci
phi = (1 + np.sqrt(5)) / 2
psi = (1 - np.sqrt(5)) / 2
def fib_binet(n):
    """Closed-form Fibonacci via Binet's formula."""
    return round((phi**n - psi**n) / np.sqrt(5))

print("\nBinet formula vs recursive (first 15):")
gen = fibonacci_gen()
for i in range(15):
    actual = next(gen)
    binet = fib_binet(i)
    print(f"  F({i}) = {actual}  (Binet: {binet})  {'✓' if actual == binet else '✗'}")

# --- Experiment: Method of differences to find polynomial formulas ---
# Hypothesis: if kth differences of a sequence are constant, it's a degree-k polynomial
# Try changing: the sequence

import numpy as np

def find_polynomial_degree(seq):
    """Find the degree of polynomial generating a sequence via differences."""
    diffs = list(seq)
    degree = 0
    while len(set(diffs)) > 1 and len(diffs) > 1:
        diffs = [diffs[i+1] - diffs[i] for i in range(len(diffs)-1)]
        degree += 1
        if len(diffs) < 2:
            break
    return degree, diffs[0] if diffs else None

# Test sequences  <-- try modifying these
test_sequences = {
    'Triangular':  [n*(n+1)//2 for n in range(1, 12)],
    'Squares':     [n**2 for n in range(1, 12)],
    'Cubes':       [n**3 for n in range(1, 12)],
    'n^4':         [n**4 for n in range(1, 12)],
    'Fibonacci':   [1,1,2,3,5,8,13,21,34,55,89],
}

for name, seq in test_sequences.items():
    deg, const = find_polynomial_degree(seq)
    print(f"{name:15s}: degree = {deg}, constant diff = {const}")

# --- Mini Project: OEIS Sequence Explorer ---
# Problem: Identify unknown sequences and match them to known patterns.
# Task: Given a list of numbers, detect: arithmetic/geometric/polynomial/Fibonacci-like patterns.

import numpy as np

def analyze_sequence(seq):
    """
    Analyze a sequence and output:
    - Type: arithmetic, geometric, polynomial degree k, Fibonacci-like, or unknown
    - Formula if found
    """
    seq = list(seq)
    n = len(seq)

    # Check arithmetic (1st differences constant)
    d1 = [seq[i+1]-seq[i] for i in range(n-1)]
    if len(set(d1)) == 1:
        return f"Arithmetic: a(n) = {seq[0]} + {d1[0]}*(n-1)"

    # Check geometric (ratios constant)
    ratios = [seq[i+1]/seq[i] for i in range(n-1) if seq[i] != 0]
    if ratios and len(set(round(r, 8) for r in ratios)) == 1:
        return f"Geometric: a(n) = {seq[0]} * {ratios[0]:.4f}^(n-1)"

    # Check polynomial via differences
    diffs = list(seq)
    degree = 0
    while len(set(round(x, 6) for x in diffs)) > 1 and len(diffs) > 1 and degree < 6:
        diffs = [diffs[i+1]-diffs[i] for i in range(len(diffs)-1)]
        degree += 1
    if len(diffs) > 0 and len(set(round(x,4) for x in diffs)) == 1:
        return f"Polynomial degree {degree}"

    # Check Fibonacci-like (a(n) = a(n-1) + a(n-2))
    fib_like = all(abs(seq[i] - seq[i-1] - seq[i-2]) < 1e-6 for i in range(2, n))
    if fib_like:
        return f"Fibonacci-like: a(n) = a(n-1) + a(n-2), starts ({seq[0]}, {seq[1]})"

    return "Unknown pattern"

test_cases = [
    [2, 5, 8, 11, 14, 17],        # arithmetic
    [3, 6, 12, 24, 48, 96],       # geometric
    [1, 4, 9, 16, 25, 36],        # squares
    [1, 8, 27, 64, 125],          # cubes
    [1, 1, 2, 3, 5, 8, 13],      # Fibonacci
    [2, 1, 3, 4, 7, 11, 18],      # Lucas
    [1, 3, 6, 10, 15, 21],        # triangular
]

for seq in test_cases:
    result = analyze_sequence(seq)
    print(f"{str(seq)[:35]:>37}: {result}")