Skip to content

HSCunha/ono-primes

BranchesTags

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

4 Commits
examples
examples
 
 
ono_primes
ono_primes
 
 
output
output
 
 
tests
tests
 
 
.gitignore
.gitignore
 
 
ono-primes.ipynb
ono-primes.ipynb
 
 
readme.md
readme.md
 
 
requirements.txt
requirements.txt
 
 
setup.py
setup.py
 
 

Repository files navigation

Ono Primes

A Python library implementing prime detection using integer partitions, based on the 2023 paper "Integer Partitions Detect the Primes" by William Craig, Jan-Willem van Ittersum, and Ken Ono.

Table of Contents

Background

In 2023, mathematicians William Craig, Jan-Willem van Ittersum, and Ken Ono published a groundbreaking paper demonstrating that the prime numbers can be detected purely through integer partition theory — a branch of mathematics historically unconnected to primality.

This was a surprise to the mathematical community. For centuries, partitions and primes were considered separate domains. Ono's team found a precise algebraic identity involving MacMahon-style partition functions that equals zero if and only if a given integer is prime.

This library is a Python implementation of those ideas, designed for:

  • Mathematical experimentation with partition-based primality
  • Education — understanding the connection between partitions and primes
  • Research — a foundation for exploring faster variants of the MacMahon functions
  • Benchmarking — comparing partition-based detection against classical methods

The Mathematics

MacMahon Partition Functions

A partition of an integer n is a way of writing n as an unordered sum of positive integers. For example, the partitions of 5 are:

5
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

MacMahon studied weighted sums over partitions, where the weight is a product of multiplicities of part sizes. In a partition, if part size s appears m times, then m is the multiplicity of s.

The key functions in this library are:

M1(n) — Weighted sum over partitions with a single distinct part size:

M1(n) = Σ m   over all partitions (m, s) where m*s = n

This is equivalent to the classical sum-of-divisors function σ₁(n):

M1(6) = 1 + 2 + 3 + 6 = 12

M2(n) — Weighted sum over partitions with exactly two distinct part sizes:

M2(n) = Σ (m1 * m2)   over all partitions m1*s1 + m2*s2 = n
         where s1 < s2, m1 >= 1, m2 >= 1

Example for n = 6:

Partition 1*1 + 1*5 = 6  →  m1=1, m2=1  →  contributes 1*1 = 1
Partition 2*1 + 1*4 = 6  →  m1=2, m2=1  →  contributes 2*1 = 2
Partition 1*2 + 1*4 = 6  →  m1=1, m2=1  →  contributes 1*1 = 1
...
M2(6) = 4

The Prime Detection Equation

The central theorem of the paper states:

For any integer n ≥ 2, n is prime if and only if:

(n² - 3n + 2) · M1(n) - 8 · M2(n) = 0

This is an exact algebraic identity — not a probabilistic test, not an approximation. When the left-hand side evaluates to exactly zero, n is guaranteed to be prime.

Worked example for n = 7 (prime):

M1(7) = 1 + 7 = 8
M2(7) = 8

(7² - 3·7 + 2) · M1(7) - 8 · M2(7)
= (49 - 21 + 2) · 8 - 8 · 8
= 30 · 8 - 64
= 240 - 240
= 0  ✓  (prime)

Worked example for n = 4 (composite):

M1(4) = 1 + 2 + 4 = 7
M2(4) = 2

(4² - 3·4 + 2) · M1(4) - 8 · M2(4)
= (16 - 12 + 2) · 7 - 8 · 2
= 6 · 7 - 16
= 42 - 16
= 26 ≠ 0  (composite)

Why This Matters

Classical primality tests like trial division or Miller-Rabin work by attempting to find factors. The Ono-Craig-van Ittersum result works by an entirely different mechanism — it counts weighted partition structures.

The mathematical significance is profound:

  1. It unifies two separate areas of number theory — partition theory and prime detection
  2. It is an exact identity, not an asymptotic or probabilistic result
  3. It opens a new research direction: if a MacMahon function variant can be computed in O(log n) time, it could become the foundation of new cryptographic algorithms

Installation

Important: It is strongly recommended to install this library inside a virtual environment to avoid conflicts with your system Python packages.

Setting Up a Virtual Environment

Windows (Command Prompt or PowerShell)

# Navigate to your project directory
cd ono-primes

# Create a virtual environment named .venv
python -m venv .venv

# Activate the virtual environment
# Command Prompt:
.venv\Scripts\activate.bat

# PowerShell:
.venv\Scripts\Activate.ps1

