Number Sequences in Computing

Discover patterns in computing - from powers of 2 to Fibonacci in algorithms, understanding sequences helps predict system behavior and optimize performance.

Powers of 2: The Foundation

The most important sequence in computing is powers of 2, as digital systems are fundamentally binary.

Power 2^n Value Binary Computing Context
2⁰ 1 1 1 Single bit
2¹ 2 2 10 Boolean states
2² 4 4 100 2-bit values
2³ 8 8 1000 Byte (8 bits)
2⁸ 256 256 100000000 Max byte value + 1
2¹⁰ 1,024 1,024 10000000000 1 KiB
2¹⁶ 65,536 65,536 - 16-bit max + 1
2²⁰ 1,048,576 1,048,576 - 1 MiB
2³² 4,294,967,296 4,294,967,296 - 32-bit max + 1
Memory Tip: Learn these key powers by heart: 2¹⁰=1024, 2²⁰=~1M, 2³⁰=~1G, 2³²=~4G

Essential Computing Sequences

1. Mersenne Numbers (2ⁿ - 1)

All bits set in n-bit field

2¹ - 1 = 1    (binary: 1)
2² - 1 = 3    (binary: 11)
2³ - 1 = 7    (binary: 111)
2⁴ - 1 = 15   (binary: 1111)
2⁸ - 1 = 255  (binary: 11111111)

Used in: Bitmasks, maximum values

2. Factorials (n!)

Important in algorithms

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
10! = 3,628,800

Used in: Permutations, complexity analysis

3. Perfect Squares

n² sequence

1² = 1
2² = 4
3² = 9
4² = 16
5² = 25
8² = 64
16² = 256

Used in: Hash tables, quadratic algorithms

4. Triangular Numbers

Sum of first n integers

T(1) = 1
T(2) = 3
T(3) = 6
T(4) = 10
T(5) = 15
T(n) = n(n+1)/2

Used in: Memory allocation, array indexing

Fibonacci Sequence

F(n) = F(n-1) + F(n-2), starting with F(0)=0, F(1)=1

The Sequence
F(0) = 0
F(1) = 1
F(2) = 1
F(3) = 2
F(4) = 3
F(5) = 5
F(6) = 8
F(7) = 13
F(8) = 21
F(9) = 34
F(10) = 55
Computing Applications
  • Fibonacci Heap: Efficient priority queue
  • Fibonacci Search: Division algorithm
  • Golden Ratio: UI design proportions
  • Dynamic Programming: Classic example
  • Recursive Analysis: Worst-case scenarios
Algorithm Insight: Fibonacci demonstrates the difference between naive recursion O(2ⁿ) and dynamic programming O(n).

Geometric Progressions

Sequences where each term is multiplied by a constant ratio.

Exponential Growth (Base > 1)
Powers of 2

1, 2, 4, 8, 16, 32, 64...

Memory sizes, tree levels

Powers of 10

1, 10, 100, 1000, 10000...

Decimal places, scientific notation

Powers of 16

1, 16, 256, 4096...

Hexadecimal place values

Exponential Decay (0 < Base < 1)
Application Sequence Formula Use Case
Binary Search n, n/2, n/4, n/8... n/2ᵏ Search space reduction
Cache Miss Rate 0.5, 0.25, 0.125... (1/2)ᵏ Performance modeling
Network Timeout 1, 0.9, 0.81, 0.729... 0.9ᵏ Exponential backoff

Arithmetic Progressions

Sequences where each term increases by a constant difference.

Linear Growth Examples
  • Array Indices: 0, 1, 2, 3, 4... (d=1)
  • Even Numbers: 0, 2, 4, 6, 8... (d=2)
  • Memory Addresses: 0x1000, 0x1004, 0x1008... (d=4 for 32-bit ints)
  • Port Numbers: 8080, 8081, 8082... (d=1)
Sum Formula

Sum of first n terms:

S(n) = n/2 × (2a + (n-1)d)

Where:
a = first term
d = common difference
n = number of terms

Example: 1+2+3+...+100
S(100) = 100/2 × (2×1 + 99×1)
       = 50 × 101 = 5050

Sequences in Algorithm Complexity

Big O Notation and Sequences
Complexity Sequence (n=1,2,4,8,16) Growth Type Example Algorithm
O(1) 1, 1, 1, 1, 1 Constant Array access
O(log n) 0, 1, 2, 3, 4 Logarithmic Binary search
O(n) 1, 2, 4, 8, 16 Linear Linear search
O(n log n) 0, 2, 8, 24, 64 Linearithmic Merge sort
O(n²) 1, 4, 16, 64, 256 Quadratic Bubble sort
O(2ⁿ) 2, 4, 16, 256, 65536 Exponential Naive Fibonacci

Real-World Applications

1. Network Protocols
TCP Window Scaling
Window sizes: 64KB, 128KB, 256KB, 512KB
Powers of 2 for efficient buffering
Exponential Backoff
Retry delays: 1s, 2s, 4s, 8s, 16s
Prevents network congestion
2. Cybersecurity
  • Password Cracking: Brute force attempts grow exponentially
  • Hash Chains: Rainbow tables use sequences for space-time tradeoffs
  • DDoS Mitigation: Rate limiting uses geometric progression
  • Key Sizes: Security levels double with each additional bit
3. Database Systems
  • B-tree Growth: Node capacity affects tree height logarithmically
  • Hash Table Sizing: Usually powers of 2 for bit masking
  • Buffer Pool: Page sizes are powers of 2 (4KB, 8KB, 16KB)

Practice Exercises

Exercise 1: Powers of 2
  1. What is 2¹⁵? (Hint: 2¹⁰ = 1024)
  2. How many bytes can be addressed with a 24-bit address?
  3. If a binary tree has height 10, what's the maximum number of nodes?
Exercise 2: Fibonacci
  1. Calculate F(12) using the recursive formula
  2. What's the ratio F(n+1)/F(n) as n gets large?
  3. How many function calls does naive recursive Fibonacci make for F(5)?
Exercise 3: Growth Rates
  1. For n=1000, compare n, n log n, and n²
  2. At what value of n does 2ⁿ exceed n²?
  3. Which grows faster: n! or 2ⁿ?
Exercise 4: Real-World Problem

A hash table starts with 16 buckets and doubles when 75% full. What are the first 5 resize thresholds?

Sequence Generator

Powers Calculator
Fibonacci Generator

Next Steps

Number sequences are everywhere in computing. Apply this knowledge:

Review Binary
Network Protocols
Operating Systems