Algorithms¶

This page provides detailed documentation for all the mathematical algorithms implemented in the Lychrel package.

Fibonacci Sequences¶

Generalized Fibonacci Sequences (Lucas Sequences)¶

The Fibonacci sequence is one of the most famous sequences in mathematics. The Lychrel package implements a generalized version called Lucas sequences.

Mathematical Definition¶

A generalized Fibonacci sequence is defined by the recurrence relation:

\[F(n) = p \cdot F(n-1) - q \cdot F(n-2)\]

where \(p\) and \(q\) are integer parameters, with initial conditions:

\[F(0) = 0, \quad F(1) = 1\]

Special Cases¶

By choosing different values of \(p\) and \(q\), we get different famous sequences:

Standard Fibonacci (\(p=1, q=-1\)): \(F(n) = F(n-1) + F(n-2)\)

Sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144...

Lucas Numbers (\(p=1, q=-1\), with \(F(0)=2, F(1)=1\)):

Sequence: 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123...

Pell Numbers (\(p=2, q=-1\)): \(F(n) = 2F(n-1) + F(n-2)\)

Sequence: 0, 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378...

Jacobsthal Numbers (\(p=1, q=-2\)): \(F(n) = F(n-1) + 2F(n-2)\)

Sequence: 0, 1, 1, 3, 5, 11, 21, 43, 85, 171, 341...

Function Reference¶

lychrel.fibonacci(n, p=1, q=-1)

Calculate the n-th term of a generalized Fibonacci sequence.

Parameters:

n (int): The index of the term to calculate (must be >= 0)
p (int, optional): First parameter of the recurrence relation (default: 1)
q (int, optional): Second parameter of the recurrence relation (default: -1)

Returns: int - The n-th term of the sequence

Raises: ValueError if n is negative

Examples¶

import lychrel

# Standard Fibonacci sequence
print(lychrel.fibonacci(10))  # 55
print(lychrel.fibonacci(20))  # 6765

# Pell numbers (p=2, q=-1)
print(lychrel.fibonacci(10, p=2, q=-1))  # 2378

# Jacobsthal numbers (p=1, q=-2)
print(lychrel.fibonacci(10, p=1, q=-2))  # 341

# Custom parameters
for i in range(10):
    print(lychrel.fibonacci(i, p=3, q=-2))

Performance Note¶

The implementation uses an iterative algorithm with O(n) time complexity and O(1) space complexity. Thanks to Rust's BigInt type, it can handle arbitrarily large Fibonacci numbers:

# Calculate very large Fibonacci numbers
print(lychrel.fibonacci(1000))
# Returns a number with 209 digits!

Kaprekar's Routine¶

Kaprekar's Constant¶

Kaprekar's routine is a mathematical algorithm discovered by Indian mathematician D. R. Kaprekar. For 4-digit numbers in base 10, the routine always converges to 6174, known as Kaprekar's constant.

The Algorithm¶

Take any 4-digit number with at least two different digits (e.g., 3524)
Arrange the digits in descending order: 5432
Arrange the digits in ascending order: 2345
Subtract the smaller from the larger: 5432 - 2345 = 3087
Repeat with the result

Example with 3524:

3524 → 5432 - 2345 = 3087
3087 → 8730 - 0378 = 8352
8352 → 8532 - 2358 = 6174
6174 → 7641 - 1467 = 6174  (fixed point!)

Function Reference¶

lychrel.kaprekar(n, base=10, max_iterations=1000)

Apply Kaprekar's routine to a number until reaching a fixed point or cycle.

Parameters:

n (int): The starting number
base (int, optional): The numerical base to use (default: 10)
max_iterations (int, optional): Maximum number of iterations (default: 1000)

Returns: int - The Kaprekar constant or cycle value reached

Raises: ValueError if max_iterations is exceeded or invalid input

Examples¶

import lychrel

# All 4-digit numbers converge to 6174
print(lychrel.kaprekar(1234))  # 6174
print(lychrel.kaprekar(9876))  # 6174
print(lychrel.kaprekar(4680))  # 6174
print(lychrel.kaprekar(3524))  # 6174

# Works with different bases
result = lychrel.kaprekar(1234, base=10)
print(result)

# Control maximum iterations
result = lychrel.kaprekar(1234, max_iterations=100)

Other Kaprekar Constants¶

Different digit lengths have different Kaprekar constants:

3 digits: 495
4 digits: 6174
5 digits: Multiple cycles possible
6 digits: Multiple constants (549945, 631764)

