Problem 600: Integer Sided Equiangular Hexagons

Problem 600 source code

C++

#include <cstdint>
#include <algorithm>
#include <iostream>

// Project Euler 600: Integer Sided Equiangular Hexagons
//
// An equiangular hexagon has all interior angles 120 degrees, so successive edge directions
// differ by 60 degrees. With side lengths (a,b,c,d,e,f) around the hexagon, the closure
// condition becomes:
//   a - d = c - f,
//   b - e = f - c.
//
// We count ordered side-length 6-tuples of positive integers satisfying closure and
// perimeter <= n, then quotient by the dihedral symmetries of a hexagon (rotations and
// reflections) using Burnside's lemma.
//
// Burnside requires the number of tuples fixed by each symmetry. The rotation cases reduce
// to simple compositions. Reflections split into two types and reduce to tractable integer
// sums. The identity count can be computed by summing over the difference parameter p:
// writing d=A, f=C, e=E and letting
//   a = A + p,  b = E - p,  c = C + p,
// yields perimeter 2(A+C+E)+p and positivity bounds that depend only on p.

using u64 = std::uint64_t;
using u128 = unsigned __int128;
using i64 = std::int64_t;

static void print_u128(u128 x) {
    if (x == 0) {
        std::cout << '0';
        return;
    }
    char buf[64];
    int n = 0;
    while (x > 0) {
        buf[n++] = (char)('0' + (u64)(x % 10));
        x /= 10;
    }
    while (n--) std::cout << buf[n];
}

static inline u128 choose2(u64 t) {
    if (t < 2) return 0;
    return (u128)t * (u128)(t - 1) / 2;
}

static inline u128 choose3(u64 t) {
    if (t < 3) return 0;
    return (u128)t * (u128)(t - 1) * (u128)(t - 2) / 6;
}

static inline u128 tet(u64 r) {
    // Number of nonnegative integer triples with sum <= r is C(r+3,3).
    return (u128)(r + 1) * (u128)(r + 2) * (u128)(r + 3) / 6;
}

static u128 fix_identity(u64 n) {
    // Sum over p (called x in many derivations).
    // For fixed p, let A=d, C=f, E=e. Then:
    //   a=A+p >=1  => A >= 1-p
    //   c=C+p >=1  => C >= 1-p
    //   b=E-p >=1  => E >= p+1
    // Perimeter: 2(A+C+E)+p <= n  => A+C+E <= floor((n-p)/2).

    u128 total = 0;
    for (i64 p = -(i64)n; p <= (i64)n; ++p) {
        const i64 T = ((i64)n - p) / 2;
        const i64 A0 = std::max<i64>(1, 1 - p);
        const i64 E0 = std::max<i64>(1, p + 1);
        const i64 base = 2 * A0 + E0;
        if (T < base) continue;
        const i64 R = T - base;
        total += tet((u64)R);
    }
    return total;
}

static u128 fix_reflection_even(u64 n) {
    // Representative reflection constraints: (a,b,c,d,e,f) = (a,b,c,d,c,b).
    // Closure gives d = a - c + b.
    // Perimeter: 2a + 3b + c <= n, and d>=1 implies c <= a+b-1.

    u128 total = 0;
    if (n < 6) return 0;

    const u64 bmax = (n - 3) / 3; // need 3b+3 <= n for any solution
    for (u64 b = 1; b <= bmax; ++b) {
        const i64 M = (i64)n - 3 * (i64)b; // M = n - 3b

        // Need M - 2a >= 1 for c>=1.
        const i64 Amax = (M - 1) / 2;
        if (Amax <= 0) continue;

        // Split where a+b-1 <= M-2a  <=>  3a <= M-b+1.
        const i64 Asplit = ((i64)n - 4 * (i64)b + 1) / 3;
        i64 m = std::min<i64>(Amax, std::max<i64>(0, Asplit));

        // Region 1: a=1..m, c_max = a+b-1.
        if (m >= 1) {
            const u128 sum_a = (u128)m * (u128)(m + 1) / 2;
            total += sum_a + (u128)(b - 1) * (u128)m;
        } else {
            m = 0;
        }

        // Region 2: a=m+1..Amax, c_max = M-2a.
        if (Amax > m) {
            const i64 cnt = Amax - m;
            const u128 sum_a = (u128)Amax * (u128)(Amax + 1) / 2 - (u128)m * (u128)(m + 1) / 2;
            total += (u128)M * (u128)cnt - (u128)2 * sum_a;
        }
    }
    return total;
}

static u128 fix_reflection_odd(u64 n) {
    // Representative odd reflection fixes: (a,b,c,d,e,f)=(a,a,c,a,a,c).
    // Condition: 4a+2c <= n  <=> 2a + c <= floor(n/2).

    const u64 T = n / 2;
    if (T < 3) return 0;
    const u64 amax = (T - 1) / 2;
    // Sum_{a=1..amax} (T - 2a)
    return (u128)amax * (u128)(T - (amax + 1));
}

static u128 H(u64 n) {
    const u128 id = fix_identity(n);
    const u128 r1 = (u64)(n / 6);
    const u64 T3 = n / 3;
    const u128 r2 = choose2(T3);
    const u64 T2 = n / 2;
    const u128 r3 = choose3(T2);
    const u128 fe = fix_reflection_even(n);
    const u128 fo = fix_reflection_odd(n);

    const u128 num = id + 2 * r1 + 2 * r2 + r3 + 3 * fe + 3 * fo;
    return num / 12;
}

int main() {
    // Validation points from the statement.
    if (H(6) != 1) {
        std::cerr << "Validation failed: H(6)\n";
        return 1;
    }
    if (H(12) != 10) {
        std::cerr << "Validation failed: H(12)\n";
        return 1;
    }
    if (H(100) != 31248) {
        std::cerr << "Validation failed: H(100)\n";
        return 1;
    }

    print_u128(H(55106));
    std::cout << "\n";
    return 0;
}

