fm-prime 1.0.9
Comprehensive prime number utilities with multiple algorithms including the novel Hyperbolic Equation Method with intelligent caching
License: MIT
Requires Python: >=3.7
Keywords: prime, prime-numbers, primes, primality-test, sieve, eratosthenes, miller-rabin, wheel-factorization, hyperbolic, number-theory, mathematics, cryptography

# Comprehensive Prime Number Utilities

This repository contains both JavaScript and Python implementations for prime number computations using multiple mathematical approaches including the novel **Hyperbolic Equation Method**.

> **Note**: While the JavaScript implementations are highly functional and optimized, **Python methods are generally quicker due to their efficient handling of numerical computations and file I/O operations**.

---

## Table of Contents

- [Overview](#overview)
- [Key Methods](#key-methods)
- [Mathematical Foundation](#mathematical-foundation)
- [Hyperbolic Equation Approach](#hyperbolic-equation-approach-novel)
- [Quick Start](#quick-start)
- [Documentation](#documentation)
- [Author](#author)

---

## Overview

This repository includes multiple approaches to prime number computation:

### Available Methods

1. **6k±1 Pattern (Wheel-6)** - Tests only 33% of numbers
2. **Wheel-30** - Tests only 27% of numbers (eliminates multiples of 2, 3, 5)
3. **Wheel-210** - Tests only 23% of numbers (eliminates multiples of 2, 3, 5, 7)
4. **Miller-Rabin** - Probabilistic test for very large primes
5. **Sieve of Eratosthenes** - Bulk generation of all primes up to N
6. **Hyperbolic Equation Method ⭐** - O(√N) two-way search with intelligent file caching

---

## Key Methods

### For Single Prime Checks
- **Small numbers (<10⁶)**: Use 6k±1 trial division
- **Large numbers (>10⁶)**: Use Miller-Rabin test

### For Bulk Prime Generation
- **Small ranges (<10K)**: Use 6k±1 Sieve or Hyperbolic with Caching
- **Medium ranges (<1M)**: Use Wheel-30 Sieve or Hyperbolic with Caching
- **Large ranges (>1M)**: Use Wheel-210 Sieve or Hyperbolic with Caching ⭐
- **Repeated queries**: Use Hyperbolic with Caching (leverages previously computed results)

---

## Mathematical Foundation

### The 6k±1 Pattern

**All primes > 3 are of form 6k±1**

**Proof:**
- Every integer can be written as: 6k, 6k+1, 6k+2, 6k+3, 6k+4, or 6k+5
- **6k** = divisible by 6 → not prime
- **6k+2** = 2(3k+1) → divisible by 2 → not prime
- **6k+3** = 3(2k+1) → divisible by 3 → not prime
- **6k+4** = 2(3k+2) → divisible by 2 → not prime
- **6k+1** and **6k+5 = 6k-1** → only these can be prime ✓

Therefore, only 2 out of every 6 positions need testing (33% of numbers).

### Factorization Patterns

For composite numbers in 6k±1 form:

**For 6n+1:**
- 6n+1 = (6k+1)(6kk+1) → n = 6k·kk + k + kk
- 6n+1 = (6k-1)(6kk-1) → n = 6k·kk - k - kk

**For 6n-1:**
- 6n-1 = (6k+1)(6kk-1) → n = 6k·kk - k + kk
- 6n-1 = (6k-1)(6kk+1) → n = 6k·kk + k - kk

---

## Hyperbolic Equation Approach (Novel)

### Overview

This approach transforms the prime factorization problem into solving **hyperbolic equations**, providing a geometric perspective on primality testing.

### Mathematical Derivation

#### Starting Point

For a number of form 6n+1, if composite, it factors as (6k+1)(6kk+1).

We can express this as a quadratic equation:
```
k² - sk + p = 0
where: s = k + kk, p = k·kk
```

#### Derivation for 6n+1

From: n = 6k·kk + k + kk = 6p + s

We have: s = n - 6p

The discriminant: δ = s² - 4p = (n-6p)² - 4p = n² - 12np + 36p² - 4p

For integer solutions, δ must be a perfect square: δ = r²

This gives us: n² - 12np + 36p² - 4p - r² = 0

Solving for p using the quadratic formula and requiring integer solutions:

```
δ' = 16(3n+1)² - 144(n²-r²) = 16(9r² + 6n + 1)
```

For δ' to be a perfect square, we need:

### **9r² + 6n + 1 = m²**

Rearranging:

### **(m - 3r)(m + 3r) = 6n+1**

#### Derivation for 6n-1

Similarly, for numbers of form 6n-1:

### **9r² - 6n + 1 = m²**

Rearranging:

### **(3r - m)(3r + m) = 6n-1**

### The Hyperbolic Equations

These are **hyperbola equations** in the (r, m) plane:

**For 6n+1:** m² - 9r² = 6n+1

**For 6n-1:** 9r² - m² = 6n-1

### Algorithm

To check if a number is composite:

```
For 6n+1:
  for r = 0 to √n:
    discriminant = 9r² + 6n + 1
    m = √discriminant

    if m² == discriminant:  # Perfect square
      check = m - 3r - 1
      if check % 6 == 0 and check >= 6:
        divisor = check + 1
        return composite (divisor found)

  return prime (no divisor found)
```

### Key Properties

1. **Geometric Interpretation**: Each n value creates a hyperbola in (r, m) space
2. **Integer Solutions**: Composite numbers correspond to integer points on these hyperbolas
3. **Natural Bound**: Solutions cluster near the asymptote m ≈ 3r
4. **Constraints**:
   - For 6n+1: 7r ≤ n-8 (first pattern) or 5r ≤ n-4 (second pattern)
   - For 6n-1: 7r ≤ n+8 (first pattern) or 5r ≤ n+4 (second pattern)

### Advantages

✅ **Mathematical Elegance**: Transforms factorization into geometry
✅ **Educational Value**: Shows connection between algebra and number theory
✅ **Alternative Perspective**: Different from trial division approach
✅ **Potentially Novel**: Specific formulation may be unique

### Performance and Trade-offs

#### Without Caching (First Run)
- **Performance**: The first run performance is O(√n), similar to optimized trial division.
- **Operations**: Each check involves more complex operations (e.g., square roots) than simple trial division.

#### With Caching (Subsequent Runs)
- **Performance**: Subsequent runs are extremely fast, often O(1) or near-O(1) for checks within the cached range, as it becomes a simple file lookup.
- **Use Case**: Ideal for applications that repeatedly query primes, especially within similar or expanding ranges. The benefits of caching grow as the application runs longer and performs more queries.

### Research Potential

🔍 **Areas for investigation:**
- Density patterns of integer solutions
- Relationship to Pell equations
- Distribution of (r, m) pairs
- Optimization of solution search

### ✅ Optimized Implementation

**Now production-ready with major improvements!**

The optimized implementation includes:
- **Two-way search**: Bottom-up (finds factors near √N) + Top-down (finds small factors quickly)
- **Modular filters**: Quadratic residue checks (mod 64, 63, 65) eliminate ~94% of non-squares before expensive square roots
- **File-level granular caching** ⭐ (NEW): Intelligent file-based caching that only reads/processes necessary files
  - Copies complete files when their range is below target
  - Only filters the boundary file that crosses the target
  - **2.5x faster** on average vs. traditional folder-based caching
  - Stops immediately when exact target is found (optimization)
- **Verified accuracy**: 100% correct results (664,579 primes under 10,000,000)

**Available in both JavaScript and Python:**
- `src/services/primeHyperbolic.optimized.mjs`
- `fm_prime/prime_hyperbolic_optimized.py`

**Original research version** (for educational purposes) remains in `/investigation` folder.

---

## Installation

### npm (JavaScript) 📦

```bash
# Install globally
npm install -g primefm

# Or install in your project
npm install primefm

# Or use directly without installing
npx primefm
```

**Package URL:** https://www.npmjs.com/package/primefm

### PyPI (Python) 🐍 - Coming Soon

```bash
pip install primefm
```

---

## Quick Start

### Interactive Prime Finder

**Using the installed package:**

```bash
# JavaScript - after npm install -g primefm
primefm

# Or use directly
npx primefm

# Python - after pip install primefm (coming soon)
primefm
```

**For local development:**

```bash
# JavaScript
node findPrimes.mjs

# Python
python3 findPrimes.py
```

Both provide an interactive menu to choose from 6 different prime-finding methods.

### Programmatic Usage

#### JavaScript (Using npm package)

```javascript
// After: npm install primefm
import { isPrimeOptimized } from 'primefm/checker';
import { sieveWheel210 } from 'primefm/wheel210';
import { sieveHyperbolicOptimized } from 'primefm/hyperbolic';

// Check single prime
console.log(isPrimeOptimized('999983'));  // true

// Find all primes up to 100,000 (Wheel-210)
const primes = sieveWheel210('100000');
console.log(`Found ${primes.length} primes`);

// Find all primes with caching (very fast for repeated use)
const cachedPrimes = sieveHyperbolicOptimized('100000');
console.log(`Found ${cachedPrimes.length} primes`);
```

<details>
<summary>For local development (without npm package)</summary>

```javascript
import { isPrimeOptimized } from './src/services/primeChecker.optimized.mjs';
import { sieveWheel210 } from './src/services/wheel210.optimized.mjs';
import { sieveHyperbolicOptimized } from './src/services/primeHyperbolic.optimized.mjs';
```

</details>

#### Python (PyPI package coming soon)

```python
# After: pip install primefm (once published)
# from primefm import is_prime_optimized, sieve_wheel210, sieve_hyperbolic_optimized

# For now, use local imports:
import sys
sys.path.insert(0, 'src/services-py')

from prime_optimized import is_prime_optimized
from wheel210 import sieve_wheel210
from prime_hyperbolic_optimized import sieve_hyperbolic_optimized

# Check single prime
print(is_prime_optimized(999983))  # True

# Find all primes up to 100,000 (Wheel-210)
primes = sieve_wheel210(100000)
print(f"Found {len(primes)} primes")

# Find all primes with caching (very fast for repeated use)
cached_primes = sieve_hyperbolic_optimized(100000)
print(f"Found {len(cached_primes)} primes")
```

### Visualization

Explore the hyperbolic approach visually:
```bash
python analyze-hyperbolic-visual.py     # Generates plots
python analyze-hyperbolic-patterns.py   # Text analysis
```

### Examples

See the `examples/` directory for complete working examples:

```bash
# Run comprehensive demonstration
python examples/example_hyperbolic_optimized.py
```

**Examples include:**
- Generating primes with caching
- Checking individual numbers for primality
- Finding all divisors
- Performance benchmarking
- Cache management

For more details, see **[examples/README.md](./examples/README.md)**

---

## Documentation

### User Guides

- **[USER_GUIDE.md](./USER_GUIDE.md)** - How to use the library (API, examples)
- **[METHODS_GUIDE.md](./METHODS_GUIDE.md)** - Detailed explanation of all methods
- **[COMPARISON.md](./COMPARISON.md)** - Performance benchmarks and comparisons

### Implementation Details

- **[JavaScript Services README](./src/services/README.md)** - JavaScript implementations
- **[Python Services README](./src/services-py/README.md)** - Python implementations

### Research & Analysis

- **Data Files**: `hyperbolic_solutions.csv`, `hyperbola_curves.csv`
- **Visualization**: `hyperbolic_analysis.png` (generated by analysis script)

---

## Performance Summary

| Method | Candidates Tested | Best For |
|--------|------------------|----------|
| 6k±1 | 33% | General purpose, simple |
| Wheel-30 | 27% | Better performance |
| Wheel-210 | 23% | Maximum single-run performance |
| Miller-Rabin | Variable | Very large numbers |
| Hyperbolic (Optimized) ⭐ | 33% | Repeated queries, caching benefits |

### Special Note on Hyperbolic Method
- **First run**: Similar to other O(√N) methods
- **Subsequent runs**: Extremely fast due to file-based caching
- **Use case**: Ideal for applications that frequently query primes in similar ranges

---

## Why Python is Faster

1. **Efficient Libraries**: Optimized math libraries (faster than JavaScript)
2. **Native BigInt**: Handles large integers natively
3. **Better File I/O**: Faster file operations
4. **Simpler Syntax**: Easier to optimize

For production use: **Python recommended for performance-critical applications**

---

## Author

**Farid Masjedi**

- GitHub: [@faridmasjedi](https://github.com/faridmasjedi)
- Email: farid.masjedi1985@gmail.com

---

## Contributing

Contributions welcome! Areas of interest:
- Performance optimizations
- Additional mathematical approaches
- Literature review on hyperbolic method novelty
- More comprehensive benchmarks

---

## License

Open source - feel free to use, modify, and distribute.

---

## Acknowledgments

- Mathematical derivations based on systematic exploration of 6k±1 patterns
- Hyperbolic approach independently discovered through algebraic analysis
- Wheel factorization builds on classical number theory techniques

---

*For detailed usage instructions, see [USER_GUIDE.md](./USER_GUIDE.md)*

*For performance comparisons, see [COMPARISON.md](./COMPARISON.md)*

*For method explanations, see [METHODS_GUIDE.md](./METHODS_GUIDE.md)*