files / problems / kissing-5d / compute / q1 / integer_q5_44.c

2.6 KB · on GitHub

/* Exhaustive integer Delsarte search for T_Q5 at N=44.
 *
 * T = {-1, -4/5, -1/2, -3/10, 0, 1/5, 1/2}
 * n_{-1}+...+n_{1/2} = C(44,2)=946, n_{-1} ≤ 22.
 * Real box (deg 14) is used only to clip ranges; every integer point in the
 * clipped box is tested with exact integer Gegenbauer inequalities.
 */
#include <stdio.h>
#include <stdint.h>

typedef int64_t i64;

/* P_k(t) * D_k as integers, from delsarte.gegenbauer_dim5 evaluated at T
 * and cleared of denominators.  Generated by dump_q5_tables.py. */
#include "integer_q5_44_tables.h"

int main(void)
{
    const int N = 44;
    const int pairs = 946;
    /* Clipped real box, padded by 1. */
    /* Real LP box padded by 15 (HiGHS error is ≪ 1). n_{-1} is the full 0..22. */
    const int lo[7] = {0, 50, 50, 153, 197, 0, 286};
    const int hi[7] = {22, 103, 147, 267, 286, 43, 326};
    long scanned = 0, hits = 0;
    int hit_n[3][7];

    for (int n0 = lo[0]; n0 <= hi[0]; n0++)
    for (int n5 = lo[5]; n5 <= hi[5]; n5++)
    for (int n1 = lo[1]; n1 <= hi[1]; n1++)
    for (int n2 = lo[2]; n2 <= hi[2]; n2++)
    for (int n3 = lo[3]; n3 <= hi[3]; n3++) {
        int used5 = n0 + n5 + n1 + n2 + n3;
        /* n4 + n6 = pairs - used5, n4 in [lo4,hi4], n6 in [lo6,hi6] */
        int rem = pairs - used5;
        int n4min = lo[4];
        int n4max = hi[4];
        if (rem - hi[6] > n4min) n4min = rem - hi[6];
        if (rem - lo[6] < n4max) n4max = rem - lo[6];
        if (n4min > n4max) continue;
        for (int n4 = n4min; n4 <= n4max; n4++) {
            int n6 = rem - n4;
            scanned++;
            int ns[7] = {n0, n1, n2, n3, n4, n5, n6};
            int ok = 1;
            for (int k = 0; k < NROWS && ok; k++) {
                i64 s = (i64)N * ROW_D[k];
                for (int j = 0; j < 7; j++)
                    s += 2 * (i64)ns[j] * ROW_A[k][j];
                if (s < 0) ok = 0;
            }
            if (ok && hits < 3) {
                for (int j = 0; j < 7; j++) hit_n[hits][j] = ns[j];
                hits++;
            }
        }
    }
    printf("{\n");
    printf("  \"N\": 44,\n");
    printf("  \"T\": [\"-1\", \"-4/5\", \"-1/2\", \"-3/10\", \"0\", \"1/5\", \"1/2\"],\n");
    printf("  \"scanned\": %ld,\n", scanned);
    printf("  \"n_hits\": %ld,\n", hits);
    printf("  \"empty\": %s,\n", hits == 0 ? "true" : "false");
    printf("  \"hits\": [");
    for (long i = 0; i < hits; i++) {
        if (i) printf(", ");
        printf("{\"n\": [%d,%d,%d,%d,%d,%d,%d]}",
               hit_n[i][0], hit_n[i][1], hit_n[i][2], hit_n[i][3],
               hit_n[i][4], hit_n[i][5], hit_n[i][6]);
    }
    printf("]\n}\n");
    return 0;
}