Euclid Primes

A small, resume-able producer/consumer pipeline that generates Euclid numbers (E = primorial + 1), marks probable primes (via Miller–Rabin), and records results in a SQLite database for later inspection and processing. Designed for long-running computations and sharing results (for example via Zenodo).

This repository contains two main components:

• producer.py — incrementally computes primorials and Euclid numbers, runs Miller–Rabin, and writes records to a SQLite database (euclid.db). It is resume-able: if stopped and restarted it continues from the last processed index.
• consumer.py — picks up candidate records from the DB and runs stronger trial division / Pollard–Rho (or other factorization methods) to find nontrivial factors and classify records.

---

Features

• Resume-able storage using a single SQLite file (euclid.db).
• Each euclid row records last_prime (the last prime used in the primorial), the Euclid number (stored as text), bit-length, MR result, small factors (if any), and status (candidate / composite / prime / done).
• Split producer/consumer architecture so you can run the expensive primality tests and factorization in separate processes or machines.
• Simple CLI options for tuning Miller–Rabin rounds, trial division limits, and batch sizes.

---

Requirements

• Python 3.8+ (uses standard library for the default code)
• Optional: pandas for CSV/Excel export
• Optional: pyecm or other factorization libraries for improved factoring in the consumer

Example (optional dependencies):

python3 -m venv .venv
source .venv/bin/activate
pip install pandas pyecm

---

Quick start

1. Put producer.py and consumer.py in a directory, e.g. ~/euclid.

2. Run the producer in one terminal (this will create euclid.db the first time):

python3 producer.py --db euclid.db --mr 12 --trial 200000

• --mr sets Miller–Rabin rounds (higher → lower false-prime probability).
• --trial sets a small-factor trial-division limit used by the producer to catch tiny factors quickly.

3. In a separate terminal (or machine) run the consumer:

python3 consumer.py --db euclid.db --trial 1000000

The consumer will fetch status='candidate' rows and try to factor them. Found factors will be written to the DB and the status updated.

---

Database schema (typical)

primes (optional)

• idx INTEGER PRIMARY KEY
• p INTEGER

euclid

• idx INTEGER PRIMARY KEY — index n (number of primes multiplied)
• last_prime INTEGER — the last prime used in the primorial (e.g. 29)
• primorial TEXT (optional) — decimal string of the primorial (may be large)
• euclid TEXT — primorial + 1 as decimal string
• bits INTEGER — bit-length of euclid
• is_probable_prime INTEGER — Miller–Rabin result (0/1 or NULL if not tested)
• small_factor TEXT — comma-separated small factors if found
• status TEXT — candidate / done / composite / prime
• mr_rounds INTEGER — MR rounds used when testing
• created_at, updated_at TEXT — ISO timestamps

If your DB was created before last_prime existed, add the column with:

ALTER TABLE euclid ADD COLUMN last_prime INTEGER;

---

Example SQL queries

Open the DB with the sqlite3 CLI, DB Browser, or VS Code extension. Useful queries:

• Show last 10 rows:

SELECT idx, last_prime, bits, is_probable_prime, small_factor, status
FROM euclid
ORDER BY idx DESC LIMIT 10;

• List current candidates (probable primes):

SELECT idx, last_prime, bits, euclid
FROM euclid
WHERE status='candidate'
ORDER BY idx;

• Find rows with discovered factors:

SELECT idx, last_prime, small_factor
FROM euclid
WHERE small_factor IS NOT NULL
ORDER BY idx;

• How many rows total:

SELECT COUNT(*) FROM euclid;

Run sqlite3 -header -column euclid.db for more readable CLI output.

---

GUI & easy inspection

• DB Browser for SQLite — sudo apt install sqlitebrowser and then sqlitebrowser euclid.db.
• DBeaver — snap install dbeaver-ce and connect to the file.
• VS Code — use a SQLite extension (e.g. SQLite by Alex Covizzi) and open the DB file inside the editor.
• Export to CSV using Python & pandas:

import sqlite3
import pandas as pd
conn = sqlite3.connect('euclid.db')
df = pd.read_sql_query('SELECT * FROM euclid', conn)
df.to_csv('euclid.csv', index=False)

---

Running continuously / as a service

Simple workflow using tmux:

tmux
python3 producer.py --db euclid.db
# detach with Ctrl+b d

Example systemd unit for the producer (/etc/systemd/system/euclid-producer.service):

[Unit]
Description=Euclid Producer
After=network.target

[Service]
User=YOUR_USER
WorkingDirectory=/home/YOUR_USER/euclid
ExecStart=/usr/bin/python3 /home/YOUR_USER/euclid/producer.py --db /home/YOUR_USER/euclid/euclid.db --mr 12
Restart=on-failure
RestartSec=5

[Install]
WantedBy=multi-user.target

Enable and start:

sudo systemctl daemon-reload
sudo systemctl enable --now euclid-producer.service

Note: adjust paths and user to match your environment.

---

Practical notes & recommendations

• primorial grows very fast — storing the primorial and euclid as decimal TEXT is simple and portable but the file size will grow if you keep many large values.
• Miller–Rabin: if MR returns composite the result is certain. If it returns probable prime, there is a small probability of error. Increase MR rounds to reduce this risk or use a provable algorithm such as ECPP for a certificate.
• Consumer: consider adding ECM (pyecm) or other specialized factorization tools for better results on medium-size factors.
• If multiple processes write concurrently, use SQLite WAL mode to reduce database is locked errors:

PRAGMA journal_mode = WAL;

---

Development & contributions

Contributions welcome. Suggested improvements:

• Add optional ECPP integration (produce/verify primality certificates).
• Replace Python big-int primorial computations with GMP-backed code for extreme-scale runs.
• Add more robust job-queueing (e.g. Redis/RQ or Celery) if you want distributed workers.

Please open issues / PRs in the repository.

---

License

This project is available under the MIT License. See LICENSE.