Exhaustive Search for a System of 10 Diophantine Equations

---

Overview

This script executes a staged exhaustive search to find a unique set of 20 distinct integer values ($a_0$ through $a_{19}$), each between 1 and 25 inclusive, that simultaneously satisfy a system of 10 algebraic constraints ($c_1$ through $c_{10}$).

The objective is to find a solution vector $sol = (a_0, a_1, \dots, a_{19})$ such that the following conditions are met:

1. Domain: $1 \le a_i \le 25$ for all $i \in [0, 19]$.
2. Uniqueness: All 20 values ($a_0, a_1, \dots, a_{19}$) must be distinct.
3. Constraints: All 10 constraints ($c_1$ through $c_{10}$) must evaluate to zero.

The script optimizes the search process by breaking it down into incremental stages, using the constraints to calculate dependent variables (e.g., $a_0, a_2, a_8$) instead of iterating through them, thus drastically reducing the computational time required for the brute-force search.

---

The 10 Constraint

The system requires that the absolute value of each expression equals zero, which simplifies the equations to the following 10 identities:

Constraint	Simplified Equation	Notes
c1	$a_0 + a_1 + a_2 - a_3 = 30$
c2	$a_4 a_5 + 16 / a_6 = 224$	Requires $a_6$ to be a divisor of 16.
c3	$a_7 - a_8 + a_9 + a_{10} = 8$
c4	$a_{11} - a_{12} + a_{13} + a_{14} = 22$
c5	$a_{15} + a_{16} - a_{17} - a_{18} + a_{19} = 40$
c6	$a_0 + a_4 - a_7 a_{11} + a_{15} = -12$
c7	$a_1 / a_5 + a_8 + a_{16} = 37$	Requires $a_1$ to be a multiple of $a_5$.
c8	$a_2 + a_9 - a_{12} a_{17} = -16$
c9	$-a_6 - a_{10} - a_{13} + a_{18} = 10$
c10	$a_3 + a_{14} a_{19} = 202$

---

Search Methodology (Staged Brute Force)

The script uses four sets of partial solutions, where the final three sets build upon the previous ones, incorporating new constraints and pruning invalid paths.

1. Stage 0: Initial Candidates (S0)

• Constraint Used: $c_{10}$
• The set S0 is initialized with 20 valid triples $(a_3, a_{14}, a_{19})$ that satisfy $c_{10}$ and the range/distinctness rules for these three variables.

2. Stage 1 to 3: Incremental Pruning (S, S2, S3)

Stage	New Constraint Added	Variables Solved/Calculated
S	$c_2$	Loops for $a_4, a_5, a_6$
S2	$c_7$	Loops for $a_1, a_{16}$; Calculates $a_8$
S3	$c_6$	Loops for $a_7, a_{11}, a_{15}$; Calculates $a_0$

3. Stage 4: Final Search and Verification (S4)

• Loops: The final search iterates through $a_9, a_{12}, a_{17}$.
• Calculation: All remaining variables ($a_2, a_{10}, a_3, a_{13}, a_{18}$) are calculated from the remaining constraints ($c_8, c_3, c_1, c_4, c_9$).
• Final Checks: The script verifies:
  • Range: All 20 variables are $1 \le a_i \le 25$.
  • Uniqueness: All 20 variables are distinct.
  • Final Constraint: The unused constraint $c_5$ must be satisfied.
  • Global Test: The test(sol) function confirms all 10 equations are zero.

The script prints the sizes of the intermediate sets and the final solution(s) found in S4.

Execution

python3 main.py