PowerShell Note: If you get an execution policy error, run this first:

Set-ExecutionPolicy -ExecutionPolicy RemoteSigned -Scope CurrentUser

macOS / Linux

# Navigate to your project directory
cd ono-primes

# Create a virtual environment named .venv
python3 -m venv .venv

# Activate the virtual environment
source .venv/bin/activate

Verify the Virtual Environment is Active

Once activated, your terminal prompt will show (.venv) as a prefix:

(.venv) PS C:\Users\yourname\code\repos\ono-primes>

You can also verify which Python is being used:

# Windows
where python

# macOS / Linux
which python
# Should point to .venv/bin/python or .venv\Scripts\python.exe

Deactivating the Virtual Environment

When you are done working on the project:

deactivate

From Source

With your virtual environment activated, clone and install the library:

# Clone the repository
git clone https://github.com/yourusername/ono-primes.git
cd ono-primes

# Create and activate the virtual environment (see above)
python -m venv .venv
.venv\Scripts\activate.bat   # Windows
# or
source .venv/bin/activate    # macOS / Linux

# Install the library in editable mode with all dependencies
pip install -e .

To confirm the installation was successful:

pip show ono-primes

Dependencies

Package Version Purpose
sympy >=1.10 Divisor computation, validation
Python >=3.10 Type hints, match statements

All dependencies are installed automatically via pip install -e .

To install dependencies manually inside your virtual environment:

pip install -r requirements.txt

To see all currently installed packages in your virtual environment:

pip list

Quick Start

With your virtual environment activated:

from ono_primes import is_prime_ono, M1, M2

# Check if a number is prime
print(is_prime_ono(7))   # True
print(is_prime_ono(8))   # False

# Inspect the partition functions
print(M1(7))             # 8
print(M2(7))             # 8

# Get all primes up to 50
from ono_primes import primes_up_to
print(primes_up_to(50))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

API Reference

Partition Functions

M1(n)

from ono_primes.partitions import M1

M1(n: int) -> int

Calculates the sum of all divisors of n. Equivalent to the classical sigma function σ₁(n). Results are cached automatically with lru_cache.

Parameter Type Description
n int A positive integer ≥ 1

Returns: int — The sum of all divisors of n.

Raises: ValueError if n < 1.

M1(1)   # 1
M1(6)   # 12  (1 + 2 + 3 + 6)
M1(7)   # 8   (1 + 7)
M1(12)  # 28  (1 + 2 + 3 + 4 + 6 + 12)

M2(n)

from ono_primes.partitions import M2

M2(n: int) -> int

Calculates the MacMahon M2 function: the sum of products (m1 * m2) over all two-part partitions n = m1·s1 + m2·s2 where s1 < s2. Results are cached.

Parameter Type Description
n int A positive integer ≥ 1

Returns: int — The M2 value for n.

Raises: ValueError if n < 1.

M2(6)   # 4
M2(7)   # 8
M2(12)  # ...

partition_summary(n)

from ono_primes.partitions import partition_summary

partition_summary(n: int) -> dict

Returns a dictionary summary of all partition function values for n.

partition_summary(6)
# {'n': 6, 'M1': 12, 'M2': 4}

Prime Detection

is_prime_ono(n)

from ono_primes.prime_detection import is_prime_ono

is_prime_ono(n: int) -> bool

Returns True if n is prime using the Ono-Craig-van Ittersum equation.

Parameter Type Description
n int Any integer

Returns: bool

Raises: TypeError if n is not an integer.

is_prime_ono(2)    # True
is_prime_ono(7)    # True
is_prime_ono(1)    # False
is_prime_ono(100)  # False

prime_indicator(n)

from ono_primes.prime_detection import prime_indicator

prime_indicator(n: int) -> int

Returns the raw value of the Ono equation for n. A return value of 0 means n is prime. The magnitude of non-zero values has no standard interpretation but can be explored mathematically.

prime_indicator(7)   # 0   (prime)
prime_indicator(8)   # 48  (composite)
prime_indicator(4)   # 26  (composite)

primes_up_to(limit)

from ono_primes.prime_detection import primes_up_to

primes_up_to(limit: int) -> list[int]

Returns a list of all prime numbers up to and including limit.

primes_up_to(30)
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

prime_generator(start)

from ono_primes.prime_detection import prime_generator

prime_generator(start: int = 2) -> Generator[int, None, None]

An infinite generator that yields prime numbers starting from start.

gen = prime_generator()
[next(gen) for _ in range(10)]
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

