"""Kaplan's conjecture for 28 to 81 points in every dimension d >= 5.

In AG(d,3) the counts become: pairs inside parts add up to r1*N*C(n,2) and
triples to N*(r2*C(n,3) + (r1-r2)*L), over N = (3^d-1)/2 classes, with
r1 = c1/N = 1/3 - (2/3)e and r2 = c2/N = 1/9 - (8/9)e, where e = 1/(3^d-1).
Both are linear in e, and d >= 5 means 0 < e <= 1/242. Parts have at most
n <= 81 points, so by induction on d they're bounded by the four-feature
values F4, and the allowed splits don't depend on d. A line T <= u + v*P over
all allowed splits rules L = F4[n]+1 out in dimension d when
u + v*r1*C(n,2) < r2*C(n,3) + (r1-r2)*t. The left minus right side is linear
in e, so if it's negative at e = 1/242 (d = 5) and not positive at e = 0 (the
limit), it's negative for every d >= 5. Exact fractions throughout.

  python3 alld.py > out/alld.txt
"""
from fractions import Fraction as F
from math import comb
from bound import G3

# the four-feature maxima: g(n) up to 27; 28..47 (bound.py); 48..53 (attack/,
# exact maxima for single cuts); 54..60 (the cards left out); 61..81 (complements
# of caps: (m^2 - 81m + 2160)/2 for m = 81 - n <= 20)
F4 = G3 + [117, 118, 119, 121, 124, 128, 131, 135, 140, 146, 152, 159, 167, 176, 186, 197, 209, 222, 231, 241,
           252, 264, 276, 289, 305, 323, 342, 357, 373, 390, 408, 427, 447] + \
     [(m * m - 81 * m + 2160) // 2 for m in range(20, -1, -1)]
assert len(F4) == 82 and F4[81] == 1080
D5 = (F(40, 121), F(13, 121))   # e = 1/242
LIMIT = (F(1, 3), F(1, 9))       # e = 0


def certificate(n, t):
    ok = [(a, b, n - a - b) for a in range(n + 1) for b in range(n - a + 1) if a >= b >= n - a - b
          and a < len(F4) and F4[a] + F4[b] + F4[n - a - b] + min(a * b, b * (n - a - b), a * (n - a - b)) >= t]
    if not ok:
        return 'no split allowed', None
    pts = sorted({(sum(comb(k, 2) for k in p), sum(comb(k, 3) for k in p)) for p in ok})
    A0, C3 = comb(n, 2), comb(n, 3)
    if all(r1 * A0 > pts[-1][0] for r1, r2 in (D5, LIMIT)):
        return 'pairs alone (too many)', None
    for P1, T1 in pts:  # try every line through two points that stays above all points
        for P2, T2 in pts:
            if P1 < P2:
                v = F(T2 - T1, P2 - P1); u = T1 - v * P1
                gap = lambda r: u + v * r[0] * A0 - (r[1] * C3 + (r[0] - r[1]) * t)
                if all(T <= u + v * P for P, T in pts) and gap(D5) < 0 and gap(LIMIT) <= 0:
                    return 'line', (u, v)
    return 'NOT RULED OUT', None


for n in range(28, 82):
    how, cert = certificate(n, F4[n] + 1)
    print(f'n={n}: at most {F4[n]} lines in every AG(d,3), d >= 5  ({how}'
          + (f': T <= {cert[0]} + {cert[1]} P' if cert else '') + ')')