Number Sequences: Fibonacci Variants and Mathematical Patterns

# Standard Fibonacci with memoization
from functools import lru_cache

@lru_cache(None)
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)

# Space-optimized O(1)
def fib_opt(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

# Lucas numbers: L(0)=2, L(1)=1, L(n)=L(n-1)+L(n-2)
def lucas(n):
    a, b = 2, 1
    for _ in range(n):
        a, b = b, a + b
    return a

# Tribonacci: T(0)=0, T(1)=0, T(2)=1
def tribonacci(n):
    a, b, c = 0, 0, 1
    for _ in range(n):
        a, b, c = b, c, a + b + c
    return a

# Pell: P(0)=0, P(1)=1, P(n)=2*P(n-1)+P(n-2)
def pell(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, 2*b + a
    return a

# Sum of geometric series: a*(r^n - 1)/(r-1)
def geo_sum(a, r, n, mod=None):
    if r == 1:
        s = a * n
    else:
        s = a * (r**n - 1) // (r - 1)
    return s % mod if mod else s

# Sum 1^2 + 2^2 + ... + n^2 = n(n+1)(2n+1)/6
def sum_squares(n): return n * (n+1) * (2*n+1) // 6

# Sum 1^3 + ... + n^3 = (n(n+1)/2)^2
def sum_cubes(n): return (n * (n+1) // 2) ** 2

# 509. Fibonacci Number
def fib_lc(n: int) -> int:
    if n <= 1: return n
    a, b = 0, 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b

# 1137. N-th Tribonacci
def tribonacci_lc(n: int) -> int:
    a, b, c = 0, 1, 1
    for _ in range(n):
        a, b, c = b, c, b + c + a
    # Wait — this shifts wrong. Correct:
    pass

def tribonacci_correct(n: int) -> int:
    if n == 0: return 0
    if n <= 2: return 1
    a, b, c = 0, 1, 1
    for _ in range(n - 2):
        a, b, c = b, c, a + b + c
    return c

# 70. Climbing Stairs (Fibonacci)
def climbStairs(n: int) -> int:
    a, b = 1, 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b

#include <bits/stdc++.h>
using namespace std;

// All in O(1) space, O(n) time
long long fibonacci(int n) {
    if (n <= 1) return n;
    long long a = 0, b = 1;
    for (int i = 2; i <= n; i++) { long long c = a+b; a=b; b=c; }
    return b;
}

long long tribonacci(int n) {
    if (n == 0) return 0;
    if (n <= 2) return 1;
    long long a = 0, b = 1, c = 1;
    for (int i = 3; i <= n; i++) { long long d=a+b+c; a=b; b=c; c=d; }
    return c;
}