fm-prime 1.0.4

Comprehensive prime number utilities with multiple algorithms including the novel Hyperbolic Equation Method with intelligent caching

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
• Key Methods
• Mathematical Foundation
• Hyperbolic Equation Approach
• Quick Start
• Documentation
• 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

Limitations

⚠️ Performance: Similar O(√n) complexity to trial division ⚠️ Operations: More operations per iteration (sqrt, multiply, modulo) ⚠️ Practical Use: Not faster than optimized trial division

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
• Intelligent caching: File-based caching via output-big folder system - reuses previously computed primes
• Verified accuracy: 100% correct results (664,579 primes under 10,000,000)

Available in both JavaScript and Python:

• src/services/primeHyperbolic.optimized.mjs
• src/services-py/prime_hyperbolic_optimized.py

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

---

Installation

npm (JavaScript) 📦

# 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

pip install primefm

---

Quick Start

Interactive Prime Finder

Using the installed package:

# JavaScript - after npm install -g primefm
primefm

# Or use directly
npx primefm

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

For local development:

# 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)

// 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`);

For local development (without npm package)

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

Python (PyPI package coming soon)

# 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:

python analyze-hyperbolic-visual.py     # Generates plots
python analyze-hyperbolic-patterns.py   # Text analysis

---

Documentation

User Guides

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

Implementation Details

• JavaScript Services README - JavaScript implementations
• Python Services README - 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
• Email: [e-mail]

---

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

For performance comparisons, see COMPARISON.md

For method explanations, see METHODS_GUIDE.md