Chapter 3: Numerical Programs
Fibonacci, Lucas, and Mathematical Sequences in Python
Welcome to Numerical Programs!
Get ready to explore the magical world of mathematical sequences!
Note
Definition of Numerical Programs: Computer programs which are designed to solve complex mathematical problems. Here, we use methods such as numerical approximation for situations where the computation impossible or impractical to complete.
What You Will Learn Today
📚 Learning Objectives
By the end of this session, you will be able to:
Understand Mathematical Sequences - Recognize and describe patterns in Fibonacci, Lucas, Tribonacci, Collatz, Factorial, and Prime Number sequences
Implement Multiple Approaches - Write recursive, iterative, memoized, and formula-based solutions for sequence generation
Analyze Algorithm Efficiency - Compare time and space complexity of different implementation strategies and understand trade-offs
Visualize Sequence Growth - Use interactive tools to explore how sequences behave and grow over time
Apply Problem-Solving Skills - Tackle real-world challenges using numerical programming techniques and algorithmic thinking
From elegant mathematics to efficient code - let’s explore the beauty of sequences! ✨
Did You Say Numerical Programs?
Note
So, like, what does numerical coding look like with, you-know-like, Python?!
Why Numerical Programs?
Numerical programs teach us fundamental programming concepts while solving real mathematical problems!
Note
What you’ll learn:
- Multiple approaches: Recursion, iteration, formulas, and more
- Efficiency matters: Some methods are faster than others
- Beautiful patterns: Mathematics meets programming
- Problem-solving: Different tools for different situations
“The Fibonacci sequence appears everywhere in nature - from sunflower seeds to galaxy spirals!” 🌻
The Fibonacci Sequence in Nature
Important
Good Articles on Fibonacci and Sunflowers
- The nature of design: the Fibonacci sequence and the Golden Ratio
- Fibonacci and sunflowers
The Fibonacci Sequence
The Fibonacci sequence is a series where each number is the sum of the two preceding ones.
Note
The Pattern:
- Start with: 0, 1
- Each next number = sum of previous two
- Sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …
- Formula: F(n) = F(n-1) + F(n-2)
Named after Leonardo Fibonacci (c. 1170-1250), who introduced it to Western mathematics through rabbit breeding problems! 🐰
Fibonacci: The Recursive Way
The most intuitive approach - directly follows the mathematical definition!
Fibonacci: Recursive Implementation
Complete the recursive approach:
Recursive Fibonacci: The Problem
Warning
Warning: Exponential Time Complexity!
The recursive approach recalculates the same values over and over:
- F(5) calls F(4) and F(3)
- F(4) calls F(3) and F(2)
- F(3) is calculated TWICE already!
Computing F(40) recursively makes ~331 million function calls! ⏰
Note
Time Complexity: O(2^n) - doubles with each increase in n!
Space Complexity: O(n) - call stack depth
Fibonacci: The Iterative Way
Much faster! Build from the bottom up instead of top down.
Fibonacci: Iterative Implementation
Complete the iterative approach:
Iterative Fibonacci: The Advantage
Tip
Much Better Performance!
The iterative approach calculates each Fibonacci number exactly once:
- Linear time instead of exponential
- Minimal memory usage (just two variables!)
- Can easily compute F(100) or even F(1000)
Computing F(1000) takes milliseconds iteratively vs. forever recursively! 🚀
Note
Time Complexity: O(n) - linear with n
Space Complexity: O(1) - constant space
Fibonacci: Memoization (Part 1)
Cache previous results to avoid having to rerun the calculations!
"""
Memoized Fibonacci - combines elegance with efficiency!
"""
def fibonacci_memo(n, memo={}):
"""
Calculate the nth Fibonacci number using memoization.
Args:
n: Position in sequence
memo: Dictionary to cache results
Returns:
The nth Fibonacci number
"""
# Check if already calculated
if n in memo:
return memo[n]Fibonacci: Memoization (Part 2)
Complete the implementation and testing.
Memoization: Best of Both Worlds
Tip
Smart Caching = Speed!
Memoization stores calculated values:
- Each Fibonacci number calculated exactly once
- Recursive elegance with iterative speed
- Great for problems with overlapping subproblems
Pros: - Clear, readable code - Fast performance - Automatic caching
Cons: - Uses extra memory for cache - Still has recursion overhead - Need to manage memo dictionary
Note
Time Complexity: O(n) - each value computed once
Space Complexity: O(n) - stores n values in memo
Fibonacci: Binet’s Formula (Part 1)
A direct mathematical formula - no loops or recursion needed!
Fibonacci: Binet’s Formula (Part 2)
Complete the implementation:
Binet’s Formula: The Golden Ratio Connection
Tip
φ (phi) - The Golden Ratio ≈ 1.618
The Fibonacci sequence is intimately connected to the golden ratio!
\[F(n) = \frac{\phi^n - \psi^n}{\sqrt{5}}\]
where \(\phi = \frac{1 + \sqrt{5}}{2}\) and \(\psi = \frac{1 - \sqrt{5}}{2}\)
Note
Time Complexity: O(1) - constant time!
Space Complexity: O(1) - constant space
Caveat: Floating-point errors for very large n (but works great for reasonable values!)
This formula can compute F(n) instantly, no matter how large n is! ⚡
Fibonacci: Matrix Method (Part 1)
Another mathematical approach using matrix exponentiation! (Learn more at https://ianthehenry.com/posts/fibonacci/)
"""
Matrix method - fast for very large n using exponentiation!
"""
def multiply_matrices(a, b):
"""Multiply two 2x2 matrices."""
return [
[a[0][0]*b[0][0] + a[0][1]*b[1][0], a[0][0]*b[0][1] + a[0][1]*b[1][1]],
[a[1][0]*b[0][0] + a[1][1]*b[1][0], a[1][0]*b[0][1] + a[1][1]*b[1][1]]
]
def matrix_power(matrix, n):
"""Raise matrix to power n using fast exponentiation."""
if n == 1:
return matrix
if n % 2 == 0:
half = matrix_power(matrix, n // 2)
return multiply_matrices(half, half) # Continued from previous slide
else:
return multiply_matrices(matrix, matrix_power(matrix, n - 1))
Fibonacci: Matrix Method (Part 2)
Complete the implementation with the main Fibonacci function.
Comparing Fibonacci Methods
Important
Which Method Should You Choose?
| Method | Time | Space | Best For |
|---|---|---|---|
| Recursive | O(2^n) | O(n) | 🐌 Learning only! |
| Iterative | O(n) | O(1) | 🚀 General use |
| Memoization | O(n) | O(n) | 💡 Many lookups |
| Binet’s Formula | O(1) | O(1) | ⚡ Small-medium n |
| Matrix Power | O(log n) | O(log n) | 🏆 Very large n |
For most practical purposes, iterative is your best friend! 🎯
Fibonacci: Interactive Visualization
Watch the exponential growth - each term builds on the previous two! 📈
The Lucas Sequence
What is the Lucas Sequence?
Similar to Fibonacci, but starts with 2 and 1 instead of 0 and 1!
Note
The Pattern:
- Start with: 2, 1
- Each next number = sum of previous two (same rule as Fibonacci!)
- Sequence: 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, …
- Formula: L(n) = L(n-1) + L(n-2)
Named after François Édouard Anatole Lucas (1842-1891), who studied number sequences!
Tip
Fun Fact: Lucas numbers are related to Fibonacci numbers by the formula:
\(L(n) = F(n-1) + F(n+1)\)
Lucas Sequence: Implementation (Part 1)
We can use the same techniques as Fibonacci!
Lucas Sequence: Implementation (Part 2)
Complete the implementation:
# Start with first two Lucas numbers
prev, current = 2, 1
# Build up to nth number
for _ in range(2, n + 1):
prev, current = current, prev + current
return current
# Generate first 15 Lucas numbers
lucas_seq = [lucas_iterative(i) for i in range(15)]
print(lucas_seq)
# Output: [2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843]Lucas: Recursive with Memoization (Part 1)
Lucas: Recursive with Memoization (Part 2)
Complete the implementation:
# Base cases
if n == 0:
return 2
elif n == 1:
return 1
# Calculate and store
memo[n] = lucas_memo(n - 1, memo) + lucas_memo(n - 2, memo)
return memo[n]
# Calculate some Lucas numbers
for i in [10, 20, 30, 40]:
print(f"L({i}) = {lucas_memo(i)}")
# Output: L(10)=123, L(20)=15127, L(30)=1860498, L(40)=228826127Relationship Between Fibonacci and Lucas
Tip
They’re Mathematical Cousins!
Several beautiful relationships exist:
"""
Exploring Fibonacci and Lucas relationships.
"""
def show_relationship(n):
"""Show relationship between Fibonacci and Lucas numbers."""
fib_prev = fibonacci_iterative(n - 1) if n > 0 else 0
fib_n = fibonacci_iterative(n)
fib_next = fibonacci_iterative(n + 1)
lucas_n = lucas_iterative(n)
print(f"n = {n}")
print(f"F({n-1}) + F({n+1}) = {fib_prev} + {fib_next} = {fib_prev + fib_next}")
print(f"L({n}) = {lucas_n}")
print(f"Match: {fib_prev + fib_next == lucas_n}\n")Testing the Relationship
Mathematics is full of beautiful patterns like this! ✨
Other Interesting Sequences
The Tribonacci Sequence
Like Fibonacci, but each number is the sum of the THREE preceding ones!
Note
The Pattern:
- Start with: 0, 0, 1
- Each next number = sum of previous THREE
- Sequence: 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, …
- Formula: T(n) = T(n-1) + T(n-2) + T(n-3)
Tribonacci: Implementation
"""
Tribonacci sequence - sum of three previous numbers!
"""
def tribonacci(n):
"""Calculate nth Tribonacci number."""
if n <= 1:
return 0
elif n == 2:
return 1
a, b, c = 0, 0, 1
for _ in range(3, n + 1):
a, b, c = b, c, a + b + c
return c
# Generate sequence
trib_seq = [tribonacci(i) for i in range(15)]
print(trib_seq)
# Output: [0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927]Tribonacci: Interactive Visualization
Summing three terms instead of two makes the sequence grow even faster! 🚀
The Padovan Sequence
A unique sequence with a spiral geometric interpretation!
Note
The Pattern:
- Start with: 1, 1, 1
- Formula: P(n) = P(n-2) + P(n-3)
- Sequence: 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, …
Named after Richard Padovan who discovered it in 1994!
Padovan: Implementation
"""
Padovan sequence - appears in spiral triangles!
"""
def padovan(n):
"""Calculate nth Padovan number."""
if n <= 2:
return 1
a, b, c = 1, 1, 1
for _ in range(3, n + 1):
a, b, c = b, c, a + b
return c
# Generate sequence
pad_seq = [padovan(i) for i in range(15)]
print(pad_seq)
# Output: [1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37]The Pell Sequence
Closely related to the Pythagorean approximation of √2!
Note
The Pattern:
- Start with: 0, 1
- Formula: P(n) = 2·P(n-1) + P(n-2)
- Sequence: 0, 1, 2, 5, 12, 29, 70, 169, 408, 985, …
Pell numbers approximate √2 when you divide consecutive terms!
Pell: Implementation
"""
Pell sequence - doubles the previous term then adds one before!
"""
def pell(n):
"""Calculate nth Pell number."""
if n <= 0:
return 0
elif n == 1:
return 1
prev, current = 0, 1
for _ in range(2, n + 1):
prev, current = current, 2 * current + prev
return current
# Generate sequence
pell_seq = [pell(i) for i in range(12)]
print(pell_seq)
# Output: [0, 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, 5741]The Collatz Sequence (3n+1 Problem)
Tip
One of Mathematics’ Greatest Unsolved Mysteries!
The Collatz conjecture is a deceptively simple problem that has stumped mathematicians for decades!
Note
The Rules:
- Start with any positive integer n
- If n is even: divide by 2 → n = n / 2
- If n is odd: multiply by 3 and add 1 → n = 3n + 1
- Repeat until you reach 1
Named after Lothar Collatz (1910-1990), who proposed it in 1937!
The Collatz Conjecture
Warning
The Unsolved Mystery:
The conjecture states that no matter what positive integer you start with, you will always eventually reach 1.
- Tested for numbers up to 2^68 ≈ 295 quintillion!
- No counterexample has ever been found
- Yet no one has proven it works for ALL numbers
- Mathematicians have tried for over 85 years!
Paul Erdős said: “Mathematics may not be ready for such problems.” 🤔
Tip
Why is it so hard?
- The sequence seems chaotic and unpredictable
- Some numbers take very long paths to reach 1
- No clear pattern emerges from studying examples
Collatz: Basic Implementation
"""
Collatz sequence - does every number reach 1?
"""
def collatz(n):
"""
Generate Collatz sequence starting from n.
Returns list of numbers until reaching 1.
"""
sequence = [n]
while n != 1:
n = n // 2 if n % 2 == 0 else 3 * n + 1
sequence.append(n)
return sequence
# Example: Starting from 6
print(collatz(6))
# Output: [6, 3, 10, 5, 16, 8, 4, 2, 1]Notice how the sequence goes up and down unpredictably!
Collatz: Interactive Version
Let’s create a more user-friendly version!
"""
Interactive Collatz sequence generator.
"""
def collatz(n):
sequence = [n]
while n != 1:
n = n // 2 if n % 2 == 0 else 3 * n + 1
sequence.append(n)
return sequence
def main():
num = int(input("Enter a seed to generate the Collatz sequence: "))
print("Collatz sequence:", collatz(num))
print(f"Length of sequence: {len(collatz(num))}")
# Define a section of code that runs only when the Python
# file is executed as a standalone script (at command line)
# if __name__ == "__main__":
# main()Try different numbers and see how long it takes to reach 1! 🎯
Collatz: Examples and Patterns
Output:
Starting from 5:
Sequence: [5, 16, 8, 4, 2, 1]
Length: 6
Max value reached: 16
Starting from 12:
Sequence: [12, 6, 3, 10, 5, 16, 8, 4, 2, 1]
Length: 10
Max value reached: 16
Starting from 27:
Sequence: [27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, ...]
Length: 112
Max value reached: 9232Notice how 27 reaches a maximum of 9232 - much higher than where it started! 📈
Collatz: Analyzing Stopping Times
The stopping time is how many steps it takes to reach 1.
"""
Find which number has the longest Collatz sequence.
"""
def collatz_analysis(max_start):
"""
Analyze Collatz sequences for numbers 1 to max_start.
"""
longest_sequence = 0
longest_start = 0
for i in range(1, max_start + 1):
seq = collatz(i)
if len(seq) > longest_sequence:
longest_sequence = len(seq)
longest_start = i
print(f"Longest sequence up to {max_start}:")
print(f"Starting number: {longest_start}")
print(f"Sequence length: {longest_sequence}")
# Show the sequence
seq = collatz(longest_start)
print(f"First 20 steps: {seq[:20]}...")
collatz_analysis(100)Collatz: Interesting Facts
Note
Fascinating Observations:
- Unpredictable lengths: Small numbers can have long sequences
- 27 takes 111 steps to reach 1
- But 26 only takes 10 steps!
- Maximum heights: Sequences often climb before falling
- Starting at 27 reaches 9232 (342× larger!)
- Starting at 703 reaches 250,504
- Even/odd pattern: Sequences alternate between even and odd
- After an odd number: always even (3n+1 makes it even)
- After an even number: could be either
The sequence seems to have a mind of its own! 🎢
Collatz: Interactive Visualization
Watch how the sequence climbs and falls - each number tells a different story! 📊
Collatz: Why It Matters
Important
Beyond the Problem:
The Collatz conjecture teaches us important lessons:
For Mathematics:
- Sometimes simple questions have complex answers
- Computational testing ≠ proof
- Pattern recognition has limits
- Beauty in unsolved problems
For Programming:
- Testing algorithms thoroughly
- Handling edge cases
- Data visualization
- Understanding complexity
“Computational experiments can suggest patterns, but only mathematics can prove them true for all numbers!”
No one knows if there’s a number that never reaches 1! 🔍
The Factorial Sequence
Not recursive sums, but products! Essential for combinatorics.
Note
The Pattern:
- n! = n × (n-1) × (n-2) × … × 2 × 1
- 0! = 1 (by definition)
- Sequence: 1, 1, 2, 6, 24, 120, 720, 5040, 40320, …
- Grows VERY fast!
Factorial: Implementation
"""
Factorial - both recursive and iterative versions.
"""
def factorial_iterative(n):
"""Calculate n! using iteration."""
if n <= 1:
return 1
result = 1
for i in range(2, n + 1):
result *= i
return result
def factorial_recursive(n):
"""Calculate n! using recursion."""
if n <= 1:
return 1
return n * factorial_recursive(n - 1)
# Compare both methods
for i in range(8):
print(f"{i}! = {factorial_iterative(i)}")
# Output: 0!=1, 1!=1, 2!=2, 3!=6, 4!=24, 5!=120, 6!=720, 7!=5040Factorial: Interactive Visualization
Logarithmic scale used for visualization - factorials grow EXTREMELY fast! 🚀
Prime Number Sequence
The building blocks of all natural numbers!
Note
What are Primes?
- Numbers greater than 1 divisible only by 1 and themselves
- Sequence: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, …
- Infinite in quantity but no simple formula to generate them!
Prime Numbers: Sieve of Eratosthenes
def sieve_of_eratosthenes(n):
"""
Find all prime numbers up to n using the Sieve of Eratosthenes algorithm.
Args:
n: Upper limit (inclusive) to find primes
Returns:
List of all prime numbers up to n
"""
# Create a boolean array "is_prime[0..n]" and initialize all entries as true
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False # 0 and 1 are not prime
# Start with the smallest prime number, 2
p = 2
while p * p <= n:
# If is_prime[p] is not changed, then it's a prime
if is_prime[p]:
# Mark all multiples of p as not prime
for i in range(p * p, n + 1, p):
is_prime[i] = False
p += 1
# Return list of primes
return [num for num, prime in enumerate(is_prime) if prime]
# Testing
primes = sieve_of_eratosthenes(100)
print(f"Primes up to 100: {primes}")
# Output: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, ...]Prime Numbers: Interactive Visualization
Notice the distribution by the density bars - prime numbers become less frequent as they get larger! 🔢
Challenge Exercises
Time to test your understanding!
Can you solve these numerical programming challenges? 🎯
Challenge 1: Fibonacci Sum
Write a function that calculates the sum of all Fibonacci numbers up to and including the nth Fibonacci number.
Tip
Hint: You can use any method to generate Fibonacci numbers, then sum them. Or think about a direct formula!
Try both iterative and mathematical approaches!
Challenge 2: Even Fibonacci Numbers
Find the sum of all even-valued Fibonacci numbers that do not exceed a given limit.
Tip
Hint: Generate Fibonacci numbers one by one, check if even, and add to sum. Stop when you exceed the limit!
Pattern observation: Every third Fibonacci number is even!
Challenge 3: Generalized Sequence
Write a function that takes two starting numbers and generates n terms of a Fibonacci-like sequence.
Tip
Hint: Your function should work for ANY two starting numbers, not just specific sequences!
This tests your ability to generalize patterns!
Challenge 4: Collatz Stopping Time
Find which number from 1 to n has the longest Collatz sequence (takes most steps to reach 1).
Tip
Hint: Test each number from 1 to n, calculate its Collatz sequence length, and track the maximum!
Some small numbers take surprisingly long journeys!
Challenge 5: Fibonacci Index Finder
Write a function that finds the index (position) of a given number in the Fibonacci sequence. Return -1 if not found.
Tip
Hint: Generate Fibonacci numbers until you find the target or exceed it. You could also use Binet’s formula in reverse!
Bonus: Can you do this without generating the entire sequence?
Solutions to Challenges
Let’s see multiple approaches to each problem!
Remember: There’s often more than one way to solve a problem! 💡
Solution 1: Fibonacci Sum (Approach 1)
"""
Solution 1.1: Direct approach - generate and sum.
"""
def fibonacci_sum_direct(n):
"""
Calculate sum of first n+1 Fibonacci numbers.
Simple and straightforward approach.
"""
if n < 0: return 0
total = 0
a, b = 0, 1 # F(0), F(1)
total += a # Add F(0)
# Generate and add remaining Fibonacci numbers
for i in range(n):
total += b
a, b = b, a + b
return total
# Testing
print(f"Sum of F(0) to F(5): {fibonacci_sum_direct(5)}") # Output: Sum of F(0) to F(5): 12
print(f"Sum of F(0) to F(10): {fibonacci_sum_direct(10)}") # Output: Sum of F(0) to F(10): 143Time Complexity: O(n) - generates each number once
Space Complexity: O(1) - only uses a few variables
Solution 1: Fibonacci Sum (Approach 2)
"""
Solution 1.2: Mathematical approach using formula.
"""
def fibonacci_sum_formula(n):
"""
Use the formula: Sum of F(0) to F(n) = F(n+2) - 1
"""
if n < 0: return 0
# Calculate F(n+2)
if n + 2 <= 1: return n + 2
a, b = 0, 1
for _ in range(n + 1):
a, b = b, a + b
# Sum is F(n+2) - 1
return b - 1
# Testing
print(f"Sum of F(0) to F(5): {fibonacci_sum_formula(5)}") # Output: Sum of F(0) to F(5): 12
print(f"Sum of F(0) to F(10): {fibonacci_sum_formula(10)}") # Output: Sum of F(0) to F(10): 143Time Complexity: O(n) - still generates up to F(n+2)
Space Complexity: O(1) - constant space
The mathematical insight makes the solution elegant! ✨
Solution 2: Even Fibonacci (Part 1)
Solution 2: Even Fibonacci (Part 2)
Test the function with different limits.
# Testing
print(f"Sum of even Fibonacci ≤ 100: {even_fibonacci_sum(100)}")
# Output: Sum of even Fibonacci ≤ 100: 44
print(f"Sum of even Fibonacci ≤ 1000: {even_fibonacci_sum(1000)}")
# Output: Sum of even Fibonacci ≤ 1000: 798
print(f"Sum of even Fibonacci ≤ 4000000: {even_fibonacci_sum(4000000)}")
# Output: Sum of even Fibonacci ≤ 4000000: 4613732Time Complexity: O(log limit) - Fibonacci grows exponentially
Space Complexity: O(1) - constant space
Solution 2: Even Fibonacci Numbers (Approach 2)
"""
Solution 2.2: Optimized - every 3rd Fibonacci is even!
"""
def even_fibonacci_sum_optimized(limit):
"""
Use pattern: every 3rd Fibonacci number is even.
Start with F(2)=2 and skip directly to next even ones.
"""
total = 0
# Start with first two numbers where third will be even
a, b = 1, 2 # F(1)=1, F(2)=2
while b <= limit:
total += b # b is always even in this loop
# Jump to next even Fibonacci: F(n+3) = 4*F(n) + F(n-3)
# Or simply: generate 3 steps
a, b = b, a + b
a, b = b, a + b
a, b = b, a + b
return total
# Testing
print(f"Sum of even Fib ≤ 100: {even_fibonacci_sum_optimized(100)}") # Fib ≤ 100: 44
print(f"Sum of even Fib ≤ 4000000: {even_fibonacci_sum_optimized(4000000)}") # Fib ≤ 4000000: 4613732Time Complexity: O(log limit / 3) - 3x fewer iterations!
Space Complexity: O(1) - constant space
Recognizing patterns makes code faster! 🚀
Solution 3: Generalized Sequence (Part 1)
"""
Solution 3.1: Simple iterative approach.
"""
def generalized_sequence(start1, start2, n):
"""
Generate n terms of a Fibonacci-like sequence.
Args:
start1: First number in sequence
start2: Second number in sequence
n: Number of terms to generate
Returns:
List of n terms
"""
if n <= 0:
return []
elif n == 1:
return [start1]Solution 3: Generalized Sequence (Part 2)
Complete the implementation and testing.
elif n == 2:
return [start1, start2]
sequence = [start1, start2]
for _ in range(2, n):
next_term = sequence[-1] + sequence[-2]
sequence.append(next_term)
return sequence
# Test with different starting values
print("Lucas:", generalized_sequence(2, 1, 10))
print("Fibonacci:", generalized_sequence(0, 1, 10))
print("Custom:", generalized_sequence(5, 5, 10))Solution 3: Generator Approach (Part 1)
"""
Solution 3.2: Generator approach for memory efficiency.
"""
def generalized_sequence_generator(start1, start2, n):
"""
Generate n terms using a generator (memory efficient).
Useful when you need to process terms one at a time
or for very long sequences.
"""
if n <= 0:
return
yield start1
if n == 1:
returnSolution 3: Generator Approach (Part 2)
Complete the generator and testing.
Generators are perfect for large sequences or streaming data! 🌊
Solution 4: Collatz Stopping Time (Part 1)
First, let’s create a helper function to calculate sequence length.
"""
Solution 4.1: Straightforward approach - Part 1
"""
def collatz_length(n):
"""Calculate length of Collatz sequence starting from n."""
length = 0
while n != 1:
if n % 2 == 0:
n = n // 2
else:
n = 3 * n + 1
length += 1
return length
# Test the helper function
print(f"Length of sequence from 6: {collatz_length(6)}")
# Output: Length of sequence from 6: 8
print(f"Length of sequence from 27: {collatz_length(27)}")
# Output: Length of sequence from 27: 111Solution 4: Collatz Stopping Time (Part 2)
Now use the helper to find the longest sequence.
"""
Solution 4.1: Straightforward approach - Part 2
"""
def longest_collatz(max_n):
"""
Find number with longest Collatz sequence up to max_n.
Returns: tuple of (number, sequence_length)
"""
max_length = 0
max_number = 0
for i in range(1, max_n + 1):
length = collatz_length(i)
if length > max_length:
max_length = length
max_number = i
return (max_number, max_length)
# Testing
result = longest_collatz(20)
print(f"Up to 20: number {result[0]} has sequence length {result[1]}")
# Output: Up to 20: number 18 has sequence length 20
result = longest_collatz(100)
print(f"Up to 100: number {result[0]} has sequence length {result[1]}")
# Output: Up to 100: number 97 has sequence length 118Solution 4: Memoization Approach (Part 1)
Using memoization (or the use of pre-calculated results which may be necessary for use later) to cache results for better performance.
"""
Solution 4.2: Optimized with memoization - Part 1
"""
def longest_collatz_memo(max_n):
"""
Find longest Collatz sequence using memoization.
Cache previously calculated lengths for efficiency.
"""
memo = {1: 0} # Base case: reaching 1 takes 0 more steps
def collatz_length_memo(n):
"""Calculate length with memoization."""
if n in memo:
return memo[n]
if n % 2 == 0:
length = 1 + collatz_length_memo(n // 2)
else:
length = 1 + collatz_length_memo(3 * n + 1)
memo[n] = length
return lengthSolution 4: Memoization Approach (Part 2)
Complete the implementation and testing
"""
Solution 4.2: Optimized with memoization - Part 2
"""
# Continue from previous slide...
max_length = 0
max_number = 0
for i in range(1, max_n + 1):
length = collatz_length_memo(i)
if length > max_length:
max_length = length
max_number = i
return (max_number, max_length)
# Testing
result = longest_collatz_memo(1000)
print(f"Up to 1000: number {result[0]} has sequence length {result[1]}")
# Output: Up to 1000: number 871 has sequence length 178
result = longest_collatz_memo(10000)
print(f"Up to 10000: number {result[0]} has sequence length {result[1]}")
# Much faster than the non-memoized version!Memoization can dramatically speed up repeated calculations! ⚡
Solution 5: Fibonacci Index Finder (Approach 1)
"""
Solution 5.1: Sequential search approach.
"""
def fibonacci_index(target):
"""
Find the index of target in Fibonacci sequence.
Returns index if found, -1 otherwise.
"""
if target < 0:
return -1
if target == 0:
return 0
index = 1
a, b = 0, 1
while b < target:
a, b = b, a + b
index += 1
# Check if we found it
if b == target:
return index
else:
return -1Solution 5: Fibonacci Index Finder (Approach 1 continued)
"""
Solution 5.1: Sequential search approach.
"""
# Testing
test_values = [0, 1, 2, 5, 13, 21, 100, 144, 150]
for val in test_values:
idx = fibonacci_index(val)
if idx != -1:
print(f"F({idx}) = {val}")
else:
print(f"{val} is not a Fibonacci number")
# Output shows which values are Fibonacci numbers and their indicesSolution 5: Fibonacci Index Finder (Approach 2)
"""
Solution 5.2: Using inverse Binet's formula (mathematical approach).
"""
import math
def fibonacci_index_binet(target):
"""
Find Fibonacci index using inverse Binet's formula.
Uses the golden ratio to calculate index directly.
"""
if target < 0: return -1
if target == 0: return 0
# Golden ratio
phi = (1 + math.sqrt(5)) / 2
# Inverse Binet's formula
# If target = F(n), then n ≈ log_phi(target * sqrt(5) + 0.5)
n = math.log(target * math.sqrt(5) + 0.5) / math.log(phi)
n = round(n)
# Verify by calculating F(n)
psi = (1 - math.sqrt(5)) / 2
fib_n = round((phi**n - psi**n) / math.sqrt(5))
if fib_n == target: return n
else: return -1Mathematics provides elegant shortcuts! 🎓
Solution 5: Fibonacci Index Finder (Approach 2, continued)
Mathematics provides elegant shortcuts! 🎓
Summary
Tip
What We Learned:
- Fibonacci: Multiple implementation strategies (recursion, iteration, memoization, formulas)
- Lucas Numbers: Related to Fibonacci with different starting values
- Other Sequences: Tribonacci, Padovan, Pell, Collatz, and more!
- Efficiency Matters: Different approaches have different time/space complexities
- Pattern Recognition: Mathematical insights can simplify problems
Note
Key Takeaways:
- Iterative approaches are usually most practical
- Memoization combines elegance with efficiency
- Mathematical formulas can provide O(1) solutions
- Pattern recognition is a valuable skill
Keep Exploring!
Tip
Next Steps:
- Implement other famous sequences (Catalan numbers, Bell numbers)
- Explore dynamic programming techniques
- Study the mathematics behind these sequences
- Try optimizing for very large numbers (using big integers)
- Investigate how these sequences appear in nature!
Mathematics and programming together create beautiful solutions! ✨