erdos-straus-cuda

Erdos-Straus Solution Counter

GPU kernel for counting solutions \(f(p)\) to the Erdos-Straus equation:

$$\frac{4}{p} = \frac{1}{x} + \frac{1}{y} + \frac{1}{z}$$

for each prime \(p\), where \(x \leq y \leq z\).

The Erdos-Straus conjecture (1948) asserts that \(f(p) \geq 1\) for all primes \(p \geq 2\). This kernel computes the exact count of ordered solutions for every prime in a batch.

Usage

# /// script
# dependencies = ["torch", "kernels"]
# ///
import torch
from kernels import get_kernel

erdos_straus = get_kernel("cahlen/erdos-straus-cuda")

# Count solutions for a batch of primes
primes = torch.tensor([2, 3, 5, 7, 11, 13, 97, 9973], dtype=torch.int64, device="cuda")
counts = erdos_straus.count(primes)
print(dict(zip(primes.tolist(), counts.tolist())))
# {2: 1, 3: 3, 5: 2, 7: 5, 11: 8, 13: 12, 97: 251, 9973: 62624}

API

erdos_straus.count(primes: Tensor) -> Tensor

Algorithm

For each prime \(p\), the kernel enumerates all valid \((x, y, z)\) triples:

1. Iterate \(x\) from \(\lceil p/4 \rceil + 1\) to \(\lfloor 3p/4 \rfloor\)
2. Compute the remainder fraction \(\frac{4x - p}{px}\) and iterate \(y\) in the valid range
3. Check if \(z = \frac{px \cdot y}{(4x-p)y - px}\) is a positive integer with \(z \geq y\)

Each thread handles one prime. Throughput scales linearly with GPU cores.

Results

Verified on 8x NVIDIA B200 GPUs at bigcompute.science:

• 10^8: 5.76M primes, conjecture holds (all \(f(p) \geq 1\))
• 10^9: 50.8M primes, in progress

All data open at github.com/cahlen/idontknow.

Citation

@misc{humphreys2026erdosstraus,
  author = {Humphreys, Cahlen},
  title = {GPU-Accelerated Erdos-Straus Solution Counting},
  year = {2026},
  url = {https://bigcompute.science}
}

Human-AI collaborative research. Not peer-reviewed. All code and data open for verification.