gen = prime_generator(start=100)
next(gen)  # 101

Utilities

benchmark(n)

from ono_primes.utils import benchmark

benchmark(n: int) -> dict

Benchmarks the Ono method against SymPy's isprime for a single value of n.

benchmark(13)
# {
#   'n': 13,
#   'ono_result': True,
#   'sympy_result': True,
#   'results_match': True,
#   'ono_time_seconds': 0.000412,
#   'sympy_time_seconds': 0.000003,
#   'speedup_factor': 137.3
# }

validate_range(low, high)

from ono_primes.utils import validate_range

validate_range(low: int, high: int) -> dict

Validates the Ono method against SymPy's isprime over a range of integers. Returns a summary of any disagreements and total timing.

validate_range(2, 100)
# {
#   'range': (2, 100),
#   'all_match': True,
#   'disagreements': [],
#   'total_ono_time_seconds': 1.234,
#   'total_sympy_time_seconds': 0.002
# }

equation_table(low, high)

from ono_primes.utils import equation_table

equation_table(low: int, high: int) -> list[dict]

Returns a table of raw equation values for a range of integers. Useful for mathematical exploration.

equation_table(2, 8)
# [
#   {'n': 2, 'indicator': 0,  'is_prime': True},
#   {'n': 3, 'indicator': 0,  'is_prime': True},
#   {'n': 4, 'indicator': 26, 'is_prime': False},
#   {'n': 5, 'indicator': 0,  'is_prime': True},
#   {'n': 6, 'indicator': 32, 'is_prime': False},
#   {'n': 7, 'indicator': 0,  'is_prime': True},
#   {'n': 8, 'indicator': 48, 'is_prime': False},
# ]

Examples

Basic Prime Detection

from ono_primes import is_prime_ono

for n in range(2, 30):
    if is_prime_ono(n):
        print(n, end=" ")
# 2 3 5 7 11 13 17 19 23 29

Generating Primes

from ono_primes.prime_detection import prime_generator

gen = prime_generator()
primes = [next(gen) for _ in range(20)]
print(primes)
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]

Exploring the Partition Functions

from ono_primes.partitions import M1, M2, partition_summary

for n in range(2, 15):
    s = partition_summary(n)
    print(f"n={n:3d}  M1={s['M1']:4d}  M2={s['M2']:4d}")

Golden-angle (Fermat) Spiral Visualization

%matplotlib widget  # for interactive rotation in Jupyter

from ono_primes import plot_fermats_spiral_3d

ax = plot_fermats_spiral_3d(
    n_max=1500,
    radial_scale=0.08,
    z_scale=0.01,
)

Fermat vs Logarithmic Spiral of Integers

Fermat vs Log spirals

Each dot represents an integer (n = 1, 2, 3, ...).

  • Gray and green dots are composite numbers.
  • Pink and gold dots are prime numbers.

The lower (pink/gray) layer is the 3D Fermat (golden‑angle) spiral of the integers:

$$\varphi = \pi (3 - \sqrt{5}), \qquad r_F(n) = c_F \sqrt{n}, \qquad \theta_F(n) = n \varphi$$ $$x_F(n) = r_F(n)\cos\theta_F(n), \quad y_F(n) = r_F(n)\sin\theta_F(n), \quad z_F(n) = k_F n$$

where

$$c_F = \text{fermat\_radial\_scale},$$

and

$$k_F = \texttt{fermat\_z\_scale}.$$

The upper (gold/green) layer is the 3D logarithmic spiral of the integers:

$$\theta_L(n) = k_\theta n, \qquad r_L(n) = a\, e^{b\,\theta_L(n)}$$ $$x_L(n) = r_L(n)\cos\theta_L(n), \quad y_L(n) = r_L(n)\sin\theta_L(n), \quad z_L(n) = k_L n + \Delta z$$

where

$$a = \texttt{log\_a} b = \texttt{log\_b} k_L = \texttt{log\_z\_scale} k_\theta = 1\ \text{rad}$$

in the code, and

$$\Delta z$$

is a constant vertical offset so the log spiral floats above the Fermat spiral.

Benchmarking

from ono_primes.utils import benchmark

for n in [7, 13, 29, 50]:
    r = benchmark(n)
    print(f"n={n:3d}  ono={r['ono_time_seconds']:.5f}s  "
          f"sympy={r['sympy_time_seconds']:.5f}s  "
          f"match={r['results_match']}")

Validating Against SymPy

from ono_primes.utils import validate_range

