GCD Sum Numerical Experiments

Goal Compute and explore

S(N) = sum_{1<=a<=N} [ 1/(a(a+1)) * sum_{0<=b<a} gcd(a(a+1), b(b+1)) ]

using multiple backends, automated bound testing, and idea generation (OpenAI API when available, local fallback otherwise).

Mathematical Approach (Efficiency)

• Divisor identity: gcd(n,m) = sum_{d|n,m} phi(d). This turns the inner sum into sum_{d|a(a+1)} phi(d) * C(d,a) with C(d,a)=#{0<=b<a : d|b(b+1)}.
• Counting C(d,a): for prime powers p^k, solutions to b(b+1)≡0 mod p^k are b≡0 or b≡-1 (two residues). Combine across primes using CRT; count b<a by periodicity.
• Split-gcd: gcd(a(a+1), X) = gcd(a,X)*gcd(a+1,X) (since gcd(a,a+1)=1). Used for a fast semi-backend and sanity checks.
• Hybrid backend: chooses naive (small a), semi (medium), divisor (large), with fallbacks if factorization is incomplete.

Repository Layout

• src/core.py: gcd tools, factorization, phi, divisor utilities
• src/counts.py: exact/heuristic C(d,a) counting with CRT residue cache
• src/backends.py: naive, semi, divisor, hybrid computation
• src/bounds.py: bound families, fitting, violation checks, safe formula eval
• src/api_ideas.py: OpenAI Responses API wrapper + local idea generator
• src/db.py: sqlite schema and queries
• src/plots.py: matplotlib outputs
• src/runner.py: main loop and scheduler
• scripts/install.sh: venv + deps
• scripts/setup_systemd.sh: install systemd service
• systemd/gcdsum.service: systemd unit template

Setup (Ubuntu / Lightsail)

1. Install system packages.
2. Install Python deps.
3. Start the 24/7 service.

sudo apt-get update
sudo apt-get install -y python3 python3-venv build-essential
./scripts/install.sh
./scripts/setup_systemd.sh

Single command to deploy/run:

• ./scripts/install.sh && ./scripts/setup_systemd.sh

Service Controls

• sudo systemctl status gcdsum.service
• sudo systemctl restart gcdsum.service
• journalctl -u gcdsum.service -f

Smoke Test (small N, validates backends) Run a small target and exit:

MAIN_N_TARGET=50 BLOCK_SIZE_A=50 IDEA_INTERVAL_HOURS=1000 OPENAI_API_KEY= python -m src.runner

Configuration (env vars)

• DATA_DIR (default ./data)
• OPENAI_API_KEY (optional)
• OPENAI_MODEL (default gpt-4.1-mini)
• API_MAX_CALLS_PER_DAY (default 12)
• IDEA_INTERVAL_HOURS (default 6)
• VALIDATION_A_MAX (default 500)
• MAIN_N_TARGET (default unlimited)
• BLOCK_SIZE_A (default 5000)
• FACTOR_TIMEOUT_SEC (default 0.5)
• RANDOM_SEED (default 1337)
• RUN_RETENTION (default 30)
• API_DAILY_SPEND_LIMIT_USD (optional)

Outputs

• data/experiments.sqlite: main database
• data/runs/YYYYMMDD_HHMM/: plots and recent CSV
• data/current_summary.md: current status
• data/current_best_conjecture.txt: current best bound
• data/logs/runner.log: rotating file logs

Cost Controls

• Daily API call cap enforced and persisted in sqlite.
• Idea calls only once per IDEA_INTERVAL_HOURS.
• Optional daily usage check if API_DAILY_SPEND_LIMIT_USD is set.

Notes

• If OpenAI API is unavailable or OPENAI_API_KEY is not set, the system falls back to local idea generation.
• Backends are cross-validated on a<=VALIDATION_A_MAX; if a mismatch occurs, the divisor backend is disabled automatically.