Python

def tet(r):
    if r < 0: return 0
    return (r + 1) * (r + 2) * (r + 3) // 6

def choose2(t):
    if t < 2: return 0
    return t * (t - 1) // 2

def choose3(t):
    if t < 3: return 0
    return t * (t - 1) * (t - 2) // 6

def fix_identity(n):
    total = 0
    for p in range(-n, n + 1):
        T = (n - p) // 2
        A0 = max(1, 1 - p)
        E0 = max(1, p + 1)
        base = 2 * A0 + E0
        if T < base: continue
        R = T - base
        total += tet(R)
    return total

def fix_reflection_even(n):
    total = 0
    if n < 6: return 0
    bmax = (n - 3) // 3
    for b in range(1, bmax + 1):
        M = n - 3 * b
        Amax = (M - 1) // 2
        if Amax <= 0: continue
        Asplit = (n - 4 * b + 1) // 3
        m = min(Amax, max(0, Asplit))
        
        if m >= 1:
            sum_a = m * (m + 1) // 2
            total += sum_a + (b - 1) * m
        else:
            m = 0
            
        if Amax > m:
            cnt = Amax - m
            sum_a = Amax * (Amax + 1) // 2 - m * (m + 1) // 2
            total += M * cnt - 2 * sum_a
            
    return total

def fix_reflection_odd(n):
    T = n // 2
    if T < 3: return 0
    amax = (T - 1) // 2
    return amax * (T - (amax + 1))

def H(n):
    id_val = fix_identity(n)
    r1 = n // 6
    T3 = n // 3
    r2 = choose2(T3)
    T2 = n // 2
    r3 = choose3(T2)
    fe = fix_reflection_even(n)
    fo = fix_reflection_odd(n)
    
    num = id_val + 2 * r1 + 2 * r2 + r3 + 3 * fe + 3 * fo
    return num // 12

def solve():
    return str(H(55106))

if __name__ == '__main__':
    print(solve())

Java

import java.math.BigInteger;

public class Euler600 {

    static BigInteger choose2(long t) {
        if (t < 2)
            return BigInteger.ZERO;
        BigInteger T = BigInteger.valueOf(t);
        return T.multiply(BigInteger.valueOf(t - 1)).divide(BigInteger.valueOf(2));
    }

    static BigInteger choose3(long t) {
        if (t < 3)
            return BigInteger.ZERO;
        BigInteger T = BigInteger.valueOf(t);
        return T.multiply(BigInteger.valueOf(t - 1)).multiply(BigInteger.valueOf(t - 2)).divide(BigInteger.valueOf(6));
    }

    static BigInteger tet(long r) {
        if (r < 0)
            return BigInteger.ZERO;
        BigInteger R = BigInteger.valueOf(r);
        return R.add(BigInteger.ONE).multiply(R.add(BigInteger.valueOf(2))).multiply(R.add(BigInteger.valueOf(3)))
                .divide(BigInteger.valueOf(6));
    }

    static BigInteger fixIdentity(long n) {
        BigInteger total = BigInteger.ZERO;
        for (long p = -n; p <= n; p++) {
            long T = (n - p) / 2;
            long A0 = Math.max(1, 1 - p);
            long E0 = Math.max(1, p + 1);
            long base = 2 * A0 + E0;
            if (T < base)
                continue;
            long R = T - base;
            total = total.add(tet(R));
        }
        return total;
    }

    static BigInteger fixReflectionEven(long n) {
        BigInteger total = BigInteger.ZERO;
        if (n < 6)
            return BigInteger.ZERO;

        long bmax = (n - 3) / 3;
        for (long b = 1; b <= bmax; b++) {
            long M = n - 3 * b;
            long Amax = (M - 1) / 2;
            if (Amax <= 0)
                continue;

            long Asplit = (n - 4 * b + 1) / 3;
            long m = Math.min(Amax, Math.max(0, Asplit));

            if (m >= 1) {
                long sumA = m * (m + 1) / 2;
                long toAdd = sumA + (b - 1) * m;
                total = total.add(BigInteger.valueOf(toAdd));
            } else {
                m = 0;
            }

            if (Amax > m) {
                long cnt = Amax - m;
                long sumA = Amax * (Amax + 1) / 2 - m * (m + 1) / 2;
                long toAdd = M * cnt - 2 * sumA;
                total = total.add(BigInteger.valueOf(toAdd));
            }
        }
        return total;
    }

    static BigInteger fixReflectionOdd(long n) {
        long T = n / 2;
        if (T < 3)
            return BigInteger.ZERO;
        long amax = (T - 1) / 2;
        long toAdd = amax * (T - (amax + 1));
        return BigInteger.valueOf(toAdd);
    }

    static BigInteger H(long n) {
        BigInteger idVal = fixIdentity(n);
        BigInteger r1 = BigInteger.valueOf(n / 6);
        long T3 = n / 3;
        BigInteger r2 = choose2(T3);
        long T2 = n / 2;
        BigInteger r3 = choose3(T2);
        BigInteger fe = fixReflectionEven(n);
        BigInteger fo = fixReflectionOdd(n);

        BigInteger num = idVal.add(r1.multiply(BigInteger.valueOf(2)))
                .add(r2.multiply(BigInteger.valueOf(2)))
                .add(r3)
                .add(fe.multiply(BigInteger.valueOf(3)))
                .add(fo.multiply(BigInteger.valueOf(3)));
        return num.divide(BigInteger.valueOf(12));
    }

    public static String solve() {
        return H(55106).toString();
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}