Rust, \$A(1), \dotsc, A(1375)\$ in 10 minutes
Unofficial score on Ryzen 7 1800X (8 cores/16 threads). Build with cargo build --release and run with time target/release/tetrahedron n to compute \$A(1), \dotsc, A(n)\$.
This runs in \$O(n^4)\$ time. (So to estimate a good value of \$n\$ for your CPU, first time it for some smaller \$n\$, then multiply that \$n\$ by a factor of \$\left(\frac{600\,\mathrm{s}}{t}\right)^{1/4}\$.)
How it works
Any triangle that fits inside a tetrahedron of minimal side \$k \le n\$ may be translated inside a tetrahedron of side \$n\$ in exactly \$\binom{n - k + 3}{3}\$ ways. This means we only need to find it in one position, leaving six free parameters. Two of these parameters may be computed from the other four (up to a sign choice) if the triangle is to be equilateral, so we only need to loop over an \$O(n^4)\$ space.
src/main.rs
use rayon::prelude::*;
fn get_counts(n: i64, a0: i64) -> Vec<i64> {
let mut c = vec![0; n as usize];
let a0a0 = a0 * a0;
for a1 in if a0 == 0 { 1 } else { -n + 1 }..n {
let d = a0a0 + a1 * a1;
let m = n - a0.abs() - a1.abs();
for a2 in if m > 0 {
-n + 2 - (m & 1)..n
} else {
-n - m + 2..n + m
}
.step_by(2)
{
let d = d + a2 * a2;
let r = 2 * (a0a0 - d);
if r == 0 {
continue;
}
for b0 in a0..n {
let pp = d * (3 * d - 4 * (a0a0 + b0 * (b0 - a0)));
if pp < 0 {
break;
}
let p = (pp as f64).sqrt() as i64;
if p * p != pp {
continue;
}
let q = 2 * a0 * b0 - d;
let mut check = |p: i64| {
let b1r = p * a2 + q * a1;
if b1r % r != 0 {
return;
}
let b1 = b1r / r;
let b2r = -p * a1 + q * a2;
if b2r % r != 0 {
return;
}
let b2 = b2r / r;
if (b0, b1, b2) <= (a0, a1, a2) || b0 + b1 + b2 & 1 != 0 {
return;
}
let t = 0.max(a0 + a1 + a2).max(b0 + b1 + b2)
+ 0.max(-a0 - a1 + a2).max(-b0 - b1 + b2)
+ 0.max(-a0 + a1 - a2).max(-b0 + b1 - b2)
+ 0.max(a0 - a1 - a2).max(b0 - b1 - b2);
if t >= 2 * n {
return;
}
c[t as usize / 2] += 1;
};
check(p);
if p != 0 {
check(-p);
}
}
}
}
c
}
fn add_vec(c0: Vec<i64>, c1: Vec<i64>) -> Vec<i64> {
c0.into_iter().zip(c1).map(|(x0, x1)| x0 + x1).collect()
}
fn main() {
let n = std::env::args().skip(1).next().expect("missing argument");
let n = n.parse().expect("not an integer");
let counts = (0..n)
.into_par_iter()
.map(|a0| get_counts(n, a0))
.reduce(|| vec![0; n as usize], add_vec);
let (mut d0, mut d1, mut d2, mut d3) = (0, 0, 0, 0);
for (i, x) in (1..).zip(counts) {
d3 += x;
d2 += d3;
d1 += d2;
d0 += d1;
println!("{} {}", i, d0);
}
}
Cargo.toml
[package]
name = "tetrahedron"
version = "0.1.0"
authors = ["Anders Kaseorg <andersk@mit.edu>"]
edition = "2018"
[dependencies]
rayon = "1.3.0"
Try it online! (Parallelism removed for TIO.)