Currently, the function works best with 4-digit numbers in base 10.

Read Out Loud¶

The Look-and-Say Sequence¶

The "Read Out Loud" function implements the famous Look-and-Say sequence (also called the Morris Number Sequence), discovered by mathematician John Conway.

How It Works¶

The sequence is generated by "reading" the digits of the previous number, counting consecutive occurrences of each digit:

1       →  "one 1"               → 11
11      →  "two 1s"              → 21
21      →  "one 2, one 1"        → 1211
1211    →  "one 1, one 2, two 1s" → 111221
111221  →  "three 1s, two 2s, one 1" → 312211

Function Reference¶

lychrel.look_and_say(n)

Generate the next term in the Look-and-Say sequence.

Parameters:

n (int): The current number to "read out loud"

Returns: int - The next number in the sequence

Example: look_and_say(1211) returns 111221 (one 1, one 2, two 1s)

Examples¶

import lychrel

# Basic examples
print(lychrel.look_and_say(1))        # 11
print(lychrel.look_and_say(12))       # 1112
print(lychrel.look_and_say(3211))     # 131221
print(lychrel.look_and_say(2333355))  # 124325

# Generate the Look-and-Say sequence
n = 1
for i in range(10):
    print(f"Step {i}: {n}")
    n = lychrel.look_and_say(n)

# Output:
# Step 0: 1
# Step 1: 11
# Step 2: 21
# Step 3: 1211
# Step 4: 111221
# Step 5: 312211
# Step 6: 13112221
# Step 7: 1113213211
# Step 8: 31131211131221
# Step 9: 13211311123113112211

Interesting Properties¶

The sequence never contains digits greater than 3 (when starting from 1)
The length of each term grows by approximately 30% each step
The sequence is related to the cosmological theorem proved by John Conway
No term in the sequence contains "333" when starting from 1

Collatz Conjecture¶

The 3n+1 Problem¶

The Collatz conjecture is one of the most famous unsolved problems in mathematics. It's also known as the 3n+1 problem, Ulam conjecture, or Hailstone sequence.

The Conjecture¶

Starting with any positive integer \(n\):

If \(n\) is even: divide it by 2 (\(n → n/2\))
If \(n\) is odd: multiply by 3 and add 1 (\(n → 3n+1\))

The conjecture states: No matter what number you start with, you will always eventually reach 1.

Despite being tested for extremely large numbers (up to \(2^{68}\)), no proof exists.

Function Reference¶

lychrel.collatz(n)

Generate the complete Collatz sequence starting from n until reaching 1.

Parameters:

n (int): The starting positive integer (must be > 0)

Returns: list[int] - The complete sequence from n to 1 (inclusive)

Raises: ValueError if n <= 0

Examples¶

import lychrel

# Simple example
sequence = lychrel.collatz(5)
print(sequence)
# [5, 16, 8, 4, 2, 1]

# Longer sequence
sequence = lychrel.collatz(27)
print(len(sequence))  # 111 steps!
print(sequence[:10])  # First 10 terms
# [27, 82, 41, 124, 62, 31, 94, 47, 142, 71]

# Visualize the sequence
for i, n in enumerate(lychrel.collatz(10)):
    print(f"Step {i}: {n}")

# Find stopping time (number of steps to reach 1)
def stopping_time(n):
    return len(lychrel.collatz(n)) - 1

# Find which number < 100 has the longest sequence
max_len = 0
max_n = 0
for n in range(1, 100):
    length = stopping_time(n)
    if length > max_len:
        max_len = length
        max_n = n

print(f"Number with longest sequence: {max_n}")
print(f"Sequence length: {max_len}")
# Number with longest sequence: 97
# Sequence length: 118

Interesting Patterns¶

The number 27 takes 111 steps to reach 1
The highest number reached starting from 27 is 9,232
Some numbers quickly drop to 1, while others take long, chaotic paths
The sequences often reach high peaks before eventually descending to 1

# Find the maximum value reached in the Collatz sequence
def max_in_sequence(n):
    return max(lychrel.collatz(n))

print(max_in_sequence(27))   # 9232
print(max_in_sequence(97))   # 13120
print(max_in_sequence(871))  # 190996

Current Research¶

No counterexample has been found despite extensive computational searches
The problem has been verified for all numbers up to \(2^{68} ≈ 2.95 × 10^{20}\)
Many partial results exist, but a complete proof remains elusive
The problem is easy to state but remarkably difficult to solve