C++, all up to 40 in ten minutes
Runs in \$O(n^9)\$ time complexity (fortunately, it seems to be divided by at least 36 and it's also multi-threaded). I tested on Ubuntu 19.10 on AMD Ryzen 5 2600 (12 threads), tested with clang++ -Ofast -march=native -flto -no-pie -fopenmp
and ran with timeout 600 ./a.out
.
Code:
//#define _GLIBCXX_DEBUG
#include <iostream>
#include <cstring>
#include <complex>
#include <streambuf>
#include <bitset>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>
#include <random>
#include <set>
#include <list>
#include <map>
#include <deque>
#include <stack>
#include <queue>
#include <string>
#include <iomanip>
#include <unordered_set>
#include <thread>
struct pt3
{
short x, y, z;
bool operator < (const pt3& rhs) const
{
return std::tie(x, y, z) < std::tie(rhs.x, rhs.y, rhs.z);
}
pt3 operator - (const pt3& rhs) const
{
return {short(x - rhs.x), short(y - rhs.y), short(z - rhs.z)};
}
int sqdist() const
{
return int(x)*int(x) + int(y)*int(y) + int(z)*int(z);
}
};
int solve(int n)
{
//the several lines below took a lot of tinkering-until-it-works
std::set<pt3> pt3s;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
for(int k = 0; k < n; k++)
{
if(i+j+k >= n) continue;
pt3 pt { short(i+j), short(j+k), short(i+k) };
pt3s.insert(pt);
}
std::vector<pt3> points; //copy into a vector, they're much faster for this
for(pt3 el : pt3s) points.push_back(el);
//printf("n=%d, ps=%d\n", n, points.size());
int64_t ans = 0;
#pragma omp parallel for schedule(guided) reduction(+:ans)
for(int i = 0; i < points.size(); i++)
for(int j = i + 1; j < points.size(); j++)
for(int k = j + 1; k < points.size(); k++)
{
pt3 a = points[i], b = points[j], c = points[k];
//consider pairwise distances
pt3 p1 = a-b, p2 = a-c, p3 = b-c; //33% of all time
int d1 = p1.sqdist(), d2 = p2.sqdist(), d3 = p3.sqdist(); //another 33% of all time
if(d1 != d2 || d1 != d3) continue;
ans++;
//printf("%d %d %d; %d %d %d; %d %d %d\n", p1.x, p1.y, p1.z, p2.x, p2.y, p2.z, p3.x, p3.y, p3.z);
}
return ans;
}
int main()
{
for(int i = 1;; i++)
{
int ans = solve(i);
printf("n=%d: %d\n", i, ans);
}
}
Output:
n=1: 0
n=2: 4
n=3: 24
n=4: 84
n=5: 224
n=6: 516
n=7: 1068
n=8: 2016
n=9: 3528
n=10: 5832
n=11: 9256
n=12: 14208
n=13: 21180
n=14: 30728
n=15: 43488
n=16: 60192
n=17: 81660
n=18: 108828
n=19: 142764
n=20: 184708
n=21: 236088
n=22: 298476
n=23: 373652
n=24: 463524
n=25: 570228
n=26: 696012
n=27: 843312
n=28: 1014720
n=29: 1213096
n=30: 1441512
n=31: 1703352
n=32: 2002196
n=33: 2341848
n=34: 2726400
n=35: 3160272
n=36: 3648180
n=37: 4195164
n=38: 4806496
n=39: 5487792
n=40: 6244992