result = validate_range(2, 50)
print(f"All results match SymPy: {result['all_match']}")
print(f"Total Ono time:          {result['total_ono_time_seconds']:.4f}s")
print(f"Total SymPy time:        {result['total_sympy_time_seconds']:.4f}s")

Performance

Current Complexity

Function Time Complexity Notes
M1(n) O(√n) Via SymPy's divisor function
M2(n) O(n³) approx Triple nested loop
is_prime_ono(n) Dominated by M2(n) See above

Caching

Both M1(n) and M2(n) use Python's functools.lru_cache with unlimited size. Repeated calls with the same n are essentially free after the first computation.

import time
from ono_primes.partitions import M2

# First call — computed fresh
start = time.perf_counter()
M2(30)
print(f"First call:  {time.perf_counter() - start:.5f}s")

# Second call — served from cache
start = time.perf_counter()
M2(30)
print(f"Cached call: {time.perf_counter() - start:.5f}s")

Known Limitations

  • Not suitable for large n in the current implementation. The triple nested loop in M2(n) grows very quickly. For n > 50, computation time becomes significant.
  • Research use only — classical primality tests (sympy.isprime, gmpy2) are orders of magnitude faster for production use.
  • Future work: The paper suggests that alternative MacMahon function forms may yield faster algorithms. This library is a foundation for that research.

Project Structure

ono_primes/
├── __init__.py            # Public API surface
├── partitions.py          # M1(n), M2(n), partition_summary(n)
├── prime_detection.py     # is_prime_ono, prime_indicator, primes_up_to, prime_generator
├── utils.py               # benchmark, validate_range, equation_table
├── tests/
│   ├── __init__.py
│   ├── test_partitions.py      # Tests for M1, M2, partition_summary
│   ├── test_prime_detection.py # Tests for is_prime_ono, prime_indicator, etc.
│   └── test_utils.py           # Tests for benchmark, validate_range, etc.
├── examples/
│   └── example_usage.py   # Runnable demonstration script
├── .venv/                 # Virtual environment (not committed to git)
├── .gitignore
├── README.md
├── setup.py
└── requirements.txt

Running Tests

Ensure your virtual environment is activated before running tests.

Run the full test suite with:

python -m unittest discover -s ono_primes/tests -v

Run a specific test file:

python -m unittest ono_primes.tests.test_partitions -v
python -m unittest ono_primes.tests.test_prime_detection -v
python -m unittest ono_primes.tests.test_utils -v

Run the example script:

python ono_primes/examples/example_usage.py

Contributing

Contributions are welcome, especially in the following areas:

  1. Performance optimizations for M2(n) — algorithmic improvements, NumPy vectorization, or Cython extensions
  2. Higher-order MacMahon functions — implementing M3(n), M4(n), etc. from the paper's more general framework
  3. Alternative prime equations — the paper contains multiple partition-based identities; implementing and testing additional ones
  4. Documentation — mathematical explanations, Jupyter notebook tutorials

To contribute:

# Clone and set up your virtual environment
git clone https://github.com/yourusername/ono-primes.git
cd ono-primes

python -m venv .venv
.venv\Scripts\activate.bat      # Windows
source .venv/bin/activate       # macOS / Linux

pip install -e .

# Make your changes, add tests, then open a pull request

Note: Never commit your .venv/ folder. Add it to .gitignore:

.venv/
__pycache__/
*.pyc
*.egg-info/
dist/
build/

Roadmap

  • v0.1.0 — Core M1, M2, and is_prime_ono implementation
  • v0.2.0 — Implement M3(n) and M4(n) from the paper
  • v0.3.0 — NumPy-accelerated partition enumeration
  • v0.4.0 — Jupyter notebook tutorials and mathematical documentation
  • v0.5.0 — Explore and implement any known O(n log n) shortcuts
  • v1.0.0 — Stable API, full documentation, PyPI release

References

  1. Craig, W., van Ittersum, J.-W., & Ono, K. (2023). Integer Partitions Detect the Primes. arXiv:2301.XXXXX

  2. MacMahon, P.A. (1916). Combinatory Analysis, Volumes I and II. Cambridge University Press.

  3. Andrews, G.E. (1998). The Theory of Partitions. Cambridge University Press.

  4. SymPy Development Team (2023). SymPy: Python library for symbolic mathematics. https://www.sympy.org

About

No description, website, or topics provided.

Resources

Readme
Activity

Stars

0 stars

Watchers

0 watching

Forks

0 forks
Report repository

Releases

No releases published

Packages

 
 
 

Contributors

Languages