cahlen/erdos-straus-cuda

Erdos-Straus Solution Counter

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

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

for each prime $pp$, where $x\le y\le zx\; \backslash leq\; y\; \backslash leq\; z$.

The Erdos-Straus conjecture (1948) asserts that $f(p)\ge 1f(p)\; \backslash geq\; 1$ for all primes $p\ge 2p\; \backslash 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

Parameter	Type	Description
primes	Tensor[int64] (1-D, CUDA)	Batch of primes to count solutions for
Returns	Tensor[int32] (1-D, CUDA)	Solution count $f(p)f(p)$ for each prime

Algorithm

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

1. Iterate $xx$ from $\lceil p\mathrm{/}4\rceil +1\backslash lceil\; p/4\; \backslash rceil\; +\; 1$ to $\lfloor 3p\mathrm{/}4\rfloor \backslash lfloor\; 3p/4\; \backslash rfloor$
2. Compute the remainder fraction $\frac{4x-p}{px}\backslash frac\{4x\; -\; p\}\{px\}$ and iterate $yy$ in the valid range
3. Check if $z=\frac{px\cdot y}{(4x-p)y-px}z\; =\; \backslash frac\{px\; \backslash cdot\; y\}\{(4x-p)y\; -\; px\}$ is a positive integer with $z\ge yz\; \backslash 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)\ge 1f(p)\; \backslash 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.