Searching for Primes: A Neural AlphaZero Approach to a Factoring Game
Abstract
We study a one-player token game on an N× N board where tokens slide along diagonals or duplicate onto neighbouring ones to form a combinatorial rectangle R× S. A conserved integer weight W' and a strict monovariant guarantee O(N2)-length solutions, placing the game in NP. We prove that reaching a final position factors this 2N-bit W' into two N-bit factors V,M < 2N that encode the rectangle's rows and columns. Consequently, solving the game for a balanced-semiprime target is equivalent to integer factoring. However, if the target rectangle is known, the solution reduces to two polynomial-time steps: a forced downward chip-flow and a 0/1-polynomial factorisation leveraging Cohn's theorem. The game's entire difficulty is thus isolated to the initial number-theoretic split. Supplying the popcounts of the factors as a promise preserves this asymptotic hardness but bounds the target search space. We exploit this constrained space using a learned policy/value network and an AlphaZero-style Monte-Carlo tree search, empirically probing the limits of neural look-ahead on a factoring-equivalent environment.
Related
- Bits per Spike as a Betting Game: An Interpretable Unit for Held-Out Log-Likelihood in Neural Data Analysis
- Cellular Maximal-Density Factoring: Joint Shadings, Stable Refinements, and a Conditional Kakeya Application
- Searching for Bell-CHSH-Violating Bose Operators
- Searching for related contributors to a DNA mixture using single cell analysis
- Parallel Searching Method for Verifying Finiteness of Prime Numbers Presented as Specific Linear Combinations of Factorials
BibTeX
@misc{crasmaru2026searching,
title = {{Searching for Primes: A Neural AlphaZero Approach to a Factoring Game}},
author = {Marcel Crasmaru},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.22968},
eprint = {2609.22968},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.22968},
}
RIS
TY - UNPB
TI - Searching for Primes: A Neural AlphaZero Approach to a Factoring Game
AU - Marcel Crasmaru
PY - 2026
DA - 2026/09/19
PB - arXiv
DO - 10.48550/arxiv.2609.22968
UR - https://arxiv.org/abs/2609.22968
AB - We study a one-player token game on an N× N board where tokens slide along diagonals or duplicate onto neighbouring ones to form a combinatorial rectangle R× S. A conserved integer weight W' and a strict monovariant guarantee O(N^2)-length solutions, placing the game in NP. We prove that reaching a final position factors this 2N-bit W' into two N-bit factors V,M < 2^N that encode the rectangle's rows and columns. Consequently, solving the game for a balanced-semiprime target is equivalent to integer factoring. However, if the target rectangle is known, the solution reduces to two polynomial-time steps: a forced downward chip-flow and a 0/1-polynomial factorisation leveraging Cohn's theorem. The game's entire difficulty is thus isolated to the initial number-theoretic split. Supplying the popcounts of the factors as a promise preserves this asymptotic hardness but bounds the target search space. We exploit this constrained space using a learned policy/value network and an AlphaZero-style Monte-Carlo tree search, empirically probing the limits of neural look-ahead on a factoring-equivalent environment.
ER -