# Arup Guha
# 2/15/2025
# Recursion Examples

import random

# Returns the nth Fibonacci Number
def fib(n):

    # These are small cases, just directly return the answer.
    if n < 2:
        return n

    # Otherwise this is the formula we use.
    return fib(n-1) + fib(n-2)

# Returns n factorial.
def fact(n):

    # 0! = 1! = 1
    if n <= 1:
        return 1

    # Usual recursive breakdown.
    return n*fact(n-1)

# Returns True if and only if the value val is in the sorted array
# arr[low..high]
def binsearch(arr, low, high, val):

    # No search space.
    if low > high:
        return False

    # Halfway in between my search space.
    mid = (low+high)//2

    # Our value is on the left side.
    if val < arr[mid]:
        return binsearch(arr, low, mid-1, val)
    
    # Value is on right side.
    elif val > arr[mid]:
        return binsearch(arr, mid+1, high, val)

    # Found it.
    else:
        return True

def testbinsearch():

    # Create random array.
    vals = []
    for i in range(10):
        vals.append(random.randint(1, 1000))
    # Sort it.
    vals.sort()

    # Print so we can see whats in the array.
    print(vals)

    # Get value to search for.
    x = int(input("What value do you want to search for?\n"))

    # Print result of search.
    if binsearch(vals, 0, len(vals)-1, x):
        print("We found it.")
    else:
        print("It's not in the array.")

# Prints out a transcript of moves to solve the Towers of Hanoi with n disks from
# tower start to tower end. start and end are 2 integers from the set {1,2,3}
def towers(n, start, end):

    # Base case no work.
    if n < 1:
        return

    # My temporary tower.
    mid = 6- start - end

    # Move all disks but the bottom to temp tower.
    towers(n-1, start, mid)
    print("Moving disk",n,"from tower",start,"to tower",end)
    towers(n-1, mid, end)

def fastmodexpo(base, exp, mod):

    # Assuming mod > 1.
    if exp == 0:
        return 1
    
    # Even exponent, let's split in half.
    if exp%2 == 0:
        tmp = fastmodexpo(base, exp//2, mod)
        return (tmp*tmp)%mod

    # Just the regular breakdown.
    tmp = fastmodexpo(base, exp-1, mod)
    return (tmp*base)%mod

# Returns a inverse mod p, provided that p is prime and a is not a multiple of p.
def modinvprime(a, p):
    return fastmodexpo(a, p-2, p)

a = 67
ainv = modinvprime(a, 101)
print(a,ainv,(a*ainv)%101)